本教學投影片係屬教科書著作之延伸，亦受著作權法之保護。

Presentation on theme: "本教學投影片係屬教科書著作之延伸，亦受著作權法之保護。"— Presentation transcript:

1 本教學投影片係屬教科書著作之延伸，亦受著作權法之保護。
請依出版社授權使用規範利用本教學資源，非經授權許可不得以影印、拷貝、列印等方法進行重製，亦不得改作、公開展示著作內容，亦請勿對第三人公開傳輸、散布。 戴顯權 著 / 資料結構 © 滄海圖書

2 Chapter 3 鏈結串列 戴顯權 著 / 資料結構 © 滄海圖書

3 本章內容 3.1 鏈結串列簡介 3.2 單向鏈結串列 3.3 環狀鏈結串列 3.4 雙向鏈結串列 3.5 應用範例— 處理學生成績資料
3.1　鏈結串列簡介 3.2　單向鏈結串列 3.3　環狀鏈結串列 3.4　雙向鏈結串列 3.5　應用範例— 處理學生成績資料 3.6　** Convex hull 戴顯權 著 / 資料結構 © 滄海圖書

4 鏈結串列 我們可用陣列來表示一個串列，它的優缺點分別為：
優點：用陣列來表示串列，我們只要用元素的索引值就可 以很快地取得一個元素，因此能很容易地達成隨機存取 (random access) 的目的。 缺點：插入和刪除的運算所需要的時間複雜度為O(n)。這 是因為陣列元素的實際記憶體位置是依序相連的，因此元 素的插入與刪除運算都必須進行元素位置的更動，以維持 實際記憶體位置相連的要求 戴顯權 著 / 資料結構 © 滄海圖書

5 鏈結串列 如果我們的應用常常需要在串列中做插入與刪除的 運算，那麼使用陣列來表示串列就不合適
在這種情況下，使用鏈結串列(linked list) 才是正確 的選擇 鏈結串列的元素並不要求使用實際相連的記憶體位 置，我們只需要利用鏈結來維持元素間的連續性以 及順序即可 戴顯權 著 / 資料結構 © 滄海圖書

6 鏈結串列 使用一種稱為「節點」(node) 的基本資料結構，每一 個節點至少包含兩個欄位：資料欄位與鏈結欄位
鏈結欄位所記錄的是下一個節點的索引值或位址 鏈結串列的另一個優點是：我們可以輕易地做到節 點的插入與刪除運算，不需要搬移資料，只需要改 變鏈結 戴顯權 著 / 資料結構 © 滄海圖書

7 鏈結串列 鏈結串列裡的任何一個節點，實際上可以放在記憶 體裡的任何一個位址上
每一個元素節點除了資料部分外，還需要有一個指 向串列裡的下一個元素的指標(pointer)，這個指標一 般我們就稱之為鏈結(link)。 戴顯權 著 / 資料結構 © 滄海圖書

8 鏈結串列 一般會在串列的前端加上一個特殊節點，稱為首節 點(head node 或first node)
最後一個節點的鏈結或者指標為 NULL 戴顯權 著 / 資料結構 © 滄海圖書

9 使用靜態配置節點實作鏈結串列 mylist 是一個陣列，因此 每一個節點可以透過一 個整數索引來追蹤到 所以，next 欄位宣告為 整數型態
#define Max_Node 7 typedef struct listnode { char data[8]; /* 資料欄位*/ int next; /* 鏈結欄位*/ } Node; Node mylist[Max_Node]; mylist 是一個陣列，因此 每一個節點可以透過一 個整數索引來追蹤到 所以，next 欄位宣告為 整數型態 戴顯權 著 / 資料結構 © 滄海圖書

10 初始化 假設我們只有一個鏈結串列，並 且用mylist[0] 做為首節點，那麼 經過初始化以後的mylist 變成：
其中next 欄位的0 表示鏈結串列 結束，–1 表示該節點未被用到 (是自由節點)。為了簡化起見， 我們假設Max_Node=7 戴顯權 著 / 資料結構 © 滄海圖書

11 初始化 經過一段時間的處理，鏈結串列現在變成如下圖所 示 戴顯權 著 / 資料結構 © 滄海圖書

12 插入一個新節點 例如台北，並且要加在台南 節點之後，步驟是：
從mylist 的首節點(mylist[0]) 向下掃描，找出第一個next 欄位為 –1 的節點(自由節點)。 找到mylist[1]，我們在 mylist[1].data 欄位中填入 「台北」 戴顯權 著 / 資料結構 © 滄海圖書

13 插入一個新節點 從鏈結的首節點(mylist[0]) 沿著鏈結走，尋找台南的所 在節點，結果我們找到 mylist[4]
戴顯權 著 / 資料結構 © 滄海圖書

14 插入一個新節點 把mylist[4].next 指派給 mylist[1].next。因此 mylist[1].next 變為3
戴顯權 著 / 資料結構 © 滄海圖書

15 插入一個新節點 把mylist[4].next 設為新節 點的位置1 戴顯權 著 / 資料結構 © 滄海圖書

16 刪除一個節點 要刪除一個節點，例如台 南，我們可以按照以下的 步驟來進行：
首先沿著鏈結，找到台南 的所在位置(mylist[4])，以 及台南的前一個節點位置 戴顯權 著 / 資料結構 © 滄海圖書

17 刪除一個節點 把mylist[4].next 指派給 mylist[0].next 戴顯權 著 / 資料結構 © 滄海圖書

18 刪除一個節點 把mylist[4].next 設為 –1， 還原為自由節點 戴顯權 著 / 資料結構 © 滄海圖書

19 節點表示法－陣列 使用陣列結構來實作鏈結串列的優點是：鏈結的方 式很簡單
但是它也有一個缺點：一開始就必須宣告陣列的大 小，宣告太多而使用太少，則浪費記憶體；宣告太 少而不足使用，則缺乏彈性 戴顯權 著 / 資料結構 © 滄海圖書

20 使用動態配置節點實作鏈結串列 節點的產生與使用
戴顯權 著 / 資料結構 © 滄海圖書

21 使用動態配置節點實作鏈結串列 節點的產生與使用
定義Node 為含有兩個欄位的結構型態，其中data 欄 位是整數型態 next 欄位是指標型態，它指到一個listnode 資料型態， 也就是Node 本身 最後的一個宣告指令，則是宣告listA 為指向一個 Node 資料型態的指標 換句話說，每一個節點都有一個資料欄位以及一個 鏈結欄位，其中鏈結欄位是一個指向某個節點的指 標 戴顯權 著 / 資料結構 © 滄海圖書

22 使用動態配置節點實作鏈結串列 節點的產生與使用
跟前一小節的陣列作法不同的是，在此每個節點都 可以動態配置、歸還 換句話說，只有當程式在執行的過程中有需要時， 才機動地向系統要記憶體；而且一旦不需要了，還 可以馬上還給系統 因此，我們並不需要事先預估我們的程式可能會用 到多少個節點 戴顯權 著 / 資料結構 © 滄海圖書

23 使用動態配置節點實作鏈結串列 節點的產生與使用
動態配置在C 語言可以用malloc 庫存函式來呼叫 它的結果是傳回節點在記憶體中的位址，即 listA=(Node*) malloc (sizeof (Node)); 其結果可以用下圖表示： 戴顯權 著 / 資料結構 © 滄海圖書

24 使用動態配置節點實作鏈結串列 節點的產生與使用
節點在記憶體裡的實際位置，因為位置(位址) 就儲存 於指標listA 中 現在，假設要把55 存入data 欄位、NULL 存入鏈結 欄位，那麼可以用以下的指令來完成： listA->data=55; listA->next=NULL; 戴顯權 著 / 資料結構 © 滄海圖書

25 使用動態配置節點實作鏈結串列 節點的產生與使用
或者也可以寫成： (*listA).data=55; (*listA).next=NULL; 這是因為*listA 本身就代表指標listA 所指向的記憶體位置 它的結果會如下圖所示，其中我們用 接地來表示它的next 欄位等於NULL 戴顯權 著 / 資料結構 © 滄海圖書

26 使用動態配置節點實作鏈結串列 插入節點 假設我們要把新節點， 即NewNode 指標所指 向的節點，插入p 指 標所指向的節點之後， 如圖3.2 所示。我們 必須處理兩個鏈結 戴顯權 著 / 資料結構 © 滄海圖書

27 NewNode->next=p->next;
使用動態配置節點實作鏈結串列 插入節點 把NewNode 所指向的節 點之鏈結欄位設定為p 所指向節點的鏈結欄位 值，使得p 所指向節點 的下一個節點現在也變 成NewNode 所指向節點 的下一個節點。 換句話說，就是執行 NewNode->next=p->next; 戴顯權 著 / 資料結構 © 滄海圖書

28 使用動態配置節點實作鏈結串列 插入節點 接著處理p 所指向節點的 鏈結欄位，把它的內容 更新為NewNode，使得p 所指向節點的下個節點 變成NewNode 所指向的 節點 換句話說，就是執行 p->next=NewNode; 戴顯權 著 / 資料結構 © 滄海圖書

29 使用動態配置節點實作鏈結串列 插入節點 單向鏈結串列的插入運算之虛擬碼如下： 戴顯權 著 / 資料結構 © 滄海圖書

30 使用動態配置節點實作鏈結串列 插入節點 以C 語言來表示： 戴顯權 著 / 資料結構 © 滄海圖書

31 戴顯權 著 / 資料結構 © 滄海圖書

32 使用動態配置節點實作鏈結串列 刪除節點 要刪除某個節點，我們只要改變它的前個節點( prenode) 的鏈結，把它的鏈結內容更新為指向欲刪除節點的下個 節點的位址即可，如此便將p 從串列中刪除 首先必須先取得prenode 的位址。最後要把p 所佔用的記 憶體歸還，才算是完整的刪除運算 換句話說，就是執行 prenode->next=p->next; free( p); 戴顯權 著 / 資料結構 © 滄海圖書

33 使用動態配置節點實作鏈結串列 刪除節點 戴顯權 著 / 資料結構 © 滄海圖書

34 使用動態配置節點實作鏈結串列 刪除節點 單向鏈結串列的刪除運算之虛擬碼如下： 戴顯權 著 / 資料結構 © 滄海圖書

35 使用動態配置節點實作鏈結串列 刪除節點 以C 語言來表示： 戴顯權 著 / 資料結構 © 滄海圖書

36 戴顯權 著 / 資料結構 © 滄海圖書

37 環狀鏈結串列 鏈結串列中，最後一個節點的鏈結欄位固定指向 NULL。這種鏈結串列稱為線性鏈結串列(linear linked list)
它的特點是：如果要拜訪串列裡的任一節點，都必 須從首指標(FirstNode) 開始循序地拜訪鏈結 戴顯權 著 / 資料結構 © 滄海圖書

38 環狀鏈結串列 從任意節點出發均無法走到在它之前的節點，因此 在出發節點前面的節點資料都無法取得
有一個簡單的辦法可以解決這個問題，而且這個辦 法不需要額外使用任何變數或者記憶體 戴顯權 著 / 資料結構 © 滄海圖書

39 環狀鏈結串列 所有節點的鏈結構成一個環，因此稱為環狀鏈結串 列(circular linked list)
從任何節點出發都可以拜訪到所有的節點，最後也 可以回到原出發節點 環狀鏈結串列的運算基本上和單向鏈結串列並無不 同，只是環狀鏈結可以從任意一個節點開始，而結 束條件則是回到原出發節點，而不是「鏈結欄位等 於NULL」 戴顯權 著 / 資料結構 © 滄海圖書

40 回收環狀鏈結串列 假設avail 指標指向一個可使用的鏈結串列之首節點 位址
當我們要把一個已使用過、存有資料的環狀鏈結串 列做回收還給avail 時，我們只需要先把環狀鏈結串 列的首節點(FirstNode) 所指向節點之鏈結欄位值暫 存在temp 裡 然後把FistNode所指向節點的鏈結欄位值更新為avail 最後再把avail 指標更新為temp 就可以了 戴顯權 著 / 資料結構 © 滄海圖書

41 回收環狀鏈結串列 avail 指標就指向FirstNode 所指向節點原先的下一個 節點，而FirstNode 所指向節點的鏈結欄位值則是原 本avail 指標所指向的位址 整個環狀鏈結串列已歸還為可使用的串列，由avail 指標即可取用剛歸還的環狀鏈結串列之節點 戴顯權 著 / 資料結構 © 滄海圖書

42 回收環狀鏈結串列 戴顯權 著 / 資料結構 © 滄海圖書

43 回收環狀鏈結串列 戴顯權 著 / 資料結構 © 滄海圖書

44 環狀鏈結串列的特性 由串列中任何一個節點開始，都可拜訪整個串列裡 的所有節點。
回收整個環狀鏈結串列的時間複雜度是O(1)，跟串 列的長度無關。 戴顯權 著 / 資料結構 © 滄海圖書

45 戴顯權 著 / 資料結構 © 滄海圖書

46 戴顯權 著 / 資料結構 © 滄海圖書

47 雙向鏈結串列 戴顯權 著 / 資料結構 © 滄海圖書

48 雙向鏈結串列 戴顯權 著 / 資料結構 © 滄海圖書

49 雙向鏈結串列 戴顯權 著 / 資料結構 © 滄海圖書

50 插入節點 要插入一個(由NewNode 指標所指向的) 新節點到p 指 標所指向的節點之右 戴顯權 著 / 資料結構 © 滄海圖書

51 插入節點 處理新節點上的兩個鏈結 左鏈結：NewNode->left 右鏈結：NewNode->right
戴顯權 著 / 資料結構 © 滄海圖書

52 插入節點 戴顯權 著 / 資料結構 © 滄海圖書

53 插入節點 改變舊節點的鏈結，讓它們都更改為指向新節點 左鏈結p->right->left ，更新為指向NewNode
右鏈結p->right，把它更新為NewNode 戴顯權 著 / 資料結構 © 滄海圖書

54 插入節點 戴顯權 著 / 資料結構 © 滄海圖書

55 插入節點 戴顯權 著 / 資料結構 © 滄海圖書

56 戴顯權 著 / 資料結構 © 滄海圖書

57 ( p->left)->right=p->right
刪除節點 改變p 所指向節點之左邊節點的右鏈結，使它越過p 所指向的節點 ( p->left)->right=p->right 戴顯權 著 / 資料結構 © 滄海圖書

58 ( p->right)->left =p->left
刪除節點 改變p 所指向節點之右邊節點的左鏈結，使它越過p 所指向的節點 ( p->right)->left =p->left 戴顯權 著 / 資料結構 © 滄海圖書

59 刪除節點 完成p 的前、後節點的鏈結指標更新後，我們就可 以把p 所指節點的記憶體釋回，以完成刪除p 節點 的整個運算 free( p)
戴顯權 著 / 資料結構 © 滄海圖書

60 刪除節點 戴顯權 著 / 資料結構 © 滄海圖書

61 刪除節點 戴顯權 著 / 資料結構 © 滄海圖書

62 Convex hull Convex hull 問題的定義是：
戴顯權 著 / 資料結構 © 滄海圖書

63 Convex hull 在一一檢查各個點的內角是否符合convex hull 的要求 時，我們經常需要增加或刪除點
因此，正好可以利用雙向鏈結串列的便利性來解決 這個問題 戴顯權 著 / 資料結構 © 滄海圖書

64 利用Graham 掃描解決convex hull 問題
步驟1：(解決特殊情形) 如果S 裡的點數小於3，那麼直接傳回S； 如果所有的點都在同一條直線上，那麼找出最短的一條線 段的兩個端點，其中這條線段包含S 裡的所有點，傳回這 兩個點； 戴顯權 著 / 資料結構 © 滄海圖書

65 利用Graham 掃描解決convex hull 問題
步驟2：(根據角度來排序S 裡的點) 找一個在S 分布範圍中間的點P，P 可以是S 裡的一個點， 也可以不是 戴顯權 著 / 資料結構 © 滄海圖書

66 利用Graham 掃描解決convex hull 問題
接著從P 點往下畫一條垂直線L 戴顯權 著 / 資料結構 © 滄海圖書

67 利用Graham 掃描解決convex hull 問題
根據S 中各點與L 所形成的夾角大小把S 排序；角度相同 的則比較與P 點間的距離，在此僅保留距離最長的點 戴顯權 著 / 資料結構 © 滄海圖書

68 利用Graham 掃描解決convex hull 問題
按照排序後的S 裡的各點順序建立(環狀) 雙向鏈結串列 戴顯權 著 / 資料結構 © 滄海圖書

69 利用Graham 掃描解決convex hull 問題
　　for (Pa = P1, Pb = Pa->right_link ; Pa! = Pb ; ) 　　{ 　　 Pc =Pb->right_link; 　　 if (由Pa、Pb、Pc 所形成的外部夾角) 　　 /* 外部夾角相當於內部夾角 */ 　　 { 　　 從雙向鏈結串列中刪除Pb; 　　 Pb = Pa; Pa = Pb->left_link; 　　 } 　　 else { Pa = Pb; Pb = Pc;} 　　} 最後的雙向鏈結串列將只保留形成convex hull 的點。 戴顯權 著 / 資料結構 © 滄海圖書

70 利用Graham 掃描解決convex hull 問題
戴顯權 著 / 資料結構 © 滄海圖書

71 利用Graham 掃描解決convex hull 問題
戴顯權 著 / 資料結構 © 滄海圖書

72 利用Graham 掃描解決convex hull 問題
戴顯權 著 / 資料結構 © 滄海圖書

73 Convex hull 形成圖解 一開始，平面上有一群頂點集合S 戴顯權 著 / 資料結構 © 滄海圖書

74 Convex hull 形成圖解 加入 9 與0 的頂點 戴顯權 著 / 資料結構 © 滄海圖書

75 Convex hull 形成圖解 加入 1 戴顯權 著 / 資料結構 © 滄海圖書

76 Convex hull 形成圖解 加入 2 戴顯權 著 / 資料結構 © 滄海圖書

77 Convex hull 形成圖解 加入 3 戴顯權 著 / 資料結構 © 滄海圖書

78 Convex hull 形成圖解 加入4後，需刪除3 戴顯權 著 / 資料結構 © 滄海圖書

79 Convex hull 形成圖解 刪除3 戴顯權 著 / 資料結構 © 滄海圖書

80 Convex hull 形成圖解 加入5後，需刪除4 戴顯權 著 / 資料結構 © 滄海圖書

81 Convex hull 形成圖解 刪除4 戴顯權 著 / 資料結構 © 滄海圖書

82 Convex hull 形成圖解 加入6、7 戴顯權 著 / 資料結構 © 滄海圖書

83 Convex hull 形成圖解 加入8後，需刪除6、7 戴顯權 著 / 資料結構 © 滄海圖書

84 Convex hull 形成圖解 形成最後的convex hull 戴顯權 著 / 資料結構 © 滄海圖書

85 Convex hull 形成圖解 戴顯權 著 / 資料結構 © 滄海圖書

86 Convex hull 形成圖解 戴顯權 著 / 資料結構 © 滄海圖書