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

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

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

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

對照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

新增節點 2019/5/14

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

刪除節點 2019/5/14

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

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

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

練習 2019/5/14

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

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

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

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

串列清除 2019/5/14

串列清除 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); }

串列反轉 2019/5/14

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

串列反轉 (程式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三個指標

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

串列連結 2019/5/14

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

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

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

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

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

堆疊與佇列 2019/5/14

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

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

多項式的應用 2019/5/14

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

多項式 – 用鏈結串列 以單向鏈結串列表示多項式 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 8 14 -3 10 10 6 null

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

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

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

多項式相加 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;

多項式相加

多項式相加

多項式相加