线性表—双向链表的表示与实现.ppt

《线性表—双向链表的表示与实现.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、六、双向链表１、双向链表的存储结构双向链表：链表中每个结点除后继指针域和数据域外还有一个前驱指针域。其结点的结构为：双向链表结点的结构体定义如下：typedefstructNode{DataTypedata;structNode*next;structNode*prior;}DLNode;priordatanext1sa0a1an带头结点的双向循环链表的结构示意图。…与单链表类同，双向链表分带头结点和不带头结点两种，也分有循环和非循环两种结构。下面仅讨论带头结点的双向循环链表。head22、双向链表的操作实现(1)前插设p已

2、指向第i元素，请在第i元素前插入元素xxsai-1aip指针域的变化：①ai-1的后继从ai(指针是p)变为x（指针是s):s->next=p;p->prior->next=s;②ai的前驱从ai-1(指针是p->prior)变为x(指针是s);s->prior=p->prior;p->prior=s;3p指针域的变化：后继方向：ai-1的后继由ai(指针p)变为ai+1(指针p->next);p->prior->next=p->next;前驱方向：ai+1的前驱由ai(指针p)变为ai-1(指针p->prior);p->n

3、ext->prior=p->prior;(2)双向链表的删除操作设p指向第i个元素，删除第i个元素ai-1aiai+14例:已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。a．在P结点后插入S结点的语句序列是-----------。b．在P结点前插入S结点的语句序列是-----------。c．删除P结点的直接后继结点的语句序列是------。d．删除P结点的直接前驱结点的语句序列是-------。e．删除P结点的语句序列是------------。5(1)P->next=Q->next;(10)Q-

4、>prior->next=P;(2)P->prior=Q->prior;(11)Q->next->prior=P;(3)P->next=S;(12)P->next->prior=S;(4)P->prior=S;(13)P->prior->next=S;(5)S->next=P;(14)P->next->prior=P->prior(6)S->prior=P;(15)Q=P->next;(7)S->next=P->next;(16)Q=P->prior;(8)S->prior=P->prior;(17)free(P);(9)P

5、->prior->next=p->next;(18)free(Q);解答：a.(12)(7)(3)(6)3必须在12和7的后面，其余的顺序可变b.(13)(8)(4)(5)同上c.(15)(1)(11)(18)不可变d.(16)(2)(10)(18)不可变e.(9)(14)(17)6七、静态链表静态链表：在数组中增加一个（或两个）指针域，这些指针域用来存放下一个（或上一个）数据元素在数组中的下标，从而构成用数组构造的单链表（或双链表）。静态链表中的指针又称仿真指针。7静态单链表的类型定义如下：#defineMAXSIZE10

6、00//预分配最大的元素个数（连续空间)typedefstruct{DataTypedata;//数据域intnext;//指示域}component,SLinkList[MAXSIZE];//一维结构型数组例1：软考题：L={23，17，47，05，31}若此分量定义为指针型，属于动态链表（题目中是指针）；若此分量定义为整型（通常存放下标），则属于静态链表。Z47Y31V23X17U05100200104108116112Z47Y31V23X17U058例2：一线性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)

7、，用静态链表如何表示？data1ZHAO3LI5QIAN6WU0ZHOU4SUN2…………0123456…1000cur说明1：假设S为SLinkList型变量，则S[MAXSIZE]为一个静态链表；S[0].next则表示第1个结点在数组中的位置。说明2：如果数组的第i个分量表示链表的第k个结点，则：S[i].data表示第k个结点的数据；S[i].next表示第k+1个结点(即k的直接后继)的位置。i头结点9说明3：静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就可以了。例如：在线性表S=(ZHA

8、O,QIAN,SUN,LI,ZHOU,WU)的QIAN,SUN之间插入新元素LIU，可以这样实现：S[7].next=S[3].next；Step2:将QIAN的游标换为新元素LIU的下标：S[3].next=7Step1:将QIAN的游标值存入next的游标中：data……2SUN4ZH