第4章 鏈結串列（Linked Lists） 4-1 動態記憶體配置-(6) 4-2 鏈結串列的基礎-(7)

Presentation on theme: "第4章 鏈結串列（Linked Lists） 4-1 動態記憶體配置-(6) 4-2 鏈結串列的基礎-(7)"— Presentation transcript:

1 第4章 鏈結串列（Linked Lists） 4-1 動態記憶體配置-(6) 4-2 鏈結串列的基礎-(7)
4-3 單向鏈結串列 – (7) 4-4 環狀鏈結串列 – (7)(8) 4-5 雙向鏈結串列 – (8) 4-6 鏈結串列的應用 - 多項式表示法 –(8) 2018/11/13 CH04-鏈結串列

2 4-1 動態記憶體配置-說明 動態記憶體配置不同於陣列的靜態記憶體配置
靜態記憶體配置是在編譯階段就配置記憶體空間， 動態記憶體配置是等到執行階段，才向作業系統要求配置所需的記憶體空間， 可以讓程式設計者靈活運用程式所需的記憶體空間。 在C語言<stdlib.h>標頭檔的標準函式庫提供兩個函數：malloc()和free()，可以配置和釋放程式所需的記憶體空間。 2018/11/13 CH04-鏈結串列

3 4-1 動態記憶體配置-malloc() malloc()函數：配置記憶體空間
fp = (資料型態*) malloc(sizeof(資料型態)); 上述語法因為函數傳回void通用型指標，所以需要加上型態迫換，將函數傳回的指標轉換成指定資料型態的指標， sizeof運算子可以計算指定資料型態的大小。 2018/11/13 CH04-鏈結串列

4 Malloc()函式 - 範例1 說明 配置一個浮點數變數的記憶空間，如下所示：
fp = (float *) malloc(sizeof(float)); fp是浮點數的指標變數 傳回值經過型態迫換成float指標後, 再指派給指標fp 如果記憶體不足的話函式回傳NULL 2018/11/13 CH04-鏈結串列

5 Malloc()函式 - 範例2 說明 結構與結構陣列也可以使用動態記憶體配置來配置所需要的記憶體空間，如下所示：
struct test *score; score=(struct test *) malloc(num*sizeof(struct test)); 上述程式碼在宣告結構指標score之後, 呼叫malloc()函式配置test結構陣列的記憶體空間 其大小為num*sizeof(struct test) num是結構陣列的元素個數!! 2018/11/13 CH04-鏈結串列

6 4-1 動態記憶體配置-free() free()函數：釋放配置的記憶體空間 free()函數可以釋放malloc()函數配置的記憶體空間，
例如：指標fp是一個指向malloc()函數傳回的浮點數記憶體空間的指標 (參考pp.4)， 呼叫free()函數釋放這塊記憶體，如下所示： free(fp); 上述程式碼的指標fp可以是float浮點數指標，也可以是malloc()函數傳回的其它資料型態指標、陣列或結構指標。 2018/11/13 CH04-鏈結串列

7 程式範例: Ch4-1.c 程式目的 使用動態記憶體配置的malloc()函式配置浮點數和結構陣列的記憶體空間來儲存學生的數學成績, 在計算後, 使用free函式釋放掉配置的記憶體空間!! 程式執行結果 請輸入學生人數3 請輸入第1位的成績.68 請輸入第2位的成績.89 請輸入第3位的成績.69 成績總分: 平均成績: 2018/11/13 CH04-鏈結串列

8 score=(struct test *)malloc(num*sizeof(struct test));
/* 配置成績陣列的記憶體 */ score=(struct test *)malloc(num*sizeof(struct test)); if ( score != NULL ) { /* 檢查指標 */ sum = 0; /* 讀取成績 */ for ( i = 0; i < num; i++ ) { ptr = &score[i]; /* 指向結構的指標 */ printf("請輸入第%d位的成績. ==> ", i+1); scanf("%d", &temp); ptr->math = temp; /* 指定數學成績 */ sum += temp; } /* 配置浮點數的記憶體 */ ave = (float *) malloc(sizeof(float)); *ave = (float) sum / (float) num; /* 計算平均 */ printf("成績總分: %6d\n", sum); printf("平均成績: %6.2f\n", *ave); free(ave); /* 釋回記憶體空間 */ free(score); } else printf("成績結構陣列的記憶體配置失敗!\n"); system("PAUSE"); return 0; } /* 程式範例: Ch4-1.c */ #include <stdio.h> #include <stdlib.h> /* 主程式 */ int main() { struct test { /* 宣告結構 */ int math; }; /* 結構陣列指標變數宣告 */ struct test *score, *ptr; float *ave; int i, num, sum, temp; printf("請輸入學生人數 ==> "); /* 讀取學生人數 */ scanf("%d", &num); 2018/11/13 CH04-鏈結串列

9 4-2 鏈結串列的基礎-說明 「有序串列」（Ordered List）或稱為「線性串列」（Linear List）是一種元素間擁有順序的集合，如下所示： (a0, a1, a2, …, an)，ai，0 <= i <= n 上述集合是一個線性串列， 如果是空的線性串列，表示串列中沒有任何元素，是使用( )空括號表示。 2018/11/13 CH04-鏈結串列

10 4-2 鏈結串列的基礎-範例 一些線性串列的範例，如下所示： 上述線性串列中的元素之間有前後關係的循序性!!
英文的月份：( Jan, Feb, March, …, Oct, Nov, Dec )。 英文的星期：( Mon, Tue, Wed, Thu, Fri, Sat, Sun )。 撲克牌的點數：( A, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K )。 樓層：( B2, B1, 1, 2, 3, 4, 5, 6 )。 生肖：( 鼠, 牛, 虎, …… , 狗, 猪 )。 上述線性串列中的元素之間有前後關係的循序性!! 例如: 二月(Feb)之後是三月(March), 之前是一月(Jan) 2018/11/13 CH04-鏈結串列

11 4-2 鏈結串列的基礎-運算 線性串列的相關運算，如下所示： length()：取得線性串列的長度。 get()：存取線性串列的第i個元素。
search()：從左到右，或從右到左走訪線性串列。 delete()：在線性串列第i個元素刪除元素。 insert()：在線性串列第i個元素插入元素。 2018/11/13 CH04-鏈結串列

12 4-2 鏈結串列的基礎-使用陣列實作線性串列 郵寄名單 陣列實作線性串列 2018/11/13 CH04-鏈結串列

13 4-2 鏈結串列的基礎-使用陣列實作線性串列(問題1)
複雜的新增與刪除運算 在新增或刪除名單時，因為陣列儲存的是循序且連續資料，所以在陣列中需要搬移大量元素，才能滿足同縣巿位在同一區段。 例如：在桃園巿新增江小魚，則王小美、李光明和周星星都需要依序往後搬移1個元素，才能將江小魚插入， 同理，刪除王大毛時，之後的所有元素也需要往前搬移。 2018/11/13 CH04-鏈結串列

14 4-2 鏈結串列的基礎-使用陣列實作線性串列(問題2)
浪費記憶體空間 因為並不知道名單有多少位，所以需要宣告一個很大的結構陣列來儲存名單， 如果最後只使用到幾個元素，就會造成大量記憶體空間的閒置。 2018/11/13 CH04-鏈結串列

15 4-2 鏈結串列的基礎-使用鏈結串列實作線性串列
「鏈結串列」（Linked Lists）是一種實作線性串列的資料結構。 在現實生活中，鏈結串列如同火車掛車廂以線性方式將車廂連結起來，每個車廂是鏈結串列的節點（Nodes），儲存線性串列的資料，車廂和車廂之間的鏈結，就是節點間的鏈結（Link）。如下圖所示： 2018/11/13 CH04-鏈結串列

16 4-2 鏈結串列的基礎-使用鏈結串列實作線性串列(實作)
用C語言建立鏈結串列是宣告一個結構作為節點，內含指標的成員變數來鏈結其它節點， 使用動態記憶體配置在執行階段配置節點所需的記憶體空間， 即可解決結構陣列實作上浪費記憶體的問題。 2018/11/13 CH04-鏈結串列

17 例如：使用鏈結串列建立的郵寄名單，筆者僅以編號（從大到小）代表名單的節點資料，郵寄名單的鏈結串列，如下圖所示：
每一個節點都是一個『結構變數』 節點擁有一個指標成員變數指向下一個指標的位址 first是指向鏈結串列開頭節點的指標 最後一個節點指向NULL  表示串列結束!!! 2018/11/13 CH04-鏈結串列

18 改用鏈結串列後之陣列問題說明 在串列中新增或刪除節點時 因為鏈結串列的存取是使用指標變數
所以可以在不搬移元素的情況下, 插入或刪除郵件名單(前範例)  解決陣列實作時資料搬移的問題!! 原因 : 只需要改變節點指標變數所指向的節點即可!! 2018/11/13 CH04-鏈結串列

19 4-3 單向鏈結串列 4-3-1 建立和走訪單向鏈結串列 4-3-2 刪除單向鏈結串列的節點 4-3-3 插入單向鏈結串列的節點
2018/11/13 CH04-鏈結串列

20 4-3 單向鏈結串列-說明 單向鏈結串列是最簡單的一種鏈結串列 因為節點指標都是指向同一個方向，依序從前一個節點指向下一個節點，
然後最後1個節點指向NULL，所以稱為單向鏈結串列，如下圖所示： 2018/11/13 CH04-鏈結串列

21 4-3 單向鏈結串列-標頭檔 01: /* 程式範例: Ch4-3.h */
02: struct Node { /* Node節點結構 */ 03: int data; /* 結構變數宣告 */ 04: struct Node *next; /* 指向下一個節點 */ 05: }; 06: typedef struct Node LNode; /* 串列節點的新型態 */ 07: typedef LNode *List; /* 串列的新型態List */ 08: List first = NULL; /* 串列的開頭指標first */ 09: /* 抽象資料型態的操作函數宣告 */ 10: extern void creatList(int len, int *array); 11: extern int isListEmpty(); 12: extern void printList(); 13: extern List searchNode(int d); 14: extern int deleteNode(List ptr); 15: extern void insertNode(List ptr, int d); 2018/11/13 CH04-鏈結串列

22 模組函式說明 10: extern void creatList(int len, int *array);
使用參數的陣列建立串列, 陣列的第1個元素是串列的最後1個元素;最後1個元素是串列的第1個元素 11: extern int isListEmpty(); 檢查串列是否為空的;如果是回傳1, 否則回傳0 12: extern void printList(); 走訪與顯示串列的節點資料 13: extern List searchNode(int d); 使用走訪方式搜尋串列中是否有參數的節點; 如果找到就回傳節點指標; 否則回傳NULL 14: extern int deleteNode(List ptr); 在串列中刪除參數節點指標的節點 15: extern void insertNode(List ptr, int d); 在串列中第1個參數節點指標位置之後, 插入第2個參數資料的節點 2018/11/13 CH04-鏈結串列

23 4-3-1 建立和走訪單向鏈結串列-建立(說明)
建立單向鏈結串列 在createList()函數是使用for迴圈將取得的陣列值建立成串列節點，每執行一次迴圈，就在串列開頭插入一個新節點，如下所示： for ( i = 0; i < len; i++ ) { newnode = (List) malloc(sizeof(LNode)); newnode->data = array[i]; newnode->next = first; first = newnode; } 2018/11/13 CH04-鏈結串列

24 4-3-1 建立和走訪單向鏈結串列-建立(圖例)
前頁程式碼的圖形說明 2018/11/13 CH04-鏈結串列

25 4-3-1 建立和走訪單向鏈結串列-走訪(說明)
單向鏈結串列的走訪 單向鏈結串列的「走訪」（Traverse）和一維陣列的走訪十分相似 其差異在於陣列是遞增索引值來走訪陣列，串列是使用指標運算來處理節點的走訪，如下所示： List current = first; // current是節點的指標 while ( current != NULL ) { ………….. current = current->next; // 每執行一次while迴圈, 就只向下一個節點, 直到到達串列最後的NULL為止 } 2018/11/13 CH04-鏈結串列

26 4-3-1 建立和走訪單向鏈結串列-走訪(圖例)
2018/11/13 CH04-鏈結串列

27 程式範例: createList.c與Ch4-3-1.c
程式目的 實作單向鏈結串列的模組函式: createList(), isListEmpty(), printList()與searchNode(), 接著使用陣列值建立單向鍊結串列, 然後輸入值搜尋串列和顯示串列內容!! 程式執行結果 原來的串列: [6][5][4][3][2][1] 串列是否為空的: 0 請輸入搜尋的郵寄編號(-1結束)3 串列包含節點[3] 請輸入搜尋的郵寄編號(-1結束)8 串列不含節點[8] 請輸入搜尋的郵寄編號(-1結束)-1 2018/11/13 CH04-鏈結串列

28 List current = first; /* 目前的串列指標 */
/* 函數: 顯示串列資料 */ void printList() { List current = first; /* 目前的串列指標 */ while ( current != NULL ) { /* 顯示主迴圈 */ printf("[%d]", current->data); current = current->next; /* 下一個節點 */ } printf("\n"); /* 函數: 搜尋節點資料 */ List searchNode(int d) { List current = first; /* 目前的串列指標 */ while ( current != NULL ) { /* 搜尋主迴圈 */ if ( current->data == d ) /* 是否找到資料 */ return current; /* 找到 */ return NULL; /* 沒有找到 */ /* 程式範例: createList.c */ /* 函數: 建立串列 */ void createList(int len, int *array) { int i; List newnode; for ( i = 0; i < len; i++ ) { /* 配置節點記憶體 */ newnode = (List) malloc(sizeof(LNode)); newnode->data = array[i]; /* 建立節點內容 */ newnode->next = first; first = newnode; } /* 函數: 檢查串列是否是空的 */ int isListEmpty() { if ( first == NULL ) return 1; else return 0; 2018/11/13 CH04-鏈結串列

29 printf("請輸入搜尋的郵寄編號(-1結束) ==> "); scanf("%d", &temp); /* 讀取節點值 */
while ( temp != -1 ) { printf("請輸入搜尋的郵寄編號(-1結束) ==> "); scanf("%d", &temp); /* 讀取節點值 */ if ( temp != -1 ) /* 搜尋節點資料 */ if ( searchNode(temp) != NULL ) printf("串列包含節點[%d]\n", temp); else printf("串列不含節點[%d]\n", temp); } system("PAUSE"); return 0; /* 程式範例: Ch4-3-1.c */ #include <stdio.h> #include <stdlib.h> #include "Ch4-3.h" #include "createList.c" /* 主程式 */ int main() { int temp; /* 宣告變數 */ int data[6]={ 1, 2, 3, 4, 5, 6 }; /* 建立串列的陣列 */ List ptr; /* 4-3-1: 建立, 走訪與搜尋串列 */ createList(6, data); /* 建立串列 */ printf("原來的串列: "); printList(); /* 顯示串列 */ printf("串列是否空的: %d\n", isListEmpty()); temp = 0; 2018/11/13 CH04-鏈結串列

30 4-3-2 刪除單向鏈結串列的節點-情況1 刪除串列的第1個節點：只需將串列指標first指向下一個節點，如下圖所示：
first = first->next; 2018/11/13 CH04-鏈結串列

31 4-3-2 刪除單向鏈結串列的節點-情況2 刪除串列的最後1個節點：只需將最後1個節點ptr的前一個節點指標指向NULL，如下圖所示：
while (current->next!=ptr) current = current->next; current->next = NULL; 2018/11/13 CH04-鏈結串列

32 4-3-2 刪除單向鏈結串列的節點-情況3(1) 刪除串列的中間節點：將刪除節點前一個節點的next指標，指向刪除節點下一個節點，
例如：刪除節點3，如下圖所示： 2018/11/13 CH04-鏈結串列

33 4-3-2 刪除單向鏈結串列的節點-情況3(2) 在執行刪除節點3操作後的串列圖形，如下所示：
while (current->next!=ptr) current = current->next; current->next = ptr->next; 2018/11/13 CH04-鏈結串列

34 程式範例: deleteNode.c與Ch4-3-2.c
程式目的 實作單向鏈結串列的deleteNode()函式, 然後輸入欲刪除的節點值, 在串列中分別刪除3種不同情況的節點!! 程式執行結果 原來的串列: [6][5][4][3][2][1] 請輸入刪除的郵寄編號(-1結束) 6 刪除節點: 6 刪除後串列: [5][4][3][2][1] 請輸入刪除的郵寄編號(-1結束) 3 刪除節點: 3 刪除後串列: [5][4][2][1] 請輸入刪除的郵寄編號(-1結束) 1 刪除節點: 1 刪除後串列: [5][4][2] 請輸入刪除的郵寄編號(-1結束) -1 2018/11/13 CH04-鏈結串列

35 int deleteNode(List ptr) { List current = first; /* 指向前一節點 */
* 程式範例: deleteNode.c */ /* 函數: 刪除節點 */ int deleteNode(List ptr) { List current = first; /* 指向前一節點 */ int value = ptr->data; /* 取得刪除的節點值 */ if ( isListEmpty() ) /* 檢查串列是否是空的 */ return -1; if (ptr==first || ptr==NULL) {/* 串列開始或NULL */ /* 情況1: 刪除第一個節點 */ first = first->next; /* 刪除第1個節點 */ } else { while (current->next!=ptr) /* 找節點ptr的前節點 */ current = current->next; if ( ptr->next == NULL ) /* 是否是串列結束 */ /* 情況2: 刪除最後一個節點 */ current->next = NULL; /* 刪除最後一個節點 */ else /* 情況3: 刪除中間節點 */ current->next = ptr->next; /* 刪除中間節點 */ } free(ptr); /* 釋放節點記憶體 */ return value; /* 傳回刪除的節點值 */ 2018/11/13 CH04-鏈結串列

36 #include <stdio.h> #include <stdlib.h> #include "Ch4-3.h"
/* 程式範例: Ch4-3-2.c */ #include <stdio.h> #include <stdlib.h> #include "Ch4-3.h" #include "createList.c" #include "deleteNode.c" /* 主程式 */ int main() { int temp; /* 宣告變數 */ int data[6]={ 1, 2, 3, 4, 5, 6 };/* 建立串列的陣列 */ List ptr; createList(6, data); /* 建立串列 */ printf("原來的串列: "); printList(); /* 顯示串列 */ 2018/11/13 CH04-鏈結串列

37 printf("請輸入刪除的郵寄編號(-1結束) ==> "); scanf("%d", &temp); /* 讀取郵寄編號 */
/* 4-3-2: 節點刪除 */ temp = 0; while ( temp != -1 ) { printf("請輸入刪除的郵寄編號(-1結束) ==> "); scanf("%d", &temp); /* 讀取郵寄編號 */ if ( temp != -1 ) { /* 搜尋節點資料 */ ptr = searchNode(temp); /* 找尋節點 */ if ( ptr != NULL ) { temp = deleteNode(ptr); /* 刪除節點 */ printf("刪除節點: %d\n", temp); printf("刪除後串列: "); printList(); /* 顯示刪除後串列 */ } system("PAUSE"); return 0; 2018/11/13 CH04-鏈結串列

38 4-3-3 插入單向鏈結串列的節點-情況1 將節點插入串列第1個節點之前：只需將新節點newnode的指標指向串列的第1個節點first，新節點就成為串列的第1個節點，如下圖所示： newnode->next = first; first = newnode; 2018/11/13 CH04-鏈結串列

39 4-3-3 插入單向鏈結串列的節點-情況2 將節點插在串列的最後1個節點之後：只需將原來串列最後1個節點的指標指向新節點newnode，新節點指向NULL，如下圖所示： ptr->next = newnode; newnode->next = NULL; 2018/11/13 CH04-鏈結串列

40 4-3-3 插入單向鏈結串列的節點-情況3(1) 將節點插在串列的中間位置：假設節點是插在p和q兩個節點之間，p是q的前一個節點，如下圖所示： 2018/11/13 CH04-鏈結串列

41 4-3-3 插入單向鏈結串列的節點-情況3(2) 只需將p指標指向新節點newnode，然後將新節點指標指向q，就可以插入新節點，如下圖所示： newnode->next=ptr->next; ptr->next = newnode; 2018/11/13 CH04-鏈結串列

42 程式範例: insertNode.c與Ch4-3-3.c
程式目的 實作單向鏈結串列的insertNode()函式, 然後輸入欲插入節點的位置與節點值, 在串列中分別插入3種不同情況的節點!! 程式執行結果 原來的串列: [6][5][4][3][2][1] 插入後串列: [50][6][5][4][3][2][1] 請輸入插入其後的郵寄編號(-1結束) 1 請輸入新的郵寄編號(0~100)10 插入後串列: [50][6][5][4][3][2][1][10] 請輸入插入其後的郵寄編號(-1結束) 6 請輸入新的郵寄編號(0~100) 8 插入後串列: [50][6][8][5][4][3][2][1][10] 請輸入插入其後的郵寄編號(-1結束) -1 2018/11/13 CH04-鏈結串列

43 /* 程式範例: insertNode.c */ /* 函數: 插入節點 */
void insertNode(List ptr, int d) { List newnode; /* 配置節點記憶體 */ newnode = (List) malloc(sizeof(LNode)); newnode->data = d; /* 指定節點值 */ if ( ptr == NULL ) { /* 情況1: 插入第一個節點 */ newnode->next = first; /* 新節點成為串列開始 */ first = newnode; } else { if ( ptr->next == NULL ) { /* 串列最後一個節點 */ /* 情況2: 插入最後一個節點 */ ptr->next = newnode; /* 最後指向新節點 */ newnode->next = NULL; /* 新節點指向NULL */ /* 情況3: 插入成為中間節點 */ newnode->next=ptr->next; /* 新節點指向下一節點 */ ptr->next = newnode; /* 節點ptr指向新節點 */ 2018/11/13 CH04-鏈結串列

44 #include <stdio.h> #include <stdlib.h> #include "Ch4-3.h"
* 程式範例: Ch4-3-3.c */ #include <stdio.h> #include <stdlib.h> #include "Ch4-3.h" #include "createList.c" #include "insertNode.c" /* 主程式 */ int main() { int temp; /* 宣告變數 */ int data[6]={ 1, 2, 3, 4, 5, 6 }; /* 建立串列的陣列 */ List ptr; createList(6, data); /* 建立串列 */ printf("原來的串列: "); printList(); /* 顯示串列 */ /* 4-3-3: 節點插入 */ temp = 0; insertNode(NULL, 50); /* 插入第一個節點 */ printf("插入後串列: "); printList(); /* 顯示插入後串列 */ 2018/11/13 CH04-鏈結串列

45 printf("請輸入插入其後的郵寄編號(-1結束) ==> "); scanf("%d", &temp); /* 讀取郵寄編號 */
while ( temp != -1 ) { printf("請輸入插入其後的郵寄編號(-1結束) ==> "); scanf("%d", &temp); /* 讀取郵寄編號 */ if ( temp != -1 ) { ptr = searchNode(temp); /* 找尋節點 */ if ( ptr != NULL ) printf("請輸入新的郵寄編號(0~100) ==> "); scanf("%d", &temp); /* 讀取新的郵寄編號 */ insertNode(ptr, temp); printf("插入後串列: "); printList(); /* 顯示插入後串列 */ } system("PAUSE"); return 0; 2018/11/13 CH04-鏈結串列

46 4-4 環狀鏈結串列-說明 如果將最後一個節點的指標改為指向單向鏈結串列開始的第1個節點 (不再指向NULL)，這種串列稱為「環狀鏈結串列」（Circular Lists）。 2018/11/13 CH04-鏈結串列

47 4-4 環狀鏈結串列-應用 (例) 電腦在處理程式的記憶體空間或輸出入緩衝區的記憶體就是使用環狀串列連接各節點
每一個節點就是一塊佔用或閒置的記憶體空間!! 環狀串列的完整範例程式Ch4-4.c 因與單向鏈結串列只差在將最後一個節點從指向NULL, 改為止向第一個節點!! 故未列完整程式碼於此!! 2018/11/13 CH04-鏈結串列

48 4-4 環狀鏈結串列-建立與走訪 環狀鏈結串列的建立只需將最後1個節點的last指標指向第1個節點，即可完成環狀鏈結串列的建立，如下所示：
last->next = first; 環狀鏈結串列的走訪檢查是否到串列結束的條件是current->next == first，如下所示： CList current = first; do { ……… current = current->next; } while ( current != first ); 2018/11/13 CH04-鏈結串列

49 4-4 環狀鏈結串列-插入節點 環狀鏈結串列插入與單向串列插入不同 所以環狀串列節點插入都是單向串列的中間節點插入
因為環狀串列皆指向下一個節點 所以環狀串列節點插入都是單向串列的中間節點插入 只有第一個節點是例外狀況!! 環狀串列的節點插入可以分成兩種狀況 將節點插入第1個節點之前成為串列開始 將節點插在串列中指定節點之後 2018/11/13 CH04-鏈結串列

50 4-4 環狀鏈結串列-插入節點 (情況1-步驟) 將節點插入第1個節點之前成為串列開始，可以分成三個步驟，如下所示：
Step 1： 將新節點newnode的next指標指向串列的第1個節點。 newnode->next = first; Step 2： 然後找到最後1個節點previous且將其指標指向新節點。 previous = first; while ( previous->next != first ) previous = previous->next; previous->next = newnode; Step 3： 將串列的開始指向新節點，新節點成為串列的第1個節點。 first = newnode; 2018/11/13 CH04-鏈結串列

51 4-4 環狀鏈結串列-插入節點 (情況1-圖例) 2018/11/13 CH04-鏈結串列

52 4-4 環狀鏈結串列-插入節點 (情況2-步驟) 將節點插在串列中指定節點之後，例如：將節點插在節點ptr之後，分成二個步驟，如下所示：
Step 1：將新節點newnode的next指標指向節點ptr的下一個節點。 newnode->next = ptr->next; Step 2：將節點ptr的指標指向新節點newnode。 ptr->next = newnode; 2018/11/13 CH04-鏈結串列

53 4-4 環狀鏈結串列-插入節點 (情況2-圖例) 2018/11/13 CH04-鏈結串列

54 4-4 環狀鏈結串列-刪除節點 (情況1-步驟) 刪除環狀串列的第1個節點可以分成二個步驟，如下所示：
Step 1： 將串列開始的first指標移至第2個節點。 first = first->next; Step 2： 將最後1個節點的previous指標指向第2個節點。 previous->next = ptr->next; 2018/11/13 CH04-鏈結串列

55 4-4 環狀鏈結串列-刪除節點 (情況1-圖例) 刪除環狀串列的第1個節點 2018/11/13 CH04-鏈結串列

56 4-4 環狀鏈結串列-刪除節點 (情況2-步驟) 刪除環狀串列的中間節點，例如：刪除節點ptr分成二個步驟，如下所示：
Step 1：先找到節點ptr的前一個節點previous。 while ( previous->next != ptr ) previous = previous->next; Step 2：將前節點的指標指向節點ptr的下節點。 previous->next = ptr->next; 2018/11/13 CH04-鏈結串列

57 4-4 環狀鏈結串列-刪除節點 (情況2-圖例) 刪除環狀串列的中間節點 2018/11/13 CH04-鏈結串列

58 4-5 雙向鏈結串列 4-5-1 雙向鏈結串列的建立與走訪 4-5-2 雙向鏈結串列內節點的插入 4-5-3 雙向鏈結串列內節點的刪除
2018/11/13 CH04-鏈結串列

59 4-5 雙向鏈結串列-說明 「雙向鏈結串列」（Doubly Linked Lists）是另一種常見的鏈結串列結構，這是一種允許無方向性走訪的鏈結串列。 所以，我們可以將兩個方向相反的單向鏈結串列結合起來，建立一種無方向性的鏈結串列，這就是雙向鏈結串列，如下圖所示： 2018/11/13 CH04-鏈結串列

60 4-5 雙向鏈結串列-標頭檔 01: /* 程式範例: Ch4-5.h */
02: struct Node { /* Node節點結構 */ 03: int data; /* 結構變數宣告 */ 04: struct Node *next; /* 指向下一個節點 */ 05: struct Node *previous; /* 指向前一個節點 */ 06: }; 07: typedef struct Node DNode; /* 雙向串列節點的新型態 */ 08: typedef DNode *DList; /* 雙向串列的新型態 */ 09: DList first = NULL; /* 雙向串列的開頭指標 */ 10: DList now = NULL; /* 雙向串列目前節點指標 */ 11: /* 抽象資料型態的操作函數宣告 */ 12: extern void creatDList(int len, int *array); 13: extern void printDList(); 14: extern void nextNode(); 15: extern void previousNode(); 16: extern void resetNode(); 17: extern DList readNode(); 18: extern void insertDNode(DList ptr, int d); 19: extern void deleteDNode(DList ptr); 2018/11/13 CH04-鏈結串列

61 模組函式說明 12: extern void creatDList(int len, int *array);
使用參數的陣列建立雙向串列 13: extern void printDList(); 走訪和顯示雙向串列的節點資料 14: extern void nextNode(); 移動now指標到串列的下一個節點 15: extern void previousNode(); 移動now指標到串列的前一個節點 16: extern void resetNode(); 重設now指標指向串列的第一個節點 17: extern DList readNode(); 傳回目前走訪節點的mow指標 18: extern void insertDNode(DList ptr, int d); 在串列中第一個參數節點指標位置之後, 插入第2個參數資料的節點 19: extern void deleteDNode(DList ptr); 在串列刪除參數節點指標的節點 2018/11/13 CH04-鏈結串列

62 4-5-1 雙向鏈結串列的建立與走訪-建立(步驟)
雙向鏈結串列比單向鏈結串列多一個指向前一個節點的指標， createDList()函數使用for迴圈建立雙向串列的其它節點，其作法是將每一個新節點都插入在雙向鏈結串列的最後， 一共有四個步驟，如下所示： Step 1：將新節點的next指標指向NULL。 Step 2：將新節點的previous指標指向before指標。 Step 3：將before指向節點的next指標指向新節點。 Step 4：before指標指向串列的最後1個節點。 2018/11/13 CH04-鏈結串列

63 4-5-1 雙向鏈結串列的建立與走訪-建立(圖例)
for ( i = 1; i < len; i++ ) { newnode = (DList) malloc(sizeof(DNode)); newnode->data = array[i]; newnode->next = NULL; //Step1 newnode->previous=before;//Step2 before->next=newnode; //Step3 before = newnode; //Step4 } 2018/11/13 CH04-鏈結串列

64 4-5-1 雙向鏈結串列的建立與走訪-走訪 雙向鏈結串列走訪比單向鏈結串列靈活，
因為可以分別使用next和previous指標從兩個方向進行走訪，模組函數nextNode()、previousNode()和resetNode()可以移動now指標來走訪雙向串列下一個或前一個節點。 在C++語言的STL（Standard Template Library）或Java語言的Collections物件， 雙向串列的相關走訪函數就是容器物件（Container）的「重複指標」（Iterators）。 2018/11/13 CH04-鏈結串列

65 4-5-2 雙向鏈結串列內節點的插入-情況1(步驟)
將節點插在串列中第1個節點之前：新節點將成為串列的第1個節點，其步驟如下所示： Step 1：將新節點newnode的next指標指向雙向串列的第1個節點。 newnode->next = first; Step 2：將原串列第1個節點的previous指標指向新節點。 first->previous = newnode; Step 3：將原串列的first指標指向新節點，新節點成為環狀串列的開始。 first = newnode; 2018/11/13 CH04-鏈結串列

66 4-5-2 雙向鏈結串列內節點的插入-情況1(圖例)
Step1: newnode->next = first; Step2: first->previous = newnode; Step3: first = newnode; 2018/11/13 CH04-鏈結串列

67 4-5-2 雙向鏈結串列內節點的插入-情況2(步驟)
將節點插在串列的最後：新節點是插入成為串列的最後1個節點，其步驟如下所示： Step 1：將最後1個節點ptr的next指標指向新節點newnode。 ptr->next = newnode; Step 2：將新節點的previous指標指向原串列的最後1個節點。 newnode->previous=ptr; Step 3：將新節點的next指標指向NULL。 newnode->next = NULL; 2018/11/13 CH04-鏈結串列

68 4-5-2 雙向鏈結串列內節點的插入-情況2(圖例)
2018/11/13 CH04-鏈結串列

69 4-5-2 雙向鏈結串列內節點的插入-情況3(步驟)
將節點插入成為串列的中間節點：如果節點是插在ptr節點之後，插入步驟如下所示： Step 1：將ptr節點next指向下一個節點的previous指標指向新節點。 ptr->next->previous = newnode; Step 2：新節點的next指標指向ptr節點next指標的下一個節點。 newnode->next = ptr->next; Step 3：新節點的previous指標指向ptr節點。 newnode->previous = ptr; Step 4：將ptr節點的next指標指向新節點。 ptr->next = newnode; 2018/11/13 CH04-鏈結串列

70 4-5-2 雙向鏈結串列內節點的插入-情況3(圖例)
Step 1：將ptr節點next指向下一個節點的previous指標指向新節點。 ptr->next->previous = newnode; Step 2：新節點的next指標指向ptr節點next指標的下一個節點。 newnode->next = ptr->next; Step 3：新節點的previous指標指向ptr節點。 newnode->previous = ptr; Step 4：將ptr節點的next指標指向新節點。 ptr->next = newnode; 2018/11/13 CH04-鏈結串列

71 4-5-3 雙向鏈結串列內節點的刪除-情況1 刪除串列的第1個節點：原串列的第2個節點就成為第1個節點，其步驟如下所示：
Step 1：將first指標指向第2個節點。 first = first->next; Step 2：將原串列第2個節點的previous指標指定成NULL。 first->previous = NULL; 2018/11/13 CH04-鏈結串列

72 4-5-3 雙向鏈結串列內節點的刪除-情況2 刪除最後1個節點：原串列最後第2個節點就成為最後1個節點，其步驟如下所示：
Step 1：將原串列的最後1個節點的前一個節點的next指標指定成NULL。 ptr->previous->next = NULL; 2018/11/13 CH04-鏈結串列

73 4-5-3 雙向鏈結串列內節點的刪除-情況3(步驟)
刪除串列內的中間節點：若刪除的是串列中的ptr節點，操作步驟，如下所示： Step 1：將ptr節點previous指標指向的前一個節點的next指標指向ptr節點的下一個節點。 ptr->previous->next = ptr->next; Step 2：將ptr節點next指標指向的後一個節點的previous指標指向ptr節點的前一個節點。 ptr->next->previous = ptr->previous; 2018/11/13 CH04-鏈結串列

74 4-5-3 雙向鏈結串列內節點的刪除-情況3(圖例)
Step 1：將ptr節點previous指標指向的前一個節點的next指標指向ptr節點的下一個節點。 ptr->previous->next = ptr->next; Step 2：將ptr節點next指標指向的後一個節點的previous指標指向ptr節點的前一個節點。 ptr->next->previous = ptr->previous; 2018/11/13 CH04-鏈結串列

75 4-6 鏈結串列的應用 - 多項式表示法(開頭節點串列)
開頭節點的觀念 是指在串列的開頭新增一個虛節點，這個節點並沒有儲存資料，只是作為串列的第1個節點，所有環狀串列的節點都是中間節點， 換句話說，刪除和插入的操作就只剩下第4-4節的第二種情況。(刪除環狀串列的中間節點) 2018/11/13 CH04-鏈結串列

76 4-6 鏈結串列的應用 - 多項式表示法(標頭檔)
01: /* 程式範例: Ch4-6.h */ 02: struct Node { /* Node節點結構 */ 03: float coef; int exp; /* 結構變數宣告 */ 04: struct Node *next; /* 指向下一個節點 */ 05: }; 06: typedef struct Node PNode; 07: typedef PNode *PList; /* 多項式串列的新型態 */ 08: /* 抽象資料型態的操作函數宣告 */ 09: extern PList createPoly(int len, float *array); 10: extern void printPoly(PList first); 2018/11/13 CH04-鏈結串列

77 成員函式說明 09: extern PList createPoly(int len, float *array);
使用參數陣列建立多項式串列, 陣列元素值是係數, 索引值是指數, 傳回值是串列的開頭指標!! 10: extern void printPoly(PList first); 顯示多項式, 參數是串列開頭指標!! 2018/11/13 CH04-鏈結串列

78 4-6 鏈結串列的應用 - 多項式表示法(多項式圖例)
使用含開頭節點的環狀串列來處理多項式，如下所示：(每一個項目都是PNode形態的節點) A(X)=7X4+3X2+4 B(X)=6X5+5X4+X2+7X+9 2018/11/13 CH04-鏈結串列

79 程式範例: createPoly.c與Ch4-6.c
題目 在C程式中實作多項式標頭檔的createPoly()和printPoly()函式, 然後使用陣列值建立多項式的鏈結串列, 並且顯示多項式的內容!! 程式輸出 7.0X^4+3.0X^2+4.0X^0 6.0X^5+5.0X^4+1.0X^2+7.0X^1+9.0X^0 2018/11/13 CH04-鏈結串列

80 /* 程式範例: createPoly.c */ /* 函數: 建立多項式的串列 */
PList createPoly(int len, float *array) { int i; PList first, ptr, newnode; /* 建立開頭節點 */ first = (PList) malloc(sizeof(PNode)); first->coef = 0.0; /* 建立開頭節點的內容 */ first->exp = -1; ptr = first; /* 前一個節點指標 */ for ( i = len-1; i >= 0; i-- ) { if ( array[i] != 0.0 ) { /* 配置節點記憶體 */ newnode = (PList) malloc(sizeof(PNode)); newnode->coef = array[i]; /* 建立節點的內容 */ newnode->exp = i; ptr->next = newnode; /* 連結新節點 */ ptr = newnode; /* 成為前一個節點 */ } ptr->next = first; /* 連結第1個節點, 建立環狀串列 */ return first; 2018/11/13 CH04-鏈結串列

81 void printPoly(PList first) {
/* 函數: 顯示多項式 */ void printPoly(PList first) { PList ptr = first->next; /* 串列真正的開頭 */ float c; int e; while ( ptr != first ) { /* 顯示主迴圈 */ c = ptr->coef; //印係數 e = ptr->exp; //印指數 printf("%3.1fX^%d", c, e); ptr = ptr->next; /* 下一個節點 */ if ( ptr != first ) printf("+"); } printf("\n"); 2018/11/13 CH04-鏈結串列

82 #include <stdio.h> #include <stdlib.h> #include "Ch4-6.h"
/* 程式範例: Ch4-6.c */ #include <stdio.h> #include <stdlib.h> #include "Ch4-6.h" #include "createPoly.c" /* 主程式 */ int main() { PList a = NULL; /* 多項式串列1的開頭指標 */ PList b = NULL; /* 多項式串列2的開頭指標 */ /* 建立多項式物件所需的陣列 */ float list1[6] = { 4, 0, 3, 0, 7, 0 }; float list2[6] = { 9, 7, 1, 0, 5, 6 }; a = createPoly(6, list1); /* 建立多項式串列1 */ b = createPoly(6, list2); /* 建立多項式串列2 */ printPoly(a); /* 顯示多項式1 */ printPoly(b); /* 顯示多項式2 */ system("PAUSE"); return 0; } 2018/11/13 CH04-鏈結串列

83 作業1 [課本4-53] 學習評量1, 2, 4, 6 紙本繳交 繳交期限 : 2009-1-9 晚上18:00前繳作業 (下課前交)
2018/11/13 CH04-鏈結串列

84 Ex: //#include "Ch.4-3.cpp" /* 主程式*/ int main() { int temp; /* 宣告變數*/
#include <stdio.h> #include <stdlib.h> #include "Ch4-3.h" void create(int len, int *array) { int i; List newnode; for ( i = 0; i < len; i++ ) { /* 配置節點記憶體*/ newnode = (List) malloc(sizeof(LNode)); newnode->data = array[i]; /* 建立節點內容*/ newnode->next = first; first = newnode; } /* 函數: 檢查串列是否是空的*/ int isListEmpty() { if ( first == NULL ) return 1; else return 0; /* 函數: 顯示串列資料*/ void printList() { List current = first; /* 目前的串列指標*/ while ( current != NULL ) { /* 顯示主迴圈*/ printf("[%d]", current->data); current = current->next; /* 下一個節點*/ printf("\n"); /* 函數: 搜尋節點資料*/ List searchNode(int d) { List current = first; /* 目前的串列指標*/ while ( current != NULL ) { /* 搜尋主迴圈*/ if ( current->data == d ) /* 是否找到資料*/ return current; /* 找到*/ return NULL; /* 沒有找到*/ //#include "Ch.4-3.cpp" /* 主程式*/ int main() { int temp; /* 宣告變數*/ int data[6]={ 1, 2, 3, 4, 5, 6 }; /* 建立串列的陣列*/ List ptr; /* 4-3-1: 建立, 走訪與搜尋串列*/ create(6, data); /* 建立串列*/ printf("原來的串列: "); printList(); /* 顯示串列*/ printf("串列是否空的: %d\n", isListEmpty()); temp = 0; while ( temp != -1 ) { printf("請輸入搜尋的郵寄編號(-1結束) ==> "); scanf("%d", &temp); /* 讀取節點值*/ if ( temp != -1 ) /* 搜尋節點資料*/ if ( searchNode(temp) != NULL ) printf("串列包含節點[%d]\n", temp); else printf("串列不含節點[%d]\n", temp); } system("PAUSE"); return 0; 2018/11/13 CH04-鏈結串列

85 Ex: Ch4-3.h /* 程式範例: Ch4-3.h */ struct Node { /* Node節點結構*/
int data; /* 結構變數宣告*/ struct Node *next; /* 指向下一個節點*/ }; typedef struct Node LNode; /* 串列節點的新型態*/ typedef LNode *List; /* 串列的新型態List */ List first = NULL; /* 串列的開頭指標first */ /* 抽象資料型態的操作函數宣告*/ void create(int len, int *array); int isListEmpty(); void printList(); List searchNode(int d); // extern int deleteNode(List ptr); //extern void insertNode(List ptr, int d); 2018/11/13 CH04-鏈結串列

86 2018/11/13 CH04-鏈結串列

87 程式範例: Ch4-6.c /* 程式範例: Ch4-6.c */ #include <stdio.h>
#include <stdlib.h> #include "Ch4-6.h" //#include "createPoly.c" /* 主程式*/ int main() { PList a = NULL; /* 多項式串列的開頭指標*/ PList b = NULL; /* 多項式串列的開頭指標*/ /* 建立多項式物件所需的陣列*/ float list1[6] = { 4, 0, 3, 0, 7, 0 }; float list2[6] = { 9, 7, 1, 0, 5, 6 }; a = createPoly(6, list1); /* 建立多項式串列*/ b = createPoly(6, list2); /* 建立多項式串列*/ printPoly(a); /* 顯示多項式*/ printPoly(b); /* 顯示多項式*/ system("PAUSE"); return 0; } 2018/11/13 CH04-鏈結串列

88 /* 程式範例: createPoly.c */
/* 函數: 建立多項式的串列*/ #include <stdio.h> #include <stdlib.h> #include "Ch4-6.h" //#include "createPoly.c" PList createPoly(int len, float *array) { int i; PList first, ptr, newnode; /* 建立開頭節點*/ first = (PList) malloc(sizeof(PNode)); first->coef = 0.0; /* 建立開頭節點的內容*/ first->exp = -1; ptr = first; /* 前一個節點指標*/ for ( i = len-1; i >= 0; i-- ) { if ( array[i] != 0.0 ) { /* 配置節點記憶體*/ newnode = (PList) malloc(sizeof(PNode)); newnode->coef = array[i]; /* 建立節點的內容*/ newnode->exp = i; ptr->next = newnode; /* 連結新節點*/ ptr = newnode; /* 成為前一個節點*/ } ptr->next = first; /* 連結第個節點, 建立環狀串列*/ return first; /* 函數: 顯示多項式*/ void printPoly(PList first) { PList ptr = first->next; /* 串列真正的開頭*/ float c; int e; while ( ptr != first ) { /* 顯示主迴圈*/ c = ptr->coef; //印係數 e = ptr->exp; //印指數 printf("%3.1fX^%d", c, e); ptr = ptr->next; /* 下一個節點*/ if ( ptr != first ) printf("+"); } printf("\n"); 2018/11/13 CH04-鏈結串列

89 /* 程式範例: Ch4-6.h */ /* 程式範例: Ch4-6.h */ struct Node { /* Node節點結構*/
float coef; int exp; /* 結構變數宣告*/ struct Node *next; /* 指向下一個節點*/ }; typedef struct Node PNode; typedef PNode *PList; /* 多項式串列的新型態*/ /* 抽象資料型態的操作函數宣告*/ extern PList createPoly(int len, float *array); extern void printPoly(PList first); 2018/11/13 CH04-鏈結串列