循環鏈表(Circular Linked List)
循環鏈表是一種首尾相接的鏈表
循環鏈表
()單循環鏈表 ——在單鏈表中將終端結點的指針域NULL改為指向表頭結點或開始結點即可
()多重鏈的循環鏈表 ——將表中結點鏈在多個環上
帶頭結點的單循環鏈表
注意
判斷空鏈表的條件是head==head>next;
僅設尾指針的單循環鏈表
用尾指針rear表示的單循環鏈表對開始結點a 和終端結點a n 查找時間都是O()而表的操作常常是在表的首尾位置上進行因此實用中多采用尾指針表示單循環鏈表帶尾指針的單循環鏈表可見下圖
注意
判斷空鏈表的條件為rear==rear>next;
循環鏈表的特點
循環鏈表的特點是無須增加存儲量僅對表的鏈接方式稍作改變即可使得表處理更加方便靈活
【例】在鏈表上實現將兩個線性表(a a …a n )和(b b …b m )連接成一個線性表(a …a n b …b m )的運算
分析 若在單鏈表或頭指針表示的單循環表上做這種鏈接操作都需要遍歷第一個鏈表找到結點a n 然後將結點b 鏈到a n的後面其執行時間是O(n)若在尾指針表示的單循環鏈表上實現則只需修改指針無須遍歷其執行時間是O()
相應的算法如下
LinkList Connect(LinkList ALinkList B)
{//假設AB為非空循環鏈表的尾指針
LinkList p=A>next;//①保存A表的頭結點位置
A>next=B>next>next;//②B表的開始結點鏈接到A表尾
free(B>next);//③釋放B表的頭結點
B>next=p;//④
return B;//返回新循環鏈表的尾指針
}
注意
①循環鏈表中沒有NULL指針涉及遍歷操作時其終止條件就不再是像非循環鏈表那樣判別p或p>next是否為空而是判別它們是否等於某一指定指針如頭指針或尾指針等
②在單鏈表中從一已知結點出發只能訪問到該結點及其後續結點無法找到該結點之前的其它結點而在單循環鏈表中從任一結點出發都可訪問到表中所有結點這一優點使某些運算在單循環鏈表上易於實現
From:http://tw.wingwit.com/Article/program/sjjg/201311/23305.html
