資料結構 – 鏈結串列 Linked List 2009.05 綠園. 鏈結串列 -Linked List Linked List 是由許多相同資料型態的項目所組 成的有限序列。 可以把鏈結串列想像成火車，有多少人就只掛多 少節的車廂，需要車廂時再跟系統要一個車廂， 人少了就把車廂還給系統。 鏈結串列是有多少資料用多少記憶體空間，有新.

Presentation on theme: "資料結構 – 鏈結串列 Linked List 2009.05 綠園. 鏈結串列 -Linked List Linked List 是由許多相同資料型態的項目所組 成的有限序列。 可以把鏈結串列想像成火車，有多少人就只掛多 少節的車廂，需要車廂時再跟系統要一個車廂， 人少了就把車廂還給系統。 鏈結串列是有多少資料用多少記憶體空間，有新."— Presentation transcript:

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

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

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

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

5 【複習】動態記憶體配置 【 new 與 delete 】 利用 new 取得動態空間 int *ptr; ptr = new int; *ptr = 10; 可以合併寫成 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 雙向鏈結串列的節點加入 對於雙向鏈結串列的節點加入有三種可能情況： – 將新節點加入此串列的第一個節點前，如下圖： 步驟 1. 將新節點的右鏈結 (RLINK) 指向原串列的第一個節點。 2. 將原串列第一個節點的左鏈結 (LLINK) 指向新節點。 3. 將原串列的串列首指標 head 指向新節點，且新節點的左 鍵結指向 NULL 。

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

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

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

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

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