扫码获取更多资源

●循环链表

在单链表中，将最后一个结点的指针域NULL改为指向头结点，这样形成的链式存储 结构称为单向循环链表，简称循环链表(Circular Linked List) 0 循环链表是线性表另一种形式的链式存储结构，即首尾相接的链式存储结构。在循环 链表中也设置一个头结点，如图2-15(a)所示。空循环链表如图2-15(b)所示。

因为循环链表与单链表结构一样，所以它们的基本操作也基本一致，其差别仅在于当涉 及访问表中结点操作时，其终止条件不再像单链表那样判别P或p->next是否为空，而是 判别它们是否等于头指针。 在很多实际问题中，链表的操作常常是在表的首尾位置上进行。如果表长为n,则对设 头指针的循环链表第一个结点的査找时间是0(1),最后一个结点的查找时间是03)。如 果在循环链表中仅设置尾指针 Rear而不设头指针Head,则对第一个结点和最后一个结点 的查找时间都是0(1)。因此，实际应用中多釆用尾指针表示循环链表。

算法设计

(1) 保存循环链表La的头结点，作为连接后的新循环链表头结点。

（2）将循环链表Lb的第一个结点连接到循环链表La的最后一个结点上。

（3）释放循环链表Lb的头结点。

（4）将循环链表Lb最后一个结点指向循环链表La的头结点。

（5）重置连接后新循环链表的尾指针。

算法描述

算法分析

（1） 问题规模：两个循环链表的“长度和”（设La长度为n,Lb长度为m）

（2） 基本操作：指针修改等。

（3） 时间分析：基本操作与问题规模无关，因此算法2-26的时间复杂度为0（1）。 如果在单链表或头指针表示的循环链表上进行这种连接操作，则都需要扫描La,找到 其最后一个结点，然后将Lb的第一个结点b1连接到為的后面，其时间复杂度是O（n）。 如果在尾指针表示的循环链表上实现，则只需要修改指针，不需要扫描整个链表。

联系我们：