點(diǎn)擊查看：2015年計(jì)算機(jī)二級公共基礎(chǔ)知識復(fù)習(xí)知識點(diǎn)匯總

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

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

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

　　(1)在循環(huán)鏈表中增加一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蚋鶕?jù)需要來設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。

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

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

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

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

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

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

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

　　相應(yīng)的算法如下：

　　LinkListConnect(LinkListA,LinkListB){

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

　　LinkListp=A->next;//①保存A表的頭結(jié)點(diǎn)位置

　　A->next=B->next->next;//②B表的開始結(jié)點(diǎn)鏈接到A表尾

　　free(B->next);//③釋放B表的頭結(jié)點(diǎn)

　　B->next=p;//④

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

　　}

　　注意：

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

　�、谠趩捂湵碇校瑥囊灰阎Y(jié)點(diǎn)出發(fā)，只能訪問到該結(jié)點(diǎn)及其后續(xù)結(jié)點(diǎn)，無法找到該結(jié)點(diǎn)之前的其它結(jié)點(diǎn)。而在單循環(huán)鏈表中，從任一結(jié)點(diǎn)出發(fā)都可訪問到表中所有結(jié)點(diǎn)，這一優(yōu)點(diǎn)使某些運(yùn)算在單循環(huán)鏈表上易于實(shí)現(xiàn)。

　　相關(guān)推薦：

　　2015年9月計(jì)算機(jī)等級考試成績查詢時(shí)間通知

　　2015計(jì)算機(jī)二級公共基礎(chǔ)知識精選選擇題專項(xiàng)練習(xí)

　　2015計(jì)算機(jī)二級《公共基礎(chǔ)知識》精選選擇題90道

　　2015年9月計(jì)算機(jī)等級考試真題及答案解析專題