第 4 章鏈結串列 本章學習目標. 理解一個基本的資料結構 - 鏈結串列資料結構 如何透過結構 指標 自我參考機制實現鏈結串列資料結構 C 語言的別名機制 鏈結串列在插入與刪除非末端元素時, 有極佳的時間複雜度
鏈結串列 4-2 4.1 有序串列 (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) 太陽系八大行星 : ( 水星, 金星, 地球, 火星, 木星, 土星, 天王星, 海王星 ) 阿花之總統任期年份 : ()
鏈結串列 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 刪除後, 串列形成 (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 種運算 ( 插入與刪除運算 ) 則較為費時 因為必須對其後的資料項進行搬移, 使得連續的項目仍然保持位於陣列的連續位置之特性 為了改善插入或刪除運算的時間複雜度, 我們將採用另一種非循序映射的方法 在資料結構領域中, 我們稱之為鏈結串列
鏈結串列 4-5 4.2 鏈結串列 (Linked List) 鏈結串列是一種常見的資料結構, 它由節點 (node) 組成, 節點又稱為串列節點 (list node), 每一個節點至少包含一個資料欄位 (data field) 與鏈結欄位 (link field) 節點的資料欄位可用來存放資料 鏈結欄位則是用來使得節點與節點間產生鏈結關係, 以便構成串列 節點的示意如圖 4-1 為了使用鏈結串列, 因此我們可以給每一個鏈結串列一個名稱, 該名稱可以視為一個鏈結並指向第一個節點, 故又稱之為串列頭 圖 4-1 鏈結串列的節點
鏈結串列 4-6 鏈結串列依據整體結構常見的有 (1) 單向鏈結串列 (2) 環狀鏈結串列 (3) 雙向鏈結串列 (4) 雙向環狀鏈結串列 (5) 其他為了特殊應用所設計的鏈結串列 如表示樹狀結構時採用的鏈結串列, 於樹一章中另行說明
鏈結串列 4-7 假設要以鏈結串列存放樂透開獎的六個球號, 其開獎順序為 (26,18,15,29,32, 12) 則上述四種常見的鏈結串列示意圖如下 1. 單向鏈結串列 (Singly Linked List): 每一個節點的鏈結欄位 (link) 將指向下一個節點, 而最後一個節點的鏈結欄位將指向 NULL 如圖 4-2 與 4-3 都是單向鏈結串列的示意圖 圖 4-2 單向鏈結串列 ( 圖示一 ) 圖 4-3 單向鏈結串列 ( 圖示二 )
鏈結串列 4-8 2. 環狀鏈結串列 (Circular Linked List): 將單向鏈結串列最後一個節點的鏈結欄位指向第一個節點, 稱之為環狀鏈結串列 如圖 4-4 是環狀鏈結串列的示意圖 圖 4-4 ( 單向 ) 環狀鏈結串列
鏈結串列 4-9 3. 雙向鏈結串列 (Doubly Linked List): 每一個節點都有兩個鏈結欄位, 稱為左鏈結欄位 (llink) 及右鏈結欄位 (rlink), 分別指向前一個節點及下一個節點, 而第一個節點的左鏈結欄位及最後一個節點的右鏈結欄位將指向 NULL 如圖 4-5 是雙向鏈結串列的示意圖 圖 4-5 雙向鏈結串列
鏈結串列 4-10 4. 雙向環狀鏈結串列 (Circular Doubly Linked List): 將雙向鏈結串列第一個節點的左鏈結欄位指向最後一個節點, 並將最後一個節點的右鏈結欄位將指向第一個節點, 稱之為雙向環狀鏈結串列 如圖 4-6 是雙向環狀鏈結串列的示意圖 圖 4-6 雙向環狀鏈結串列
鏈結串列 4-11 4.3 以陣列實作鏈結串列 鏈結串列是抽象的概念, 並未規範在程式語言中如何實作鏈結串列資料結構 假設程式語言提供了類似指標的功能, 一般我們會運用指標來實作鏈結欄位 如果程式語言未提供類似指標的功能, 仍舊可以運用陣列來實作鏈結串列, 但一般很少會這樣子做 假設我們使用二維陣列來存放鏈結串列, 則每一個節點必須使用一列來存放 陣列存放相同資料型態的資料, 資料欄位與鏈結欄位的資料型態也必須相同 假設資料欄位宣告為整數資料型態, 此時, 我們可以把鏈結欄位的內容設定為下一個節點的 列索引值, 因為索引值是一個整數值 為了記錄串列頭, 我們可以新增一個串列頭節點, 其資料內容為空, 而鏈結欄位存放的是第一個節點的列索引 後續接動畫頁
動畫頁 ( 書附光碟也有 ) 鏈結串列 4-12
動畫頁 ( 書附光碟也有 ) 鏈結串列 4-13
鏈結串列 4-14 由於我們使用 C 語言來實作資料結構, 因此鮮少使用陣列來存放鏈結串列, 通常 是採用結構 (struct) 搭配指標來實作鏈結串列 故而此處我們並不提供刪除節點的演算法 小試身手 4-1 採參考圖 4-7, 設計一個時間複雜度為 O(1) 的刪除演算法 請使用陣列來實作環狀 ( 單向 ) 鏈結串列, 並畫出其示意圖
鏈結串列 4-15 4.4 以結構搭配指標實作鏈結串列 如果節點的資料項目不是整數, 而是字串或字元, 那麼單純使用整數二維陣列就無法製作鏈結串列了, 因為陣列的每個元素都必須是相同的資料型態 不過如果使用結構 (struct) 搭配一維陣列就可以解決這樣的問題 我們可以如下宣告節點的 listnode 結構, 然後再宣告 List[] 結構陣列即可 struct listnode 不實用 { char data; /* 資料欄位, 內容為字元 */ int link; /* 鏈結欄位, 指出下一個位節點位於陣列的何處 */ }; struct listnode List[10]; 陣列元素的資料型態是 listnode 結構 上述的 List[] 陣列是一個靜態陣列, 在實際應用時, 通常我們不能確定鏈結串列共包含幾個節點, 因此看似動態陣列更為適當, 但在可使用動態記憶體配置的前提之下, 其實我們還有更好的方法 也就是以動態記憶體配置產生節點, 並在節點之間透過 link 產生鏈結關係, 並不需要採用動態陣列來實作鏈結串列
鏈結串列 4-16 由於透過動態記憶體配置節點 ( 例如透過 malloc 函式 ), 系統會回傳所配置節點的記憶體位址, 所以呼叫時, 必須設定一個指標來接收該節點的記憶體位址 這部分的程式碼對於部分不熟悉 C 語言者, 有些困難, 所以, 我們在本節中先 複習 指標與指標資料型態 然後逐步漸進地, 完成節點的宣告方式以及完成鏈結串列的建立 4.4.1 指標與指標資料型態 在 C 語言中, 我們可以宣告一個變數, 該變數內容是一個記憶體位址, 這樣的變數稱之為指標變數 宣告指標變數需要搭配指標運算子 * 來完成 想要存取指標變數所指向記憶體的內容時, 也必須搭配 * 來完成 除了必須使用 * 來宣告指標變數之外, 也必須同時宣告該指標將來指向之記憶體內容是哪一種資料型態 至於要取得某變數的記憶體位址並設定給指標變數, 則必須透過取址運算子 & 來完成 範例如下: 後續接動畫頁
動畫頁 ( 書附光碟也有 ) 鏈結串列 4-17
動畫頁 ( 書附光碟也有 ) 鏈結串列 4-18
鏈結串列 4-19 4.4.2 在結構體中包含指標項目 想要製作節點的資料結構, 應該使用結構 (struct) 來組織資料項目與鏈結項目, 而鏈結項目應該是一個指標變數 先由簡單的範例觀察, 當指標成為結構的其中一個項目時, 會發生什麼樣的事情? 假設我們有一個結構 s, 其項目如下, 當中包含了一個整數 i 與一個指向整數資料型態的指標 p struct s { int i; int *p; 指標變數 p 是 s 結構的一個項目 }; 此時如果要宣告結構變數 s1, 並設定其項目時, 可以使用下列敘述 : int num=100; struct s s1; 後續接動畫頁
動畫頁 ( 書附光碟也有 ) 鏈結串列 4-20
動畫頁 ( 書附光碟也有 ) 鏈結串列 4-21
鏈結串列 4-22 4.4.3 自我參考機制 自我參考機制是在 C 程式設計中完成鏈結串列資料結構的重要機制 假設各位已經對於結構內包含指標項目不會產生困惑, 那麼, 接下來只要做一點點的改變, 就能完成自我參考機制 所謂 C 語言的自我參考機制 (self-reference) 代表的是 一個結構中的某些項目被宣告為指標, 且該 指標所指向之資料型態 與 指標所屬結構 為同一結構 代表該指標必須指向與結構相同資料型態的資料 假設我們將之前介紹的 s 結構稍為修改一下, 成為 sr 結構如下 當中的 p 指標, 宣告為指向 sr 結構體型態的變數, 就是自我參考機制的實例 如下宣告 後續接動畫頁 struct sr { int i; 指標 p 指向 sr 結構, 完成自我參考機制 struct sr *p; };
動畫頁 ( 書附光碟也有 ) 鏈結串列 4-23
動畫頁 ( 書附光碟也有 ) 鏈結串列 4-24
鏈結串列 4-25 4.4.4 串列頭的宣告 在實際應用上, 一般會使用一個指標來代表鏈結串列, 稱之為 串列頭 或 串列頭指標, 串列頭會指向頭節點 以宣告串列頭指標時, 應該將其所指向的資料型態宣告為節點結構, 如下範例 struct sr *first; first=&sr1; 將串列頭指向頭節點 sr1 兩個敘述可合併為 struct sr *first=&sr1; 上面的敘述會將 sp 指向之前宣告的結構變數 sr1, 敘述執行完畢後, 記憶體內容 如圖 4-12 所示 並且可透過 -> 運算子存取所指向結構內的項目例如 :first->i 就是 10 圖 4-12 含串列頭的單向鏈結串列
鏈結串列 4-26 4.4.5 別名的應用 宣告結構變數或結構指標變數時, 需要使用 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; 使用別名宣告 變數
鏈結串列 4-27 1. 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;
鏈結串列 4-28 有了上述的推演過程, 相信您可以理解 typedef node *nodepointer; 的語 法, 亦即您只要將 node * 與 nodepointer 分開來看即可 nodepointer 指標型態別名將可直接用來宣告指向 node 型態的指標變數
鏈結串列 4-29 3. 經過定義別名後 我們可以使用 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
鏈結串列 4-30 4.4.6 動態記憶體配置與鏈結串列 雖然我們可以透過宣告變數的方式建立節點, 並透過指標變數代表節點, 但鏈結串列與陣列最大的不同在於, 鏈結串列可以充分而有效的利用可用記憶體空間 我們不該限制使用者在程式執行過程中使用的節點數量 ( 除非記憶體可用空間不足 ), 並且也不該配置過多不會用到的記憶體 只有在需要產生節點時才產生一個節點, 而不是在程式中直接透過宣告變數的方式取得節點 必須藉由 C 語言的動態記憶體配置函式 malloc() 來產生新節點 計算參數 size 的大小時, 會配合 sizeof() 函式來求出記憶體大小 而我們想要的節點已經宣告為 node 結構, 因此可以將引數設定為 sizeof(node) 在呼叫 malloc() 之後, 必須接收 malloc() 回傳的指標, 並且需要將之轉型為指向節點的指標型態例如 (struct node *) 此時也可以用別名來取代, 也就是之前介紹的 nodepointer 別名
鏈結串列 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 利用動態配置記憶體取得新節點
鏈結串列 4-32 請注意, 如果系統已無記憶體可配置了, 則 malloc() 會回傳 NULL, 因此呼叫 GetNode() 的敘述, 可以依照回傳值是否為 NULL 來判別配置是否成功 釋放節點 當節點從鏈結串列中移除後, 應把節點佔用的記憶體空間歸還給系統, 以便有效利用記憶體 此時可透過 C 語言的記憶體釋放函式 free() 來完成 free() 要求呼叫敘述傳入要被釋放的記憶體位址, 如下敘述 free(ptr); 執行後會釋放 ptr 所指節點所佔用的記憶體 老師的叮嚀 如果本節之前的所有程式碼都已經看懂了, 那麼恭喜您, 不但能夠 看懂後面的程式碼, 而且對於 C 程式設計的功力也提升了一個層次
鏈結串列 4-33
鏈結串列 4-34 4.5 單向鏈結串列的運算 鏈結串列的常見運算有很多 由於鏈結串列分為許多種類, 因此運算的演算法內容也會有些不同 本小節將針對單向鏈結串列的運算進行說明 至於雙向鏈結串列的運算, 則留待之後的小節說明 鏈結串列的各種運算又分為不同狀況時適用 例如, 插入節點運算又分為插入節點在某節點之後以及某節點之前 這兩種狀況都必須要指定某節點是哪一個節點 如果是要插入在鏈結串列的末端 ( 又稱為新增節點 ), 則不需要指定串列的目標節點 但必須同時考量到串列目前是空串列還是非空串列
鏈結串列 4-35 由於狀況有非常多種, 因此我們將在本小節中挑選重要的運算來做說明, 其餘則留給讀者做練習 為了考量各位尚未熟悉上一節 C 語言關於鏈結串列的實作語法 在提供運算的演算法時, 將同時提供虛擬碼與 C 函式兩種格式以及對應的圖形變化 ( 搭配動態投影片 ) 各位可以藉由虛擬碼 圖形變化與動態投影片來理解運算的過程, 然後再對應到 C 函式, 如此更容易理解 C 函式各敘述的意義 4.5.1 插入新節點在指定節點之後 插入新節點會面臨的第一個問題, 是要將新節點插入到鏈結串列的哪一個位置 例如插入在哪一個節點之後, 或哪一個節點之前, 兩者的演算法類似但不同 此處, 我們僅討論將新節點插入在指定的 m 節點之後的演算法 指定的 m 節點的意義是, 該節點被一個指標 m 所指向
鏈結串列 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
鏈結串列 4-37 return true endfunction 動畫頁 ( 書附光碟也有 ) } 後續接動畫頁
鏈結串列 4-38 4.5.2 移動工作節點 想要瀏覽鏈結串列中所有的資料, 就必須循序拜訪整個串列, 這個時候可利用一個工作指標指向某一個節點, 而這個指標所指向的節點稱之為工作節點 換言之, 工作節點 ( 工作指標所指向的目標 ) 必須可以移動 ( 更明確地說, 是工作指標必須可以移動 ), 如此才能拜訪整個串列的所有節點 4-1 參考圖 4-2 的單向鏈結串列, 寫一個函式, 循序印出串 列所有節點的資料 void LinkListTraverse(nodePointer L) { nodepointer w=l; 將工作指標 w 指向第一個節點 while(w!= NULL) 程式 4.1
鏈結串列 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) 後續接動畫頁
鏈結串列 4-40 動畫頁 ( 書附光碟沒有 ) 圖 4-15(b) 執行 w=w->link 後,w 指向第二個節點
鏈結串列 4-41 尋找節點與指定節點 有些時候, 我們必須指定某一個節點, 例如, 在上一小節的 插入新節點 n 在指定的節點 m 之後, 我們必須指定 m 節點是哪一個節點 為了達到這個目的, 我們可以將 m 指標一開始指向串列首節點, 然後循序往後移動到符合條件的節點為止 一般會以該節點的資料內容 data 做為比對條件 並以該節點的 link 欄位是否為 null 來判斷該節點是否為最後一個節點 往下一節點移動的指令為 m= m->link
鏈結串列 4-42 如果想要將新節點插入在 k 節點之前 ( 而非之後 ), 又想要套用之前所設計的 insertafter 函式, 則呼叫 insertafter 時, 傳入的節點應該是 k 節點的前一個節點 此時同樣可以利用比對節點的 link 欄位是否指向 k 節點來確認節點是否為 k 的前一個節點 我們將於下一小節中, 利用相同的技巧, 來尋找前一個節點, 並設計刪除節點函式 小試身手 4-2 請開啟光碟的程式碼, 在光碟程式 4.1 中, 我們提供了一個 CreateAll() 函式, 可用來從無到有, 循序建立圖 4-15 的整個串列 ( 資料原本先存放在陣列中 ), 請先看懂該函式, 或由您自行重新設計 CreateAll(), 然後分析 CreateAll() 的時間複雜度為何?
鏈結串列 4-43 4.5.3 刪除指定節點 假設我們要刪除 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 的前一個節點
鏈結串列 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
鏈結串列 4-45 上述的 DeleteNode 函式無法處理刪除第一個節點的情況 請修改 DeleteNode 函式, 使得該函式也能處理刪除第一個節點的情況 4.5.4 連結兩個串列 假設我們想要連結兩個串列 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
鏈結串列 4-46 } } else /* L1 為空串列 */ L1=L2; return L1; 圖 4-16 連接兩個鏈結串列
鏈結串列 4-47 4.6 單向環狀鏈結串列的運算 單向 環狀 鏈結串列只不過是將單向鏈結串列尾節點的鏈結指回串列的第一個節點 如此一來, 不論由哪一個節點開始出發, 都可以拜訪所有的節點 這樣的一個小改變, 有時候仍可直接套用上一節所介紹的單向鏈結串列運算 ; 但某些運算則需要進行小部分的修改 例如 PreNode 函式, 因為末節點的 link 會指向第一個節點, 而非 NULL 以下, 我們僅示範如何修改演算法來完成單向環狀鏈結串列的走訪 4-3 參考圖 4-17 的單向環狀鏈結串列, 寫一個函式, 循序 印出串列所有節點的資料
鏈結串列 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 時, 代表這是一個空串列
鏈結串列 4-49 範例 4-2 的單向鏈結串列在走訪時不必判斷是否為空串列皆可適用, 但此處則必須判斷 若將範例 4-2 的 while 迴圈條件直接修改為 (w->link!=l) 並不能直接作為本範例的解答, 因為這不會印出最後一個節點的資料 那如果把 while 迴圈條件直接修改為 (w!=l), 是否可以作為本範例的解答呢? 答案還是不行, 因為它根本不會進入迴圈內 所以我們使用 do-while 來改寫, 由於 do-while 迴圈包含在 if 條件式內, 所以單向環狀鏈結串列至少有一個節點時, 才會進入 do-while 迴圈, 不必擔心出現空串列的情況 呼叫上述函式時, 只需要採用 CLinkListTraverse(first); 將串列頭傳入函式中即可 如果想要對節點進行計數的話, 則只需要進行小幅度的修改, 這個部份留給讀者練習 小試身手 4-4
鏈結串列 4-50 修改範例 4-4, 實作一個節點計數函式 int CLinkListCounter(nodePointer L), 可在函式中增加一個 counter 變數, 使得在呼叫 CLinkListCounter(first) 之 後, 能夠取得單向環狀鏈結串列的節點數量, 其中 first 是串列頭 小試身手 4-5 4.5.1 節的 insertafter() 函式在取得新節點 n 時, 就先設定了 n->data = d; n->link = NULL;, 請問要如何修改才能將之適用於單向環狀鏈結串列, 使之可做為在單向環狀鏈結串列中插入 n 節點在指定的 m 節點之後的演算法 小試身手 4-6 請修改 4.5.3 節的 DeleteNode() 函式, 使之可以適用於單向環狀鏈結串列的刪除某節點之用, 且若欲刪除的節點為整個串列的唯一節點時, 將串列頭設定為 NULL, 也就是刪除唯一的節點後, 串列為空串列
鏈結串列 4-51
鏈結串列 4-52 4.7 雙向鏈結串列的運算 在 4.4.5 節的最後, 曾經介紹並宣告雙向鏈結串列的節點結構 DNode( 結構別名為 Dnode, 結構指標別名則命名為 DnodePointer) 它包含了一個資料欄位 data, 兩個鏈結欄位 llink 與 rlink, 分別指向前一個節點與後一個節點 至於第一個節點的 llink 與最後一個節點的 rlink 則指向 NULL 示意圖如下: 圖 4-18 雙向鏈結串列
鏈結串列 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; } 回傳指向新節點的指標
鏈結串列 4-54 釋放節點 釋放節點也使用 free(ptr) 來完成, 只不過 ptr 的資料型態不同而已 4.7.1 插入新節點在指定節點之後 想在雙向鏈結串列中, 將新節點插入在指定的 m 節點之後, 可以如下設計演算法 它與單向鏈結串列演算法最大的不同之處在於, 需要修改左鏈結欄位 llink
鏈結串列 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 }
動畫頁 ( 書附光碟也有 ) 鏈結串列 4-56 演算法對應的示意圖變化如圖 4-19 後續接動畫頁
鏈結串列 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) 因此, 上述演算法可以適用於所有的狀況 4.7.2 移動工作節點
鏈結串列 4-58 雙向鏈結串列在移動工作節點時, 可以分為向前移動與向後移動兩種, 分別是循 著 llink 與 rlink 進行移動 向後移動工作節點 假設目前工作指標為 w, 則執行下列程式碼, 就可以將之指向下一個節點 w = w->rlink; 圖 4-20 雙向鏈結串列向後移動工作節點 w
鏈結串列 4-59 向前移動工作節點 假設目前工作指標為 w, 則執行下列程式碼, 就可以將之指向前一個節點, 運算速度比單向鏈結串列快很多 w = w->llink; 圖 4-21 雙向鏈結串列向前移動工作節點 w
鏈結串列 4-60 4.7.3 刪除指定節點 要刪除 m 節點, 那麼就必須先知道 m 的前一個與後一個節點是哪一個節點 因為刪除 m 後, 前一個節點的 rlink 應該指向後一個節點, 且後一個節點的 llink 應該指向前一個節點 在雙向鏈結串列中尋找 m 的前一個與後一個節點都只需要透過鏈結欄位即可完成, 並不需要透過迴圈來尋找 因此可將刪除節點的演算法設計如下 :
鏈結串列 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; }
動畫頁 ( 書附光碟也有 ) 鏈結串列 4-62 當 m 的 llink 與 rlink 皆指向 NULL 時, 代表 m 是 L 串列的唯一節點, 此時只需要釋放 m 並將 L 指向 NULL 即可 當欲刪除的節點 m 既非 L 串列的第一個節點, 也非最後一個節點時,m 的 llink 與 rlink 都不會指向 NULL, 此時上述函式的執行過程如圖
鏈結串列 4-63 小試身手 4-7 請修改 DLDeleteNode 函式, 使得該函式能夠處理刪除第一個節點與刪 除最後一個節點的情況
鏈結串列 4-64 4.8 雙向環狀鏈結串列的運算 雙向環狀鏈結串列是將末尾節點的 rlink 指向第一個節點, 第一個節點的 llink 指向末尾節點, 如圖 4-23 這樣的一個小改變, 有時候可以簡化上一節所介紹的雙向鏈結串列運算 舉例來說, 在 4.7.3 節介紹的 DLDeleteNode 函式可以直接套用在雙向環狀鏈結串列的刪除節點應用上, 並不需要判斷欲刪除的節點是否為第一個節點或最後一個節點 ( 但仍要判斷是否為唯一的節點 ) 圖 4-23 雙向環狀鏈結串列
鏈結串列 4-65 包含標頭節點 (Head Node) 的雙向環狀鏈結串列 DLDeleteNode 函式可以直接套用在雙向環狀鏈結串列的刪除節點應用上, 但它仍包含了第一個 if 判斷式, 用來決定欲刪除的節點是否為唯一的節點 如果是唯一的節點, 則刪除節點後, 串列 L 將直接指向 NULL 在實際應用時可以為雙向環狀鏈結串列增加一個標頭節點 (Head Node) 來避免這種狀況發生 加上標頭節點的雙向環狀鏈結串列如圖 4-24 圖 4-24 包含標頭節點的雙向環狀鏈結串列
鏈結串列 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; }
鏈結串列 4-67 4.9 本章重點 鏈結串列 是一種非循序映射 相對於陣列資料結構的循序映射, 鏈結串列 在插入與刪除元素時, 可以獲得更佳的時間複雜度 雖然 鏈結串列 可以利用陣列來實作, 但在 C 語言中, 我們並不會這樣做 在 C 語言中, 實作 鏈結串列 使用的是結構 指標所構成的鏈結 自我參考機制與動態記憶體配置等技巧 這樣子做的好處在於可充分利用記憶體空間, 並且在插入與刪除元素時提供較佳的時間複雜度 為了考量到各位對於 C 語言的背景知識可能不足, 在本章中, 我們延續了上一章介紹的動態記憶體配置 指標運算等 C 語言知識, 並加入了自我參考機制 型態別名等技巧的說明 讀者務必熟悉這些 C 語言技巧, 才能將 鏈結串列 應用在各種場合之中, 使資料結構不再只是一個學科上的理論, 而能夠進行實際的運用
鏈結串列 4-68 鏈結串列常見的有 單向鏈結 雙向鏈結 環狀鏈結 串列等等, 而其中最主要的構成因子為鏈結欄位 (link field) 除了常見的單向 雙向 環狀鏈結串列之外, 許多其他種類的鏈結串列也常被應用來解決程式上的許多問題 例如之後要介紹的樹狀結構就常使用鏈結串列來儲存 光就單向鏈結與雙向鏈結來討論複雜度的話, 則是時間與空間的取捨 由於雙向鏈結多使用了一個鏈結欄位, 因此需要比較多的記憶體空間, 但也因為雙向鏈結多了一個有用的鏈結欄位, 因此也使得某些運算 ( 例如刪除節點運算 ) 的時間複雜度得以降低 所以要採用哪一種鏈結串列, 應該視應用場合來決定
本章習題 鏈結串列 4-69