點擊查看：2015年計算機二級公共基礎知識復習知識點匯總

　　循環(huán)鏈表及其基本運算

　　在線性鏈表中，雖然對數(shù)據(jù)元素的插入和刪除操作比較簡單，但由于它對第一個結點和空表需要單獨處理，使得空表與非空表的處理不一致。

　　循環(huán)鏈表，即是采用另一種鏈接方式，它的特點如下：

　　(1)在循環(huán)鏈表中增加一個表頭結點，其數(shù)據(jù)域為任意或根據(jù)需要來設置，指針域指向線性表的第一個元素的結點。循環(huán)鏈表的頭指針指向表頭結點。

　　(2)循環(huán)鏈表中最后一個結點的指針域不是空的，而是指向表頭結點。在循環(huán)鏈表中，所有結點的指針構成一個環(huán)狀鏈。

　　在循環(huán)鏈表中，只要指出表中任何一個結點的位置，均可以從它開始掃描到所有的結點，而線性鏈表做不到，線性鏈表是一種單向的鏈表，只能按照指針的方向進行掃描。

　　循環(huán)鏈表中設置了一個表頭結點，因此，在任何時候都至少有一個結點，因此空表與非空表的運算相統(tǒng)一。

　　循環(huán)鏈表的特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。

　　【例】在鏈表上實現(xiàn)將兩個線性表(a1，a2，…，an)和(b1，b2，…，bm)連接成一個線性表(a1，…，an，b1，…bm)的運算。

　　分析：若在單鏈表或頭指針表示的單循環(huán)表上做這種鏈接操作，都需要遍歷第一個鏈表，找到結點an，然后將結點b1鏈到an的后面，其執(zhí)行時間是O(n)。

　　若在尾指針表示的單循環(huán)鏈表上實現(xiàn)，則只需修改指針，無須遍歷，其執(zhí)行時間是O(1)。

　　相應的算法如下：

　　LinkListConnect(LinkListA,LinkListB){

　　//假設A，B為非空循環(huán)鏈表的尾指針

　　LinkListp=A->next;//①保存A表的頭結點位置

　　A->next=B->next->next;//②B表的開始結點鏈接到A表尾

　　free(B->next);//③釋放B表的頭結點

　　B->next=p;//④

　　returnB;//返回新循環(huán)鏈表的尾指針

　　}

　　注意：

　　①循環(huán)鏈表中沒有NULL指針。涉及遍歷操作時，其終止條件就不再是像非循環(huán)鏈表那樣判別p或p->next是否為空，而是判別它們是否等于某一指定指針，如頭指針或尾指針等。

　　②在單鏈表中，從一已知結點出發(fā)，只能訪問到該結點及其后續(xù)結點，無法找到該結點之前的其它結點。而在單循環(huán)鏈表中，從任一結點出發(fā)都可訪問到表中所有結點，這一優(yōu)點使某些運算在單循環(huán)鏈表上易于實現(xiàn)。

　　相關推薦：

　　2015年9月計算機等級考試成績查詢時間通知

　　2015計算機二級公共基礎知識精選選擇題專項練習

　　2015計算機二級《公共基礎知識》精選選擇題90道

　　2015年9月計算機等級考試真題及答案解析專題