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

第五講1．了解并掌握循環(huán)表和雙鏈表的概念。2．熟悉雙向鏈表的表示與實現。教學重點雙向鏈表的表示與實現教學難點雙向鏈表的存儲表示授課內容

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

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

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

這一過程可見圖2.17。圖

兩個用尾指針標識的單循環(huán)鏈表的連接2．4．2

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

圖2.19

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

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

圖2.21