Download presentation
Presentation is loading. Please wait.
1
鏈結串列 (Linked List) 註:要會指標(Pointer)
授課老師：蕭志明
2
鏈結串列較優於陣列，因為只需改變一些指標即可
鍊結串列特性 鏈結串列(linked list)是由許多結點所組成的，在加入和刪除功能上比陣列彈性許多。且加入與刪除的動作，可以針對串列首、串列尾或串列中的某個節點。 鏈結串列視實際需要才配置記憶體空間，可減少浪費。 可以取代陣列儲存方式(堆疊與佇列)，而其所含資料元素的數 目可以彈性的增減。 陣列儲存方式 鏈結串列儲存方式 加入與刪除 需做大量的資料搬移 僅須改變指標即可 記憶空間 無需額外的空間存放鏈結資料 需額外的空間存放鏈結資料 資料的存取 可對資料做直接的存取 適合資料的循序存取 資料的合併與分開 鏈結串列較優於陣列，因為只需改變一些指標即可
3
節點（Node） 節點 (Node)是鏈結串列中的重要元素 節點 (Node) 是一個最少有兩個欄位的結構： 一個欄位包含資料。
另一個欄位包含串列中下一個節點的位址。
4
Node的結構與產生 結構宣告： struct node { int number; struct node *llink; }
head = (struct node *) malloc (sizeof(struct node));
5
Node的結構與產生(續) 結構宣告： struct node { string name; string address;
int phone; struct node *llink; } Node 的產生： head = (struct node *) malloc (sizeof(struct node));
6
Example 假設鏈結串列中每個節點(node)的資料結構有兩欄，分別為資料(data)欄和鏈結(next)欄，結構可需告如下：
Struct node { int data; struct node *next; }; 例如：下列串列有a, b, c, d, x等的資料元素。 head：指向串列前端的指標。 tail：指向串列尾端的指標。 tail head a b c d x
7
鍊結串列概念 鍊結串列 (Linked List) 是一個有序的資料集合，其中每一個元素都包含下一個元素的位址。
也就是說，每一個元素可分為兩部份：資料 (Data) 與鍊結 (Link)。 資料部份儲存資料。 鍊結部份用於將資料鍊結在一起。它包含一個指標，負責辨識串列的下一個元素。 另外，還有一個指標變數，指向串列的第一個元素。 我們討論的鏈結串列－單一鏈結串列，每一個元素只包含一個鍊結，只能指向一個後續元素。 鍊結串列的優點是資料的新增與刪除操作。 當新增與刪除一個元素時，不必因串列中元素邏輯順序的改變，而移動它們的實際儲存位置。 因為串列不要求元素在實際儲存時，要一個接一個地存放。但也無法進行二元搜尋，必須採用循序搜尋。
8
鍊結串列概念(續) 如圖(a)所示，pHead(指向串列的第一個元素)，包含4個元素。
除了最後一個元素之外，每一個元素中的鍊結都指向它的後續元素。 而最後一個元素的鍊結是一個null指標，表示串列的結束。 若串列的指標變數為null指標，表示它是一個空的鏈結串列，如圖(b) 所示。
9
鏈結串列資料結構 鍊結串列的特性就是節點之間沒有實體的 關係，也就是說他們不是連續儲存的。 就鏈結串列而言，在節點之間沒有實體的 關係。
鍊結串列的特性就是節點之間沒有實體的 關係，也就是說他們不是連續儲存的。 就鏈結串列而言，在節點之間沒有實體的 關係。 需要指標來辨別串列的第一個節點，還有任何一個節點，其後續節點的位址。 指向串列開始位置的指標稱為表頭指標 (Head Pointer) 。在上圖中，pHead就是 head指標，而link指向節點的後續節點。
10
鍊結串列種類 可分為： 單向鏈結串列(single linked list) 環狀串列(circular linked list)
雙向鏈結串列(doubly linked list)
11
單向鏈結串列優點 以陣列方式存放資料時，若要插入（insert）或刪除（delete）某一節點（node）就倍感困難了。
如在陣列中已有a,b,d,e四個元素，現將c加入陣列中，並按字母順序排列。 方法就是d,e往後一格，然後將c插入；而刪除一元素，也必須挪移元素才不會浪費空間，有無方法來改善此一問題呢？ 這就是本章所要探討的鏈結串列（linked list）。
12
單向鏈結串列(續) 鏈結串列在加入與刪除皆比陣列來得簡單容易，因為只要利用指標（pointer）加以處理就可以了。
假設鏈結串列中每個節點（node）的資料結構有二欄，分別是資料（data）欄和鏈結（next）欄 ，若將節點結構定義為struct node 型態，則宣告如下：
13
單向鏈結串列(續) 如串列 A={a, b, c, d}，其資料結構如下：
head：指向串列前端的指標，通常假設此節點的data欄是空的亦即不放資料，這在一些運作上有其方便之處。
14
單向鏈結串列(加入於串列的前端) 假設有一串列如下： 有一節點x將加入於串列的前端，其步驟如下：
(1) x=(struct node*) malloc(sizeof(struct node)); (2) x->next=head->next;
15
單向鏈結串列(加入於串列的前端) (3)head->next=x;
16
單向鏈結串列（加入於串列的尾端） 假設有一串列如下： 將一節點x加入於串列的尾端，其步驟如下：
(1)x=(struct node *) malloc(sizeof(struct node));
17
單向鏈結串列（加入於串列的尾端） (2)x->next=NULL;
18
單向鏈結串列（加入於串列的尾端） 此時必須追蹤此串列的尾端在那兒，利用下列的片段程式 便可找到串列的尾端。
19
單向鏈結串列（加入於串列的尾端） (3)p->next=x;
20
單向鏈結串列（加入在串列某一特定節點的後面）
假設有一單向鏈結串列，按data欄位由大到小排列之。
21
單向鏈結串列（加入在串列某一特定節點的後面）
今有一節點ptr之data欄位值為75，欲加入到上述的串列中。首先我們必須找到插入的地方，可想而知75應插入到80和70之間，因此可用下述的片段程式執行之
22
單向鏈結串列（加入在串列某一特定節點的後面）
利用prev和current二個指標來追蹤，prev會緊跟在current節點之後
23
單向鏈結串列（加入在串列某一特定節點的後面）
接下來的動作：就是將ptr指向節點插在prev的後面 ptr->next=current; /* */ prev->next=ptr; /* */
24
單向鏈結串列（刪除前端節點） 假設有一串列如下： 只要三步驟便可達成目的： p=head->next;
head->next=p->next; free(p);
25
單向鏈結串列（刪除前端節點） (1) p=head->next;
26
單向鏈結串列（刪除前端節點） (2) head->next=p->next;
27
單向鏈結串列（刪除前端節點） (3)free(p); 經由free(p)便可將p節點回收。
28
單向鏈結串列（刪除串列的最後節點） 假設有一串列如下： 此時必須先追蹤尾端及尾端的前一個節點在那兒，步驟如下：
29
單向鏈結串列（刪除串列的最後節點）
30
單向鏈結串列（刪除串列的最後節點）
31
單向鏈結串列（刪除某一特定的節點） 刪除某一特定的節點也必須利用二個指標current和prev，分別指到即將被刪除節點（current）及前一節點（prev），因此prev永遠跟著current。
32
單向鏈結串列（刪除某一特定的節點） 假設有一單向鏈結串列如下： 今欲刪除“Mary”因此將del_data變數指定為“Mary”，接下來利用下列程式片段就可將current指標指向“Mary”的節點，而prev指向“John”節點，並將current指向的節點回收。
33
單向鏈結串列（刪除某一特定的節點）
34
單向鏈結串列（兩個單向鏈結串列相互連接）
假設有二個串列如下： 將x與y串列合併為z串列，其步驟如下：
35
單向鏈結串列（兩個單向鏈結串列相互連接）
36
單向鏈結串列（兩個單向鏈結串列相互連接）
37
單向鏈結串列（兩個單向鏈結串列相互連接）
38
單向鏈結串列（將一串列反轉） 顧名思義，串列的反轉（invert）乃將原先的串列首變為串列尾，同理，串列尾變為串列首。若有一串列乃是由小到大排列，此時若想由大到小排列，只要將串列反轉即可。
39
單向鏈結串列（將一串列反轉） 假設有一串列如下： 經由下面幾個步驟就可完成反轉的動作：
40
單向鏈結串列（將一串列反轉）
41
單向鏈結串列（將一串列反轉）
42
單向鏈結串列（將一串列反轉） 由此迴圈的前三個敘述p指標，current指標和prev指標有先後順序。經過一次的動作後，串列如下：
43
單向鏈結串列（將一串列反轉） 依此進行到p == NULL後，迴圈停止
44
單向鏈結串列（將一串列反轉） 最後，利用 head->next=current;
便完成串列的反轉。此動作的重點在於需要三個指標才能達成任務。
45
單向鏈結串列（計算串列的長度） 串列的長度即表示串列的節點數目，因此以下列的片段程式即可完成。
46
單向鏈結串列（計算串列的長度） 其中值得注意的是迴圈的中止條件為 (p != NULL) 而最後的count為串列的長度。
由於head節點不存放任何資料，故不予以計算之。
47
環狀串列 假若將鏈結串列最後一個節點的指標指向head節點時，此串列稱為環狀串列（circular list），如下圖所示：
環狀串列可以從任一節點來追蹤所有節點。上圖假設第一個節點在x1。
48
環狀串列（加入串列前端動作） 有一環狀串列如下：
49
環狀串列（加入串列前端動作） 利用malloc函數配置了一個節點 利用下列步驟即可將x指向的節點加入到環狀串列的前端。
50
環狀串列（加入串列前端動作）
51
環狀串列（加入串列前端動作）
52
環狀串列（加入串列尾端動作）
53
環狀串列（加入串列尾端動作） 3. 在環狀串列的某一特定節點後加入一節點，此與單向鏈結串列相似。
54
環狀串列（刪除串列的前端） 有一環狀的串列如下： 其運作過程以及對應的環狀串列如下
55
環狀串列（刪除串列的前端）
56
環狀串列（刪除串列的前端） 回收p所指向的節點，此時環狀串列剩下二個節點。
57
環狀串列（刪除串列的尾端） 有一環狀串列如下： 其運作的過程及其對應的環狀串列如下：
58
環狀串列（刪除串列的尾端）
59
環狀串列（刪除串列的尾端）
60
環狀串列（刪除特定節點） 刪除環狀串列的特定節點與單向鏈結串列相同，在此不 再贅述。
61
環狀串列（計算環狀串列的長度） 計算環狀串列的長度，基本上與計算單向鏈結串列的長度大同小異。
62
雙向鏈結串列 雙向鏈結串列(doubly linked list)乃是每個節點皆具有三個欄位，一為左鏈結（LLINK），二為資料（DATA），三為右鏈結（RLINK），其資料結構如下：
63
雙向鏈結串列 其中LLINK指向前一節點，而RLINK指向後一個節點。通常在雙向鏈結串列加上一個串列首，此串列首的資料欄不存放資料。如下圖所示：
64
雙向鏈結串列 雙向鏈結串列具有下列兩點特性： 1.假設ptr是指向任何節點的指標，則
ptr == ptr->llink->rlink == ptr->rlink->llink; 2.若此雙向鏈結串列是空的串列，則只 有一個串列首。
65
雙向鏈結串列（加入串列的前端） 假設一開始雙向鏈結串列如下： 經由下列步驟就可完成將已配置的x 節點加入前端
66
雙向鏈結串列（加入串列的前端）
67
雙向鏈結串列（加入串列的前端）
68
雙向鏈結串列（加入串列的尾端） 假設有一雙向鏈結串列如下： 經由下列步驟就可完成將已配置的x 節點加入於尾端
69
雙向鏈結串列（加入串列的尾端）
70
雙向鏈結串列（加入串列的尾端）
71
雙向鏈結串列（加入串列的尾端） 可將(2), (3)合起來就可知曉。
72
雙向鏈結串列（加入特定節點的後面） 加入在某一特定節點的後面，理論上 和單向鏈結串列相似，請看程式片段。 有一雙向鏈結串列如下（由大至小排
列）
73
雙向鏈結串列（加入特定節點的後面）
74
雙向鏈結串列（加入特定節點的後面）
75
雙向鏈結串列（加入特定節點的後面）
76
雙向鏈結串列（刪除串列的前端） 刪除雙向鏈結串列的前端，步驟如下：
77
雙向鏈結串列（刪除串列的前端）
78
雙向鏈結串列（刪除串列的前端）
79
雙向鏈結串列（刪除串列的尾端） 先追蹤到尾端的節點
80
雙向鏈結串列（刪除串列的尾端）
81
雙向鏈結串列（刪除串列的尾端）
82
雙向鏈結串列（刪除串列的特定節點） 例如刪除del_dat為cd，其片段程式如下：
83
雙向鏈結串列（刪除串列的特定節點）
84
雙向鏈結串列（刪除串列的特定節點）
85
鏈結串列之應用 以鏈結串列表示堆疊 以鏈結串列表示佇列：
由於堆疊的加入和刪除操作都在同一端，因此，我們可以將它視為每次將節點加入與刪除的動作，是串列的前端或尾端。這些過程可參閱單向鏈結串列的說明。 以鏈結串列表示佇列： 由於佇列的加入和刪除是在不同端，因此我們可以想像加入的動作是在串列的尾端，而刪除的動作是在前端即可。
86
鏈結串列之應用（多項式相加） 多項式相加可以利用鏈結串列來完成。多項式以鏈結串列來表示的話，其資料結構如下：
COEF表示變數的係數，EXP表示變數的指數，而LINK為指到下一節點的指標。
87
鏈結串列之應用（多項式相加） 假設有一多項式 A=3x14+2x8+1，以鏈結串列如下： 兩個多項式相加其原理如下圖所示：
88
鏈結串列之應用（多項式相加）
89
鏈結串列之應用（多項式相加） 1. 此時A、B兩多項式的第一個節點EXP 皆相同（EXP(p) = EXP(q)），所以相
加後放入C串列，同時p、q的指標指 向下一個節點。
90
鏈結串列之應用（多項式相加）
91
鏈結串列之應用（多項式相加） 2. EXP(p)=8<EXP(q)=10。因此將B多 項式的第二個節點加入C多項式，並
92
鏈結串列之應用（多項式相加）
93
鏈結串列之應用（多項式相加） 3. 由於EXP(p)=8>EXP(q)=6，所以將A 多項式的第二個節點加入C多項式，p
指標指向下一個節點。
94
鏈結串列之應用（多項式相加）
95
鏈結串列之應用（多項式相加） 4. 以此類推最後C多項式為 C=11x14-3x10+2x8+10x6+1
Similar presentations
