线性表-其他链式存储课件

2.5线性表的其它存储方法循环链表La1ai-1an∧aip将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成单循环链表，简称循环链表。2.5线性表的其它存储方法循环链表L空循环链表La1ai-1anai非空循环链表循环链表是否为空的条件是：L->next==L单链表是否为空的条件是：L->next==NULLL->next==L为真L->next!=L为真La1ai-1anai2.5线性表的其它存储方法循环链表——插入xspxspxsp算法描述：s=newNode;s->data=x;s->next=p->next;p->next=s;循环链表的插入操作与单链表的插入操作相同La1ai-1ai+1ai2.5线性表的其它存储方法循环链表——删除p算法描述：q=p->next;x=q->data;p->next=q->next;deleteq;循环链表的删除操作与单链表的删除操作相同anqvoidxhDelete(LinkListL,inti,ElemType&x){p=L;j=0;

while(p->next!=L&&j<i-1){p=p->next;j++;}

if(p->next==L||j>i-1)printf(“位置异常“);else//(p->next&&j==i-1){q=p->next;x=q->data;p->next=q->next;deleteq;}}2.5线性表的其它存储方法循环链表——删除与单链表的删除操作相比，差别是什么？如何查找开始结点和尾结点？2.5线性表的其它存储方法循环链表La1ai-1anai开始结点：L->next尾结点：将单链表扫描一遍，时间为O(n)有没有更简单的方法？reara1ai-1anai开始结点：rear->next->next终端结点：rear2.5线性表的其它存储方法循环链表带尾指针的循环链表一个存储结构设计得是否合理，取决于基于该存储结构的运算是否方便，时间性能是否提高。双链表2.5线性表的其它存储方法如何求结点p的直接前驱，时间性能？La1ai-1anaip为什么可以快速求得结点p的后继？如何快速求得结点p的前驱？双链表：在单链表的每个结点中再设置一个指向其前驱结点的指针域。双链表结点结构：priordatanextdata：数据域，存储数据元素；prior：指针域，存储该结点的前驱结点地址；next：指针域，存储该结点的后继结点地址。2.5线性表的其它存储方法typedefstructDulNode{ElemTypedata;structDulNode*prior,*next;}DulNode,*DuLinkList;

2.5线性表的其它存储方法双链表启示？时空权衡——空间换取时间priordatanext定义结点结构：双链表的操作——插入s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;2.5线性表的其它存储方法ai-1ai操作接口：

voidduInsert(DuLinkListL,inti,ElemTypex);

pxs注意指针修改的相对顺序双链表的操作——删除p->next=q->next;

q->next->prior=p;

2.5线性表的其它存储方法操作接口：

voidduDelete(DuLinkListL,inti,ElemType&x);

ai-1aipai+1deleteq;qq=p->next;本章总结线性表逻辑结构存储结构基本概念抽象数据类型定义⑴线性表定义