《数据结构》循环链表双向链表

1、数据结构 2.3 线性表的链式存储表示和实现线性表的链式存储表示和实现四、循环链表四、循环链表La1ai-1anaip从单链表中某结点从单链表中某结点p出发如何找到其前驱？出发如何找到其前驱？将单链表的首尾相接，将终端结点的指针域由空指针将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成改为指向头结点，构成单循环链表单循环链表，简称，简称循环链表循环链表。循环链表中增设了表头结点，统一了空表循环链表中增设了表头结点，统一了空表和非空表的运算；和非空表的运算；说明说明L空循环链表空循环链表La1ai-1anai非空循环链表非空循环链表从循环链表中的任何一个结点的位置从循环链表中的

2、任何一个结点的位置都可以找到其他所有结点，而单链表做都可以找到其他所有结点，而单链表做不到；不到；说明说明La1ai-1anai循环条件：循环条件：p!=NULLp!=L p-next!=NULLp-next!=L循环链表中没有明显的尾端循环链表中没有明显的尾端 如何避免死循环如何避免死循环对循环链表，有时不给出头指针，而是对循环链表，有时不给出头指针，而是给出尾指针，可以更方便的找到线性表的给出尾指针，可以更方便的找到线性表的第一个元素和最后一个元素结点。第一个元素和最后一个元素结点。说明说明reara1ai-1anai如何查找开始结点和终端结点？如何查找开始结点和终端结点？开始结点：开始结

3、点：rear-next-next终端结点：终端结点：rear例如：将两个链表首尾相连：例如：将两个链表首尾相连：TaTaa a1 1a an nTbTbb b1 1b bn na a1 1a an nb b1 1b bn nTaTaTbTb循环链表与线性链表操作的主要差别是循环链表与线性链表操作的主要差别是算法中循环结束的条件。算法中循环结束的条件。说明说明H Hrearrear判空条件：判空条件：H=H-next;H=H-next;判空条件：判空条件：rear=rear=rearrear-next;-next;L Lnext=NULL;L-next=NULL;a a1 1a an nb b1

4、 1b bn npTaTaTbTbTaTaa a1 1a an nTbTbb b1 1b bn n举例举例a a1 1a an nb b1 1b bn npTaTaTbTbLinkList Connect(LinkList Ta,LinkList Tb)/假设假设A、B都是非空的单循环链表都是非空的单循环链表 /p p存表头结点存表头结点 /TbTb表头连结表头连结TaTa表尾表尾 /释放释放TbTb表头结点表头结点 /修改指针修改指针 return Tb;举例举例p=Ta-next;Ta-next=Tb-next-next;free(Tb-next); Tb-next=p; 2.3 线性表的

5、链式存储表示和实现线性表的链式存储表示和实现五、双向链表五、双向链表如何求结点如何求结点p的直接前驱，时间性能？的直接前驱，时间性能？为什么可以快速求得结点为什么可以快速求得结点p的后继？的后继？如何快速求得结点如何快速求得结点p的前驱？的前驱？La1ai-1anaip 2.3 线性表的链式存储表示和实现线性表的链式存储表示和实现五、双向链表五、双向链表 特点：特点：有两个指针域，一个指向直接后继，另一有两个指针域，一个指向直接后继，另一 个指个指 向直接前趋。向直接前趋。LABCpriordatanext结点结构：结点结构：data：数据域，存储数据元素；数据域，存储数据元素；prior：指

6、针域，存储该结点的前趋结点地址；指针域，存储该结点的前趋结点地址；next：指针域，存储该结点的后继结点地址。指针域，存储该结点的后继结点地址。 2.3 线性表的链式存储表示和实现线性表的链式存储表示和实现五、双向链表五、双向链表typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next;DuLNode, *DuLinkList;LABCLABCLABC非空的双向循环链表非空的双向循环链表非空的双向链表非空的双向链表d-next-prior=d-prior-next=d理解理解ACBn双向链

7、表的插入运算双向链表的插入运算sp 2.3 线性表的链式存储表示和实现线性表的链式存储表示和实现五、双向链表五、双向链表ACBsps-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s; 2.3 线性表的链式存储表示和实现线性表的链式存储表示和实现五、双向链表五、双向链表n双向链表的插入运算双向链表的插入运算ACBsp 2.3 线性表的链式存储表示和实现线性表的链式存储表示和实现五、双向链表五、双向链表n双向链表的插入运算双向链表的插入运算ACBsp 2.3 线性表的链式存储表示和实现线性表的链式存储表示和实现五、双向链表五、双向链表s-prior=p-prior; s-next=p;p-prior-next=s;p-prior=s; n双向链表的插入运算双向链表的插入运算n双向链表的删除运算双向链表的删除运算 2.3 线性表的链式存储表示和实现线性表的链式存储表示和实现五、双向链表五、双向链表( (p-prior) )-next=p-next; ( (p-next) )-prior=p-prior; ai-1aipai结点结点p的指针是否需要修改？的指针是否需要修改？free(p); 几个特殊点的处理几个特殊点的处理l头指针的处理头指针的处理l非循环链表尾结点的指针域保持为非循环链表尾结点的指针域保持为NULLl循环链表尾