讲循环链表和双向链表.docVIP

第五讲　循环链表和双向链表 1．了解并掌握循环链表和双链表的概念。 2．熟悉双向链表的的表示与实现。 教学重点： 双向链表的表示与实现 教学难点： 双向链表的存储表示 授课内容 2．4　　循环链表和双向链表 2．4．1　循环链表 　　对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。如图2.16所示。 在单循环链表上的操作基本上与非循环链表相同，只是将原来判断指针是否为NULL变为是否是头指针而已，没有其它较大的变化。 图2.16　带头结点的单循环链表 　　 对于单链表只能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点开始遍历整个链表，不仅如此，有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针R来标识，可以使得操作效率得以提高。 　　 例如对两个单循环链表H1 、H2的连接操作，是将H2的第一个数据结点接到H1的尾结点，如用头指针标识，则需要找到第一个链表的尾结点，其时间复杂性为O(n)，而链表若用尾指针R1、R2来标识，则时间性能为O(1)。操作如下： p=R1–next;　　/*保存R1 的头结点指针*/R1-next=R2-next-next;　/*头尾连接*/free(R2-next);　/*释放第二个表的头结点*/R2-next=p;　　/*组成循环链表*/这一过程可见图2.17。 图2.17　两个用尾指针标识的单循环链表的连接 2．4．2　双向链表 　　 以上讨论的单链表的结点中只有一个指向其后继结点的指针域next，因此若已知某结点的指针为p，其后继结点的指针则为p-next ，而找其前驱则只能从该链表的头指针开始，顺着各结点的next域进行，也就是说找后继的时间性能是O(1)，找前驱的时间性能是O(n)，如果也希望找前驱的时间性能达到O(1)，则只能付出空间的代价：每个结点再加一个指向前驱的指针域，结点的结构为如图2.18所示，用这种结点组成的链表称为双向链表。 双向链表结点的定义如下： typedef　struct　dlnode{datatype　data;struct　dlnode*prior,*next;}DLNode,*DLinkList; 图2.18 　　 和单链表类似，双向链表通常也是用头指针标识，也可以带头结点和做成循环结构，图2.19是带头结点的双向循环链表示意图。显然通过某结点的指针p即可以直接得到它的后继结点的指针p-next，也可以直接得到它的前驱结点的的指针p-prior。这样在有些操作中需要找前驱时，则勿需再用循环。从下面的插入删除运算中可以看到这一点。 　　设p指向双向循环链表中的某一结点，即 p中是该结点的指针，则p-prior-next表示的是*p结点之前驱结点的后继结点的指针，即与p相等；类似，p-next-prior表示的是*p结点之后继结点的前驱结点的指针，也与p相等，所以有以下等式： 图2.19　带头结点的双循环链表 ? 　　双向链表中结点的插入：设p指向双向链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的前面，插入示意图如图2.20所示。 图2.20　双向链表中的结点插入 操作如下： s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;　　 指针操作的顺序不是唯一的，但也不是任意的，操作必须要放到操作的前面完成，否则*p的前驱结点的指针就丢掉了。读者把每条指针操作的涵义搞清楚，就不难理解了。 双向链表中结点的删除： 设p指向双向链表中某结点，删除*p。操作示意图如图2.21所示。 图2.21　双向链表中删除结点 操作如下： p-prior-next=p-next;②p-next-prior=p-prior;free(p);