《线性表(c)循环链式存储》由会员分享，可在线阅读，更多相关《线性表(c)循环链式存储（22页珍藏版）》请在金锄头文库上搜索。
1、2.5 线性表的其它存储方法,循环链表,L,a1,ai-1,an,ai,将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成单循环链表，简称循环链表。,2.5 线性表的其它存储方法,循环链表,循环链表是否为空的条件是：L-next=L 单链表是否为空的条件是：L-next=NULL,L- next=L为真,L- next!=L为真,L,a1,ai-1,an,ai,2.5 线性表的其它存储方法,循环链表插入,循环链表的插入操作与单链表的插入操作相同,void xhInsert(LinkList L,int i,ElemType x) /*让p指向第i-1个结点*/p=L; j=0;
2、 while(p-next!=L j+；,if(p-next=L ,2.5 线性表的其它存储方法,循环链表插入,与单链表的插入操作相比，差别是什么？,i的取值范围1,n+1,in+1 或 inext-next=L ,2.5 线性表的其它存储方法,循环链表删除,与单链表的删除操作相比，差别是什么？,i的取值范围1,n,in 或 inext 尾结点：将单链表扫描一遍，时间为O(n),有没有更简单的方法？,开始结点：rear-next-next 终端结点：rear,2.5 线性表的其它存储方法,循环链表,带尾指针的循环链表,一个存储结构设计得是否合理，取决于基于该存储结构的运算是否方便，时间性能是否
3、提高。,既方便找头又方便找尾,开始结点：rear-next-next 终端结点：rear,2.5 线性表的其它存储方法,带尾指针的循环链表的 -插入,P,插入操作： p=rear-next; j=0; 其余与单向循环链表插入相同,开始结点：rear-next-next 终端结点：rear,2.5 线性表的其它存储方法,带尾指针的循环链表的 -删除,P,删除操作： p=rear-next; j=0; 其余与单向循环链表的删除相同,双链表,2.5 线性表的其它存储方法,如何求结点p的直接前驱，时间性能？,为什么可以快速求得结点p的后继？,如何快速求得结点p的前驱？,双链表：在单链表的每个结点中再设
4、置一个指向其前驱结点的指针域。,双链表,结点结构：,data：数据域，存储数据元素； prior：指针域，存储该结点的前驱结点地址； next：指针域，存储该结点的后继结点地址。,2.5 线性表的其它存储方法,13,双向循环链表,空表,非空表,a1 a2 . an,头结点的next域存放第1个 结点的地址； 头结点的prior域存放尾结点 的地址；,L,L,双向循环链表为空的条件：L-next=L&L-prior=L 双向循环链表不为空条件：L-next!=L&L-prior=L,typedef struct DulNode ElemType data;struct DulNode *prio
5、r, *next; DulNode,*DuLinkList;,2.5 线性表的其它存储方法,双链表,启示？,时空权衡空间换取时间,定义结点结构：,双向链表的初始化,/*初始化函数*/ int initDLinkList(DuLinkList ,空表,L,双链表的操作插入,s-prior=p;,s-next=p-next;,p-next-prior=s;,p-next=s;,2.5 线性表的其它存储方法,ai-1,ai,操作接口： void duInsert(DuLinkList L, int i,ElemType x);,注意指针修改的相对顺序,int insDLinkList(DuLinkL
6、ist L, int i, ElemType x)DuLinkList p=L;/工作指针指向头结点DuLinkList newp;/用于指向新结点int j=0;/计数器置0/寻找插入位置，使得工作指针p指向第i-1个结点while(p-next!=L /接后,按后继方向，寻找插入位置,/插入newp=new DulNode;newp-data=x;newp-next=p-next;newp-prior=p;p-next-prior=newp;p-next=newp;return 1; ,双链表的操作删除,p-next=q-next;,q-next-prior=p;,2.5 线性表的其它存储
7、方法,操作接口： void duDelete(DuLinkList L, int i, ElemType ,ai-1,ai,ai+1,delete q;,q=p-next;,按后继方向寻找要删除的结点,int delDLinkList(DuLinkList L,int i, ElemType /接后,/删除 q=p-next; x=q-data; p-next=q-next; q-next-prior=p;delete q;return 1; ,本章总结,线 性 表,逻辑结构,存储结构,基本概念,抽象 数据 类型 定义,线性表定义 逻辑特征,ADT定义 基本操作,顺序存储,链接存储,其他存储,顺序表的特点 顺序表类定义 基本操作的实现及时间性能,单链表的特点 单链表类定义 基本操作的实现及时间性能,比 较,循环链表 双链表,
