日志

循环链表

已有 322 次阅读| 2016-3-17 16:09 |个人分类:C语言数据结构

循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点，如图所示为单链的循环链表。类似地，还可以有多重链的循环链表。

循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。但有的时候，若在循环链表中设立尾指针而不设头指针，可使某些操作简化。例如将两个线性表合并为一个表时，仅需将一个表的表尾和另一个表的表头相接。当线性表的循环链表作存储结构时，这个操作仅需改变两个指针即可，运算时间为O（1）。合并后的表如图所示。