資料結構 – 鏈結串列 Linked List 2013.05 綠園.

Presentation on theme: "資料結構 – 鏈結串列 Linked List 2013.05 綠園."— Presentation transcript:

1 資料結構 – 鏈結串列 Linked List 綠園

2 鏈結串列-Linked List Linked List是由許多相同資料型態的項目所組成的有限序列。
可以把鏈結串列想像成火車，有多少人就只掛多少節的車廂，需要車廂時再跟系統要一個車廂，人少了就把車廂還給系統。 鏈結串列是有多少資料用多少記憶體空間，有新資料加入就向系統要一塊記憶體空間，資料刪除後，就把空間還給系統。 和靜態資料結構的陣列型態不同之處是鏈結串列使用動態記憶體配置來存放資料。

3 陣列與鏈結串列比較 陣列的優點 陣列的缺點 容易製作，只需一行宣告。 索引值與儲存資料有一對一關係，容易存取。
空間上的限制與浪費，宣告時已決定最大空間，而沒有使用到的部分會造成記憶體空間浪費。 當需要刪除或插入元素時，往往需要搬動其他元素，效率不佳。 無法對多個有順序資料做良好的呈現。

4 陣列與鏈結串列比較 鏈結串列的優點 鏈結串列的缺點 程式執行時動態配置記憶體，所使用的空間可以自由增減，減少記憶體的浪費。
當元素需要被插入或刪除時，不影響其他的空間，增進效率。 鏈結串列的缺點 製作上較不易，需使用指標完成資料結構。 沒有所謂索引值，存取較不易。 存取任一元素時，可能需要經過其他元素。

5 【複習】動態記憶體配置 【new 與 delete】 利用 new 取得動態空間 int *ptr; ptr = new int;
可以合併寫成 int *ptr = new int(10); 利用 delete 釋放空間 delete ptr; ptr = NULL;

6 單向鏈結串列(Singly Linked Lists)
是串列中最常用的一種，它就像火車一般，所有節點串成一列，而且指標所指的方向一樣。 也就是串列中每筆資料除了要儲存原本的資料，還必須儲存下一筆資料的儲存位址。 在程式語言中，一個串列節點至少由兩個欄位，即一個以上的資料欄及鏈結欄組成，至於串列的組成基本要件為節點(node)，而且每一個節點不必儲存於連續記憶體位址。

7 單向鏈結串列資料結構圖

8 單向鏈結串列(Singly Linked Lists)
鏈結串列中的節點不只記錄單一數值，例如每一個節點除了有指向下一個節點的指標欄位外，還包括了記錄一位學生的姓名(name)、座號(num)、成績(score)。 因此必須宣告節點的資料型態，讓每一個節點包含一筆資料的指標，並且包含指向下一筆資料，使所有資料能被串在一起而形成一個串列類別，如下圖：

9 節點資料型態宣告 滿足上圖要求的節點資料型態宣告如下： class list /* 串列類別宣告 */
{ /* 類別內容以{…};包起來 */ public: int num; /* 座號 */ char name[10]; /* 姓名 */ int score; /* 成績 */ class list *next; /* 指標，指向下一個節點 */ }; typedef class list node; /* 定義新型態 */ typedef node *link; /* 定義新型態的變數名稱為link */ ...... link newnode = NULL; /* 宣告一欲指向新節點的指標newnode */ newnode = new node; /* 將 newnode 指向新建立的 node */

10 單向串列的節點刪除

11 單向鏈結串列的節點刪除(一) 若要在鏈結中刪除一個節點，依據所刪除節點的位置會有三種不同的情形：
1.刪除串列的第一個節點：只要把串列首指標指向第二個節點即可。如下加入四行指令即可刪除節點： top = head; head = head->next; delete top; top = null;

12 單向鏈結串列的節點刪除(二) 2.刪除串列內的中間節點：只要將刪除節點的前一個節點的指標，指向欲刪除節點的下一個節點即可，如下加入四行指令即可刪除節點Y： Y = ptr->next; ptr->next = Y->next; delete Y; Y = null;

13 單向鏈結串列的節點刪除(三) 3.刪除串列後的最後一個節點：只要指向最後一個節點的指標，直接指向NULL即可。如下加入四行指令即可刪除節點：
ptr->next=tail; ptr->next=NULL; delete ptr; ptr = null;

14 單向串列的節點插入

15 單向串列的節點插入 (一) 節點的插入方法和刪除節點相當類似，都只需要移動指標即可完成。 1.在串列的第一個節點插入節點：
只需把新節點的指標指向串列首，再把串列首移到新節點上即可。

16 單向串列的節點插入 (二) 節點的插入方法和刪除節點相當類似，都只需要移動指標即可完成。 2.在串列的最後一個節點後面插入節點：
把串列的最後一個節點的指標指向新節點，新節點再指向NULL即可。

17 單向串列的節點插入 (三) 節點的插入方法和刪除節點相當類似，都只需要移動指標即可完成。 3.在串列的中間位置插入節點：
如果插入的節點是在 X 與 Y 之間，要將新節點的指標指向 Y 節點。

18 單向串列的節點插入 (三) 節點的插入方法和刪除節點相當類似，都只需要移動指標即可完成。 3.在串列的中間位置插入節點：
接著把插入點 X 指標指向的新節點。

19 計算鏈狀串列節點個數

20 計算鏈狀串列共有多少節點 class list /*串列類別宣告*/ { public: int data; /*資料欄*/
class list *next; /*指向下一個節點*/ }; typedef class list node; /*定義node新的資料型態*/ typedef node *link; /*定義link新的資料型態指標*/ link head, p; int count; int main() { count = 0; for(p=head; p!=null; p=p->next) count ++; cout << “count = ” << count << endl; return 0; }

21 單向串列的反轉

22 單向串列的反轉 在鏈結串列中的節點特性是知道下一個節點的位置，可是卻無從得知它的上一個節點位置，不過如果要將串列反轉，則必須使用三個指標變數。如下圖所示：

23 class list /*串列類別宣告*/ { public: int num; /*學生號碼*/ int score; /*學生分數*/ char name[10]; /*學生姓名*/ class list *next; /*指向下一個節點*/ }; typedef class list node; /*定義node新的資料型態*/ typedef node *link; /*定義link新的資料型態指標*/ link invert(link x) /* x為串列的開始指標*/ { link p,q,r; p=x; /*將p指向串列的開頭*/ q=NULL; /*q是p的前一個節點*/ while(p!=NULL) r=q; /*將r接到q之後 */ q=p; /*將q接到p之後 */ p=p->next; /*p移到下一個節點*/ q->next=r; /*q連結到之前的節點 */ } return q;

24 invert(X)演變過程 執行while迴路前 第一次執行while迴路 第二次執行while迴路
當執行到p=NULL時，整個串列也就整個反轉過來了。

25 【作業練習】 linkedlist_xxxx.cpp
　設計一個簡單介面能處理對於單一鍵結串列所能提供的下述功能：(附註：所有功能儘量以函數方式來寫，以便於後續 程式可以重複使用。) 一、連續新增串列資料於串列結尾 功能：能連續輸入資料，用空格隔開，輸入000為結束。 範例：輸入『aaa bbb ccc ddd 000』，將aaa, bbb, ccc, ddd資料依序加入至串列結尾。 二、新增單一串列資料   功能：能輸入資料，並指定欲插入之節點編號，將新節點插 入。(若原串列的節點數不足，直接將新增之節點放於 串列末。 範例：輸入『eee 5』，插入新節點於串列第五個位置，並將 eee資料放入。 三、刪除單一串列資料 功能：輸入欲刪除的節點編號，將該節點刪除。 (若原串列的節點不足，則不予理會) 範例：輸入『5』，將串列的第五個節點刪除。

26 【作業練習】 linkedlist_xxxx.cpp
　設計一個簡單介面能處理對於單一鍵結串列所能提供的下述功能：(附註：所有功能儘量以函數方式來寫，以便於後續程式可以重複使用。) 四、尋找單一串列資料 功能：輸入一筆資料，傳回該串列是否有此筆資料。 範例：輸入『fff』，若串列中的某節點內含有fff資料，則傳回 true，否則為false。 五、印出所有串列資料 功能：輸入啟始節點編號以及連續列印個數 (0代表列印至串列末)，即可印出相關資料。 範例：輸入『4 10』，從串列第四個節點開始列印，連續列印10 個節點資料。 六、計算串列長度 功能：點選此一功能，隨即輸出此串列中共有幾個節點。 (空串列請輸出0) 七、清空串列資料 功能：點選此一功能，隨即清空該串列所有節點及資料。 八、離開程式

27 雙向鏈結串列

28 雙向鏈結串列 雙向鏈結串列(Double Linked List)是另外一種常用的串列結構。
可以改善這兩個缺點，因為它的基本結構和單向鏈結串列類似，至少有一個欄位存放資料。 只是它有兩個欄位存放指標，其中一個指標指向後面的節點，另一個則指向前面的節點。

29 雙向鏈結串列定義 雙向鏈結串列的資料結構，可以定義如下：
每個節點具有三個欄位，中間為資料欄位。左右各有兩個鏈結欄位，分別為LLINK及RLINK。其中RLINK指向下一個節點，LLINK指向上一個節點。 通常加上一個串列首，此串列不存任何資料，其左邊鏈結欄指向串列最後一個節點，而右邊鏈結指向第一個節點。

30 假設ptr為一指向此串列上任一節點的鏈結，則有：
建立雙向鏈結串列的方法，首先就是宣告每個節點有三個欄位，其宣告的資料類別如下： ptr=RLINK(LLINK(ptr))=LLINK(RLINK(ptr)) class list { int DATA; class list * LLINK; class list * RLINK; }; typedef class list node; typedef node * link; typedef node * head; typedef node * insertafter; typedef node * delete;

31 雙向鏈結串列的節點加入 對於雙向鏈結串列的節點加入有三種可能情況： 將新節點加入此串列的第一個節點前，如下圖：
步驟 將新節點的右鏈結(RLINK)指向原串列的第一個節點。 將原串列第一個節點的左鏈結(LLINK)指向新節點。 將原串列的串列首指標head指向新節點。 新節點的左鍵結指向NULL。

32 將新節點加入此串列的最後一個節點之後。 將原串列的最後一個節點的右鏈結指向新節點。 將新節點的左鏈結指向原串列的最後一個節點。
步驟 將原串列的最後一個節點的右鏈結指向新節點。 將新節點的左鏈結指向原串列的最後一個節點。 將新節點的右鏈結指向NULL。

33 將新節點加入到ptr節點之後，如下圖： 將ptr節點的右鏈結指向新節點。 將新節點的左鏈結指向ptr節點。
步驟 將ptr節點的右鏈結指向新節點。 將新節點的左鏈結指向ptr節點。 將ptr節點的下一個節點的左鏈結指向新節點。 將新節點的右鏈結指向ptr的下一個節點。

34 雙向鏈結串列節點刪除 對於雙向鏈結串列的節點刪除可能有三種情況： ①刪除串列的第一個節點。如下圖：
步驟 將串列首指標head指到原串列的第二個節點。 將新的串列首指標指向NULL。

35 ②刪除此串列的最後一個節點。如下圖： 步驟 1.將原串列最後一個節點之前一個節點的右鏈結指向NULL即可。

36 ③刪除串列中間的ptr節點。如下圖： 將ptr節點的前一個節點右鏈結指向ptr節點的下一個節點。
步驟 將ptr節點的前一個節點右鏈結指向ptr節點的下一個節點。 將ptr節點的下一個節點左鏈結指向ptr節點的上一個節點。