第三章 鏈結串列 Linked List

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

利用陣列結構循序來儲存串列的方式，具有以下的優缺點： 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) 是連續的，因此不論是執行元素的插入或刪除，都必須進行資料的搬移，以維持正確的順序。

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

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 蘇俄 首節點

插入新節點  找到一個空節點，填入資料  找到英國，或者條件已知  將英國的 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

刪除節點 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 首節點

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 的位址

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

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

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

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

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

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

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

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

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

插入新節點 … … 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 … …

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

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

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

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

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

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

M矩陣的 30 (5 × 6) 個元素中只有 9 個非零項，使用率只有 9/30 = 30% ◎ 稀疏矩陣的表示 0 0 1 0 2 0 -1 0 0 6 0 0 0 1 0 0 0 0 0 0 0 3 0 1 0 0 2 0 0 6 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

0 0 1 0 2 0 -1 0 0 6 0 0 0 1 0 0 0 0 0 0 0 3 0 1 0 0 2 0 0 6 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