鏈結串列 Link List chapter 6 德明科技大學資訊科技系.

Presentation on theme: "鏈結串列 Link List chapter 6 德明科技大學資訊科技系."— Presentation transcript:

1 鏈結串列 Link List chapter 6 德明科技大學資訊科技系

2 線性串列(Linear List) 線性串列
又稱有序串列(Ordered List)或循序串列(Sequential List) ，元素與元素之間有線性的相對關係，並且以循序方式儲存 堆疊與佇列都是線性串列 德明科技大學資訊科技系

3 陣列與鏈結串列比較 陣列 固定記憶體大小，設計簡單但沒彈性 鏈結串列 以節點串起整個串列，比較複雜但有彈性 德明科技大學資訊科技系

4 動態記憶體配置 Dynamical Memory Allocation 在C++使用動態記憶體配置的函數
靜態記憶體配置是在編譯階段時就配置記憶體空間 動態記憶體配置則是等到執行階段，才向作業系統要求配置所需的記憶體空間 動態記憶體配置可以讓程式設計者靈活運用程式所需的記憶體空間 在C++使用動態記憶體配置的函數 malloc() 與 free(): 只針對資料變數 new 與 delete: 針對變數與物件均可 德明科技大學資訊科技系

5 鏈結串列 「鏈結串列」(linked list) 可以用來解決單純陣列的缺點：
1. 鏈結串列的元素之間不必實體連續（即不必依元素順序佔用記憶體中的連續位址），只要有邏輯上 (logical) 的順序存在即可 2. 「鏈結」(link) 就是用來維持這順序的工具，它可以告訴我們「下一個元素放在哪裡」。 無首節點 listA 中國 美國 英國 蘇俄 有首節點 中國 美國 英國 蘇俄 首節點 德明科技大學資訊科技系

6 鏈結串列 依照資料特性，決定使用陣列或鏈結串列 鏈結串列內，一個節點包含兩部份 在電腦程式中，實作鏈結串列的方法有二
如果需要大量資料讀取，陣列比較合適 如果插入與刪除資料頻繁，鏈結串列比較合適 鏈結串列內，一個節點包含兩部份 資料 data，紀錄資料內容 鏈結 link，紀錄下一個節點的位置 在電腦程式中，實作鏈結串列的方法有二 以陣列完成 以結構與指標搭配完成 德明科技大學資訊科技系

7 以陣列實作鏈結串列 節點散佈在陣列中，實體位置沒有連續，但根據鏈結可以得到以下次序 3 1 6 7 3 1 6 7 data next
Table[0] 3 [1] 美 國 6 #define MAXNODE 9 typedef struct tagListNode { char data[8]; /*資料欄位*/ int next ; /*鏈結欄位*/ } ListNode ; ListNode table[MAXNODE] ; [2] -1 [3] 中 國 1 [4] -1 [5] -1 [6] 英 國 7 [7] 蘇 俄 [8] -1 節點散佈在陣列中，實體位置沒有連續，但根據鏈結可以得到以下次序 3 1 6 7 3 中國 1 美國 6 英國 7 蘇俄 首節點 德明科技大學資訊科技系

8 新增節點 目標：要在 ‘英國’ 節點之後插入一個新節點 ‘法國’  找到一個空節點，填入資料  找到英國，或者條件已知
data next Table[0] 3  找到一個空節點，填入資料 [1] 美 國 6 [2]  法 國  -1→7  找到英國，或者條件已知 [3] 中 國 1  將英國的 next (7) 複製到法國的next [4] -1 [5] -1  將法國的位置 (2) 填入英國的next [6]  英 國  7→2 [7] 蘇 俄 [8] -1 3 1 6 7 3 中國 1 美國 6 英國 蘇俄 7→2 2 首節點 法國 7 德明科技大學資訊科技系

9 刪除節點 目標：要刪除 ‘英國’ 節點 3 1 6 2 7 3 1 2 7 data next Table[0] 3
 找到英國 (6)，以及英國的前一個節點 ‘美國’(1) [1] 美 國 6→2 [2] 法 國 7  將英國的 next (2) 複製到美國的next [3] 中 國 1  將英國節點還原為空節點 [4] -1 [5] -1 [6] 英 國 2 → -1 [7] 蘇 俄 [8] -1 3 1 6 2 7 3 中國 1 英國 2 法國 7 蘇俄 美國 6→2 首節點 德明科技大學資訊科技系

10 指標 Pointer ◎變數是存放資料的地方 int i, j; ◎指標是存放位址的地方 int *p; 5 i j i p
p 指向 i p 裡面存放 i 的位址 *p 是 “p 所指變數” 的同義詞 相當於 j = i ; *p = 10 ; 10 i p 相當於 i=10 ; j p i j = *p ; 10 10 德明科技大學資訊科技系

11 結構 Structure student S1; //宣告S1變數 S1.age = 18 ; S1.height = 160 ;
結構則是將不同型別的元素集合起來，形成一種新的資料型別（結構） 1. struct student { 2. char name[8]; //姓名欄位 3. int age; //年齡欄位 4. int height; //身高欄位 5. } ; 此時就會產生一種叫做student的新結構體，這種結構體含有三個欄位 name age height S1 student S1; //宣告S1變數 S1.age = 18 ; S1.height = 160 ; strcpy(S1.name, “Mary”) ; Mary 18 160 name age height S1 德明科技大學資訊科技系

12 動態配置節點實作鏈結串列 鏈結串列所需的節點 資料：以結構的方式呈現多元資料 鏈結：以指標的方式動態配置節點 宣告 動態配置節點
typedef struct listnode { int data; // 資料欄位 struct listnode *next; // 鏈結欄位 } NODE; // 結點的宣告 NODE *listA; //C語言用 malloc 配置記憶體 listA = (NODE *) malloc( sizeof(NODE)) ; //C++語言用 new 配置記憶體 listA = new NODE ; data next listA 德明科技大學資訊科技系

13 鏈結串列 鏈結串列 由一個或一個以上動態記憶體分配的節點 (node)所組成
p6-10 鏈結串列 由一個或一個以上動態記憶體分配的節點 (node)所組成 每一個節點至少會有兩個或兩個以上的欄位，分別存放資料及指標，此指標稱為鏈結(link) 若某節點無下一個節點，則此節點的連結為空指標(Null) 德明科技大學資訊科技系

14 鏈結串列特性 各節點不一定要佔用連續的記憶體空間 各節點之資料型態不一定要相同 插入與刪除節點方便 重點是以指標鏈結串起
鏈結串列各元素在記憶體之位置是不連續的 鏈結串列由動態記憶體分配的節點(Node)串接而成 相形之下，陣列為一個循序(Sequential)之記憶體結構 德明科技大學資訊科技系

15 德明科技大學資訊科技系

16 單向鏈結串列 節點結構 雙向鏈結串列 節點結構 德明科技大學資訊科技系

17 單向鏈結串列與雙向鏈結串列比較 德明科技大學資訊科技系

18 單向鏈結串列 typedef struct node //以結構來表示節點 { int data; // data儲存節點資料項目
struct node *link; // link儲存下一個節點的位址 }NODE; NODE *list; 德明科技大學資訊科技系

19 指向串列的第一個節點，而首節點並沒有任何資料
其中 list：指向串列前端之指標 首節點(Head Node): 指向串列的第一個節點，而首節點並沒有任何資料 德明科技大學資訊科技系

20 單向鏈結串列的建立 list=NewNode( ); listdata=10; listlink=NULL; 德明科技大學資訊科技系

21 單向鏈結串列的插入節點 有三種不同的情形： 在串列的第一個節點前插入節點 在串列的最後一個節點後面插入節點 在串列的中間位置插入節點
德明科技大學資訊科技系

22 在串列的第一個節點前插入節點 把新節點的指標指向串列首，再把串列首移到新節點上即可 程式怎麼寫? 德明科技大學資訊科技系

23 在串列的最後一個節點後面插入節點 把串列的最後一個節點的指標指向新節點，新節點再指向NULL即可 程式怎麼寫? 德明科技大學資訊科技系

24 串列的中間位置插入節點 如果插入的節點是在P與Q之間，只要將P節點的指標指向新節點R，新節點的指標指向Q節點即可 程式怎麼寫?
德明科技大學資訊科技系

25 單向鍵結串列的刪除節點 有三種不同的情形： 刪除串列的第一個節點 刪除串列內的中間節點 刪除串列後的最後一個節點 德明科技大學資訊科技系

26 刪除串列的第一個節點 把串列首指標指向第二個節點 不要忘記將被刪除的節點釋放記憶體 程式怎麼寫? 德明科技大學資訊科技系

27 刪除串列內的中間節點 只要將刪除節點的前一個節點的指標，指向欲刪除節點的下一個節點即可 不要忘記將被刪除的節點釋放記憶體 程式怎麼寫?
德明科技大學資訊科技系

28 刪除串列的第一個節點 只要指向最後一個節點的指標，直接指向NULL即可 不要忘記將被刪除的節點釋放記憶體 程式怎麼寫?
德明科技大學資訊科技系

29 鏈結串列的反轉 將每個節點的鏈結指標往回指 德明科技大學資訊科技系

30 將目前的節點(current)指向Null，並且pt指向首節點的下一個節點
步驟一 將目前的節點(current)指向Null，並且pt指向首節點的下一個節點 德明科技大學資訊科技系

31 步驟二 使用while迴圈來將串列反轉 德明科技大學資訊科技系

32 德明科技大學資訊科技系

33 德明科技大學資訊科技系

34 步驟三 最後一個反轉後變成第一個節點 德明科技大學資訊科技系

35 鏈結串列的連結 兩個鏈結串列首尾相連 德明科技大學資訊科技系

36 鏈結串列的長度 鏈結串列內不含首節點的節點個數 例如下圖長度是4 德明科技大學資訊科技系

37 鏈結串列的長度 德明科技大學資訊科技系