資源簡介

(共88張PPT)
第2章 線性表
線性表的概念
線性表的順序存儲
線性表的鏈式存儲
單向循環鏈表
雙向循環鏈表
線性表的概念
線性表的順序存儲
線性表的鏈式存儲
2.2
2.3
2.1
點擊查看本小節知識架構
點擊查看本小節知識架構
點擊查看本小節知識架構
單向循環鏈表
2.4
點擊查看本小節知識架構
雙向循環鏈表
2.5
點擊查看本小節知識架構
學習目標
了解
掌握
掌握
掌握
了解線性表的基本概念
1
掌握單向循環鏈表的代碼編寫方法
4
2
掌握線性表順序存儲結構的代碼編寫方法
3
掌握線性表鏈式存儲結構的代碼編寫方法
本章將主要介紹數據結構中的核心概念——線性表，線性表作為一種最基本的數據結構類型，表中的數據元素之間滿足線性結構。線性表可以通過不同的物理結構實現，如順序存儲與鏈式存儲。使用順序存儲實現的線性表稱為順序表，使用鏈式存儲實現的線性表稱為單鏈表。單鏈表作為數據結構中常用的數據存儲方式，還可以實現單向循環鏈表以及雙向循環鏈表。本章將主要討論這些數據結構的代碼實現以及結構中數據元素的操作。
2.1 線性表的概念
2.1.1
線性表的定義
返回目錄
2.1.2
線性表的運算
2.1.1 線性表的定義
線性表中的數據元素之間滿足線性結構（線性結構的概念詳見1.2.1節）。線性表是n個數據元素的有限序列，記為(a 1 ,a 2 ,a 3 ,…,a n )，其含義如下。
（1）n為數據元素的個數，也可以稱為線性表的長度，當n為0時，線性表稱為空表。
（2）a i 為線性表中的第i個數據元素（也可以稱為數據結點），i稱為數據元素在線性表中的位序（等同于數組元素的下標）。
從線性表的定義可以看出，線性表中存在唯一的首個數據元素和唯一的末尾數據元素。除了首個數據元素，其他每個數據元素都有一個直接前驅（ai 的直接前驅為 a i-1 ））；除了末尾數據元素，其他每個數據元素都有一個直接后繼（ai的直接后繼為 a i+1），如圖所示。
2.1.1 線性表的定義
例如，公司的員工信息表就是一個典型的線性表。在員工信息表中，一名員工的記錄就是一個數據元素，如表所示。
從表中可以看出，員工小千的記錄為首個數據元素，員工小研的記錄為末尾數據元素。其他員工都有一個直接前驅的員工以及直接后繼的員工。
2.1.2 線性表的運算
線性表的運算指的是對線性表中的數據進行操作，其具體的實現與線性表的物理結構有關。線性表常見的幾種運算如下。
（1）置空：將線性表變成空表。
（2）求長度：獲取線性表數據結點的個數。
（3）取結點：取出線性表中的某個數據結點。
（4）定位：獲取某一個指定的數據結點。
（5）插入：將數據結點插入到線性表的指定位置。
（6）刪除：刪除線性表中的指定數據結點。
上述運算并非線性表的所有運算，也不一定要同時使用，用戶可根據不同的需求合理選擇。
2.2 線性表的順序存儲
2.2.1
順序表的定義
返回目錄
2.2.2
順序表的創建
2.2.3
插入數據結點
2.2.4
刪除數據結點
2.2 線性表的順序存儲
2.2.5
其他操作
返回目錄
2.2.6
順序表總結
2.2 線性表的順序存儲
采用順序存儲的線性表稱為順序表。其數據元素之間的邏輯結構為線性結構，并且數據元素按照邏輯順序依次存放在地址連續的存儲單元中。
2.2.1 順序表的定義
一般情況下，線性表中的所有數據結點的類型是相同的。在C語言中，通常使用一維數組和結構體來表示順序表，代碼實現如下所示。
2.2.1 順序表的定義
由以上述代碼可知，結構體中的第1個成員為一維數組，使用該數組表示順序表（因為數組中的元素在計算內存中為連續存儲），數組中保存的元素為順序表的數據結點；結構體中的第2個成員last表示數組的下標，其初始值為-1，表示數組中沒有數據結點，每插入一個數據結點，last的值加1。如圖所示。
2.2.2 順序表的創建
在對順序表中的數據結點進行操作之前，需要先創建一個空的順序表。假設一個結點所占的空間大小為L，順序表中的結點有n個，則線性表所占的空間為n*L。但實際的情況是順序表中的結點數是不確定的，其占有的空間也是不確定的，因此需要先分配max*L個連續的存儲單元，使其能存儲max個結點。
通過代碼實現創建空的順序表，如例所示。
2.2.2 順序表的創建
由例可知，創建空的順序表只需為結構體在內存上申請一塊連續的空間，并將表示數組下標的last置為-1，表示順序表（數組）中沒有任何結點。
2.2.3 插入數據結點
2.2.2節完成了創建空順序表的操作，接下來將通過代碼展示如何在順序表中插入數據結點。在插入數據結點之前，需要判斷順序表是否為滿，如果為滿則不允許插入數據結點，否則會造成數據在內存上越界。
1.不指定位置插入數據結點
插入數據結點需要先判斷順序表是否為滿，代碼如下所示。（變量定義與例2-1一致）
由上述代碼可知；當last的值等于數組元素的最大下標值時條件為真，返回值為1，表示順序表已滿；否則返回0，表示順序表還有空間。
2.2.3 插入數據結點
數據表未滿即可插入數據結點，代碼如下所示。（變量定義與例2-1一致）
2.2.3 插入數據結點
2.指定位置插入數據結點
指定位置插入數據結點，需要先遍歷整個順序表，然后找到指定的位置，并將該位置后的結點依次向后移動，最后插入數據，如圖所示。
2.2.3 插入數據結點
代碼如下所示。（變量定義與例2-1一致）
2.2.3 插入數據結點
由以上代碼可知，指定位置插入數據結點首先需要確定插入的位置，然后將該位置后的結點依次向后移動一個存儲單元（先移動末尾結點），再將新結點存入指定位置，順序表末尾結點的下標last加1。
3.顯示數據結點
插入數據結點完成后，可通過打印順序表中結點的數據判斷是否插入成功，代碼實現如下所示。（變量定義與例2-1一致）
2.2.3 插入數據結點
4.整體測試
將以上功能代碼與例2-1結合，測試數據操作是否成功，代碼參考教材2.2.3節。（變量定義與例2-1一致）
例中，主函數main()主要用于測試子函數是否正確，先創建空的順序表，然后依次插入數據結點，最后通過指定位置的方式再次插入數據結點。輸出結果如下所示。
由輸出結果可以看出，順序表中成功插入數據結點。第一輪插入的結點數據為10、20、30、40，第二輪通過指定位置的方式插入數據結點，結點數據為5、15、25、35。
2.2.4 刪除數據結點
在刪除數據結點之前，需要判斷順序表是否為空，如果為空，不允許刪除數據結點。
1.不指定位置刪除數據結點
刪除數據結點需要先判斷順序表是否為空，代碼如下所示。（變量定義與例2-1一致）
由上述代碼可知，當last的值等于-1時，條件為真，返回值為1，表示順序表為空；否則返回0，表示順序表非空。
2.2.4 刪除數據結點
順序表非空即可刪除數據結點，代碼如下所示。（變量定義與例2-1一致）
2.指定位置刪除數據結點
指定位置刪除數據結點與插入數據結點類似，如圖所示。
2.2.4 刪除數據結點
代碼如下所示。（變量定義與例2-1一致）
2.2.4 刪除數據結點
由以上代碼可知，刪除結點首先需要確定刪除的位置，然后將該位置后的結點依次向前移動一個存儲單元（先移動指定位置的下一個結點），再將順序表末尾結點的下標last減1。
3.整體測試
將以上功能代碼與例2-2結合，測試數據操作是否成功，代碼參考教材2.2.4節。（變量定義與例2-1一致）
例中，主函數main()主要用于測試子函數是否正確，先創建空的順序表，然后將數據結點依次插入到順序表的末尾，最后通過兩種方式刪除順序表中的結點。輸出結果如下所示。
由輸出結果可以看出，數據結點插入空順序表成功，總共插入5個結點，數據分別為10、20、30、40、50；執行刪除結點操作，成功刪除順序表首個結點和末尾結點。
2.2.5 其他操作
對順序表中的數據結點除了可以進行插入與刪除，還可以進行其他類型的操作，例如，修改結點數據，查找數據結點位置，刪除重復數據結點，合并順序表。
1.修改結點數據
修改結點數據指的是對順序表中某一結點的數據進行修改，如圖所示。
2.2.5 其他操作
代碼如下所示。（變量定義與例2-1一致）
2.2.5 其他操作
2.查找數據結點位置
查找數據結點位置指的是獲取結點的下標值，如圖所示。
2.2.5 其他操作
代碼如下所示。（變量定義與例2-1一致）
3.刪除重復數據結點
刪除重復數據結點指的是刪除順序表中數據相同的結點，如圖所示。
2.2.5 其他操作
代碼如下所示。（變量定義與例2-1一致）
2.2.5 其他操作
4.合并順序表
合并順序表指的是將兩個順序表合并為一個順序表，同時去除數據重復的結點，如圖所示。
2.2.5 其他操作
代碼如下所示。（變量定義與例2-1一致）
5.整體測試
將以上功能代碼與例2-2、例2-3使用的函數接口結合，查看數據操作是否成功，代碼參考教材2.2.5節。
2.2.5 其他操作
例中，主函數調用子函數實現的功能包括創建空順序表并插入數據結點；修改順序表中結點的數據；刪除數據重復的結點；創建第2個空順序表并插入數據結點；合并兩個順序表。輸出結果如下所示。
由輸出結果可以看出，第1個順序表創建并插入數據成功，修改結點數據后順序表中出現數據同為20的兩個結點，然后成功刪除數據相同的結點；創建第2個順序表并插入數據成功，然后第1個順序表與第2個順序表合并。
2.2.6 順序表總結
通過前面的介紹可知，順序表是將數據結點放到一塊連續的內存空間上（使用數組表示順序表，數組在內存上占有連續的空間），因此順序表結構較為簡單，根據數據結點的下標即可完成數據的存取。如圖所示。
2.2.6 順序表總結
雖然通過結點下標的方式訪問數據十分高效，但是用戶每次存取數據時，都需要重新遍歷表，批量移動數據結點。如圖所示。
2.2.6 順序表總結
如圖所示，移動數據是將前一個結點的數據賦值給后一個結點。因此，無論是刪除還是插入操作，都會導致批量的賦值操作。（賦值操作的本質是重寫內存）
綜上所述，順序表并不適合頻繁存取數據，而使用線性表的另一種存儲形式——鏈式存儲（單鏈表），則可以很好地解決這一問題。
2.3 線性表的鏈式存儲
2.3.1
單鏈表的定義
返回目錄
2.3.2
單鏈表的創建
2.3.3
插入數據結點
2.3 線性表的鏈式存儲
2.3.5
刪除數據結點
返回目錄
2.3.6
其他操作
2.3 線性表的鏈式存儲
采用鏈式存儲的線性表稱為單鏈表。其數據元素之間的邏輯結構為線性結構，但是數據元素所在的存儲單元內存地址是不連續的。
2.3.1 單鏈表的定義
單鏈表不同于順序表，其結點存儲在內存地址非連續的存儲單元上，并通過指針建立它們之間的關系。需要注意的是，單鏈表中的結點形式不同于順序表，如圖所示。
由圖可知，單鏈表中的結點都是由兩部分組成，一部分為數據域（data），另一部分為指針域（next）。簡單地說，數據域用來存放結點的數據，而指針域存放的是一個指針，該指針保存的是下一個結點的內存地址，或者說該指針指向下一個結點，如圖所示。
2.3.1 單鏈表的定義
根據圖所示的單鏈表結構可知，表中每一個結點的結構都是相同的。因此，通過代碼對單鏈表進行定義時，默認的做法是定義一個結構體。根據圖所示的結點結構可知，結構體中需要定義的成員有2個，即存儲的數據與指向下一個結點的指針。代碼如下所示。
由以上代碼可知，結構體的第1個成員為結點數據（結點數據的類型是不固定的，代碼中的data為整型數據，僅作為參考）；第2個成員為指針變量，保存的是該結點的下一個結點的內存地址。
2.3.2 單鏈表的創建
在對單鏈表中的數據進行操作之前，需要先創建一個空的單鏈表。通過代碼實現創建一個空的單鏈表，如例所示。
2.3.2 單鏈表的創建
創建空單鏈表與創建順序表完全不同。例2-5的第13～21行代碼，其功能并非是在內存上申請一塊空間存放單鏈表中所有的結點，而是在內存上申請一個結點（一個結構體）所需的空間，該結點的結構與其他結點一致，只是不保存任何數據，僅作為單鏈表的頭結點使用，如圖所示。
以生活中常見的火車來打比方，創建空單鏈表操作只是申請了一個火車頭，車頭并不會載客，即不保存任何數據。初始時車頭并沒有牽引車廂，即未指向下一個結點。
2.3.3 插入數據結點
2.3.2節完成了創建空單鏈表的操作，接下來將通過代碼展示如何在單鏈表中插入數據結點。向單鏈表插入數據結點的方法有很多，包括頭插法、尾插法、順序插入法、指定位置插入法。
1.頭插法
單鏈表不同于順序表，單鏈表使用的存儲空間是不固定的。因此，插入數據結點無須判斷單鏈表是否為滿。使用頭插法插入數據結點有兩種不同的情況，即插入第一個數據結點與插入除第一個結點以外的其他數據結點，如圖所示。
2.3.3 插入數據結點
2.3.3 插入數據結點
由圖可以看出，插入數據結點的本質為修改數據結點的指針域，使指針指向的地址改變，代碼如下所示。（變量定義與例2-5一致）
2.3.3 插入數據結點
2.尾插法
尾插法即從單鏈表的末尾插入數據結點，如圖所示。
2.3.3 插入數據結點
代碼如下所示。（變量定義與例2-5一致）
由以上代碼可知，尾插法需要先找到單鏈表末尾的結點，然后將末尾結點的指針指向新插入的結點。
2.3.3 插入數據結點
3.順序插入法
順序插入法是頭插法的改良版，在插入數據結點前需要進行判斷，保證單鏈表中的數據有序排列，如圖所示。
2.3.3 插入數據結點
代碼如下所示。（變量定義與例2-5一致）
由上述代碼可知，順序插入法在插入前會將插入的結點數據與單鏈表中的結點數據進行對比，如果插入的結點數據大于鏈表中結點數據，則移動指針，繼續對比下一結點。
2.3.3 插入數據結點
4.指定位置插入法
指定位置插入法類似于頭插法，不同的是該方法在插入數據結點前進行了判斷，選擇位置后再進行插入操作，如圖所示。
2.3.3 插入數據結點
代碼如下所示。（變量定義與例2-5一致）
由以上代碼可知，指針移動的次數（while循環的次數）等于插入位置的下標值。
2.3.3 插入數據結點
5.顯示數據結點
插入數據結點完成后，即可通過打印結點數據判斷結點是否插入成功。遍歷整個單鏈表的方法很簡單，只需要使用指針依次訪問結點中的數據即可，如圖所示。
2.3.3 插入數據結點
根據圖設計代碼完成顯示功能，代碼如下所示。（變量定義與例2-5一致）
6.整體測試
將以上功能代碼與例2-5結合，查看數據操作是否成功，代碼參考教材2.3.3節。
2.3.3 插入數據結點
例中，主函數主要用于測試子函數是否正確。測試分為4個部分：先創建一個空單鏈表，使用順序插入法將數據80、60、40插入鏈表，通過顯示結點數據，判斷結點是否插入成功并自動排序；使用尾插法將數據100、200、300插入鏈表，通過顯示結點數據，判斷結點是否插入成功；使用頭插法將數據30、10插入鏈表，通過顯示結點數據，判斷結點是否插入成功，查看數據顯示順序是否與插入順序相反；使用指定位置插入法將數據5、5插入鏈表的第0位和第1位，通過顯示結點數據，判斷結點是否插入成功，查看數據是否在指定的位置上。輸出結果如下所示。
由輸出結果可以看出，4種插入方法都可以成功將數據結點插入到鏈表中。其中，使用順序插入法插入的數據自動完成排序（從小到大）；使用頭插法插入的數據顯示順序與插入順序相反；使用指定位置插入法插入的數據出現在正確的位置上。
2.3.4 刪除數據結點
在刪除數據結點之前，需要判斷單鏈表是否為空（如果為空，則不允許刪除數據結點）。接下來將通過代碼展示如何在單鏈表中刪除數據結點。從單鏈表刪除數據結點的方法包括頭刪法、指定數據刪除法。
1.頭刪法
刪除數據結點需要先判斷單鏈表是否為空，代碼實現如下所示。（變量定義與例2-5一致）
如果單鏈表不為空，則可使用頭刪法刪除數據結點。其實現的原理是：定義一個指針，指向要刪除的數據結點，然后改變指針指向，最后釋放指針指向的空間。如圖所示。
2.3.4 刪除數據結點
代碼如下所示。（變量定義與例2-5一致）
2.3.4 刪除數據結點
2.指定數據刪除法
指定數據刪除法是根據指定的具體數據，刪除單鏈表中與數據對應的結點，如圖所示。
2.3.4 刪除數據結點
代碼如下所示。（變量定義與例2-5一致）
2.3.4 刪除數據結點
3.整體測試
將以上功能代碼與例2-6結合測試，查看數據操作是否成功，代碼參考教材2.3.4節。
例中，主函數主要用于測試子函數是否正確。測試分為3個部分：先創建一個空單鏈表，使用順序插入法將數據80、60、40插入鏈表，通過顯示結點數據，判斷結點是否插入成功并自動排序；使用頭刪法將數據從鏈表中刪除，通過顯示結點數據，判斷第一個結點是否刪除；使用指定數據刪除法將數據從鏈表中刪除，通過顯示結點數據，判斷數據為80的結點是否刪除。運行結果如下所示。
由輸出結果可以看出，兩種刪除方法都可以成功將數據結點從鏈表中刪除。其中，使用順序插入法插入的數據自動完成排序（從小到大）；使用頭刪法成功將鏈表首個數據結點刪除；使用指定數據刪除法成功將數據為80的結點刪除。
2.3.5 其他操作
單鏈表中的數據結點除了可以完成插入與刪除的需求，還可以進行其他類型的操作，例如，修改結點數據，查找數據結點位置，鏈表數據翻轉，合并單鏈表。
1.修改結點數據
修改結點數據指的是通過指定的數據在鏈表中尋找匹配的結點，并將該結點的數據修改。代碼如下所示。
2.3.5 其他操作
2.查找數據結點位置
查找數據結點位置指的是通過指定的數據在鏈表中尋找匹配的結點，并獲取該結點在單鏈表中的下標。
2.3.5 其他操作
3.鏈表數據翻轉
鏈表數據翻轉指的是將單鏈表中的數據倒序排列。例如，單鏈表中結點數據的順序為1、2、3、4、5，經過翻轉后結點數據的順序為5、4、3、2、1。如圖所示。
2.3.5 其他操作
如圖所示，斷開原有的連接并使用頭插法重新插入結點，需要通過指針操作來完成。代碼如下所示。
以上示例中，定義了兩個指針p、q，將q指向需要重新插入的結點，p指向q的下一個結點。通過操作指針完成重新插入，插入采用頭插法，每插入一個結點，p、q向后移動。
2.3.5 其他操作
4.合并單鏈表
合并單鏈表指的是將兩個單鏈表合并為一個單鏈表，如圖所示。
如圖所示，將data1與data2對比，選擇值較小的結點插入新的單鏈表，如果data3較小則插入data3所在的結點，然后將data1與data4進行對比，如果data1較小則插入data1所在的結點，以此類推。
2.3.5 其他操作
上述合并使用的方式稱為歸并排序，即將已有序的子序列合并，得到完全有序的序列。例如，單鏈表1 的結點數據為1、3、5、7，單鏈表2的結點數據為2、4、6、8，那么經過合并后鏈表中的結點數據為1、2、3、4、5、6、7、8。
需要注意的是，歸并排序的前提是子序列原本就是有序序列，否則不滿足歸并條件。例如，單鏈表1的結點數據為1、2、1，單鏈表2的結點數據為2、3、2，以圖所示的方式合并后，單鏈表中的結點數據為1、2、1、2、3、2， 無法得到有序排列。
2.3.5 其他操作
代碼實現如下所示。
2.3.5 其他操作
5.整體測試
將以上功能代碼與例2-7結合，查看數據操作是否成功，代碼參考教材2.3.5節。
例中，主函數主要用于測試子函數是否正確。測試分為4個部分：先創建一個空單鏈表1，使用尾插法將數據70、50、20、10插入鏈表，通過顯示結點數據，判斷結點是否插入成功；將單鏈表1中的結點數據修改為30，通過顯示結點數據，判斷數據是否修改成功；將單鏈表1中的數據結點翻轉，通過顯示結點數據，判斷鏈表是否翻轉成功；創建空單鏈表2，使用尾插法將數據20、40、60插入鏈表，將單鏈表1和單鏈表2進行合并，通過顯示結點數據，判斷單鏈表合并是否成功。運行結果如下所示。
由輸出結果可以看出，操作全部成功。
2.4 單向循環鏈表
2.4.1
單向循環鏈表的定義
返回目錄
2.4.2
單向循環鏈表的創建
2.4.3
插入數據與顯示數據
2.4.1 單向循環鏈表的定義
在單鏈表中，頭結點指針是相當重要的，因為單鏈表的操作都需要頭結點指針。如果頭指針丟失或者損壞，那么整個鏈表都會遺失，并且浪費鏈表內存空間。為了避免這種情況的產生，可以將單鏈表設計成循環鏈表。循環鏈表可以是單向循環也可以是雙向循環，下面將介紹單向循環鏈表的操作。
單向循環鏈表指的是在單鏈表的基礎上，將尾結點的指針指向鏈表中的頭結點，而非NULL，如圖所示。
由圖所示，單向循環鏈表中的結點通過指針指向形成一個閉合的連接，結點的結構與單鏈表相同，代碼如下所示。
2.4.2 單向循環鏈表的創建
在對單向循環鏈表中的數據進行操作之前，需要先創建一個空表。通過代碼實現創建空的單向循環鏈表，如例所示。
2.4.3 插入數據與顯示數據
1.頭插法
插入數據可選用頭插法，其原理與單鏈表一致，代碼如下所示。
2.4.3 插入數據與顯示數據
2.顯示數據
顯示數據即獲取單向循環鏈表中結點的數據，代碼如下所示。
3.整體測試
將以上功能代碼與例2-9結合，測試數據操作是否成功，代碼參考教材2.4.3節。
2.4.3 插入數據與顯示數據
例中，主函數主要用于測試子函數是否正確。主要測試的功能為創建單向循環鏈表，使用頭插法插入結點，最后顯示結點數據。輸出結果如下所示。
由輸出結果可以看出，數據結點插入成功。采用頭插法插入數據結點，結點排列順序與插入順序剛好相反。
2.5 線性表的鏈式存儲
2.5.1
雙向循環鏈表的定義
返回目錄
2.5.2
雙向循環鏈表的創建
2.5.3
插入與刪除數據結點
2.5.1 雙向循環鏈表的定義
在單鏈表中，如果需要查找某一個結點的后繼時，直接通過指針移動到下一個結點即可。但是要查找某一結點的前驅時，則需要從鏈表頭開始。為了提高數據操作的效率，引入雙向循環鏈表。
雙向循環鏈表中結點的結構與單鏈表不同，每一個結點都有一個指向前一個結點的指針和一個指向后一個結點的指針，如圖所示。
2.5.1 雙向循環鏈表的定義
結點結構的代碼實現如下所示。
雙向循環鏈表中，可以通過指針快速訪問某個結點的前驅和后繼，如圖所示。
由圖可知，每個結點的prior指針指向自身的前驅，每個結點的next指針指向自身的后繼，并且形成閉合的連接。
2.5.2 雙向循環鏈表的創建
在對雙向循環鏈表中的數據進行操作之前，需要先創建一個空表。通過代碼實現創建空的雙向循環鏈表，如例所示。
2.5.2 雙向循環鏈表的創建
例中創建空雙向循環鏈表，頭結點的兩個指針prior與next的初始狀態為指向自己，如圖所示。
2.5.3 插入與刪除數據結點
雙向循環鏈表插入數據與刪除數據比單鏈表要復雜，刪除數據時需要判斷鏈表是否為空，如果為空不允許執行刪除操作。
1.插入數據結點
雙向循環鏈表第一次插入數據結點與后續插入的數據結點的情況不同，如圖所示。
2.5.3 插入與刪除數據結點
2.5.3 插入與刪除數據結點
由圖可以看出，采用頭插法插入新結點，只需要保證新結點與頭結點（前驅）、頭結點的下一個結點（后繼）建立相互指向的關系即可。為了便于理解，在第一次插入結點時，可以假設雙向循環鏈表中已經存在其他結點，其操作代碼與其他情況一致。代碼如下所示。
2.5.3 插入與刪除數據結點
2.刪除數據結點
刪除數據結點之前，必須判斷雙向循環鏈表是否為空，代碼如下所示。
刪除數據結點采用頭刪法的思想，如圖所示。
2.5.3 插入與刪除數據結點
由圖可知，刪除數據結點，只需將該結點與其前驅（頭結點）、后繼的指針指向關系斷開，并重新連接，然后將被刪除結點的空間釋放。代碼如下所示。
2.5.3 插入與刪除數據結點
3.顯示結點數據
插入或刪除結點完成后，可通過打印結點數據，判斷雙向循環鏈表中的結點操作是否正確。代碼如下所示。
4.整體測試
將以上功能代碼與例2-11結合，測試數據操作是否成功，代碼參考教材2.5.3節。
2.5.3 插入與刪除數據結點
例中，主函數主要用于測試子函數是否正確，首先創建一個空的雙向循環鏈表，然后插入數據結點，最后刪除數據結點。輸出結果如下所示。
由輸出結果可以看出，插入數據結點成功，刪除數據結點成功。
本章小結
本章主要介紹了線性表的兩種物理結構的實現——順序表與單鏈表，通過代碼設計詳細展示了二者的數據操作。單鏈表可以實現循環鏈表，循環鏈表可以是單向循環也可以是雙向循環。讀者需要理解順序表與單鏈表的結點操作原理，并熟練代碼設計，從中掌握各個功能模塊的算法設計思想。

展開更多......

收起↑