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

Presentation on theme: "資料結構與演算法 第四章　鍵結串列 徐熊健."— Presentation transcript:

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

2 目錄 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　Ｃ語言的指標

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

4 範例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

5 範例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

6 範例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

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

8 程式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，它成為鍵結串列的基本型態，可稱之為節點。

9 範例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 }

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

11 程式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 }

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

13 程式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}

14 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)的時間。

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

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

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); p→link = b_first ; return a_first ; 15 } 16 }

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

19 程式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 ｝

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

21 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

22 程式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 }

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

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

25 程式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為環狀串列的節點數。

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

27 程式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 }

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

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

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

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

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

33 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

34 程式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 }

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

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

37 程式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 }

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

39 程式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 }

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

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

42 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。

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

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