2.4　循环链表

循环链表（circular linked list）是另一种形式的链式存储结构。循环链表是将单链表中最后一个结点指针指向链表的头结点,使整个链表形成一个环。这样,从表中任何一个结点出发都可以找到表中其他的结点,如图2－12所示。

图2－12　循环链表

带有头结点的循环链表的操作实现算法和带有头结点的单链表的操作实现算法类似,其差别在于:算法中的条件在单链表中为p！＝NULL或p－＞next！＝NULL；而在循环链表中应改为p！＝head或p－＞next！＝head。空循环链表的判定条件为head－＞next＝＝head。

在循环链表中,除了头指针head外,还可以加一个尾指针rear。尾指针rear指向最后一个结点,从最后一个结点的指针又可以立即找到链表的第一个结点。在实际应用中,有时只使用表尾指针,而不设表头指针,使用尾指针来代替头指针进行某些操作往往更简单。

【例2－4】　将两个线性表合并为一个表。

将两个线性表合并为一个表时,仅将两个循环链表首尾相连即可。设La为第一个循环链表的表尾指针,Lb为第二个循环链表的表尾指针,合并后Lb为新链表的表尾指针。具体算法如下。