Presentation is loading. Please wait.

Presentation is loading. Please wait.

Chapter 4 鏈結串列 Linked List 2019/5/14.

Similar presentations


Presentation on theme: "Chapter 4 鏈結串列 Linked List 2019/5/14."— Presentation transcript:

1 Chapter 4 鏈結串列 Linked List 2019/5/14

2 設計串列的新增、刪除、走訪的演算法 建立 新增 刪除 走訪 2019/5/14

3 說明 使用new node表示向系統要空間產生新節點 使用free node表示將節點所佔的空間釋放 節點結構有兩部分
課本使用 函數malloc() 使用free node表示將節點所佔的空間釋放 課本使用 函數free() 使用malloc(), free()等實作問題,稍後再談 節點結構有兩部分 data link

4 範例4.2 建立一串列,內有兩個節點 2019/5/14

5 對照P.4-10 程式4.2 圖4.5 create2 () { list_pointer first, second; //這一行可以不管,假裝沒看見 first=new node; //課本是 first =… malloc(…) second=new node; second->link=null; second->data=20; first->data=10; first->link=second; } 注意節點之link欄位設定的先後次序 first second

6 新增節點 2019/5/14

7 ptr … 10 20 x 50 y temp node 說明﹕ptr為某一串列第一個節點,而你想要新增一節點temp到節點node後
insert ( list_pointer *ptr, list_pointer node) { list_pointer temp; temp=new node; //課本﹕測試是否有足夠記憶體產生新節點temp temp->data=50; if (*ptr!=null) { //當「非空串列」時 temp->link=node->link; node->link=temp; } else { //當「空串列」時 temp->link=null; *ptr=temp; ptr 10 20 x 50 y temp node

8 刪除節點 2019/5/14

9 ptr為串列開始(亦即第一個節點)、node為欲刪除節點,trail為node前一個節點
當trail=null時,表示欲刪除第一個節點 delete ( list_pointer *ptr, trail, node) { if (trail != null) //若node非第一個節點 trail->link=node->link; else //若node為第一個節點 *ptr=(*ptr)->link; free(node); } trail node ptr bat cat mat sat vat

10 列出串列所有節點 2019/5/14

11 ptr表示串列的第一個節點 ptr bat cat mat sat vat print_list (ptr) {
for (; ptr; ptr=ptr->link) printf(“%4d”, ptr->data); } 這樣改寫比較清楚﹕ while (ptr!=null) { print(ptr->data); ptr=ptr->link ptr bat cat mat sat vat

12 練習 2019/5/14

13 綠色數字為該節點的記憶體位址 將link的位置填滿,使其形成一串列 問題﹕ ptr為串列之第一個節點,其值為?
5 15 22 9 7 ptr bat cat mat sat vat 綠色數字為該節點的記憶體位址 將link的位置填滿,使其形成一串列 問題﹕ ptr為串列之第一個節點,其值為? 將節點mat刪除,如何更改link值? 新增一節點dat至sat後,如何更改link值?

14 將單向鏈結串列所有節點清除 將兩單向鏈結串列連結 將單向鏈結串列反轉
更多單向鏈結串列的運算 將單向鏈結串列所有節點清除 將兩單向鏈結串列連結 將單向鏈結串列反轉 2019/5/14

15 單向鏈結串列的其他運算 串列清除 串列反轉 串列連結 釋放所走訪過的串列節點,直到所有節點走遍為止 將串列的節點順序顛倒
將一串列的head接到另一個串列的尾端

16 Recall 回想一下單向鏈結串列的「走訪所有節點」 print_list (ptr) { while (ptr!=null) {
print(ptr->data); ptr=ptr->link } 這個演算法可以應用在類似的運算

17 串列清除 2019/5/14

18 串列清除 print_list (ptr) { while (ptr!=null) { erase(ptr) {
print(ptr->data); ptr=ptr->link } erase(ptr) { while (ptr!=nULL) { q=ptr; //使用q指向欲刪除的節點 以免使用ptr,造成刪除後, 無法取得ptr=ptr->next; ptr=ptr->next; free(q); }

19 串列反轉 2019/5/14

20 串列反轉 利用三個指標完成串列反轉 先想想,有三個節點,結構與指標表示如下圖,你如何完成反轉? trail, middle, lead
意即,lead一開始指向head所指向的節點 先想想,有三個節點,結構與指標表示如下圖,你如何完成反轉? t m l

21 串列反轉 (程式4.17) list_pointer invert (list_pointer lead) { list_pointer middle, trail ; middle = NULL; while (lead != null) { trail = middle; middle = lead; lead = lead->link; middle->link = trail; //將M節點反轉 } return middle; //最後M就是反轉後的串列第一個節點 //向右移動T,M L三個指標

22 串列反轉 (程式4.17) m t l l m t m l m l t m l t t m l

23 串列連結 2019/5/14

24 串列連結 先看一個簡單的問題 假設ptr2串列要連到ptr1串列之後 而且,你知道ptr1串列的尾端節點為trail1
你要如何完成此兩個串列的連結 trail1 ptr1 ptr2

25 串列連結 如何找到ptr1的尾端節點在哪裡??? print_list (ptr) { while (ptr!=null) {
print(ptr->data); ptr=ptr->link } temp=ptr1; while (temp->link != null) { temp=temp->link } 最後,temp即為尾端節點

26 串列連結 Concatenate(){ if (is_empty(ptr1) return ptr2為新的串列開頭節點; else {
temp=ptr1; while (temp->link != null) { temp=temp->link } temp->link=ptr2; return ptr1為連結後的串列開頭節點;

27 練習 如何計算一個單向鏈結串列的長度

28 串列的應用 堆疊與佇列 多項式 2019/5/14

29 堆疊與佇列 2019/5/14

30 圖4.10 堆疊底  top    NULL (a) Linked Stack front rear
   top (a) Linked Stack front (b) Linked Queue rear element link 堆疊底 element link

31 利用串列設計堆疊時﹕ 新增、刪除節點的演算法可以由程式4.3、4.4修改 新增、刪除節點的演算法與程式4.3、4.4有何不同

32 多項式的應用 2019/5/14

33 Recall﹕用陣列表示多項式 問題:係數是0的位置都是空間浪費

34 多項式 – 用鏈結串列 以單向鏈結串列表示多項式 coef expon link b 8 14 -3 10 null 10 6
struct poly_node { int coef ; int expon ; struct poly_node * link ; } ; Example: coef expon link b -3 10 null

35 多項式相加 多項式相加的規則: x的指數相同時,係數才可以相加 x的指數不同時,這一項的係數就保留 HOW??

36 多項式相加 2 8 1 0 a -3 10 b 11 14 a->expon == b->expon d 2 8 1 0 a -3 10 b 11 14 -3 10 a->expon < b->expon d

37 多項式相加 時間複雜度O(m+n) 兩多項式次數分別為m, n 3 14 2 8 1 0 a 8 14 -3 10 10 6 b 11 14
2 8 1 0 a -3 10 b 11 14 -3 10 2 8 d a->expon > b->expon

38 多項式相加 poly_pointer padd(poly_pointer a, poly_pointer b) {
poly_pointer front, rear, temp; int sum; rear =(poly_pointer)malloc(sizeof(poly_node)); if (IS_FULL(rear)) { fprintf(stderr, “The memory is full\n”); exit(1); } front = rear; while (a && b) { switch (COMPARE(a->expon, b->expon)) { case -1: /* a->expon < b->expon */ attach(b->coef, b->expon, &rear); b= b->link; break; case 0: /* a->expon == b->expon */ sum = a->coef + b->coef; if (sum) attach(sum,a->expon,&rear); a = a->link; b = b->link; case 1: /* a->expon > b->expon */ attach(a->coef, a->expon, &rear); a = a->link; for (; a; a = a->link) for (; b; b=b->link) rear->link = NULL; temp = front; front = front->link; free(temp); return front;

39 多項式相加

40 多項式相加

41 多項式相加


Download ppt "Chapter 4 鏈結串列 Linked List 2019/5/14."

Similar presentations


Ads by Google