資料結構 (Data Structures) Course 4: Link Lists ( 鏈結串列 ) 授課教師 : 陳士杰 國立聯合大學資訊管理學系
Outlines 本章重點 Link List s Def. 與 Array 的比較 Link List 之基本操作 (Insert, Delete) Link list 的種類 : Single Link List ( 單向鏈結串列 ) Circular Link List ( 環狀鏈結串列 ) Double Link List ( 雙向鏈結串列 ) Link List 常見的三個運作 Length ( 計算串列長度 ) Concatenate ( 連結兩個串列 ) Invert ( 反轉 ) Storage Pool 2
Linked List Concepts Def: 由一組節點 (Node) 所組成的有序串列, 各 Node 除了 Data 欄之外, 另外有 1 個 Link 欄 ( 或稱 Pointer), 用以指向其它 Node 之位址 例 : 單向鏈結串列之節點 : struct node /* 串列結構宣告 */ { int data; /* 資料 */ struct node *next; /* 指標, 指向下一個節點 */ }; 3
Linked list 的特質 : 各 Node 不一定要佔用連續的 Memory 空間 各 Node 之型態 (Data Type) 不一定要相同 僅支援 Sequential Access Insert/Delete Node 容易 4
Link list 的種類 : Single Link List ( 單向鏈結串列 ) Circular Link List ( 環状鏈結串列 ) Double Link List ( 雙向鏈結串列 ) 5
Single Linked List ( 單向鏈結串列 ) Def: 由一組節點 (Node) 所組成的有序串列, 各 Node 除了 Data 欄之外, 另外有 1 個 Link 欄 ( 或稱 Pointer), 用以指向 下一個 Node 之位址 範例 : 名為 phead 之單向鏈結串列 ( 視首節點或首指標之名稱為何而定 ) 6
Linked List Algorithms Create List Insert Node Delete Node 在一些鏈節串列運作中, 我們可能會設定其它輔助用的指標!! 7
Create List 以 list 為名的空串列 : 以指標作為串列首 : list null 8
Insert Node 將資料 item 插入在串列 list 中的節點 x 之後 x list 2 1 t item 9
begin New(t); // 跟系統要求記憶體空間以配置一個新節點, 且讓指標 t 指向該節點 t data = item; // 把 item 塞到這個新節點 t 的 Data 欄位中 1 t link = x link; // 先把新節點 t 掛到 x 節點之後!! 2 x link = t; // 再將 x 節點接到節點 t end 10
例 : 插入資料 20 在節點 x 之前 x list 限制 : 不准用迴圈指令, 且動作需於 O(1) 常數時間完成 Ans: x begin New(t); t data = x data; t link = x link; x link = t; x data = 20; x = t; end; list t Data 20 Data 11
Delete Node 刪除鏈節串列的節點時, 會先 1 改變串列指標, 以做到邏輯性移除 (Logically Remove) 的動作, 2 再將要被移除的節點做實際刪除 (Physically Delete) 的動作, 讓節點從記憶體中刪除 需要兩個輔助指標 x 與 ppre x 用以指向欲刪除的節點,pPre 指向節點 x 所 在之前一個 node 例 : 刪除串列 list 中之節點 x, Case 1: ( 要砍第一個 node)-- 若 x 為第一個 node, 則令 ppre = Case 2: ( 要砍串列中間的 node) list list x 2 ( 回收 ) list 1 ppre x ppre 2 ( 回收 ) 1 12
begin 1 if (ppre = ) then // 表示 x 為第一個節點 list = x link; else // 表示 x 節點是中間節點 ppre link = x link; 2 Ret(x); // 將 節點 x 回收. 有的書是用 delete(x), release(x), dispose(x) etc. end 13
Circularly Linked Lists ( 環狀鏈結串列 ) Def: 將 Single link list 中, 最後一個 node 的指標指回第 一個 node. 圖示 : list 14
特質 : 不論從哪個 Node 開始, 必定能夠拜訪 ( 經過 ) 所有 Node. 並無明顯的頭尾節點 Single Link List 必須從頭開始才可以 回收整個串列的時間為 O(1). ( 即 : 與 Link list 長度無關 ) Single Link List 回收時間為 O(n). 其中, n 為長度或 Node 數目. 15
Single Linked List: 回收時間的比較 ( 單向 vs. 環狀 ) list 3 S 1 2 AV Procedure Release list(list: pointer to S.L.) begin end if (list ) then S = list; 1 while (S link( ) ) do S = S link; 2 S link = AV; 3 AV = list; // 回收節點至 AV list AV list 中 //while 迴圈會讓 S 一直前進至最後一節點 Time = O(n) 16
Circular Linked List C: P 1 C AV 2 3 AV Procedure Release C(C: pointer to S.L.) begin end if (C ) then 1 p = C link; 2 C link = AV; 3 AV = P; // 只動了三個指標!! Time = O(1) 17
Doubly Linked List ( 雙向鏈結串列 ) Def: 串列中各節點除了 Data 欄之外, 另外有 2 個 Link 欄, 用以指向 前一個與下一個節點之位址 圖示 : LLink Data LLink: Pointer 指向前一個 Node. RLink: Pointer 指向後一個 Node. RLink 18
一般使用雙向鏈結串列時, 通常會加入串列首 (Head Node), 此 Node 不存資料 - 此時, 雙向鏈結串列可視為 2 個 Circular Link List. 19
插入 Node t 在 Node x 之後 Doubly Linked List Insertion x 3 2 4 1 begin end 1 t RLink = x RLink; 2 t LLink = x; 3 (x RLink) RLink) LLinkLLink = t; 4 x RLink = t; t 須改變 4 個指標 20
Doubly Linked List Deletion 刪除一個節點 x 1 x 3 ( 回收 ) 2 begin end 1 (x LLink) LLink) RLink = x RLink; 2 (x RLink) RLink) LLinkLLink = x LLink ; 3 Ret(x); 須改變 2 個指標 21
Double linked list 與 Single linked list 的比較 Double Single 優 可立即知道前後 Node 所在 只知道前 ( 或後 ) Node 所在 缺 刪除 Node 時, 不須給前一個 Node 必須給前一個 Node 之位置 任何一個 Node 開始, 必可經過所有 Nodes 可靠度高 一定要從第一個 Node 開始 可靠度低, 萬一指標斷裂, 串列一分為二,Data lost 缺 插入節點麻煩 ( 須改變 4 個指標 ) 容易 ( 只改變 2 個指標 ) 優 刪除節點麻煩 ( 須改變 2 個指標 ) 容易 ( 只改變 1 個指標 ) Link 所需的空間較大 較少 22
動作 : Link list 三個常見的動作 Length ( 求串列長度 ) Concatenate ( 串列連結 ) Invert ( 反轉 ) 討論對象 : Single linked list Circular linked list 共有 6 個主要的 Algorithm 23
For Single linked list : Length list count++; P //p 不為空 () 時, 則 count 加 1,, 以讓 p 往下跑 Procedure Length list(list: pointer to S.L.) begin count = 0; p = list; while (p ) ) do begin count++; p = p link; end; return count; end Time: O(n) 24
For Circular linked list C : C p Procedure Length C(C: pointer to S.L.) begin if (C = ) then return 0; else begin count = 0; p = C; repeat // 不能用 while 迴圈!! 一定至少要做一次!!! count++; p = p link; until p = C; C end; end Time: O(n) 25
For Single Linked List 假設連結 A, B 串列成為 C 串列 : Concatenate Case 1: A = and B, 則 C = B. Case 2: A and B =, 則 C = A. Case 3: A and B, 則 C = A+B. Case 4: A = and B =, 則 C =. C A 3 B p 1 2 26
Procedure Con.two.S(A, B, C: pointer to S.L.) begin C = ; if (A = and B ) then C = B; //Case 1 else if (A and B = ) then C = A; //Case 2 else if (A and B ) then //Case 3 begin p = A; 1 while(p link link ) do p = p link; 2 p link = B; 3 C = A; end; Time: O(n) 或 O(m) return C; // 回傳 Case 1~4 的結果 (m, n 分別為 A, B 串列的長度 ) end 看 p 是在哪條串列上跑!!! 27
For Circular Linked List 假設連結 A, B 串列成為 C 串列 : Case 1: A = and B, 則 C = B. Case 2: A and B =, 則 C = A. Case 3: A and B, 則 C = A+B. Case 4: A = and B =, 則 C =. C 1 A B 3 2 相當於 28
Procedure Con.two.S(A, B, C: pointer to C.L.) begin C = ; if (A = and B ) then C = B; //Case 1 else if (A and B = ) then C = A; //Case 2 else if (A and B ) then //Case 3 begin 1 C = A link; 2 A link = B link; 3 B link = C; end; return C; // 回傳 Case 1~ 4 的結果 Time: O(1) end ( 沒有任何的迴圈指令, 只有指標的改變 ) 29
Invert For Single Linked List 需要三個指標 : r, q, p r 跟著 q 走,q 跟著 p 走,p 往前進 1 2 q r r s s p q p 3 s r q p 4 s r q s p P 跑到 時結束, 同時 S 要指向 q 30
Procedure Invert S(S: pointer to S.L.) begin end p = S; q = ; while (p ) do begin r = q; //r 一開始會在此被設為 q = p; p = p link; q link = r; end; S = q; //S 可能指向反轉後的第一個節點反轉後的第一個節點或是 null list Time: O(n) 31
For Circular Linked List 亦需要三個指標 : r, q, p r 跟著 q 走,q 跟著 p 走,p 往前進 1 r C q p 2 C r q p 3 C p r q 4 C p r q C P 跑到 C 時結束, 同時 C 要指向 q 32
Procedure Invert C(C: pointer to C.L.) begin if (C ) then begin p = C link; //p 指向 C 的下一個 node q = C; // 初值 while (p c) do begin r = q; q = p; p = p link; q link = r; end; C link = q; C = q; end; end Time: O(n) 33
Array 與 Link List 的比較 Link List Array 優 元素佔用非連續性的 Memory Space 佔用連續性的空間 缺 各 node 之 data type 不一定相同 各元素型態皆須一致 使用之前無須事先宣告大小, 可任意增 / 刪空間 Insert/Delete 元素較易, 花費 O(1) ( 只更改指標即可 ) 資料共享易達成 ( 指標指到相同位址即可 ) 串列分裂 合併容易 大小必須事先宣告, 無法任意增 / 刪空間 較難, 花費 O(n) ( 須挪移元素 ) 不易達成 ( 兩個獨立 Array 不易做資料共享, 只能複製資料到另一個 Array) 缺僅支援 Sequential Access 可支援 Random 與 Sequential Access 優 循序讀取慢 ( 要先讀取指標, 才能取出下一個 node) 需要額外的 Link 空間需求 可靠度低 ( point 斷裂, 資料 lost) 較難 快 沒有 高 34
利用 Single link list 表示多項式 假設 f(x) = 5x 8 +4x 3 +2x+9, 請用 Single link list 表示 Ans: Node Structure 設計如右 : coe exp link coe: Coefficient( 係數 ); exp: Exponent( 指數 ); link: Pointer 表示如下 : f 5 8 4 3 2 1 9 0 假設 f(x) = 5x 4 y 2 +8x 3 y+9xy, 請用 Single link list 表示 Ans: Node Structure 設計如右 : coe x - exp y exp link coe: Coefficient( 係數 ); exp: Exponent( 指數 ); link: Pointer 表示如下 : f 5 4 2 8 3 1 9 1 1 35
補充 36
Storage Pool Def: 可用節點 (Free Node) 之集合 ( 集中管理之處 ), 通常 O.S. 以 Single link list 來管理 Free Nodes, 稱為 AV-list (Available list). AV 需提供二個運作 : New(t): 相當於刪除 AV-list 中 Free Node. (if AV-list ) Ret(t): 相當於 Insert 節點到 AV-list 中. 37
New(t) AV t 1 AV 2 begin if (AV ) then begin 1 t = AV; 2 AV = AV link link; end; else print( No Free Node. ); end 38
Ret(t) AV 2 1 t begin 1 t link = AV; 2 AV = t; end 39
存取節點資料的表示方式 若單一節點是由指標 t 指向該節點 : t Data Link t Data: 存取指標 t 所指向之節點中的 data 值 t Link: 存取指標 t 所指向之節點中的 link 值 40
Ex: t 50 20 80 60 null p q r Print(p Data) = 20 Print((p Link) Data) = 80 r 相當於 q Link 或 (p link) link 將 p 的下一個 node 改指向 r 節點 =(p link) r 41