本章內容 3-1 串列的定義 3-2 用陣列直接儲存串列循序配置串列 3-3 串列加上鏈結鏈結配置串列 3-4 用結構體陣列實作鏈結串列 3-5 指標與結構體 3-6 動態配置節點實作鏈結串列 3-7 鏈結串列的其他運算 3-8 環狀鏈結串列 3-9 雙向鏈結串列 *3-10 鏈結串列的應用 2

Size: px

Start display at page:

Download "本章內容 3-1 串列的定義 3-2 用陣列直接儲存串列循序配置串列 3-3 串列加上鏈結鏈結配置串列 3-4 用結構體陣列實作鏈結串列 3-5 指標與結構體 3-6 動態配置節點實作鏈結串列 3-7 鏈結串列的其他運算 3-8 環狀鏈結串列 3-9 雙向鏈結串列 *3-10 鏈結串列的應用 2"

订鸠洪
5 years ago
Views:

1 第三章 Linked List 版權屬作者所有, 非經作者同意不得用於教學以外用途 1

2 本章內容 3-1 串列的定義 3-2 用陣列直接儲存串列循序配置串列 3-3 串列加上鏈結鏈結配置串列 3-4 用結構體陣列實作鏈結串列 3-5 指標與結構體 3-6 動態配置節點實作鏈結串列 3-7 鏈結串列的其他運算 3-8 環狀鏈結串列 3-9 雙向鏈結串列 *3-10 鏈結串列的應用 2

3 3-1 串列 (list) 的定義串列是許多項目有順序的排列 ( 集合 (set) 裡的元素則沒有前後之分 ) 二次大戰同盟國國名串列中國美國英國蘇俄 10 到 30 之間的質數由小到大排列常用於串列上的運算 : 1. 插入新節點 (Insert) - 在原有的串列中加入一個新的元素 2. 刪除某節點 (Delete) - 將某一個元素從原本的串列中移除 3. 找尋某節點 (Find) - 依照需求將所指定的 ( 或第幾個 ) 元素值讀出來串列的實作方式 1. 循序配置串列 (sequential allocation list) 2. 鏈結配置串列 (linked allocation list) 3

4 3-2 用陣列直接儲存串列循序配置串列中國 Alli[0] 11 Prime[0] 美國 Alli[1] 13 Prime[1] 英國 Alli[2] 17 Prime[2] 蘇俄 Alli[3] 19 Prime[3] 23 Prime[4] 29 Prime[5] 利用陣列循序儲存串列的方式, 具有以下的優缺點 : 優點 : 只要標明要查詢第幾個元素, 就能很快地根據元素註標讀寫該元素, 因為陣列的隨機存取 (random access) 效率相當高, 時間複雜度為 O(1) 缺點 : 插入元素 (insert) 和刪除元素 (delete) 兩個動作所需時間的複雜度為 O(n) 這是因為陣列所有元素在記憶體中的實體位置 (physical location) 是連續的, 因此不論是執行元素的插入或刪除, 都必須進行資料的搬移, 以維持正確的順序 ( 參考 2.2 節 ) 4

5 3-3 串列加上鏈結鏈結配置串列鏈結串列 (linked list) 可以用來解決陣列循序配置的缺點 : 1. 鏈結串列的元素之間不必實體連續 ( 不必依元素順序佔用記憶體中的連續位址 ), 只要有邏輯上 (logical) 的順序存在即可 2. 鏈結 (link) 就是用來維持這順序的工具, 它可以告訴我們下一個元素放在哪裡無首節點 ( 由一個指標指到 ) lista 中國美國英國蘇俄有首節點 ( 為了往後方便運算 ) 首節點中國美國英國蘇俄 5

6 3-4 用結構體陣列實作鏈結串列 data 欄位存放資料本身, next 欄位存放下一個資料的位置 Table[0] [1] [2] [3] [4] [5] [6] [7] [8] 美中英蘇 data 國國國俄 next 首節點 : 從這裡開始 -1: 空節點節散散佈在陣列中, 實體位置沒有連續, 但根據鏈結可以得到以下次序中國 1 美國 6 英國 7 蘇俄 0 首節點 6

7 要在英國節點之後插入一個新節點法國 data next Table[0] [1] [2] [3] [4] [5] [6] [7] [8] 首節點 3 美法中英蘇國國國國俄找到一個空節點 (next 值為 -1), 填入資料法國找到英國, 或者條件已知將英國的 next (7) 複製到法國的 next 將法國的位置 (2) 填入英國的 next 中國 1 美國 6 英國 7 2 蘇俄 0 2 法國 7 7

要刪除英國節點 data Table[0] 3 首節點 [1] [2] [3] [4] [5] [6] [7] [8] 美法中英蘇國國國國俄 next 3 6 2 2 7 1-1 -1-1 0-1

8 要刪除英國節點 data Table[0] 3 首節點 [1] [2] [3] [4] [5] [6] [7] [8] 美法中英蘇國國國國俄 next 沿著串列找到英國 (6), 以及英國的前一個節點美國 (1) 將英國的 next (2) 複製到美國的 next 將英國節點還原為空節點中國 1 美國 6 2 英國 2 法國 7 蘇俄 0 8

9 用陣列結構來實作鏈結串列用陣列結構來實作鏈結串列的優缺點 : 優點 - 鏈結方式簡單 ; 利用 next 欄位即可取得下一節點的位置缺點 - 須先宣告陣列大小 ; 缺乏彈性 9

10 例 3.2: 新增阿里山加在太魯閣之後 data next table[0] 5 table[1] 日月潭 2 table[2] 墾丁 0 table[3] -1 table[4] -1 table[5] 溪頭 7 table[6] -1 table[7] 太魯閣 1 table[8] -1 data next table[0] 5 table[1] 日月潭 2 table[2] 墾丁 0 table[3] 阿里山 -1 1 table[4] -1 table[5] 溪頭 7 table[6] -1 table[7] 太魯閣 1 3 table[8] -1 鏈結串列圖示溪頭 7 太魯閣 1 日月潭 2 墾丁 0 首節點插入新節點溪頭 7 太魯閣 3 阿里山 1 日月潭 2 墾丁 0 首節點 10

11 例 3.3: 刪除太魯閣 data next table[0] 5 table[1] 日月潭 2 table[2] 墾丁 0 table[3] 阿里山 1 table[4] -1 table[5] 溪頭 7 table[6] -1 table[7] 太魯閣 3 table[8] -1 data next table[0] 5 table[1] 日月潭 2 table[2] 墾丁 0 table[3] 阿里山 1 table[4] -1 table[5] 溪頭 7 3 table[6] -1 table[7] 太魯閣 3-1 table[8] -1 鏈結串列圖示溪頭 7 太魯閣 3 阿里山 1 日月潭 2 墾丁 0 首節點刪除節點首節點溪頭 3 阿里山 1 日月潭 2 墾丁 0 11

12 3-5 ( 複習 ) 指標與結構體變數是存放資料的地方指標是存放位址的地方 i = 5 ; j = i ; i j 5 5 int i, j; int *p; i = 5 ; j = i ; p = &i ; p 指向 i &: 取址符號 p i p = &i ; 5 p 裡面存放 i 的位址 12

13 *p 是 p 所指變數的同義詞相當於 i=10 ; int i, j; int *p; i = 5 ; j = i ; p = &i ; *p = 10 ; j = *p ; *p = 10 ; 10 相當於 j = i ; j p j = *p ; 10 p i i 10 13

14 結構體 (structure) 結構體是將不同型別的元素集合起來, 形成一種新的資料型別 1. struct student { 2. char name[8]; // 姓名欄位 3. int age; // 年齡欄位 4. int height; // 身高欄位 5. } ; 此時就會產生一種叫做 student 的新結構體, 這種結構體含有三個欄位, 其中姓名欄位是一個字元陣列年齡欄位是整數身高欄位也是整數例 : struct student S1; name age height S1 S1.age = 18 ; S1.height = 160 ; strcpy(s1.name, Mary ) ; name age height S1 Mary 宣告 typedef int INTEGER ; 就產生一個新的型別叫 INTEGER, 可以根據這個型別來宣告變數 : INTEGER i, j ; 它的效果就好像宣告 int i, j; 一樣 14

15 typedef 與 struct 合併使用 // 就可不需用 struct 來宣告變數 typedef struct student { char name[8]; int age; int height; } STUDENT; STUDENT S1, S2; 15

16 3-6 動態配置節點實作鏈結串列動態配置節點方式實作鏈結串列, 常會執行的串列運算按照順序為 : 1. 宣告節點結構 2. 動態配置節點 3. 指標在串列中移動 4. 插入新節點 5. 刪除節點 6. 建立串列 16

17 1. 宣告節點結構 typedef struct listnode { int data; /* 資料欄位 */ struct listnode *next; /* 鏈結欄位 */ } NODE; NODE *lista; 注意 : 鏈結欄位改為指標 2. 動態配置節點 lista = (NODE *) malloc (sizeof(node)) ; 在 C++ 語言中則可用 new 運算子 lista = new NODE ; lista data next e.g., 20 填入資料欄位,NULL 填入鏈結欄位 : lista->data = 20 ; lista->next = NULL ; 17

18 2. 動態配置節點 (cont d) lista->data = 20 ; lista->next = NULL ; 相當於 (*lista).data = 20 ; (*lista).next = NULL ; 不需要 lista 所指的節點時, 需動態歸還 ( 記憶體 ): C: free(lista); C++: delete lista; 18

19 3. 指標在串列中移動 p 首節點 // 執行敘述 p = p->next ; // 指標 p 指向下一個節點 p 首節點 19

20 例 3.4: 走訪整個鏈結串列 void ListTraverse(ListNode *head) { ListNode *p = head; p = p->next ; // 指標 p 沿著鏈結而指向下一個節點 while ( p!= NULL ) { printf( \n%d, p->data ); // 印出節點資料 p = p->next ; } } 20

21 要將指標 NewNode 所指到的新節點插入指標 p 所指舊節點之後 p 舊節點新節點 NewNode 第一步 : 掛上新節點的鏈結 NewNode->next = p->next ; p 第二步 : 改變舊節點的鏈結 NewNode p->next = NewNode ; p NewNode p NewNode 21

22 1. int InsertAfter(ListNode *p, int value) 2. { ListNode *NewNode; 3. NewNode = (ListNode*) malloc(sizeof(listnode)); // 動態配置節點 // C++: NewNode = new ListNode; 4. if (NewNode == NULL) 5. return FALSE; // 配置失敗 6. NewNode->data = value; // 將新節點的值填入 7. NewNode->next = p->next; // 掛上新節點的鏈結 8. p->next = NewNode; // 改變原有節點的鏈結 9. return TRUE; // 傳回成功訊息 10. } 22

23 要刪除指標 Node 所指到的節點 Node 第一步 : 找到前一個節點 PreNode = GetPreNode(head,Node) ; PreNode Node 第二步 : 前一節點的鏈結, 使它越過舊節點 PreNode->next = Node->next ; PreNode Node 第三步 : 將舊節點動態歸還 free( Node ) ; PreNode 23

24 1. int DeleteNode(ListNode *head, ListNode *OldNode) 2. { ListNode *PreNode; 3. if (head == OldNode) // 不可刪除首節點 4. return FALSE; // 非法刪除, 傳回失敗訊息 5. PreNnode = GetPreNode(head, OldNode); // 找到前一節點 6. if ( PreNode == NULL) //OldNode 節點不在串列中 7. return FALSE; // 無法刪除, 傳回失敗訊息 8. PreNode->next = OldNode->next; // 越過刪除原有節點 9. free(oldnode); // 歸還被刪除節點 // C++: delete OldNode; 10. return TRUE; 11. } 24

25 1. ListNode *GetPreNode(ListNode *head, ListNode *OldNode) 2. { ListNode *p, *q; 3. p= head; 4. q= head->next; //p 在左, q 在右 5. while ((q!= NULL) && (q!= OldNode)) 6. { p= q; 7. q= q->next; //p 與 q 各往右一步 8. } 9. if (q!= NULL) // 找到 10. return (p); 11. else 12. return (NULL); 13. } 25

26 6. 建立鏈結串列建立鏈結串列的方法是重複地將新節點加入串列新節點加入的位置 1. 可以是串列的前面 2. 也可以是在串列的尾端 ( 例 : 函式 InserTail ) 3. 也可以是在串列的特定地方 ( 例如按照 data 欄位大小排列 )

27 1. int InserTail(ListNode *head, int value) 2. { ListNode *NewNode, *p =head; 3. NewNode = (ListNode*) malloc(sizeof(listnode)); // 動態配置節點 // C++: NewNode = new ListNode; 4. if (NewNode == NULL) 5. return FALSE; // 配置失敗 6. NewNode->data = value; // 將新節點的值填入 7. NewNode->next = NULL; 8. While (p->next!= NULL) // 移到原本最後的節點 9. p= p->next; 10. p->next = NewNode; 11. return TRUE; // 傳回成功訊息 12. } 27

28 3-7 鏈結串列的其他運算計算串列長度 ( 節點數目 )-- 線性鏈結串列 head p 在這裡時, count = 0 p 在這裡時, count = 1 p 在這裡時, count = 2 p 在這裡時, count = 3 p 在這裡時, count = 4 int ListLength ( ListNode *head) { int counter = 0 ; ListNode *p = head->next ; while ( p!= NULL) { counter ++ ; p= p->next ; } return counter ; } p 在這裡時, 迴圈結束 28

29 串接兩鏈結串列 -- 線性鏈結串列 p ListA ListB void ListConcate ( ListNode *lista, ListNode *listb) { ListNode *p = lista ; while ( p->next!= NULL) // p 一路往右直到最後一個節點 p = p->next ; p->next = listb->next ; // 改變其鏈結 } 29

30 3-8 環狀鏈結串列 Head 線性鏈結串列最後節點 Head 環狀鏈結串列最後節點線性鏈結串列 : 要拜訪節點須從首節點開始最後節點的鏈結不接地, 而是指向首節點從任何一個節點開始, 都可以走訪所有節點繞回原起點就停止 30

31 例 3.5: 走訪整個環狀鏈結串列 void CListTraverse(ListNode *head) { ListNode *p = head; p = p->next ; // 指標 p 沿著鏈結而指向下一個節點 while ( p!= head) { printf( \n%d, p->data ); // 印出節點資料 p = p->next ; } } 31

32 3-9 雙向鏈結串列 Head 線性雙向鏈結串列環狀雙向鏈結串列 Head 宣告節點結構 typedef struct tagdlistnode { struct tagdlistnode *left; int data; struct tagdlistnode *right; } DListNode; 32

33 要將指標 NewNode 所指到的新節點插入指標 p 所指舊節點之右 p NewNode 第一步 : 掛上新節點的兩個鏈結 NewNode->left = p; NewNode->right = p->right ; p NewNode 第二步 : 改變舊節點的兩個鏈結 ; 注意順序! p->right->left = NewNode; p->right = NewNode ; p NewNode 33

34 雙向鏈結串列 1. int InsertAfter(DListNode *p, int value) 2. { DListNode *NewNode; 3. NewNode = (DListNode*) malloc(sizeof(dlistnode)); 4. if (NewNode == NULL) 5. return FALSE; // 配置失敗 6. NewNode->data = value; // 將新節點的值填入 7. NewNode->left= p; 8. NewNode->right= p->right; 9. p->right->left= NewNode; 10. p->right= NewNode; 11. return TRUE; // 傳回成功訊息 12. } 34

35 要刪除指標 p 所指到的節點 p 第一步 : 改變左邊節點的右指標使它越過舊節點 p->left->right = p->right ; p 第二步 : 改變右邊節點的左指標使它越過舊節點 p->right ->left = p->left ; p 第三步 : 將舊節點歸還系統 free( p ) ; 35

36 雙向鏈結串列 - 刪除 1. int DeleteNode(DListNode *p) 2. { if (p== NULL) 3. return FALSE; 4. p->left->right= p->right; 5. p->right->left= p->left; 6. free(p); 7. return TRUE; 8. } 36

37 3-10 鏈結串列的應用 * 多項式的表示與運算使用鏈結串列表示多項式, 每個非零項使用一個節點, 每個節點包含兩個資料欄位 : 係數欄位和冪次欄位, 以及一個鏈結欄位節點結構可以宣告為 : typedef struct tagplistnode { float coef ; /* 係數 */ } PListNode; int expo ; /* 冪次 */ struct tagplistnode *next ; /* 鏈結指標 */ 5x 4 可表示為 : 係數 5 4 冪次 37

38 A(x) = 5x x x +6 A B(x) = 9x x 2 B 多項式相加 1. 兩多項式分別從高冪次項往右掃瞄 2. 比較兩項冪次大小, 冪次大者, 複製此項至 C(x), 如果冪次相同, 則係數相加後, 同樣複製此項至 C(x) 3. 凡是已被複製的項, 多項式就往右移一項重複步驟 1,2, 直到兩個多項式都用完為止 38

39 1. 初始狀態 pa A pb B C ctail pb->exp(=5) 大於 pa->exp(=4), 複製 *pb,pb 往右一個節點 pa A pb B C ctail

40 3. pa->exp(=4) 大於 pb->exp(=2), 複製 *pa,pa 往右一個節點 A pa pb B C ctail pa->exp 等於 pb->exp, 新節點係數為 pa->coef 加 pb->coef, pa 及 pb 往右一個節點 A pa B C pb ctail

41 5. pb 已經接地, 將串列 A 剩下的節點複製到串列 C A pa B pb C ctail 41

42 副程式 (p. 3-43) PListNode *AddTail(PListNode *tail, gfloat co, int ex) PListNode *PolyAdd(PListNode *pa, PListNode *pb) 42

43 稀疏矩陣的表示 M = M 矩陣的 30 (5 6) 個元素中只有 9 個非零項, 使用率只有 9/30 = 30% 使用節點來表示每個非零項, 每個節點結構有 3 個資料欄位 data row col 之外, 兩個鏈結欄位 right down 同一列的節點藉著 right 鏈結成為一個串列, 同一行節點也藉著 down 鏈結成為一個串列節點的結構可以圖示為 : row down col data right 例如

44 M = c0 c1 c2 c3 c4 c r r r r r

45 程式題 6 (p.3-54) 1. 建立稀疏矩陣 2. 插入新節點 45

PowerPoint Presentation

PowerPoint Presentation 陣列與鏈結串列 NTU CSIE Outline 結構陣列鏈結串列單向鏈結串列之資料型態單向鏈結串列之基本運算作業結構陣列優點缺點使用容易刪除與插入造成資料移動頻繁浪費不必要之記憶體陣列長度為常數, 可能會不夠用 #include struct _student int math; int english; int computer; ; typedef struct