鏈結串列有序串列 (ordered list) 有序串列代表的是一種資料結構, 它的元素以某種順序排列 ( 該順序具有一定的意義, 不可錯置 ) 在現實中, 我們很容易可以找到有序串列的實例, 如下 : 一年的月份 : ( 一月, 二月, 三月, 四月, 五月, 六月, 七月, 八

Size: px

Start display at page:

Download "鏈結串列有序串列 (ordered list) 有序串列代表的是一種資料結構, 它的元素以某種順序排列 ( 該順序具有一定的意義, 不可錯置 ) 在現實中, 我們很容易可以找到有序串列的實例, 如下 : 一年的月份 : ( 一月, 二月, 三月, 四月, 五月, 六月, 七月, 八"

铸苏景米
7 years ago
Views:

1 第 4 章鏈結串列本章學習目標. 理解一個基本的資料結構 - 鏈結串列資料結構如何透過結構指標自我參考機制實現鏈結串列資料結構 C 語言的別名機制鏈結串列在插入與刪除非末端元素時, 有極佳的時間複雜度

2 鏈結串列有序串列 (ordered list) 有序串列代表的是一種資料結構, 它的元素以某種順序排列 ( 該順序具有一定的意義, 不可錯置 ) 在現實中, 我們很容易可以找到有序串列的實例, 如下 : 一年的月份 : ( 一月, 二月, 三月, 四月, 五月, 六月, 七月, 八月, 九月, 十月, 十一月, 十二月 ) (January, February, March, April, May, June, July, August, September, October, November, December) 一日之小時 : (00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23) 太陽系八大行星 : ( 水星, 金星, 地球, 火星, 木星, 土星, 天王星, 海王星 ) 阿花之總統任期年份 : ()

3 鏈結串列 4-3 在上述的最後一個範例中, 我們可以發現有序串列也可以是空串列除了空串列之外, 有序串列包含許多資料項 (item), 這些資料項具有順序性包含 n 個資料項的有序串列之標準格式為 (item 0, item 1,., item i-1, item i, item i+1,, item n-1 ) 有序串列又可以稱之為線性串列 (linear list), 它是一種資料結構因此, 我們可以在有序串列上進行各類運算, 這些運算常見的有下列幾種 : 1. 查詢串列的長度 ( 即回傳 n) 2. 依照順序讀取串列中的項目 ( 由左而右 ) 3. 反向依照順序讀取串列中的項目 ( 由右而左 ) 4. 查詢第 i 個項目之值 (0 i<n) 5. 修改第 i 個項目之值 (0 i<n) 6. 在第 i 個位置插入一個新的項目 item(0 i<n) 插入後, 串列形成 (item 0, item 1,., item i-1, item, item i,..., item n-1 ), 共 n+1 個項目 7. 在第 i 個位置刪除一個項目 (0 i<n)

4 鏈結串列 4-4 刪除後, 串列形成 (item 0, item 1,., item i-1, item i+1,..., item n-1 ), 共 n-1 個項目有序串列在科學與工程中也可以找到許多範例, 例如之前介紹的矩陣, 也可以用有序串列來表達, 例如 : A nxn : (a 11, a 12, a 13,..., a 1n, a 21, a 22,..., a ij,..., a nn ) 使用陣列來存放有序串列是採用一種稱為循序映射 (Sequential mapping) 的方法, 它是將項目一一填入陣列的元素中, 因此, 連續的項目 item i,item i+1 會位於陣列的連續位置 ( 連續的記憶體 ), 而其特色是在執行第 1~5 種運算時只需要常數時間而執行第 6~7 種運算 ( 插入與刪除運算 ) 則較為費時因為必須對其後的資料項進行搬移, 使得連續的項目仍然保持位於陣列的連續位置之特性為了改善插入或刪除運算的時間複雜度, 我們將採用另一種非循序映射的方法在資料結構領域中, 我們稱之為鏈結串列

5 鏈結串列鏈結串列 (Linked List) 鏈結串列是一種常見的資料結構, 它由節點 (node) 組成, 節點又稱為串列節點 (list node), 每一個節點至少包含一個資料欄位 (data field) 與鏈結欄位 (link field) 節點的資料欄位可用來存放資料鏈結欄位則是用來使得節點與節點間產生鏈結關係, 以便構成串列節點的示意如圖 4-1 為了使用鏈結串列, 因此我們可以給每一個鏈結串列一個名稱, 該名稱可以視為一個鏈結並指向第一個節點, 故又稱之為串列頭圖 4-1 鏈結串列的節點

6 鏈結串列 4-6 鏈結串列依據整體結構常見的有 (1) 單向鏈結串列 (2) 環狀鏈結串列 (3) 雙向鏈結串列 (4) 雙向環狀鏈結串列 (5) 其他為了特殊應用所設計的鏈結串列如表示樹狀結構時採用的鏈結串列, 於樹一章中另行說明

7 鏈結串列 4-7 假設要以鏈結串列存放樂透開獎的六個球號, 其開獎順序為 (26,18,15,29,32, 12) 則上述四種常見的鏈結串列示意圖如下 1. 單向鏈結串列 (Singly Linked List): 每一個節點的鏈結欄位 (link) 將指向下一個節點, 而最後一個節點的鏈結欄位將指向 NULL 如圖 4-2 與 4-3 都是單向鏈結串列的示意圖圖 4-2 單向鏈結串列 ( 圖示一 ) 圖 4-3 單向鏈結串列 ( 圖示二 )

8 鏈結串列環狀鏈結串列 (Circular Linked List): 將單向鏈結串列最後一個節點的鏈結欄位指向第一個節點, 稱之為環狀鏈結串列如圖 4-4 是環狀鏈結串列的示意圖圖 4-4 ( 單向 ) 環狀鏈結串列

9 鏈結串列雙向鏈結串列 (Doubly Linked List): 每一個節點都有兩個鏈結欄位, 稱為左鏈結欄位 (llink) 及右鏈結欄位 (rlink), 分別指向前一個節點及下一個節點, 而第一個節點的左鏈結欄位及最後一個節點的右鏈結欄位將指向 NULL 如圖 4-5 是雙向鏈結串列的示意圖圖 4-5 雙向鏈結串列

10 鏈結串列雙向環狀鏈結串列 (Circular Doubly Linked List): 將雙向鏈結串列第一個節點的左鏈結欄位指向最後一個節點, 並將最後一個節點的右鏈結欄位將指向第一個節點, 稱之為雙向環狀鏈結串列如圖 4-6 是雙向環狀鏈結串列的示意圖圖 4-6 雙向環狀鏈結串列

11 鏈結串列以陣列實作鏈結串列鏈結串列是抽象的概念, 並未規範在程式語言中如何實作鏈結串列資料結構假設程式語言提供了類似指標的功能, 一般我們會運用指標來實作鏈結欄位如果程式語言未提供類似指標的功能, 仍舊可以運用陣列來實作鏈結串列, 但一般很少會這樣子做假設我們使用二維陣列來存放鏈結串列, 則每一個節點必須使用一列來存放陣列存放相同資料型態的資料, 資料欄位與鏈結欄位的資料型態也必須相同假設資料欄位宣告為整數資料型態, 此時, 我們可以把鏈結欄位的內容設定為下一個節點的列索引值, 因為索引值是一個整數值為了記錄串列頭, 我們可以新增一個串列頭節點, 其資料內容為空, 而鏈結欄位存放的是第一個節點的列索引後續接動畫頁

12 動畫頁 ( 書附光碟也有 ) 鏈結串列 4-12

13 動畫頁 ( 書附光碟也有 ) 鏈結串列 4-13

14 鏈結串列 4-14 由於我們使用 C 語言來實作資料結構, 因此鮮少使用陣列來存放鏈結串列, 通常是採用結構 (struct) 搭配指標來實作鏈結串列故而此處我們並不提供刪除節點的演算法小試身手 4-1 採參考圖 4-7, 設計一個時間複雜度為 O(1) 的刪除演算法請使用陣列來實作環狀 ( 單向 ) 鏈結串列, 並畫出其示意圖

15 鏈結串列以結構搭配指標實作鏈結串列如果節點的資料項目不是整數, 而是字串或字元, 那麼單純使用整數二維陣列就無法製作鏈結串列了, 因為陣列的每個元素都必須是相同的資料型態不過如果使用結構 (struct) 搭配一維陣列就可以解決這樣的問題我們可以如下宣告節點的 listnode 結構, 然後再宣告 List[] 結構陣列即可 struct listnode 不實用 { char data; /* 資料欄位, 內容為字元 */ int link; /* 鏈結欄位, 指出下一個位節點位於陣列的何處 */ }; struct listnode List[10]; 陣列元素的資料型態是 listnode 結構上述的 List[] 陣列是一個靜態陣列, 在實際應用時, 通常我們不能確定鏈結串列共包含幾個節點, 因此看似動態陣列更為適當, 但在可使用動態記憶體配置的前提之下, 其實我們還有更好的方法也就是以動態記憶體配置產生節點, 並在節點之間透過 link 產生鏈結關係, 並不需要採用動態陣列來實作鏈結串列

16 鏈結串列 4-16 由於透過動態記憶體配置節點 ( 例如透過 malloc 函式 ), 系統會回傳所配置節點的記憶體位址, 所以呼叫時, 必須設定一個指標來接收該節點的記憶體位址這部分的程式碼對於部分不熟悉 C 語言者, 有些困難, 所以, 我們在本節中先複習指標與指標資料型態然後逐步漸進地, 完成節點的宣告方式以及完成鏈結串列的建立指標與指標資料型態在 C 語言中, 我們可以宣告一個變數, 該變數內容是一個記憶體位址, 這樣的變數稱之為指標變數宣告指標變數需要搭配指標運算子 * 來完成想要存取指標變數所指向記憶體的內容時, 也必須搭配 * 來完成除了必須使用 * 來宣告指標變數之外, 也必須同時宣告該指標將來指向之記憶體內容是哪一種資料型態至於要取得某變數的記憶體位址並設定給指標變數, 則必須透過取址運算子 & 來完成範例如下: 後續接動畫頁

17 動畫頁 ( 書附光碟也有 ) 鏈結串列 4-17

18 動畫頁 ( 書附光碟也有 ) 鏈結串列 4-18

19 鏈結串列在結構體中包含指標項目想要製作節點的資料結構, 應該使用結構 (struct) 來組織資料項目與鏈結項目, 而鏈結項目應該是一個指標變數先由簡單的範例觀察, 當指標成為結構的其中一個項目時, 會發生什麼樣的事情? 假設我們有一個結構 s, 其項目如下, 當中包含了一個整數 i 與一個指向整數資料型態的指標 p struct s { int i; int *p; 指標變數 p 是 s 結構的一個項目 }; 此時如果要宣告結構變數 s1, 並設定其項目時, 可以使用下列敘述 : int num=100; struct s s1; 後續接動畫頁

20 動畫頁 ( 書附光碟也有 ) 鏈結串列 4-20

21 動畫頁 ( 書附光碟也有 ) 鏈結串列 4-21

22 鏈結串列自我參考機制自我參考機制是在 C 程式設計中完成鏈結串列資料結構的重要機制假設各位已經對於結構內包含指標項目不會產生困惑, 那麼, 接下來只要做一點點的改變, 就能完成自我參考機制所謂 C 語言的自我參考機制 (self-reference) 代表的是一個結構中的某些項目被宣告為指標, 且該指標所指向之資料型態與指標所屬結構為同一結構代表該指標必須指向與結構相同資料型態的資料假設我們將之前介紹的 s 結構稍為修改一下, 成為 sr 結構如下當中的 p 指標, 宣告為指向 sr 結構體型態的變數, 就是自我參考機制的實例如下宣告後續接動畫頁 struct sr { int i; 指標 p 指向 sr 結構, 完成自我參考機制 struct sr *p; };

23 動畫頁 ( 書附光碟也有 ) 鏈結串列 4-23

24 動畫頁 ( 書附光碟也有 ) 鏈結串列 4-24

25 鏈結串列串列頭的宣告在實際應用上, 一般會使用一個指標來代表鏈結串列, 稱之為串列頭或串列頭指標, 串列頭會指向頭節點以宣告串列頭指標時, 應該將其所指向的資料型態宣告為節點結構, 如下範例 struct sr *first; first=&sr1; 將串列頭指向頭節點 sr1 兩個敘述可合併為 struct sr *first=&sr1; 上面的敘述會將 sp 指向之前宣告的結構變數 sr1, 敘述執行完畢後, 記憶體內容如圖 4-12 所示並且可透過 -> 運算子存取所指向結構內的項目例如 :first->i 就是 10 圖 4-12 含串列頭的單向鏈結串列

26 鏈結串列別名的應用宣告結構變數或結構指標變數時, 需要使用 struct 關鍵字來宣告, 非常不方便 C 語言允許我們將資料型態取一個別名, 如此, 我們就可以不使用 struct 而是直接透過別名宣告變數的資料型態, 如下範例未使用別名 struct Node { int data; struct Node *link; }; struct Node n1,n2; 宣告結構變數 struct Node *first; 使用別名 struct Node 程式 4.a { int data; struct Node *link; }; typedef struct Node node; typedef node *nodepointer; node n1,n2; nodepointer first; 使用別名宣告變數

27 鏈結串列 link 被宣告為指標, 並且指向的目標為 Node 資料型態, 因此是一種自我參考機制 2. nodepointer 指標型態的別名機制是之前沒學過的語法, 我們可以先從簡單的語法開始辨認, 假設有下列語法, 是用來宣告一個整數指標 int *p; 如果要宣告 int 的別名為 num, 則可以如下宣告指標 p typedef int num; num *p; 等同於 int *p 看懂了, 請回頭看 typedef struct Node node; 如果想要宣告的不是 int 的別名, 而是 int * 的別名, 也就是指向整數之指標型態的別名 np, 則可如下宣告, 然後再透過此別名宣告指標 p typedef int *np; np p; 您可以將 int * 與 np 分開來看 p 的資料型態是 int * 看懂了, 請回頭看 typedef node *nodepointer;

28 鏈結串列 4-28 有了上述的推演過程, 相信您可以理解 typedef node *nodepointer; 的語法, 亦即您只要將 node * 與 nodepointer 分開來看即可 nodepointer 指標型態別名將可直接用來宣告指向 node 型態的指標變數

29 鏈結串列經過定義別名後我們可以使用 node 當作新的資料型態來宣告變數 n1,n2( 節點變數 ) 或使用 nodepointer 當作新的指標資料型態來宣告指標變數 first( 指向節點的指標變數 ) 對雙向鏈結串列而言, 它具有兩個鏈結欄位 ( 鏈結欄位將指向某一個節點或 NULL) 假設它只有一個整數資料欄位, 則可以如下宣告節點結構 : struct DNode /* 雙向鏈結串列的節點結構宣告 */ { int data; struct DNode *llink; 兩個鏈結欄位都必須宣告為自我參考 struct DNode *rlink; }; typedef struct DNode Dnode; typedef Dnode *DnodePointer; 程式 4.b

30 鏈結串列動態記憶體配置與鏈結串列雖然我們可以透過宣告變數的方式建立節點, 並透過指標變數代表節點, 但鏈結串列與陣列最大的不同在於, 鏈結串列可以充分而有效的利用可用記憶體空間我們不該限制使用者在程式執行過程中使用的節點數量 ( 除非記憶體可用空間不足 ), 並且也不該配置過多不會用到的記憶體只有在需要產生節點時才產生一個節點, 而不是在程式中直接透過宣告變數的方式取得節點必須藉由 C 語言的動態記憶體配置函式 malloc() 來產生新節點計算參數 size 的大小時, 會配合 sizeof() 函式來求出記憶體大小而我們想要的節點已經宣告為 node 結構, 因此可以將引數設定為 sizeof(node) 在呼叫 malloc() 之後, 必須接收 malloc() 回傳的指標, 並且需要將之轉型為指向節點的指標型態例如 (struct node *) 此時也可以用別名來取代, 也就是之前介紹的 nodepointer 別名

31 鏈結串列 4-31 以 malloc 要求配置一個單向鏈結串列節點的範例如下 : nodepointer GetNode() { nodepointer NewNode; 要求配置一個節點 (node) 所需要的記憶體程式 4.a NewNode=(nodePointer) malloc(sizeof(node)); 必須進行轉型, 也可以改寫為 (node *) if(newnode==null) /* 已無記憶體可配置,malloc 會回傳 NULL 給 NewNode */ printf(" 記憶體不足!"); return NewNode; } 成功取得節點後, 回傳新節點的位址, 該位址存放在 NewNode 指標中圖 4-13 利用動態配置記憶體取得新節點

32 鏈結串列 4-32 請注意, 如果系統已無記憶體可配置了, 則 malloc() 會回傳 NULL, 因此呼叫 GetNode() 的敘述, 可以依照回傳值是否為 NULL 來判別配置是否成功釋放節點當節點從鏈結串列中移除後, 應把節點佔用的記憶體空間歸還給系統, 以便有效利用記憶體此時可透過 C 語言的記憶體釋放函式 free() 來完成 free() 要求呼叫敘述傳入要被釋放的記憶體位址, 如下敘述 free(ptr); 執行後會釋放 ptr 所指節點所佔用的記憶體老師的叮嚀如果本節之前的所有程式碼都已經看懂了, 那麼恭喜您, 不但能夠看懂後面的程式碼, 而且對於 C 程式設計的功力也提升了一個層次

33 鏈結串列 4-33

34 鏈結串列單向鏈結串列的運算鏈結串列的常見運算有很多由於鏈結串列分為許多種類, 因此運算的演算法內容也會有些不同本小節將針對單向鏈結串列的運算進行說明至於雙向鏈結串列的運算, 則留待之後的小節說明鏈結串列的各種運算又分為不同狀況時適用例如, 插入節點運算又分為插入節點在某節點之後以及某節點之前這兩種狀況都必須要指定某節點是哪一個節點如果是要插入在鏈結串列的末端 ( 又稱為新增節點 ), 則不需要指定串列的目標節點但必須同時考量到串列目前是空串列還是非空串列

35 鏈結串列 4-35 由於狀況有非常多種, 因此我們將在本小節中挑選重要的運算來做說明, 其餘則留給讀者做練習為了考量各位尚未熟悉上一節 C 語言關於鏈結串列的實作語法在提供運算的演算法時, 將同時提供虛擬碼與 C 函式兩種格式以及對應的圖形變化 ( 搭配動態投影片 ) 各位可以藉由虛擬碼圖形變化與動態投影片來理解運算的過程, 然後再對應到 C 函式, 如此更容易理解 C 函式各敘述的意義插入新節點在指定節點之後插入新節點會面臨的第一個問題, 是要將新節點插入到鏈結串列的哪一個位置例如插入在哪一個節點之後, 或哪一個節點之前, 兩者的演算法類似但不同此處, 我們僅討論將新節點插入在指定的 m 節點之後的演算法指定的 m 節點的意義是, 該節點被一個指標 m 所指向

36 鏈結串列 4-36 這個演算法如果想要一併適用於空串列, 必須允許 m 指向 NULL 來代表插入空串列的第一個節點演算法對應的示意圖變化如圖 4-14, 請注意, 即便 m 是串列的最後一個節點 ( 即 m->link 指向 NULL), 雖示意圖有些不同, 但該演算法也不會出錯程式 4.a 虛擬碼 C 函式功能 : 在 L 串列中的 m 節點之後插入新節點 ( 新節點資料內容為 d) Function insertafter(l,m,d) 要求系統配置一個新節點 ; 宣告一個指標 n 指向新取得的節點 If (n = NULL) then [return false] n->data d; n->link NULL If (m NULL) then [ n->link m->link; m->link n ] Else /* 串列原為空串列 */ [ L n ] int insertafter(nodepointer L, nodepointer m, int d) { nodepointer n = GetNode(); if(n == NULL) return false; n->data = d; n->link = NULL; if(m!= NULL) { 注意 : 這兩 n->link = m->link; m->link = 行順序不可 n; } 對調 else /* 串列原為空串列 */ L = n; return true; false 與 true 可事先定義為常數 0 與 1

37 鏈結串列 4-37 return true endfunction 動畫頁 ( 書附光碟也有 ) } 後續接動畫頁

38 鏈結串列移動工作節點想要瀏覽鏈結串列中所有的資料, 就必須循序拜訪整個串列, 這個時候可利用一個工作指標指向某一個節點, 而這個指標所指向的節點稱之為工作節點換言之, 工作節點 ( 工作指標所指向的目標 ) 必須可以移動 ( 更明確地說, 是工作指標必須可以移動 ), 如此才能拜訪整個串列的所有節點 4-1 參考圖 4-2 的單向鏈結串列, 寫一個函式, 循序印出串列所有節點的資料 void LinkListTraverse(nodePointer L) { nodepointer w=l; 將工作指標 w 指向第一個節點 while(w!= NULL) 程式 4.1

39 鏈結串列 4-39 } { printf("%d \t",w->data); w = w->link; } 呼叫敘述 LinkListTraverse(first); 將串列頭傳入函式中, 並以 L 指標來接收 first 在 LinkListTraverse 函式中, 我們使用一個 w 指標指向工作節點, 在迴圈執行之前, 先將之指向 L 所指向的節點, 也就是串列的第一個節點因此, 第一次印出的資料 w->data 將會是第一個節點的資料 26, 如圖 4-15(a) w->link 圖 4-15(a) 執行 w=l 後,w 指向第一個節點接著在迴圈內, 執行 w=w->link 將使得 w 指向第一個節點的 link 欄位所指向的節點, 也就是第二個節點, 因此印出 18 如圖 4-15(b) 後續接動畫頁

40 鏈結串列 4-40 動畫頁 ( 書附光碟沒有 ) 圖 4-15(b) 執行 w=w->link 後,w 指向第二個節點

41 鏈結串列 4-41 尋找節點與指定節點有些時候, 我們必須指定某一個節點, 例如, 在上一小節的插入新節點 n 在指定的節點 m 之後, 我們必須指定 m 節點是哪一個節點為了達到這個目的, 我們可以將 m 指標一開始指向串列首節點, 然後循序往後移動到符合條件的節點為止一般會以該節點的資料內容 data 做為比對條件並以該節點的 link 欄位是否為 null 來判斷該節點是否為最後一個節點往下一節點移動的指令為 m= m->link

42 鏈結串列 4-42 如果想要將新節點插入在 k 節點之前 ( 而非之後 ), 又想要套用之前所設計的 insertafter 函式, 則呼叫 insertafter 時, 傳入的節點應該是 k 節點的前一個節點此時同樣可以利用比對節點的 link 欄位是否指向 k 節點來確認節點是否為 k 的前一個節點我們將於下一小節中, 利用相同的技巧, 來尋找前一個節點, 並設計刪除節點函式小試身手 4-2 請開啟光碟的程式碼, 在光碟程式 4.1 中, 我們提供了一個 CreateAll() 函式, 可用來從無到有, 循序建立圖 4-15 的整個串列 ( 資料原本先存放在陣列中 ), 請先看懂該函式, 或由您自行重新設計 CreateAll(), 然後分析 CreateAll() 的時間複雜度為何?

43 鏈結串列刪除指定節點假設我們要刪除 m 節點, 必須先知道 m 的前一個與後一個節點是哪一個節點, 因為刪除 m 後, 前一個節點的 link 應該指向後一個節點要尋找 m 的後一個節點很簡單, 因為那是 m->link 所指向的節點要尋找 m 的前一個節點, 則必須透過迴圈來尋找, 將之撰寫為 PreNode 函式程式 4.a 虛擬碼 C 函式功能 : 尋找 m 節點的前一個節點 Function PreNode(L,m) 宣告一個指標 B B L While (B NULL) AND (B->link m) do B B->link endwhile return B endfunction nodepointer PreNode(nodePointer L, nodepointer m) { nodepointer B=L; while((b!= NULL) && (B->link!= m)) B = B->link; return B; 請注意, 當 B 為 NULL } 時, 代表沒找到當回傳值 B 指標為 NULL, 代表在串列中沒找到 m 節點如果 m 已經是第一個節點, 則不該透過 PreNode 函式尋找 m 的前一個節點

44 鏈結串列 4-44 有了上述的 PreNode 函式之後, 刪除節點的演算法就變得非常簡單了我們只需要把 m 的前一個節點的 link 指向 m 的後一個節點然後釋放 m 節點所佔用的記憶體空間即可虛擬碼 C 程式 4.a 函式功能 : 刪除 m 節點 Function DeleteNode(L,m) 宣告一個指標 B If (L = m) then [ return ERROR ] B PreNode(L,m) If (B = NULL) then [return false] B->link = m->link Free(m) return true endfunction int DeleteNode(nodePointer L, nodepointer m) { nodepointer B; if (L == m) 見小試身手 4-3 return ERROR; B = PreNode(L,m); if (B == NULL) return false; B->link = m->link; free(m); return true; } 小試身手 4-3

45 鏈結串列 4-45 上述的 DeleteNode 函式無法處理刪除第一個節點的情況請修改 DeleteNode 函式, 使得該函式也能處理刪除第一個節點的情況連結兩個串列假設我們想要連結兩個串列 L1 與 L2, 並且連結後以 L1 串列來表示串列頭, 則只需要花費 L1 串列節點數的時間, 請見下列範例 4-2 設計一個函式, 將兩個單向鏈結串列 L1,L2 連接在一起 nodepointer Concatenate(nodePointer L1,nodePointer L2) { nodepointer w = L1; if(w!= NULL) /* L1 不為空串列 */ { while(w->link!= NULL) w = w->link; w->link = L2; 將 w 移動到 L1 的最後一個節點將 L1 的最後一個節點之鏈結 L2 程式 4.2

46 鏈結串列 4-46 } } else /* L1 為空串列 */ L1=L2; return L1; 圖 4-16 連接兩個鏈結串列

47 鏈結串列單向環狀鏈結串列的運算單向環狀鏈結串列只不過是將單向鏈結串列尾節點的鏈結指回串列的第一個節點如此一來, 不論由哪一個節點開始出發, 都可以拜訪所有的節點這樣的一個小改變, 有時候仍可直接套用上一節所介紹的單向鏈結串列運算 ; 但某些運算則需要進行小部分的修改例如 PreNode 函式, 因為末節點的 link 會指向第一個節點, 而非 NULL 以下, 我們僅示範如何修改演算法來完成單向環狀鏈結串列的走訪 4-3 參考圖 4-17 的單向環狀鏈結串列, 寫一個函式, 循序印出串列所有節點的資料

48 鏈結串列 4-48 圖 4-17 ( 單向 ) 環狀鏈結串列 void CLinkListTraverse(nodePointer L) { nodepointer w=l; if(w!=null) /* 鏈結串列不為空串列 */ do { printf("%d \t",w->data); w = w->link; }while(w!=l); } 程式 4.3 由於單向環狀鏈結串列沒有任何一個節點的鏈結會指向 NULL, 因此, 當 w 為 NULL 時, 代表這是一個空串列

49 鏈結串列 4-49 範例 4-2 的單向鏈結串列在走訪時不必判斷是否為空串列皆可適用, 但此處則必須判斷若將範例 4-2 的 while 迴圈條件直接修改為 (w->link!=l) 並不能直接作為本範例的解答, 因為這不會印出最後一個節點的資料那如果把 while 迴圈條件直接修改為 (w!=l), 是否可以作為本範例的解答呢? 答案還是不行, 因為它根本不會進入迴圈內所以我們使用 do-while 來改寫, 由於 do-while 迴圈包含在 if 條件式內, 所以單向環狀鏈結串列至少有一個節點時, 才會進入 do-while 迴圈, 不必擔心出現空串列的情況呼叫上述函式時, 只需要採用 CLinkListTraverse(first); 將串列頭傳入函式中即可如果想要對節點進行計數的話, 則只需要進行小幅度的修改, 這個部份留給讀者練習小試身手 4-4

50 鏈結串列 4-50 修改範例 4-4, 實作一個節點計數函式 int CLinkListCounter(nodePointer L), 可在函式中增加一個 counter 變數, 使得在呼叫 CLinkListCounter(first) 之後, 能夠取得單向環狀鏈結串列的節點數量, 其中 first 是串列頭小試身手節的 insertafter() 函式在取得新節點 n 時, 就先設定了 n->data = d; n->link = NULL;, 請問要如何修改才能將之適用於單向環狀鏈結串列, 使之可做為在單向環狀鏈結串列中插入 n 節點在指定的 m 節點之後的演算法小試身手 4-6 請修改節的 DeleteNode() 函式, 使之可以適用於單向環狀鏈結串列的刪除某節點之用, 且若欲刪除的節點為整個串列的唯一節點時, 將串列頭設定為 NULL, 也就是刪除唯一的節點後, 串列為空串列

51 鏈結串列 4-51

52 鏈結串列雙向鏈結串列的運算在節的最後, 曾經介紹並宣告雙向鏈結串列的節點結構 DNode( 結構別名為 Dnode, 結構指標別名則命名為 DnodePointer) 它包含了一個資料欄位 data, 兩個鏈結欄位 llink 與 rlink, 分別指向前一個節點與後一個節點至於第一個節點的 llink 與最後一個節點的 rlink 則指向 NULL 示意圖如下: 圖 4-18 雙向鏈結串列

53 鏈結串列 4-53 配置節點取得一個雙向鏈結串列新節點的工作交由 DLGetNode() 函式來完成 DLGetNode() 和 GetNode() 的區別只在於宣告 NewNode 時, 要以 DnodePointer 型態來宣告 ; 而 sizeof 記憶體大小的需求則使用結構別名 Dnode 即可該函式的回傳值型態是 DnodePointer, 代表回傳一個指標指向新配置的節點函式如下 DnodePointer DLGetNode() { DnodePointer NewNode; 記憶體大小是雙向鏈結串列節點的大小程式 4.b NewNode=(DnodePointer) malloc(sizeof(dnode)); 記得轉型為指標 if(newnode==null) /* 已無記憶體可配置,malloc 會回傳 NULL 給 NewNode */ printf(" 記憶體不足!"); return NewNode; } 回傳指向新節點的指標

54 鏈結串列 4-54 釋放節點釋放節點也使用 free(ptr) 來完成, 只不過 ptr 的資料型態不同而已插入新節點在指定節點之後想在雙向鏈結串列中, 將新節點插入在指定的 m 節點之後, 可以如下設計演算法它與單向鏈結串列演算法最大的不同之處在於, 需要修改左鏈結欄位 llink

55 鏈結串列 4-55 虛擬碼 C 函式程式 4.b 功能 : 在 L 串列中的 m 節點之後插入新節點 ( 新節點資料內容為 d) Function DLinsertAfter (L,m,d) 要求系統配置一個新節點 ; 宣告一個指標 n 指向新取得的節點 If (n = NULL) then [return false] n->data d n->llink NULL; n->rlink NULL If (m NULL) then [ n->llink m; n->rlink m->rlink If (m->rlink NULL) then m->rlink->llink n; m->rlink n ] Else /* 串列原為空串列 */ [ L n ] return true endfunction int DLinsertAfter(DnodePointer L, DnodePointer m, int d) { DnodePointer n = DLGetNode(); if(n == NULL) return false; n->data = d; n->llink = NULL; n->rlink = NULL; if(m!= NULL) { n->llink = m; n->rlink = m->rlink; if(m->rlink!= NULL) m->rlink->llink = n; m->rlink = n; } 若有下一節 else 點, 則該節點 L = n; 的左鏈結應 return true; 該指向 n }

56 動畫頁 ( 書附光碟也有 ) 鏈結串列 4-56 演算法對應的示意圖變化如圖 4-19 後續接動畫頁

57 鏈結串列 4-57 如果 m 並非最後一個節點, 則應該修改的鏈結共有 4 個 m 的 rlink( 令之指向 n) n 的 llink( 令之指向 m) n 的 rlink( 令之指向下一節點 ) 下一節點的 llink( 令之指向 n) 如果 m 為最後一個節點, 則只有三個鏈結需要改變也就是沒有 llink 需要指向 n( 沒有 ) 並且 n 的 rlink 應該改為指向 NULL, 由於 m 的 rlink 在這種狀況下, 原本也是指向 NULL, 因此可以統一由 n->rlink = m->rlink; 來完成經由在演算法當中多加入了一個 if 判斷句, 用來判斷 m 是否為雙向鏈結串列的最後一個節點 (m->rlink 是否指向 NULL) 因此, 上述演算法可以適用於所有的狀況移動工作節點

58 鏈結串列 4-58 雙向鏈結串列在移動工作節點時, 可以分為向前移動與向後移動兩種, 分別是循著 llink 與 rlink 進行移動向後移動工作節點假設目前工作指標為 w, 則執行下列程式碼, 就可以將之指向下一個節點 w = w->rlink; 圖 4-20 雙向鏈結串列向後移動工作節點 w

59 鏈結串列 4-59 向前移動工作節點假設目前工作指標為 w, 則執行下列程式碼, 就可以將之指向前一個節點, 運算速度比單向鏈結串列快很多 w = w->llink; 圖 4-21 雙向鏈結串列向前移動工作節點 w

60 鏈結串列刪除指定節點要刪除 m 節點, 那麼就必須先知道 m 的前一個與後一個節點是哪一個節點因為刪除 m 後, 前一個節點的 rlink 應該指向後一個節點, 且後一個節點的 llink 應該指向前一個節點在雙向鏈結串列中尋找 m 的前一個與後一個節點都只需要透過鏈結欄位即可完成, 並不需要透過迴圈來尋找因此可將刪除節點的演算法設計如下 :

61 鏈結串列 4-61 虛擬碼 C 函式後續接動畫頁程式 4.b 功能 : 雙向鏈結串列刪除 m 節點 Function DLDeleteNode(L,m) If ((m->llink = NULL) AND (m->rlink = NULL)) then [ L = NULL Free(m) return true ] If ((m->llink = NULL) OR (m->rlink = NULL)) then [ return ERROR ] If ((m->llink NULL) AND (m->rlink NULL)) then [ m->llink->rlink = m->rlink; m->rlink->llink = m->llink ] Free(m) return true endfunction int DLDeleteNode(DnodePointer L, DnodePointer m) { if((m->llink == NULL) && (m->rlink == NULL)) { m 是唯一的節點 L = NULL; free(m); return true; } if((m->llink == NULL) (m->rlink == NULL)) return ERROR 見小試身手 4-7 if((m->llink!= NULL) && (m->rlink!= NULL)) { m->llink->rlink = m->rlink; m->rlink->llink = m->llink; } free(m); return true; }

62 動畫頁 ( 書附光碟也有 ) 鏈結串列 4-62 當 m 的 llink 與 rlink 皆指向 NULL 時, 代表 m 是 L 串列的唯一節點, 此時只需要釋放 m 並將 L 指向 NULL 即可當欲刪除的節點 m 既非 L 串列的第一個節點, 也非最後一個節點時,m 的 llink 與 rlink 都不會指向 NULL, 此時上述函式的執行過程如圖

63 鏈結串列 4-63 小試身手 4-7 請修改 DLDeleteNode 函式, 使得該函式能夠處理刪除第一個節點與刪除最後一個節點的情況

64 鏈結串列雙向環狀鏈結串列的運算雙向環狀鏈結串列是將末尾節點的 rlink 指向第一個節點, 第一個節點的 llink 指向末尾節點, 如圖 4-23 這樣的一個小改變, 有時候可以簡化上一節所介紹的雙向鏈結串列運算舉例來說, 在節介紹的 DLDeleteNode 函式可以直接套用在雙向環狀鏈結串列的刪除節點應用上, 並不需要判斷欲刪除的節點是否為第一個節點或最後一個節點 ( 但仍要判斷是否為唯一的節點 ) 圖 4-23 雙向環狀鏈結串列

65 鏈結串列 4-65 包含標頭節點 (Head Node) 的雙向環狀鏈結串列 DLDeleteNode 函式可以直接套用在雙向環狀鏈結串列的刪除節點應用上, 但它仍包含了第一個 if 判斷式, 用來決定欲刪除的節點是否為唯一的節點如果是唯一的節點, 則刪除節點後, 串列 L 將直接指向 NULL 在實際應用時可以為雙向環狀鏈結串列增加一個標頭節點 (Head Node) 來避免這種狀況發生加上標頭節點的雙向環狀鏈結串列如圖 4-24 圖 4-24 包含標頭節點的雙向環狀鏈結串列

66 鏈結串列 4-66 每當產生新的空串列時, 就直接先配置一個沒有資料的標頭節點, 初始時, 標頭節點的 llink 與 rlink 都將指向自己請注意, 標頭節點是不允許被刪除的, 因此, 刪除節點的運算將改寫為如下的演算法程式 4.bch 虛擬碼 C 函式功能 : 含標頭節點的雙向環狀鏈結串列刪除 m 節點 Function HCDLDeleteNode(L,m) If (m = L) then [ return false ] EndIf m->llink->rlink = m->rlink; m->rlink->llink = m->llink Free(m) return true endfunction int HCDLDeleteNode(DnodePointer L, DnodePointer m) { m if(l == m) 是標頭節點, return false; 不可刪除 m->llink->rlink = m->rlink; m->rlink->llink = m->llink; free(m); return true; }

67 鏈結串列本章重點鏈結串列是一種非循序映射相對於陣列資料結構的循序映射, 鏈結串列在插入與刪除元素時, 可以獲得更佳的時間複雜度雖然鏈結串列可以利用陣列來實作, 但在 C 語言中, 我們並不會這樣做在 C 語言中, 實作鏈結串列使用的是結構指標所構成的鏈結自我參考機制與動態記憶體配置等技巧這樣子做的好處在於可充分利用記憶體空間, 並且在插入與刪除元素時提供較佳的時間複雜度為了考量到各位對於 C 語言的背景知識可能不足, 在本章中, 我們延續了上一章介紹的動態記憶體配置指標運算等 C 語言知識, 並加入了自我參考機制型態別名等技巧的說明讀者務必熟悉這些 C 語言技巧, 才能將鏈結串列應用在各種場合之中, 使資料結構不再只是一個學科上的理論, 而能夠進行實際的運用

68 鏈結串列 4-68 鏈結串列常見的有單向鏈結雙向鏈結環狀鏈結串列等等, 而其中最主要的構成因子為鏈結欄位 (link field) 除了常見的單向雙向環狀鏈結串列之外, 許多其他種類的鏈結串列也常被應用來解決程式上的許多問題例如之後要介紹的樹狀結構就常使用鏈結串列來儲存光就單向鏈結與雙向鏈結來討論複雜度的話, 則是時間與空間的取捨由於雙向鏈結多使用了一個鏈結欄位, 因此需要比較多的記憶體空間, 但也因為雙向鏈結多了一個有用的鏈結欄位, 因此也使得某些運算 ( 例如刪除節點運算 ) 的時間複雜度得以降低所以要採用哪一種鏈結串列, 應該視應用場合來決定

69 本章習題鏈結串列 4-69

PowerPoint Presentation

PowerPoint Presentation 陣列與鏈結串列 NTU CSIE Outline 結構陣列鏈結串列單向鏈結串列之資料型態單向鏈結串列之基本運算作業結構陣列優點缺點使用容易刪除與插入造成資料移動頻繁浪費不必要之記憶體陣列長度為常數, 可能會不夠用 #include struct _student int math; int english; int computer; ; typedef struct