PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

以穆
5 years ago
Views:

1 資料結構 (Data Structures) Course 4: Link Lists ( 鏈結串列 ) 授課教師 : 陳士杰國立聯合大學資訊管理學系

2 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

3 Linked List Concepts Def: 由一組節點 (Node) 所組成的有序串列, 各 Node 除了 Data 欄之外, 另外有 1 個 Link 欄 ( 或稱 Pointer), 用以指向其它 Node 之位址例 : 單向鏈結串列之節點 : struct node /* 串列結構宣告 */ { int data; /* 資料 */ struct node *next; /* 指標, 指向下一個節點 */ }; 3

4 Linked list 的特質 : 各 Node 不一定要佔用連續的 Memory 空間各 Node 之型態 (Data Type) 不一定要相同僅支援 Sequential Access Insert/Delete Node 容易 4

5 Link list 的種類 : Single Link List ( 單向鏈結串列 ) Circular Link List ( 環状鏈結串列 ) Double Link List ( 雙向鏈結串列 ) 5

6 Single Linked List ( 單向鏈結串列 ) Def: 由一組節點 (Node) 所組成的有序串列, 各 Node 除了 Data 欄之外, 另外有 1 個 Link 欄 ( 或稱 Pointer), 用以指向下一個 Node 之位址範例 : 名為 phead 之單向鏈結串列 ( 視首節點或首指標之名稱為何而定 ) 6

7 Linked List Algorithms Create List Insert Node Delete Node 在一些鏈節串列運作中, 我們可能會設定其它輔助用的指標!! 7

8 Create List 以 list 為名的空串列 : 以指標作為串列首 : list null 8

9 Insert Node 將資料 item 插入在串列 list 中的節點 x 之後 x list 2 1 t item 9

10 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

11 例 : 插入資料 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

12 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

13 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

14 Circularly Linked Lists ( 環狀鏈結串列 ) Def: 將 Single link list 中, 最後一個 node 的指標指回第一個 node. 圖示 : list 14

15 特質 : 不論從哪個 Node 開始, 必定能夠拜訪 ( 經過 ) 所有 Node. 並無明顯的頭尾節點 Single Link List 必須從頭開始才可以回收整個串列的時間為 O(1). ( 即 : 與 Link list 長度無關 ) Single Link List 回收時間為 O(n). 其中, n 為長度或 Node 數目. 15

16 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

17 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

18 Doubly Linked List ( 雙向鏈結串列 ) Def: 串列中各節點除了 Data 欄之外, 另外有 2 個 Link 欄, 用以指向前一個與下一個節點之位址圖示 : LLink Data LLink: Pointer 指向前一個 Node. RLink: Pointer 指向後一個 Node. RLink 18

19 一般使用雙向鏈結串列時, 通常會加入串列首 (Head Node), 此 Node 不存資料 - 此時, 雙向鏈結串列可視為 2 個 Circular Link List. 19

20 插入 Node t 在 Node x 之後 Doubly Linked List Insertion x begin end 1 t RLink = x RLink; 2 t LLink = x; 3 (x RLink) RLink) LLinkLLink = t; 4 x RLink = t; t 須改變 4 個指標 20

21 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

22 Double linked list 與 Single linked list 的比較 Double Single 優可立即知道前後 Node 所在只知道前 ( 或後 ) Node 所在缺刪除 Node 時, 不須給前一個 Node 必須給前一個 Node 之位置任何一個 Node 開始, 必可經過所有 Nodes 可靠度高一定要從第一個 Node 開始可靠度低, 萬一指標斷裂, 串列一分為二,Data lost 缺插入節點麻煩 ( 須改變 4 個指標 ) 容易 ( 只改變 2 個指標 ) 優刪除節點麻煩 ( 須改變 2 個指標 ) 容易 ( 只改變 1 個指標 ) Link 所需的空間較大較少 22

23 動作 : Link list 三個常見的動作 Length ( 求串列長度 ) Concatenate ( 串列連結 ) Invert ( 反轉 ) 討論對象 : Single linked list Circular linked list 共有 6 個主要的 Algorithm 23

24 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

25 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

26 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

27 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

28 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

29 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

30 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

31 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

32 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

33 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

34 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

35 利用 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 假設 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

36 補充 36

37 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

38 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

39 Ret(t) AV 2 1 t begin 1 t link = AV; 2 AV = t; end 39

40 存取節點資料的表示方式若單一節點是由指標 t 指向該節點 : t Data Link t Data: 存取指標 t 所指向之節點中的 data 值 t Link: 存取指標 t 所指向之節點中的 link 值 40

41 Ex: t 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

陣列與鏈結串列 Array and Linked List

陣列與鏈結串列 Array and Linked List 講師 : 洪安 1 大綱結構陣列鏈結串列單向鏈結串列之資料型態單向鏈結串列之基本運算課堂練習 2 結構陣列優點缺點使用容易 class student int math; int english; int computer; ; 刪除與插入造成資料移動頻繁浪費不必要之記憶體 int main() student s[5];