基本数据结构要点.ppt

基本数据结构 通信录课程设计实例 软件功能要求： 1.通信录具有新增联系人信息 2.通信录能够删除联系人信息 3.通信录能够查询到相应的联系人信息 4.能够修改联系人信息 软件核心数据结构—联系人信息 学号、姓名、年龄、性别、电话、地址邮箱、QQ号、身份证号、备注等 (4) 按值查找Locate(L,x) 在线性表L中查找值为ｘ的数据元素，若查找成功则返回第一个值为x的元素的序号或地址; 否则，在L中未找到值为ｘ的数据元素，返回一特殊值（例如0），表示查找失败。 (5) 插入元素Inselem (L,i,x) 在线性表L的第 i 个位置上插入一个值为 x 的新元素，这样使原序号为 i , i+1, ..., n 的数据元素的序号变为 i+1,i+2, ..., n+1，要求1≤i≤Getlen(L)+1，插入后原表长增1。 (6) 删除元素Delelem(L,i) 在线性表L中删除序号为i的数据元素，删除后使序号为 i+1, i+2,..., n 的元素变为序号i, i+1,...,n-1，要求1≤i≤Getlen(L)，删除后表长减１。 2.2 线性表的顺序结构及运算实现 2.3 线性表的链式存储和运算实现 2.3.1链表的存储结构 链式存储结构是利用任意的存储单元来存放线性表中的元素，存储数据的单元在内存中可以连续，也可以零散分布。 由于线性表中各元素间存在着线性关系，每一个元素有一个直接前驱和一个直接后继。为了表示元素间的这种线性关系，在这种结构中不仅要存储线性表中的元素，还要存储表示元素之间逻辑关系的信息。所以用链式存储结构表示线性表中的一个元素时至少需要两部分信息，除了存储每一个数据元素值以外，还需存储其后继或前驱元素所在内存的地址。两部分信息一起构成链表中的一个结点。结点的结构如下所示。 C语言采用结构数据类型描述结点如下： typedef struct LNode{ ElemType data; //结点值 struct LNode *next; //存储下一个结点的地址 }LNode,*LinkList; LNode *head; 图 2-7 链表结构示意图 请大家完成如下操作 (1) 初始化线性表Initlist(L) (2) 求线性表的长度Getlen(L) (3) 按序号取元素Getelem(L,i) (4) 按值查找Locate(L,x) (5) 插入元素Inselem (L,i,x) (6) 删除元素Delelem(L,i) 图2-15 双向链表结点结构图 2.3.4 双向链表 结点的插入过程如图2-17所双向链表示： 注意：在图2-17中，关键语句指针操作序列既不是唯一也不是任意的。操作①必须在操作③之前完成，否则*p的前驱结点就丢掉了。 【解】算法思路：扫描双向链表DL，查找链表DL的第i个位置并在第i个位置之后插入元素x。 status ListInsert_DuL(DuLinkList DL,int i, ElemType x) { Dnode *s; if(!p=get_linklist(DL,i)) //p指向第i个元素结点， return ERROR; //p=NULL表示第i个元素不存在 if(!(s=(DulinkList)malloc(sizeof(Dnode)))) return OVERFLOW; s-data=x; //为新元素建结点 s-next=p-next;　 //插入 s-prior=p; p-next-prior=s; p-next=s return OK; } 2.3.5循环双链表 与循环单链表一样，也可以使用循环双链表。循环单链表和循环双链表可通过尾结点找到头结点，也常作为编辑器的数据结构，尤其是循环双链表。 图2-19是带头结点且有n个结点的循环双链表。 在循环双向链表中，对于一些只涉及一个方向指针且存储结构不变的操作（如查找、求表长等），其算法实现与单链表相同。在进行插入或删除等结构变化的操作时，与双链表相同，必须同时修改两个方向上的指针，操作过程比单链表复杂。 【例2-8】编写从循环双向链表中删除第i(i≥1)个结点的算法。 【解】算法思想：扫描循环双向链表，查找第i个结点。若找到，修改其前趋结点的next域和后继结点的prior域，删除第i个（1≤i≤表长）结点，返回OK；否则返回ERROR。当删除的结点是链表中的第一个结点时，除上述操作外，还需要修改头指针。 算法如下：