第三章 鏈結串列 Linked List 版權屬作者所有，非經作者 同意不得用於教學以外用途.

Presentation on theme: "第三章 鏈結串列 Linked List 版權屬作者所有，非經作者 同意不得用於教學以外用途."— Presentation transcript:

1 第三章 鏈結串列 Linked List 版權屬作者所有，非經作者 同意不得用於教學以外用途

2 本章內容 3-1 串列的定義 3-2 用陣列直接儲存串列—循序配置串列 3-3 串列加上鏈結—鏈結配置串列 3-4 用結構體陣列實作鏈結串列
3-1 串列的定義 3-2 用陣列直接儲存串列—循序配置串列 3-3 串列加上鏈結—鏈結配置串列 3-4 用結構體陣列實作鏈結串列 3-5 指標與結構體 3-6 動態配置節點實作鏈結串列 3-7 鏈結串列的其他運算 3-8 環狀鏈結串列 3-9 雙向鏈結串列 3-10 鏈結串列的應用

3 3-1 串列(list)的定義 串列 是許多項目有順序的排列 ( 集合 (set) 裡的元素則沒有前後之分) 常用於串列上的幾個運算
二次大戰同盟國國名串列 中國 美國 英國 蘇俄 10到30之間的質數由小到大排列 11 13 17 19 23 29 常用於串列上的幾個運算 1. 插入新節點 (Insert) － 在原有的串列中加入一個新的元素。 2. 刪除某節點 (Delete) － 將某一個元素從原本的串列中移除。 3. 找尋某節點 (Find) － 依照需求將所指定的（或第幾個）元素值讀出來 串列的實作方式 「循序配置串列」(sequential allocation list) 「鏈結配置串列」(linked allocation list)

4 3-2 用陣列直接儲存串列—循序配置串列 利用陣列循序儲存串列的方式，具有以下的優缺點：
中國 Alli[0] 11 Prime[0] 美國 Alli[1] 13 Prime[1] 英國 Alli[2] 17 Prime[2] 蘇俄 Alli[3] 19 Prime[3] 23 Prime[4] 29 Prime[5] 利用陣列循序儲存串列的方式，具有以下的優缺點： 優點：只要標明要查詢第幾個元素，就能很快地根據元素註標讀寫該元素，因為陣列的隨機存取 (random access) 效率相當高，時間複雜度為 O(1)。 缺點：插入元素 (insert) 和刪除元素 (delete) 兩個動作所需時間的複雜度為O(n)。這是因為陣列所有元素在記憶體中的實體位置 (physical location) 是連續的，因此不論是執行元素的插入或刪除，都必須進行資料的搬移，以維持正確的順序(參考2.2節)。

5 3-3 串列加上鏈結—鏈結配置串列 「鏈結串列」(linked list) 可以用來解決陣列循序配置的缺點：
1. 鏈結串列的元素之間不必實體連續（不必依元素順序佔用記憶體中的連續位址），只要有邏輯上 (logical) 的順序存在即可 2. 「鏈結」(link) 就是用來維持這順序的工具，它可以告訴我們「下一個元素放在哪裡」。 無首節點 (由一個指標指到) listA 中國 美國 英國 蘇俄 有首節點 中國 美國 英國 蘇俄 首節點

6 3-4 用結構體陣列實作鏈結串列 data 欄位存放資料本身 next 欄位存放下一個資料的位置 3 1 3 6 1 7 6 7 data
3-4 用結構體陣列實作鏈結串列 data next 從這裡開始 Table[0] 3 3 [1] 美 國 6 6 data 欄位存放資料本身 [2] -1 [3] 中 國 1 1 [4] -1 next 欄位存放下一個資料的位置 [5] -1 [6] 英 國 7 7 [7] 蘇 俄 [8] -1 節散散佈在陣列中，實體位置沒有連續，但根據鏈結可以得到以下次序 3 首節點 1 中國 3 6 美國 1 7 英國 6 蘇俄 7

7 插入新節點  找到一個空節點(next值為-1)，填入資料 ‘法國’ 7  找到英國，或者條件已知
要在 ‘英國’ 節點之後插入一個新節點 ‘法國’ data next Table[0] 3  找到一個空節點(next值為-1)，填入資料 ‘法國’ [1] 美 國 6 [2]  法 國 7 →7  -1  找到英國，或者條件已知 [3] 中 國 1 [4] -1  將英國的 next (7) 複製到法國的next [5] -1 [6]  英 國 →2  7  將法國的位置 (2) 填入英國的next [7] 蘇 俄 [8] -1 3 1 6 7 3 中國 1 美國 6 英國 7 蘇俄 2 首節點 法國

8 刪除節點 3 1 6 2 7 3 1 2 7 要刪除 ‘英國’ 節點 data next Table[0] 3
 沿著串列找到英國 (6)，以及英國的前一個節點 ‘美國’(1) [1] 美 國 →2 6 [2] 法 國 7  將英國的 next (2) 複製到美國的next [3] 中 國 1  將英國節點還原為空節點 [4] -1 [5] -1 [6] 英 國 → -1 2 [7] 蘇 俄 [8] -1 3 1 6 2 7 3 中國 1 英國 2 法國 7 蘇俄 美國 6 首節點

9 要將「阿里山」加在「太魯閣」之後 data next table[0] 5 table[1] 日 月 潭 2 table[2] 墾 丁
日 月 潭 2 table[2] 墾 丁 table[3] -1 table[4] table[5] 溪 頭 7 table[6] table[7] 太 魯 閣 1 table[8] data next table[0] 5 table[1] 日 月 潭 2 table[2] 墾 丁 table[3] 阿 里 山 -1→1 table[4] -1 table[5] 溪 頭 7 table[6] table[7] 太 魯 閣 1→3 table[8] 鏈結串列圖示 溪頭 7 太魯閣 1 日月潭 2 墾丁 5 首節點 7 1 2 插入新節點 墾丁 0 日月潭 2 阿里山 1 太魯閣 3 溪頭 7 5 首節點 7 2 3 1

10 刪除「太魯閣」 data next table[0] 5 table[1] 日 月 潭 2 table[2] 墾 丁 table[3]
日 月 潭 2 table[2] 墾 丁 table[3] 阿 里 山 -1→1 table[4] -1 table[5] 溪 頭 7 table[6] table[7] 太 魯 閣 1→3 table[8] data next table[0] 5 table[1] 日 月 潭 2 table[2] 墾 丁 table[3] 阿 里 山 1 table[4] -1 table[5] 溪 頭 7→3 table[6] table[7] 太 魯 閣 3→-1 table[8] 鏈結串列圖示 墾丁 0 日月潭 2 阿里山 1 太魯閣 3 溪頭 7 5 首節點 7 2 3 1 刪除節點 溪頭 3 阿里山 1 日月潭 2 墾丁 5 首節點 3 1 2

11 3-5 指標與結構體 ◎變數是存放資料的地方 int i, j; i 5 j 5 p i ◎指標是存放位址的地方 int *p; 5 同義詞
3-5 指標與結構體 ◎變數是存放資料的地方 int i, j; i 5 i = 5 ; j = i ; j 5 p i ◎指標是存放位址的地方 int *p; p = &i ; 5 同義詞 p 指向 i ←→ p 裡面存放 i 的位址

12 ◎ *p 是 “p 所指變數” 的同義詞 p i 10 j p i 10 10 相當於 i=10 ; *p = 10 ;
相當於 j = i ; j p i j = *p ; 10 10

13 結構體 (structure) 結構體是將不同型別的元素集合起來，形成一種新的資料型別
1. struct student { 2. char name[8]; //姓名欄位 3. int age; //年齡欄位 4. int height; //身高欄位 5. } ; 此時就會產生一種叫做student的新結構體，這種結構體含有三個欄位，其中姓名欄位是一個字元陣列、年齡欄位是整數、身高欄位也是整數。 S1 S1 S1.age = 18 ; S1.height = 160 ; strcpy(S1.name, “Mary”) ; name name Mary age age 18 height height 160 宣告 typedef int INTEGER ; 就產生一個「新」的型別叫INTEGER，可以根據這個型別來宣告變數： INTEGER i, j ; 它的效果就好像宣告 int i, j; 一樣。

14 3-6 動態配置節點實作鏈結串列 動態配置節點方式實作鏈結串列，常會執行的串列運算按照順序為： 1. 宣告節點結構 2. 動態配置節點
3-6 動態配置節點實作鏈結串列 動態配置節點方式實作鏈結串列，常會執行的串列運算按照順序為： 1. 宣告節點結構 2. 動態配置節點 3. 指標在串列中移動 4. 插入新節點 5. 刪除節點 6. 建立串列

15 listA->next = NULL ;
宣告節點結構 注意：鏈結欄位改為指標 typedef struct listnode { int data; /*資料欄位*/ struct listnode *next; /*鏈結欄位*/ }NODE; NODE *listA; 2. 動態配置節點 listA = (NODE *) malloc( sizeof(NODE)) ; 在C++語言中則可用 new 運算子 listA = new NODE ; data next 20 填入資料欄位，NULL 填入鏈結欄位： listA->data = 20 ; listA->next = NULL ; listA

16 3. 指標在串列中移動 執行敘述 p = p->next ; 指標 p 指向下一個節點 40 30 20 10 首節點 p 40 30

17 走訪整個鏈結串列 void ListTraverse(ListNode *head) { ListNode *p = head; } p = p->next ; while ( p != NULL ) { printf( “\n%d”, p->data ); //印出節點資料 } p = p->next ; //指標p沿著鏈結而指向下一個節點

18 插入新節點 … … … … … … … 要將指標 NewNode 所指到的新節點，插入指標 p 所指舊節點之後 p NewNode
第一步：掛上新節點的鏈結 NewNode->next = p->next ; … … p NewNode 第二步：改變舊節點的鏈結 p->next = NewNode ; … p NewNode … … NewNode p

19 1. int InsertAfter(ListNode *p, int value)
2. { ListNode *NewNode; NewNode = (ListNode*) malloc(sizeof(ListNode)); //動態配置節點 // C++: NewNode = new ListNode; if (NewNode == NULL) 5. return FALSE; //配置失敗 NewNode->data = value; //將新節點的值填入 NewNode->next = p->next; //掛上新節點的鏈結 p->next = NewNode; //改變原有節點的鏈結 return TRUE; //傳回成功訊息 10. }

20 刪除節點 … … … … … 要刪除指標 Node 所指到的節點 Node 第一步：找到前一個節點 Node PreNode
PreNode = GetPreNode(head,Node) ; 第二步：前一節點的鏈結，使它越過舊節點 PreNode->next = Node->next ; … Node PreNode 第三步：將舊節點動態歸還 … PreNode free( Node ) ;

21 1.int DeleteNode(ListNode *head, ListNode *OldNode)
2.{ ListNode *PreNode; if (head == OldNode) //不可刪除首節點 4. return FALSE; //非法刪除，傳回失敗訊息 PreNnode = GetPreNode(head, OldNode); //找到前一節點 if ( PreNode == NULL)//OldNode節點不在串列中 7. return FALSE; //無法刪除，傳回失敗訊息 PreNode->next = OldNode->next; //越過刪除原有節點 free(OldNode); //歸還被刪除節點 // C++: delete OldNode; return TRUE; 11.}

22 6. 建立鏈結串列 建立鏈結串列的方法是重複地將新節點加入串列。 新節點加入的位置 可以是串列的前面 也可以是在串列的尾端
也可以是在串列的特定地方（例如按照 data 欄位大小排列）。 39 39 41 39 41 58 39 41 58 103

23 3-6 鏈結串列的其他運算 ◎計算串列長度（節點數目）-- 線性鏈結串列 int ListLength( NODE *head)
3-6 鏈結串列的其他運算 ◎計算串列長度（節點數目）-- 線性鏈結串列 Head P在這裡時，count = 0 P在這裡時，count = 1 P在這裡時，count = 2 P在這裡時，count = 3 P在這裡時，count = 4 P在這裡時，迴圈結束 int ListLength( NODE *head) { int counter = 0 ; NODE *p = head ; while ( (p = p->next) != NULL) counter ++ ; return counter ; }

24 void ListConcate( NODE *listA, NODE *listB) { NODE *p = listA ;
◎串接兩鏈結串列 -- 線性鏈結串列 A p B void ListConcate( NODE *listA, NODE *listB) { NODE *p = listA ; while ( p->next != NULL) // p一路往右直到最後一個節點 p = p->next ; p->next = listB->next ; // 改變其鏈結 }

25 3-7 環狀鏈結串列 環狀鏈結串列的特點 1. 最後節點的鏈結不接地，而是指向首節點
3-7 環狀鏈結串列 線性鏈結串列 最後節點 Head 環狀鏈結串列 最後節點 Head 環狀鏈結串列的特點 1. 最後節點的鏈結不接地，而是指向首節點 2. 從任何一個節點開始，都可以走訪所有節點。只要繞回原起點就可以停止

26 3-8 雙向鏈結串列 typedef struct dlist_node { struct dlist_node *left;
3-8 雙向鏈結串列 typedef struct dlist_node { struct dlist_node *left; int data; struct dlist_node *right; }Dnode; 線性雙向鏈結串列 Head 環狀雙向鏈結串列 Head

27 插入新節點 … … p … p … p … NewNode NewNode NewNode
要將指標 NewNode 所指到的新節點，插入指標 p 所指舊節點之右 p NewNode 第一步：掛上新節點的兩個鏈結 … p NewNode NewNode->left = p; NewNode->right = p->right ; 第二步：改變舊節點的兩個鏈結 … p NewNode p->right->left = NewNode; p->right = NewNode ; …

28 刪除節點 p … … … p … p … 要刪除指標 p 所指到的節點 第一步：改變左邊節點的右指標使它越過舊節點
p->left->right = p->right ; 第二步：改變右邊節點的左指標使它越過舊節點 … p p->right ->left = p->left ; 第三步：將舊節點歸還系統 free( p ) ; …

29 3-9 鏈結串列的應用 5x4 可表示為： ◎ 多項式的表示與運算
3-9 鏈結串列的應用 ◎ 多項式的表示與運算 使用鏈結串列表示多項式，每個非零項使用一個節點，每個節點包含兩個資料欄位：係數欄位和冪次欄位，以及一個鏈結欄位。節點結構可以宣告為： typedef struct plistnode { float coef ; /* 係數*/ int expo ; /* 冪次*/ struct plistnode *next ; /*鏈結指標*/ } Pnode; 係數 冪次 5x4 可表示為： 5 4

30 2. 比較兩項冪次大小，冪次大者，複製此項至C(x)，如果冪次相同，則係數相加後，同樣複製此項至C(x)。
A(x) = 5x x x +6 A 5 4 6.1 2 2.9 1 6 B(x) = 9x x2 B 9 5 3.2 2 ※ 多項式相加 1.    兩多項式分別從高冪次項往右掃瞄。 2.    比較兩項冪次大小，冪次大者，複製此項至C(x)，如果冪次相同，則係數相加後，同樣複製此項至C(x)。 3.    凡是已被複製的項，多項式就往右移一項。重複步驟1,2，直到兩個多項式都用完為止。

31 2. pb->exp(=5) 大於 pa->exp(=4) ，複製 *pb，pb往右一個節點
1. 初始狀態 pa A 5 4 6.1 2 2.9 1 6 pb B 9 5 3.2 2 ctail C 2. pb->exp(=5) 大於 pa->exp(=4) ，複製 *pb，pb往右一個節點 pa A 5 4 6.1 2 2.9 1 6 pb B 9 5 3.2 2 ctail C 9 5

32 3. pa->exp(=4) 大於 pb->exp(=2) ，複製 *pa，pa往右一個節點
5 4 6.1 2 2.9 1 6 pb B 9 5 3.2 2 ctail C 9 5 5 4 4. pa->exp 等於 pb->exp，新節點係數為 pa->coef 加 pb->coef，pa及pb往右一個節點 pa A 5 4 6.1 2 2.9 1 6 pb B 9 5 3.2 2 ctail 9 5 C 5 4 9.3 2

33 5. pb已經接地，將串列 A 剩下的節點複製到串列 C
pa A 5 4 6.1 2 2.9 1 6 pb B 9 5 3.2 2 C 9 5 5 4 9.3 2 ctail 2.9 1 6

34 M矩陣的 30 (5  6) 個元素中只有 9 個非零項，使用率只有 9/30 = 30%
◎ 稀疏矩陣的表示 M = 5  6 M矩陣的 30 (5  6) 個元素中只有 9 個非零項，使用率只有 9/30 = 30% ◎使用節點來表示每個非零項，每個節點結構有 3 個資料欄位— data、row、col 之外，兩個鏈結欄位— right、down。 同一列的節點藉著 right 鏈結成為一個串列， 同一行節點也藉著down鏈結成為一個串列。節點的結構可以圖示為： row col data 例如 1 3 6 down right

35 M = 5 ×6 c0 c1 c2 c3 c4 c5 1 2 3 4 5 2 1 4 2 r0 1 1 -1 1 3 6 r1 2 2 1 1 r2 3 3 3 3 3 5 1 r3 4 4 2 2 4 5 6 r4