4.1 單項鏈結串列 4.2 環狀串列 4.3 雙向鏈結串列 4.4 鏈結串列之應用

Presentation on theme: "4.1 單項鏈結串列 4.2 環狀串列 4.3 雙向鏈結串列 4.4 鏈結串列之應用"— Presentation transcript:

1 4.1 單項鏈結串列 4.2 環狀串列 4.3 雙向鏈結串列 4.4 鏈結串列之應用
Chapter 4 鏈結串列 4.1 單項鏈結串列 4.2 環狀串列 4.3 雙向鏈結串列 4.4 鏈結串列之應用

2 鏈結串列 鏈結串列（linked list）是由許多節點所組成的，在加入和刪除功能上比陣列容易許多。
鏈結串列可分為單向鏈結串列（single linked list）、環狀串列（circular linked list）及雙向鏈結串列（doubly linked list），本章的目標旨在如何學習到每一種鏈結串列的加入與刪除，而這些加入與刪除的動作，又可針對串列首、串列尾或串列的某個特定的節點。

3 4.1 單向鏈結串列 以陣列方式存放資料時，若要插入（insert）或刪除（delete）某一節點（node）就倍感困難了，如在陣列中已有a,b,d,e四個元素，現將c加入陣列中，並按字母順序排列，方法就是d,e往後一格，然後將c插入；而刪除一元素，也必須挪移元素才不會浪費空間，有無方法來改善此一問題呢？這就是本章所要探討的鏈結串列（linked list）。

4 4.1 單向鏈結串列 鏈結串列在加入與刪除皆比陣列來得簡單容易，因為只要利用指標（pointer）加以處理即可。
4.1 單向鏈結串列 鏈結串列在加入與刪除皆比陣列來得簡單容易，因為只要利用指標（pointer）加以處理即可。 假設鏈結串列中每個節點（node）的資料結構有二欄，分別是資料（data）欄和鏈結（next）欄　　 ，若將節點結構定義為struct node 型態，則表示如下：

5 4.1 單向鏈結串列 如串列 A={a, b, c, d}，其資料結構如下：
4.1 單向鏈結串列 如串列 A={a, b, c, d}，其資料結構如下： head：指向串列前端的指標，通常假設此節點的data欄是空的亦即不放資料，這在一些運作上有其方便之處。

6 4.1 單向鏈結串列 加入動作 1.加入於串列的前端： 假設有一串列如下：

7 4.1 單向鏈結串列 有一節點x將加入於串列的前端，其步驟如下：
4.1 單向鏈結串列 有一節點x將加入於串列的前端，其步驟如下： x=(struct node*) malloc(sizeof(struct node));

8 4.1 單向鏈結串列 (x->next=head->next; /* */ 

9 4.1 單向鏈結串列 head->next=x; /* */ 

10 4.1 單向鏈結串列 2.加入於串列的尾端： 假設有一串列如下：

11 4.1 單向鏈結串列 將一節點x加入於串列的尾端，其步驟如下：
4.1 單向鏈結串列 將一節點x加入於串列的尾端，其步驟如下： x=(struct node *)malloc(sizeof(struct node)); x->next=NULL;

12 4.1 單向鏈結串列 此時必須追蹤此串列的尾端在那兒，利用下列的片段程式 便可找到串列的尾端。

13 4.1 單向鏈結串列 p->next=x;

14 4.1 單向鏈結串列 加入在串列某一特定節點的後面 假設有一單向鏈結串列，按data欄位由大到小排列之。

15 4.1 單向鏈結串列 今有一節點ptr之data欄位值為75，欲加入到上述的串列中。首先我們必須找到插入的地方，可想而知75應插入到80和70之間，因此可用下述的片段程式執行之

16 4.1 單向鏈結串列 利用prev和current二個指標來追蹤，prev會緊跟在current節點之後

17 4.1 單向鏈結串列 接下來的動作：就是將ptr指向節點插在prev的後面 ptr->next=current; /*  */ prev->next=ptr; /*  */  

18 4.1 單向鏈結串列 刪除動作 刪除串列的前端節點 假設有一串列如下：

19 4.1 單向鏈結串列 只要幾個步驟便可達成目的： p=head->next; head->next=p->next;

20 4.1 單向鏈結串列 free(p); 經由free(p)便可將p節點回收。

21 4.1 單向鏈結串列 刪除串列的最後節點： 假設有一串列如下：

22 4.1 單向鏈結串列 此時必須先追蹤尾端及尾端的前一個 節點在那兒，步驟如下： p=head->next;

23 4.1 單向鏈結串列 prev->next=NULL; free(p);

24 4.1 單向鏈結串列 刪除某一特定的節點： 刪除某一特定的節點也必須利用二個 指標current和prev，分別指到即將被 刪除節點（current）及前一節點 （prev），因此prev永遠跟著current。 假設有一單向鏈結串列如下：

25 4.1 單向鏈結串列 今欲刪除“Mary”因此將del_data變數指定為“Mary”，接下來利用下列程式片段就可將current指標指向“Mary”的節點，而prev指向“John”節點，並將current指向的節點回收。

26 4.1 單向鏈結串列 

27 4.1 單向鏈結串列 將兩個單向鏈結串列相互連接 假設有二個串列如下：

28 4.1 單向鏈結串列 將x與y串列合併為z串列，其步驟如下： if(x->next==NULL) z=y;
4.1 單向鏈結串列 將x與y串列合併為z串列，其步驟如下： if(x->next==NULL) z=y; if(y->next ==NULL) z=x; z=x; c=x->next;

29 4.1 單向鏈結串列

30 4.1 單向鏈結串列 將一串列反轉 顧名思義，串列的反轉（invert）乃將原先的串列首變為串列尾，同理，串列尾變為串列首。若有一串列乃是由小到大排列，此時若想由大到小排列，只要將串列反轉即可。

31 4.1 單向鏈結串列 假設有一串列如下：

32 4.1 單向鏈結串列 經由下面幾個步驟就可完成反轉的動作： p=head->next; current=NULL;

33 4.1 單向鏈結串列 while(p != NULL) { prev=current; current=p; p=p->next; current->next=prev; }

34 4.1 單向鏈結串列 由此迴圈的前三個敘述p指標，current指標和prev指標有先後順序。經過一次的動作後，串列如下：

35 4.1 單向鏈結串列 依此進行到p == NULL後，迴圈停止

36 4.1 單向鏈結串列 最後，利用 head->next=current; 便完成串列的反轉。此動作的重點在於需要三個指標才能達成任務。

37 4.1 單向鏈結串列 計算串列的長度 串列的長度即表示串列的節點數目，因此以下列的片段程式即可完成。

38 4.1 單向鏈結串列 其中值得注意的是迴圈的中止條件為 (p != NULL)
4.1 單向鏈結串列 其中值得注意的是迴圈的中止條件為 (p != NULL) 而最後的count為串列的長度。 由於head節點不存放任何資料，故不予以計算之。

39 4.2 環狀串列 假若將鏈結串列最後一個節點的指標指向head節點時，此串列稱為環狀串列（circular list），如下圖所示：
4.2 環狀串列 假若將鏈結串列最後一個節點的指標指向head節點時，此串列稱為環狀串列（circular list），如下圖所示： 環狀串列可以從任一節點來追蹤所有節點。上圖假設第一個節點在x1。

40 4.2 環狀串列 加入動作 加入一節點於環狀串列前端之步驟如下： 有一環狀串列如下： 利用malloc函數配置了一個節點

41 4.2 環狀串列 利用下列步驟即可將x指向的節點加入到環狀串列的前端。

42 4.2 環狀串列 上述(1)(2)步驟亦適用於環狀串列開始時是空的狀況。

43 4.2 環狀串列 加入一節點於環狀串列的尾端

44 4.2 環狀串列 在環狀串列的某一特定節點後加入一節點，此與單向鏈結串列相似。

45 4.2 環狀串列 刪除的動作 刪除環狀串列的前端 有一環狀的串列如下：

46 4.2 環狀串列 其運作過程以及對應的環狀串列為 回收p所指向的節點，此時環狀串列剩下二個節點。

47 4.2 環狀串列 刪除環狀串列的尾端 有一環狀串列如下：

48 4.2 環狀串列 其運作的過程及其對應的環狀串列如下：

49 4.2 環狀串列 刪除環狀串列的特定節點與單向鏈結串列相同，在此不再贅述。

50 4.2 環狀串列 如何回收整個環狀串列 回收整個環狀串列表示此串列皆不再需要了，因此將它歸還給系統，假設系統有一串列如下：

51 4.2 環狀串列 而不再需要的環狀串列為 只要下面三個步驟就可達成回收整個環狀串列。

52 4.2 環狀串列 若要回收整個單向鏈結串列呢？這就比較麻煩了，此時必須一個一個回收，因此其Big-O為O(n)，表示與串列的節點數成正比，而回收整個環狀串列其Big-O為O(1)，表示它是一常數，不受節點數的影響，以下是回收整個單向鏈結串列的過程。

53 4.2 環狀串列 此處的free(q)可表示將它歸還到系統的AV串列中。

54 4.2 環狀串列 計算環狀串列的長度 計算環狀串列的長度，基本上與計算單向鏈結串列的長度大同小異。

55 4.3 雙向鏈結串列 雙向鏈結串列(doubly linked list)乃是每個節點皆具有三個欄位， 其資料結構如下：
4.3 雙向鏈結串列 雙向鏈結串列(doubly linked list)乃是每個節點皆具有三個欄位， 一為左鏈結（LLINK） 二為資料（DATA） 三為右鏈結（RLINK） 其資料結構如下：

56 4.3 雙向鏈結串列 其中LLINK指向前一節點，而RLINK指向後一個節點。
4.3 雙向鏈結串列 其中LLINK指向前一節點，而RLINK指向後一個節點。 通常在雙向鏈結串列加上一個串列首，此串列首的資料欄不存放資料。 如下圖所示：

57 4.3 雙向鏈結串列 雙向鏈結串列具有下列兩點特性：
4.3 雙向鏈結串列 雙向鏈結串列具有下列兩點特性： 假設ptr是指向任何節點的指標，則 ptr == ptr->llink->rlink ==ptr->rlink->llink; 若此雙向鏈結串列是空的串列，則只有一個串列首。

58 4.3 雙向鏈結串列 加入動作 加入於雙向鏈結串列的前端 假設一開始雙向鏈結串列如下：

59 4.3 雙向鏈結串列 經由下列步驟就可完成將已配置的x節點加入前端

60 4.3 雙向鏈結串列

61 4.3 雙向鏈結串列 加入於雙向鏈結串列的尾端 假設有一雙向鏈結串列如下：

62 4.3 雙向鏈結串列 經由下列步驟就可完成將已配置的x節點加入於尾端

63 4.3 雙向鏈結串列

64 4.3 雙向鏈結串列 讀者可將(2), (3)合起來就可知曉。

65 4.3 雙向鏈結串列 加入某一特定節點的後面 加入在某一特定節點的後面，理論上和單向鏈結串列相似，請看程式片段。 有一雙向鏈結串列如下（由大至小排列）

66 4.3 雙向鏈結串列

67 4.3 雙向鏈結串列

68 4.3 雙向鏈結串列 刪除動作 刪除雙向鏈結串列的前端，步驟如下：

69 4.3 雙向鏈結串列

70 4.3 雙向鏈結串列 刪除雙向鏈結串列的尾端，步驟如下： 先追蹤到尾端的節點

71 4.3 雙向鏈結串列

72 4.3 雙向鏈結串列 刪除雙向鏈結串列的某一特定節點。 如刪除del_dat為cd，其片段程式如下：

73 4.3 雙向鏈結串列 此時current指向欲尋找的資料，而prev指向其current的前一節點。

74 4.3 雙向鏈結串列

75 4.4 鏈結串列之應用 以鏈結串列表示堆疊 由於堆疊的加入和刪除操作都在同一端，因此，我們可以將它視為每次將節點加入與刪除的動作，是串列的前端或尾端。這些過程可參閱單向鏈結串列的說明。

76 4.4 鏈結串列之應用 以鏈結串列表示佇列 由於佇列的加入和刪除是在不同端，因此我們可以想像加入的動作是在串列的尾端，而刪除的動作是在前端即可。

77 4.4 鏈結串列之應用 4.4.3 多項式相加 多項式相加可以利用鏈結串列來完成。多項式以鏈結串列來表示的話，其資料結構如下：
4.4 鏈結串列之應用 多項式相加 多項式相加可以利用鏈結串列來完成。多項式以鏈結串列來表示的話，其資料結構如下： COEF表示變數的係數，EXP表示變數的指數，而LINK為指到下一節點的指標。

78 4.4 鏈結串列之應用 假設有一多項式 A=3x14+2x8+1，以鏈結串列如下：

79 4.4 鏈結串列之應用 兩個多項式相加其原理如下圖所示： A=3x14+2x8+1 ; B=8x14-3x10+10x6

80 4.4 鏈結串列之應用 此時A、B兩多項式的第一個節點EXP皆相同（EXP(p) = EXP(q)），所以相加後放入C串列，同時p、q的指標指向下一個節點。

81 4.4 鏈結串列之應用 EXP(p)=8<EXP(q)=10。因此將B多項式的第二個節點加入C多項式，並且q指標指向下一個節點。

82 4.4 鏈結串列之應用 由於EXP(p)=8>EXP(q)=6，所以將A多項式的第二個節點加入C多項式，p指標指向下一個節點。

83 4.4 鏈結串列之應用 以此類推最後C多項式為 C=11x14-3x10+2x8+10x6+1