第三章 鏈結串列 Linked Lists

3-1 串列及鏈結串列 ◎串列 是許多項目有順序的排列，可以用陣列結構來儲存串列並且根據 元素在陣列中的位置可以判斷元素之間的順序。 3-1 串列及鏈結串列 ◎串列 是許多項目有順序的排列，可以用陣列結構來儲存串列並且根據 元素在陣列中的位置可以判斷元素之間的順序。 ◎用陣列結構來儲存串列的優缺點是： 優點： 只要標明元素註標，就能很快讀寫此元素，亦即陣列的隨機存取(random access) 的效率高。   缺點：插入 (insert) 和刪除 (delete) 元素的動作，需要時間複雜度為 O(n)。這是因為陣列元素間的實體位置(physical location)是連續的，因此元素的插入和刪除必須進行資料的搬移，以便維持新的次序。如果必須時常進行插入和刪除運算，代價將會相當大。 ◎鏈結串列 的元素之間不必實體連續，只要有邏輯上的順序存在即可，鏈結 (link)就是用來維持這順序的工具 。鏈結串列的優點是可以輕易的插入新節點，以及刪除舊節點，不需搬移資料，只要改變鏈結即可。

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

插入新節點 要在 ‘英國’ 節點之後插入一個新節點 ‘法國’ 3 1 6 7 3 1 6 2 7 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-3 動態配置節點實作鏈結串列 動態配置節點，鏈結欄位改為指標 動態配置節點 data next listA 3-3 動態配置節點實作鏈結串列 動態配置節點，鏈結欄位改為指標 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-4 環狀鏈結串列 環狀鏈結串列的特點 1. 最後節點的鏈結不接地，而是指向首節點。 3-4 環狀鏈結串列 線性鏈結串列 最後節點 Head 環狀鏈結串列 最後節點 Head 環狀鏈結串列的特點 1. 最後節點的鏈結不接地，而是指向首節點。 2. 從任何一個節點開始，都可以走訪所有節點。只要繞回原起點 就可以停止。

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

插入新節點 … … p … … p … … p … … 要將指標 NewNode 所指到的新節點，插入指標 p 所指舊節點之右 第一步：掛上新節點的兩個鏈結 … … 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-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) 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 鏈結串列的應用 ◎ 多項式的表示與運算 5x4 可表示為： 3-7 鏈結串列的應用 ◎ 多項式的表示與運算 使用鏈結串列表示多項式，每個非零項使用一個節點，每個節點包含兩個資料欄位：係數欄位和冪次欄位，以及一個鏈結欄位。節點結構可以宣告為： 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

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

/*============================================ 第三章: Page 3-8,3-10 ListInsert() 插入節點 ListDelete() 刪除節點 GetPreNode() 傳回指定節點之前一個節點 PrintList() 顯示節點內容 find_node_num() 找尋資料所在節點 GetFreeNode() 找尋空節點 table[MAX_NODE] 陣列鏈結串列 MAX_NODE 串列空間數目(陣列大小) ========================================= */

#include <iostream.h> #include <string.h> #include <stdlib.h> #define MAX_NODE 9 typedef struct ListNode { char data[8]; /*資料欄位*/ int next; }NODE; NODE table[MAX_NODE]={{"",3},{"USA",6},{"",-1}, {"ROC",1}, {"",-1},{"",-1},{"UK",7},{"USSR",0},{"",-1}}; int ListInsert(NODE [ ],char [ ],unsigned ); int GetPreNode(NODE [ ],int ); int find_node_num(NODE [ ],char *); void ListDelete(NODE [ ],int); void PrintList(NODE [ ]); unsigned GetFreeNode(NODE [ ]);

void main(void) { int choice=0, i, loopflag=1; char NewData[255], OldData[255]; system("cls"); cout << "原串列 :\n"; PrintList(table); while (loopflag) cout << "(1)插入節點,(2)刪除節點, (3) 離開 =>"; cin >> choice;

{case 1: cout << "\n請輸入欲插入之資料=>"; cin >> NewData; strupr(NewData); //TO UPPER cout << “請輸入欲插入那一資料之後 ( 輸入HEAD代表 成為第一個資料 ) =>"; cin >> OldData; strupr(OldData); if ( strcmp(OldData,"HEAD")==0) i=0; else if((i=find_node_num(table,OldData)) == -1) { cout << "找不到資料,插入失敗\n"; break; } if( (i>=0) && (ListInsert(table,NewData,i) == 0)) { cout << "串列已滿,插入失敗\n"; cout << "插入 " << NewData << " 之後的串列 :\n"; PrintList(table); break;

case 2: cout << "\n請輸入欲刪除那一資料=>"; cin >> OldData; strupr(OldData); if((i=find_node_num(table,OldData)) == -1) { cout << "找不到資料,刪除失敗\n"; break; } ListDelete(table,i); cout << "刪除 " << OldData << " 之後的串列 :\n"; PrintList(table); default: loopflag=0;

/*將資料插入串列中*/ int ListInsert(NODE table[ ],char d[ ],unsigned i) { unsigned EmptyNode; EmptyNode=GetFreeNode(table); if (EmptyNode == 0) return 0; strcpy(table [EmptyNode].data,d); table [EmptyNode].next=table[i].next; table[i].next=EmptyNode; return 1; }

/*刪除串列中一筆資料*/ void ListDelete(NODE table[],int i) { int Prenode; Prenode=GetPreNode(table,i); table[Prenode].next=table[i].next; table[i].next=-1; } /*尋找欲刪除處之上一個節點*/ int GetPreNode(NODE table[],int i) { int prenode=0,node=table[prenode].next; while(node != i && node !=0 ) { prenode=node; node=table[node].next; return (prenode);

/*顯示串列所有內容*/ void PrintList(NODE table[]) { int i; for(i = table[0].next;i != 0;i = table[i].next) cout << table[i].data << "\n"; } /*找尋資料之所在節點*/ int find_node_num(NODE table[],char *OldData) for(i=table[0].next; i!=0 && (strcmp(table[i].data,OldData)) != 0; i=table[i].next); if ( i==0 ) return -1; return i;

/*找空節點*/ unsigned GetFreeNode(NODE table[]) { unsigned i=1; for(;i <= MAX_NODE ;i ++) if(table[i].next == -1) return i; return 0; }