資料結構與演算法 第四章　鍵結串列 徐熊健

目錄 4.1 串列與鍵結串列 4.2 動態配置之鍵結串列 4.3 鍵結堆疊 4.4 鍵結佇列 4.5 環狀串列 4.6 雙向鍵結串列控制 4.1　串列與鍵結串列 4.2　動態配置之鍵結串列 4.3　鍵結堆疊 4.4　鍵結佇列 4.5　環狀串列 4.6　雙向鍵結串列控制 4.7　Ｃ語言的指標

4.1　串列與鍵結串列 串列 (list) 的抽象觀念是一組相同資料型態元素的有序集合。與陣列不同處在於：它不必要存在唯一的註標與每一元素相互對應 。 「鍵結串列」 (linked list) 則屬於非循序的儲存結構，邏輯上相鄰的二項資料，在記憶體中的實際配置不需要彼此相鄰。如果資料的引用並不強調實體配置中的連續性，或不必要賦予每一元素唯一的註標，鍵結串列可能是比較好的選擇。在作業系統中利用鍵結串列，掌握動態配置 (dynamic allocation) 所需空間的需求，更是重要的技巧。

範例4-2 以陣列存放串列資料的資料搬移狀況 假設該串列為當天水果商家出售水果之類別。 C[0] C[1] C[2] C[3] C[4] 範例4-2　以陣列存放串列資料的資料搬移狀況 假設該串列為當天水果商家出售水果之類別。 C[0] C[1] C[2] C[3] C[4] apple cherry mango peach strawberry 若“apple”賣完，則陣列將會改變如下： C[0] C[1] C[2] C[3] C[4] cherry mango peach strawberry 又若“banana”到貨，則陣列又會有如下之改變： C[0] C[1] C[2] C[3] C[4] banana cherry mango peach strawberry

範例4-3 利用link陣列掌握data陣列的資料順序 使用了二個陣列data和link來存放水果的資訊。data內存放資料，link內則存放該資料的下一筆資料註標位置；另外再用一個額外的註標head，記著第一項資料在data陣列中的位置。 head=0 [0] [1] [2] [3] [4] data apple cherry mango peach strawberry link 1 2 3 4 -1 若刪除“apple”則改變如下： head = link[head]; head=1 [0] [1] [2] [3] [4] data apple cherry mango peach strawberry link 1 2 3 4 -1

範例4-3 (續) 接著刪除“mango”將有以下改變： [0] [1] [2] [3] [4] data apple cherry 範例4-3　(續) 接著刪除“mango”將有以下改變： link[1] = link[2]; head=0 [0] [1] [2] [3] [4] data apple cherry mango peach strawberry link 1 3 4 -1 新增一資料“orange”： data[0] = “orange”;　　link[0] = link[1];　　link[1] = 0; head=0 [0] [1] [2] [3] [4] data orange cherry mango peach strawberry link 3 4 -1

4.2 動態配置之鍵結串列 鍵結串列有順序的關係，包括至少二種類型的資訊： 內含的元素。 下一項元素所在位置的資訊。 4.2　動態配置之鍵結串列 鍵結串列有順序的關係，包括至少二種類型的資訊： 內含的元素。 下一項元素所在位置的資訊。 鍵結是由指標或位址來構成，比起陣列link的使用更具一般性。

程式4-1 結構的宣告 1 define maxchar 20 2 struct FruitType 3 { char name[maxchar]; 4 struct FruitType *link; 5 }; 6 struct FruitType *head; 在程式4-1第2~5行中我們宣告了新的資料型態struct FruitType，它包括了一組長度為20的字元name，和指向struct FruitType此型態的指標（位址）*link，它成為鍵結串列的基本型態，可稱之為節點。

範例4-5 10 20 程式4-2 1 struct node 2 { int data; 3 struct node *next; first 程式4-2 1 struct node 2 { int data; 3 struct node *next; 4 }; 5 struct node *first; 6 void construct() 7 { first = (node *) malloc (sizeof(node)); // 8 first->data = 10; 9 first->next = (node *) malloc (sizeof(node)); 10 first->next->data = 20; 11 first->next->next = NULL; 12 }

4.2.1 新增資料至節點並插入節點至串列中 以下動畫表現出新增資料至節點並插入節點之串列中。 p … x 4.2.1　新增資料至節點並插入節點至串列中 以下動畫表現出新增資料至節點並插入節點之串列中。 p … x 取消p->next（令之為q）； 將x->next改為q（原來的p->next）； 將p->next改為x。

程式4-3 新增資料element至節點x中並插入節點x至串 列中p節點之後 1 struct node 2 { int data; 3 struct node *next; 4 }; 5 void InsertAfter(struct node *p; int element) 6 { node *x; 7 x =(struct node *) malloc (sizeof(node)); 8 x->data = element; 9 if (p==NULL) 10 { first = x; 11 x->next = NULL; 12 return; 13 } 14 x->link = p->link; 15 p->link = x; 16 return; 17 }

4.2.2 刪除鍵結串列中的節點 以下為刪除鍵結串列中的節點之概念圖： p … 4.2.2　刪除鍵結串列中的節點 以下為刪除鍵結串列中的節點之概念圖： p …  p->next（令之為q）改成q->next； 將當初動態配置而得的節點q（原來的p->next）還給系統。

程式4-4　刪除串列中p節點之後的節點 1 struct node 2 { int data; 3 struct node *next; 4 }; 5 int DeleteAfter(node *p) 6 { node *q; 7 q = p->next; 8 p->next = q->next; 9 int item =q->data; 10 free(q); 11 return item; 12}

4.2.3 尋找鍵結串列中的資料 程式4-5尋找鍵結串列中的資料 4.2.3　尋找鍵結串列中的資料 程式4-5尋找鍵結串列中的資料 1 struct node 2 { int data; 3 struct node *next; 4 }; 5 struct node *first; 6 struct node * SearchData(int target) 7 { node *p; 8 p = first; 9 while ((p!=NULL) && (p->data!=target)) p = p->next; 10 if (p->data == target) return (p); 11 return NULL; 12 } 在鍵結串列中，搜尋某特定資料在最差情況下，得花O(n)的時間，其中n指的是鍵結串列的節點個數。 一旦插入或刪除的節點位置已知，則執行插入或刪除只需O(1)的時間。

4.2.4 在串列最後新增節點 程式4-6在鍵結串列最後新增節點，last指在串列最後的節點 1 struct Node 4.2.4　在串列最後新增節點 程式4-6在鍵結串列最後新增節點，last指在串列最後的節點 1 struct Node 2 { int data; 3 struct Node * link; 4 } 5 struct Node * first， *last; 6 void AttachDataToList(int element) 7 { struct Node *p; 8 p = (struct Node *) malloc (sizeof (struct Node)) 9 p->data = element; p->link = NULL; 10 if (first == NULL) first = last = p ; 11 else 12 { last->link =p; 13 last = p; 14 } 15 }

4.2.5 反向串接一串列 程式4-7反向串接一串列 1 struct Node 2 { int data; 4.2.5　反向串接一串列 「鍵結串列的指標反向連接」將使原來串列內資料的順序完全對調。 程式4-7反向串接一串列 1 struct Node 2 { int data; 3 struct Node *link; 4 } 5 struct Node *first; 6 void Invert（） 7 { struct Node *r， *s， *t ; 8 r = first; 9 s = NULL; 10 while （r != NULL） 11 { t = s; 12 s = r; 13 r = r->link; 14 s->link = t; 15 } 16 first = s; 17 }

4.2.6 串接兩個鍵接串列 程式4-8串接兩個鍵接串列 1 struct Node 2 { int data; 4.2.6　串接兩個鍵接串列 程式4-8串接兩個鍵接串列 1 struct Node 2 { int data; 3 struct Node *link; 4 } 5 struct Node *a_first, *b_first, first; 6 struct Node * Concatenate 7 (struct Node * a_first, struct Node * b_first); 8 { struct Node *p ; 9 if (a_first == NULL) 10 resturn b_first ; 11 else 12 { for(p=first; p->link!=NULL; p=p->link); 13 p→link = b_first ; 14 return a_first ; 15 } 16 }

4.3　鍵結堆疊 利用陣列來實作堆疊的確方便，但是陣列在宣告時即得定義大小，宣告太大形成空間的浪費，宣告太小又怕不敷使用。改用動態配置的鍵結堆疊，即可解決使用陣列造成的缺點。 程式4-9鍵結堆疊 1 Struct StackNode 2 ｛ int data; 3 struct StackNode *link; 4 ｝ 5 struct StackNode *top;

程式4-9鍵結堆疊(續) 6 struct Stacknode *NewNode(int element) 7 ｛ struct StackNode *p; 8 p = (struct StackNode *) malloc (sizeof(StacdNode)); 9 p->data = elemeut; 10 p->link = NULL; 11 return p; 12 } 13 void PushStack(int element) 14 { struct StackNode *x ; 15 x = NewNode(element); 16 if (top==NULL) top = x; 17 else 18 ｛ x->link = top; 19 top ＝ x; 20 ｝ 21 ｝

鍵結堆疊執行push和pop的過程 : (a) push x至空堆疊 (b) push x至堆疊 (c) pop堆疊 top top x

4.4 鍵結佇列 程式4-10鍵結佇列 1 struct QueueNode 2 { char data； 4.4　鍵結佇列 程式4-10鍵結佇列 1 struct QueueNode 2 { char data； 3 struct QueueNode *next； 4 ｝ 5 struct QueueNode *front, *rear； 6 struct QueueNode * NewQNode (char element) 7 { struct QueueNode *p; 8 p = (struct QueueNode *) malloc (sizeof(QueueNode )); 9 p->data = element; 10 P->next = NULL; 11 } 12 void AddQueue(char element) 13 { struct QueueNode *p; 14 p = NewQNode(element); 15 if (rear == NULL) 16 front = p; 17 else

程式4-10鍵結佇列(續) 18 rear->next = p; 19 rear = p; 20 } 20 } 21 char DeleteQueue() 22 { struct QueueNode *p; 23 char element; 24 if (front == NULL) 25 { QueueEmpty( ); 26 return ”#”; 27 } 28 else 29 { p = front; 30 front = front->next; 31 element = p->data; 32 free(p); 33 return element; 34 } 35 }

鍵結佇列執行新增和刪除的過程 front front ： (a) 新增節點至空佇列 (b) 新增節點至佇列 (c) 刪除佇列節點 p rear rear p rear rear rear

4.5 環狀串列 環狀串列比起單向串列的好處在於： 從串列中的任何一個節點開始皆可將此串列走訪一次。 4.5　環狀串列 環狀串列比起單向串列的好處在於： 從串列中的任何一個節點開始皆可將此串列走訪一次。 可是這種串列在遇到「在串列最前加入新節奌」的需求時，倒顯得棘手。

程式4-11 在環狀串列中新增最前節點 很顯然地，這個需求得走訪所有節點，時間複雜度為O(n)，其中n為環狀串列的節點數。 程式4-11　在環狀串列中新增最前節點 1 struct node 2 { int data; 3 struct node *next; 4 } 5 struct node *first; 6 void InsertFirst(struct node *x) 7 { struct node *p; 8 if (first == NULL) 9 { first = x; 10 first->next =first; 11 } 12 else 13 { p = first; 14 while (p->next!=first) p = p->next; 15 p->next=x; 16 x->next =first; 17 first =x; 18 } 19 } 很顯然地，這個需求得走訪所有節點，時間複雜度為O(n)，其中n為環狀串列的節點數。

在環狀串列中新增最前節點（虛線為更動的指標）

程式4-12 在環狀串列中（有last指標指 向結尾節點）新增最前節點 6 void InsertFirst(struct node *x) 7 { if (last == NULL ) 8 { last = x; 9 last->next= last ; 10 } 11 else 12 { x->next =last->next; 13 last->next =x; 14 } 15 }

在環狀串列中（有last指標指向結尾節點）新增最前節點

以空節點為首之環狀串列 這種用一個空節點當做環狀串列的第一個節點的設計，可使「在串列最前加入新節奌」的需求變得簡單，此時「串列最前」實即first指標之後。 在鍵結串列中搭配使用空節點，常可使程式碼更具一般化，省下邊界情況(boundary condition) 的檢測。

程式4-13 在以空節點為首之環狀串列中新增最前節點 程式4-13　在以空節點為首之環狀串列中新增最前節點 6 void InsertFront (struct node *x ) 7 { x->next = first→next; 8 first->next =x; 9 }

4.6 雙向鏈結串列控制 以上所介紹的鏈結串列，不論是線性或是環狀的，每個節點都只有一個鏈結指標，我們只能朝一個方向走訪其他節點； 4.6　雙向鏈結串列控制 以上所介紹的鏈結串列，不論是線性或是環狀的，每個節點都只有一個鏈結指標，我們只能朝一個方向走訪其他節點； 若有反向走回的需求，單向線性或單向環狀串列將無法有效率地解決。於是有雙向鏈節串列 (doubly linked list) 孕育而生。

4.6 雙向鏈結串列控制 (續) 每個節點皆有兩個鏈節指標，分別指向該節點的前一個和下一個節點。 4.6　雙向鏈結串列控制 (續) 每個節點皆有兩個鏈節指標，分別指向該節點的前一個和下一個節點。 第一個節點的『前指標』和最後一個節點的『後指標』皆為NULL表示正是第一個和最後一個節點。 若將第一個節點的『前指標』指向最後一個節點，最後一個節點的『後指標』指向第一個節點，則形成環狀雙向鏈結串列

4.6.1 新增資料至環狀雙向鍵結節點 程式4-14 雙向鏈結串列的節點宣告 1 struct Dnode 4.6.1　新增資料至環狀雙向鍵結節點 程式4-14　雙向鏈結串列的節點宣告 1 struct Dnode 2 { struct Dnode *prev; 3 int data; 4 Dnode *next; 5 } 6 struct Dnode *head

程式4-15 產生新雙向鏈結節點 1 Dnode NewDnode(int element) 2 { Dnode *p; 程式4-15　產生新雙向鏈結節點 1 Dnode NewDnode(int element) 2 { Dnode *p; 3 p=(struct Dnode *) malloc(sizeof(Dnode))； 4 p->data=element； 5 p->prev=NULL； 6 p->next=NULL； 7 return p； 8 }

4.6.2 搜尋環狀雙向鏈結串列中的資料 程式4-16 搜尋環狀雙向鏈結串列中的資料 4.6.2　搜尋環狀雙向鏈結串列中的資料 程式4-16　搜尋環狀雙向鏈結串列中的資料 1 struct Dnode *SearchDnodeList(int element) 2 { Dnode *p； 3 if (head==NULL) 4 SearchEmptyList(); 5 else 6 { p = head; 7 while ((p->data!=element)&& (p->next!=head)) 8 p = p->next; 9 if (p->data==element) return p; 10 } 11 return NULL; 12 }

4.6.3揷入節點至環狀雙向鏈結串列 可知有四個鏈結指標會有異動：  p->prev = x ;  p->next = x->next ;  x->next->prev = p ;  x->next = p ;

程式4-17 揷入節點至環狀雙向鏈結串列中 1 void InsertDList(struct Dnode *x , 程式4-17　揷入節點至環狀雙向鏈結串列中 1 void InsertDList(struct Dnode *x , struct Dnode *p) 2 { if (x==NULL) 3 { p->prev = p; 4 p->next = p; 5 head = p; 6 } 7 else 8 { p->prev = x; 9 p->next = x->next; 10 x->next->prev = p; 11 x->next = p; 12 } 13 }

4.6.4 刪除雙向鏈結串列的一個節點 可知，異動的鏈結指標有兩處： 4.6.4　刪除雙向鏈結串列的一個節點 可知，異動的鏈結指標有兩處：  x->prev->next = x->next ;  x->next->prev = x->prev ;

程式4-18 刪除雙向鏈結串列中的一個節點 1 void DeleteDList(struct Dnode *x) 程式4-18　刪除雙向鏈結串列中的一個節點 1 void DeleteDList(struct Dnode *x) 2 { if (x==NULL) 3 DeleteEmptyList(); 4 else if ((x==head) && (head->next==head)) 5 head = NULL ; 7 else 8 { x->prev->next = x->next ; 9 x->next->prev = x->prev ; 10 } 11 free(x); 12 }

4.6.5 包含開頭空節點的鍵結串列 程式4-19 環狀雙向鍵結串列（含開頭空節點）新增和刪除節點 4.6.5　包含開頭空節點的鍵結串列 程式4-19　環狀雙向鍵結串列（含開頭空節點）新增和刪除節點 1 void InsertHDList(struct Dnode *x， struct Dnode *p) 2 { p->prev = x ; 3 p->next = x->next ; 4 x->next->prev = p ; 5 x->next = p ; 6 } 7 void DeleteHDList(truct Dnode *x) 8 { if (x == first) 9 DeleteEmptyList(); 10 else 11 { x->prev->next = x->next; 12 x->next->prev = x->prev; 13 free(x); 14 } 15 }

4.7 C語言的指標 在C語言中，指標 (pointer) 是個存放位址 (address) 的變數。 指標在運用的時候，可能與位址、程序中的參數以及陣列間有密切的關係。

4.7.1 指標與位址 &x即為整數變數x的位址A0A0，p = &x則把位址A0A0指定給整位址變數p。所以現在x是5，*p也是5。 4.7.1　指標與位址 &x即為整數變數x的位址A0A0，p = &x則把位址A0A0指定給整位址變數p。所以現在x是5，*p也是5。 整數*p可解讀成：「以p的內容為位址，取出該位址的整數內容，令其為*p」。 在此例中，p的內容為A0A0，取出位址A0A0的整數內容即為5。&x則可解讀為：「取出整數變數x在記憶體中的位址，令之為&x」。 在此例中，x為5，而&x是A0A0 　。同理p為A0A0，而&p為A0D0。

4.7.2 指標與程序參數 程式4-20 錯誤的資料對調 1 void swap(int x, int y) 2 { int temp; 4.7.2　指標與程序參數 程式4-20　錯誤的資料對調 1 void swap(int x, int y) 2 { int temp; 3 temp = x; 4 x = y; 5 y = temp; 6 } 程式4-21　資料對調 1 void swap(int *px, int *py) 2 { int temp; 3 temp = *px; 4 *px = *py; 5 *py = temp; 6 }

4.7.3　指標與陣列 當陣列名稱要傳入程序中時，其實傳的即為陣列的起始位址。程式4-22是個計算字串長度的程序，它用字元位址指標變數來存放傳入的字元位址。 程式4-22　計算字串長度 1 int strlen(char *s) 2 { int n; 3 for (n=0; *s!=’\0’; s++) n++; 4 return n; 5 }