(21)--第2章线性表第6讲-循环链表数据结构.pdf

2.3.22.3.2循环链表循环链表(CircularList)(CircularList)

循环单链表是单链表的变形。链表尾结点的next指针

不是NULL，而是指向了单链表的前端。

R

La1a2a3Zan

L

-

为简化操作，在循环单链表中往往加入头结点。

U

La1an

D

Q

L(空表的状态)

循环单链表的判空条件是：L-next==L。

循环单链表的特点是：只要知道表中某一结点的地址，

就可搜寻到所有其他结点的地址。R

在搜寻过程中，没有一个结点的next域为空。

Z

for(p=L-next;p!=L;p=p-next)

L

……;-

循环单链表的所有操作的实现类似于单链表，差别在

于检测到链尾，指针不为NULL，而是回到链头。

U

D

La1a2a3an

Q

循环单链表的算法设计举例循环单链表的算法设计举例

（1）初始化线性表运算算法

创建一个空的循环单链表，它只有头结点，由L指

R

向它。该结点的next域指向该头结点。

Z

L

StatusInitList_cl(LinkListL)

{//操作结果：构造一个空的循环链表L

-

//产生头结点,并使L指向此头结点

L=(LinkList)malloc(sizeof(LNode));

U

if(!L)D//存储分配失败

exit(OVERFLOW);

L-next=L;//指针域为空

Q

returnOK;

}

（2）求线性表的长度算法

设置变量i作为计数器，i初值为0，p初始时指向第

一个结点。然后沿next域逐个往下移动，每移动一次，

i值增1。当p所指结点为头结点时这一过程结束，i之值

即为表长。R