講循環(huán)鏈表和雙向鏈表

第五講1．了解并掌握循環(huán)表和雙鏈表的概念。2．熟悉雙向鏈表的表示與實(shí)現(xiàn)。教學(xué)重點(diǎn)雙向鏈表的表示與實(shí)現(xiàn)教學(xué)難點(diǎn)雙向鏈表的存儲(chǔ)表示授課內(nèi)容

循環(huán)鏈表雙向鏈表2．42．4．1

循環(huán)鏈表雙向鏈表循環(huán)鏈表對(duì)于單鏈表而言，最后一個(gè)結(jié)點(diǎn)的指針域是空指針，如果將該鏈表頭指針置入該指針域，則使得鏈表頭尾結(jié)點(diǎn)相連，就構(gòu)成了單循環(huán)鏈表。如圖所示。單循環(huán)鏈表上的操作基本上與非循環(huán)鏈表相同，只是將原來判斷指針是否為NULL變?yōu)槭欠袷穷^指針而已，沒有其它較大的變化。圖2.16

帶頭結(jié)點(diǎn)的單循環(huán)鏈表對(duì)于單鏈表只能從頭結(jié)點(diǎn)開始遍歷整個(gè)鏈表于單循環(huán)鏈表則可以從表中任意結(jié)點(diǎn)開始遍歷整個(gè)鏈表，不僅如此，有時(shí)對(duì)鏈表常做的操作是在表尾、表頭進(jìn)行，此時(shí)可以改變一下鏈表的標(biāo)識(shí)方法，不用頭指針而用一個(gè)指向尾結(jié)點(diǎn)的指針R來標(biāo)識(shí)，可以使得操作效率得以提高。例如對(duì)兩個(gè)單循環(huán)鏈表H1H2連接操作是將的第一個(gè)數(shù)結(jié)點(diǎn)接到H1的尾結(jié)點(diǎn)如用頭指針標(biāo)識(shí)，則需要找到第一個(gè)鏈表的尾結(jié)點(diǎn)，其時(shí)間復(fù)雜性為O(n)而鏈表若用尾指針R1、來標(biāo)識(shí)，則時(shí)間性能為操作如下：/*存R1的頭結(jié)點(diǎn)指針*/*尾連接*/*釋放第二個(gè)表頭結(jié)點(diǎn)*R2->next=p;/*成循環(huán)鏈表*/

這一過程可見圖2.17。圖

兩個(gè)用尾指針標(biāo)識(shí)的單循環(huán)鏈表的連接2．4．2

雙向鏈表以上討論的單鏈表的結(jié)點(diǎn)中只有一個(gè)指向其后繼結(jié)點(diǎn)的指針next若已知某結(jié)點(diǎn)的指針，其后繼結(jié)點(diǎn)的指針則為找其前驅(qū)則只能從該鏈表的頭指針開始著各結(jié)點(diǎn)的域進(jìn)行，也就是說找后繼的時(shí)間性能是O(1)驅(qū)的時(shí)間性能是果希望找前驅(qū)的時(shí)間性能達(dá)到O(1)，則只能付出空間的代價(jià)：每個(gè)結(jié)點(diǎn)再加一個(gè)指向前驅(qū)的指針域，結(jié)點(diǎn)的結(jié)構(gòu)為如.18所示，用這種結(jié)點(diǎn)組成的鏈表稱為雙向鏈表。雙向鏈表結(jié)點(diǎn)的定義如下：structdlnode{datatypedata;structdlnode*prior,*next;圖和單鏈表類似，雙向鏈表通常也是用頭指針標(biāo)識(shí)，也可以帶頭結(jié)點(diǎn)和做成循環(huán)結(jié)構(gòu)，圖2.19是帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表示意圖。顯然通過某結(jié)點(diǎn)的指針即可以直接得到它的后繼結(jié)點(diǎn)的指針，也可以直接得到它的前驅(qū)結(jié)點(diǎn)的的指針p->prior這樣在有些操作中需要找前驅(qū)時(shí)，則勿需再用循環(huán)。從下面的插入刪除運(yùn)算中可以看到這一點(diǎn)。設(shè)p指向雙向循環(huán)鏈表中的某一結(jié)點(diǎn)，即中是該結(jié)點(diǎn)的指針，則p->prior->next表示的是*點(diǎn)之前驅(qū)結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針即與等類似示的是*p結(jié)點(diǎn)之后繼結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針，也與相等，所以有以下等式：/

圖2.19

帶頭結(jié)點(diǎn)的雙循環(huán)鏈表雙向鏈表中結(jié)點(diǎn)的插入：設(shè)指向雙向鏈表中某結(jié)點(diǎn)，指向待插入的值為的新結(jié)，將*插入到*前面，插入示意圖如圖所示。圖2.20

雙向鏈表中的結(jié)點(diǎn)插入操作如下：s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;指針操作的順序不是唯一的，但也不是任意的，操作①必須要放到操作④的前面完成，否則*前驅(qū)結(jié)點(diǎn)的指針就丟掉了。讀者把每條指針操作的涵義搞清楚，就不難理解了。雙向鏈表中結(jié)點(diǎn)的刪除：設(shè)指向雙向鏈表中某結(jié)點(diǎn)，刪除*。操作示意圖如圖2.21所示。/

圖2.21