第三章 鏈結串列 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 常用於串列上的幾個運算： 3-1 串列 1. 插入新節點 (Insert) － 在原有的串列中加入一個新的元素。
3-1 串列 ◎串列 是許多項目有順序的排列 二次大戰同盟國國名若依筆劃數目由少至多來排列 中國 美國 英國 蘇俄 10到30之間的質數由小到大排列 11 13 17 19 23 29 常用於串列上的幾個運算： 1. 插入新節點 (Insert) － 在原有的串列中加入一個新的元素。 2. 刪除某節點 (Delete) － 將某一個元素從原本的串列中移除。 3. 找尋某節點 (Find) － 依照需求將所指定的（第幾個）元素值讀出來

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) 是連續的，因此不論是執行元素的插入或刪除，都必須進行資料的搬移，以維持正確的順序。

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

6 3-3 陣列結構實作鏈結串列 3 1 6 7 3 1 6 7 data next Table[0] 3 [1] 美 國 6
3-3 陣列結構實作鏈結串列 data next Table[0] 3 [1] 美 國 6 #define MAXNODE 9 typedef struct tagListNode { char data[8]; /*資料欄位*/ int next ; /*鏈結欄位*/ } ListNode ; ListNode table[MAXNODE] ; [2] -1 [3] 中 國 1 [4] -1 [5] -1 [6] 英 國 7 [7] 蘇 俄 [8] -1 節散散佈在陣列中，實體位置沒有連續，但根據鏈結可以得到以下次序 3 1 6 7 3 中國 1 美國 6 英國 7 蘇俄 首節點

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

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

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

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

11 結構體 (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 一樣。

12 3-5 動態配置節點實作鏈結串列 動態配置節點，鏈結欄位改為指標 data next listA
3-5 動態配置節點實作鏈結串列 動態配置節點，鏈結欄位改為指標 typedef struct listnode { int data; /*資料欄位*/ struct listnode *next; /*鏈結欄位*/ }NODE; NODE *listA; 動態配置節點 listA = (NODE *) malloc( sizeof(NODE)) ; 在C++語言中則可用 new 運算子 listA = new NODE ; data next listA

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

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

15 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 ; }

16 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 ; // 改變其鏈結 }

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

18 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

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

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

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

22 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，直到兩個多項式都用完為止。

23 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

24 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

25 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

26 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

27 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