数据结构单链表的实现 数据结构之单链表基本运算的实现[10]

数据结构之单链表基本运算的实现[10]  

　　 循环链表

　　对于单链表而言 最后一个结点的指针域是空指针 如果将该链表头指针置入该指针域 则使得链表头尾结点相连 就构成了循环单链表(也称单循环链表) 如图 所示

　　图 带头结点的单循环链表

　　对循环单链表的操作与单链表基本相同 只是将原来判断指针是否为NULL变为是否是头指针而已 其它没有较大的变化

　　对于单链表只能从头结点开始遍历整个链表 而对于循环单链表则可以从表中任意结点开始遍历整个链表 不仅如此 对链表的操作可以在表尾 表头进行 此时可以改变一下链表的标识方法 不用头指针而用一个指向尾结点的指针R来标识 既可以找到尾结点 又可以找到头结点(R >next) 可以使得操作效率得以提高

　　例如对两个循环单链表H H 的连接操作 是将H 的第一个元素结点接到H 的尾结点 如用头指针标识 则需要找到第一个链表的尾结点 其时间复杂性为O(n) 而链表若用尾指针R R 来标识 则时间性能为O( ) 操作如下