Download presentation
Presentation is loading. Please wait.
1
4.1 單向鏈結串列 4.2 堆疊的加入與刪除 4.3 佇列的加入與刪除 4.4 其他型式的佇列
Chapter 4 鏈結串列 4.1 單向鏈結串列 4.2 堆疊的加入與刪除 4.3 佇列的加入與刪除 4.4 其他型式的佇列
2
4.1 單向鏈結串列 為何使用鏈結串列(linked list)？ 鏈結串列 vs. 陣列
4.1 單向鏈結串列 為何使用鏈結串列(linked list)？ 為了避免以陣列方式來存放資料時，在插入(insert)或刪除(delete)某一節點所遇到的困難 節省配置的記憶體空間 鏈結串列 vs. 陣列 在加入和刪除時利用指標(pointer)，因此比陣列來得簡單 鏈結串列在搜尋上所花費的時間會比陣列來得久
3
4.1 單向鏈結串列 單向鏈結串列 資料結構：資料(data)欄和鏈結(next)欄 資料結構定義： struct node{
4.1 單向鏈結串列 單向鏈結串列 資料結構：資料(data)欄和鏈結(next)欄 資料結構定義： struct node{ int data; struct node *next; }; struct node *head = NULL, *tail, *this, *prev, *x, *p, *ptr; head：指向串列前端的指標，tail：指向串列尾端的指標 data next
4
4.1 單向鏈結串列 如串列A={a, b, c, d}，其以鏈結串列表示的資料結構如下：
4.1 單向鏈結串列 如串列A={a, b, c, d}，其以鏈結串列表示的資料結構如下： 假設鏈結串列的第一個節點(亦即head 所指向的節點)，其data 欄不放任何資料。讓我們來看看鏈結串列中的加入與刪除動作，這些動作又可分為前端、尾端或隨機加入某一節點。
5
4.1 單向鏈結串列 加入動作
6
4.1 單向鏈結串列
7
4.1 單向鏈結串列
8
4.1 單向鏈結串列
9
4.1 單向鏈結串列
10
4.1 單向鏈結串列
11
4.1 單向鏈結串列
12
4.1 單向鏈結串列 刪除動作
13
4.1 單向鏈結串列
14
4.1 單向鏈結串列
15
4.1 單向鏈結串列
16
4.1 單向鏈結串列
17
4.1 單向鏈結串列
18
4.1 單向鏈結串列
19
4.1 單向鏈結串列 將兩串列相連接
20
4.1 單向鏈結串列
21
4.1 單向鏈結串列
22
4.1 單向鏈結串列 4.1.4 將一串列反轉
23
4.1 單向鏈結串列
24
4.1 單向鏈結串列
25
4.1 單向鏈結串列 計算串列的長度
26
4.1 單向鏈結串列
27
4.2 環狀鏈結串列
28
4.2 環狀鏈結串列 加入動作
29
4.2 環狀鏈結串列
30
4.2 環狀鏈結串列
31
4.2 環狀鏈結串列
32
4.2 環狀鏈結串列 刪除的動作
33
4.2 環狀鏈結串列
34
4.2 環狀鏈結串列
35
4.2 環狀鏈結串列
36
4.2 環狀鏈結串列
37
4.2 環狀鏈結串列 兩個環狀串列之相連
38
4.2 環狀鏈結串列
39
4.2 環狀鏈結串列
40
4.2 環狀鏈結串列
41
4.3 雙向鏈結串列 雙向鏈結串列(doubly linked list) 乃是每個節點皆具有三個欄位，一為左鏈結(LLINK)，二為資料(DATA)，三為右鏈結(RLINK)，其資料結構如下： 其中LLINK 指向前一個節點，而RLINK 指向後一個節點。通常在雙向鏈結串列加上一個串列首，此串列首的資料欄不存放資料。如下圖所示：
42
4.3 雙向鏈結串列 雙向鏈結串列具有下列兩點特性： 1. 假設ptr 是任何節點的指標，則
4.3 雙向鏈結串列 雙向鏈結串列具有下列兩點特性： 1. 假設ptr 是任何節點的指標，則 ptr = ptr→llink→rlink = ptr→rlink→llink; 2. 若此雙向鏈結串列是空串列，則只有一個串列首。 3. 雙向鏈結串列的優點為(1)加入或刪除時，無需知道其前一節點的位址；(2)可以從任一節點找到其前一節點或後一節點；(3)可以將某一節點遺失的左或右指標適時的加以恢復之；而其缺點為(1)增加一個指標空間；(2)加入時需改變四個指標，而單向只需改變二個指標即可；(3)刪除時需改變兩個指標，而單向只要改變一個即可。
43
4.3 雙向鏈結串列 加入動作
44
4.3 雙向鏈結串列
45
4.3 雙向鏈結串列
46
4.3 雙向鏈結串列
47
4.3 雙向鏈結串列
48
4.3 雙向鏈結串列
49
4.3 雙向鏈結串列
50
4.3 雙向鏈結串列
51
4.3 雙向鏈結串列 刪除的動作
52
4.3 雙向鏈結串列
53
4.3 雙向鏈結串列
54
4.3 雙向鏈結串列
55
4.3 雙向鏈結串列
56
4.3 雙向鏈結串列
57
4.3 雙向鏈結串列
58
4.4 鏈結串列的應用 以鏈結串列表示堆疊
59
4.4 鏈結串列的應用
60
4.4 鏈結串列的應用
61
4.4 鏈結串列的應用
62
4.4 鏈結串列的應用 以鏈結串列表示佇列
63
4.4 鏈結串列的應用
64
4.4 鏈結串列的應用
65
4.4 鏈結串列的應用
66
4.4 鏈結串列的應用 多項式相加
67
4.4 鏈結串列的應用
68
4.4 鏈結串列的應用
69
4.4 鏈結串列的應用
70
4.4 鏈結串列的應用
71
4.4 鏈結串列的應用
Similar presentations
