# 2021q1 Homework1 (quiz1) contributed by < `ChenBoSyun` > ###### tags: `linux2021` ## Outline [toc] ## 程式碼分析 ### linked list struct :::info 既然已經 typedef node_t 為何不用 `node_t *next`，有其他考量或是單純 coding style ::: ```c typedef struct __node { int value; struct __node *next; } node_t; ``` ### list_add_node_t 這段程式碼是將 node_t 插入 list 的頭，並且把 list 重新指向 node_t ```c static inline void list_add_node_t(node_t **list, node_t *node_t) { node_t->next = *list; *list = node_t; } ``` 下圖為進入 list_add_node_t 時的狀態，C 語言 pass by value 會配置一段記憶體空間，將傳入參數的值複製到所配置的記憶體 ```graphviz digraph { rankdir=LR; node [shape=record]; head [label="{ <data> head | <ref> }"]; "*node_t" [label="{ <data> node | <ref> }"]; "list" -> "*list" -> head; "list(in_func)" -> "*list"; "node_t" -> "*node_t"; "node_t(in_func)" -> "*node_t"; } ``` 下圖為 `node_t->next = *list;` 後的狀態，若傳入參數是 ```graphviz digraph { rankdir=LR; node [shape=record]; head [label="{ <data> head | <ref> }"]; "*node_t" [label="{ <data> node | <ref> }"]; "list" -> "*list" -> head; "list(in_func)" -> "*list"; "node_t" -> "*node_t"; "node_t(in_func)" -> "*node_t"; "*node_t" -> head; } ``` 下圖為 ` *list = node_t;` 後的狀態，這邊的動作是移動 list 的指標到 node，因此傳入的型態是 list 指標的指標，這樣才會確實的將 node address 指派給 list 的指標 ```graphviz digraph { rankdir=LR; node [shape=record]; head [label="{ <data> head | <ref> }"]; "*node_t" [label="{ <data> node | <ref> }"]; "list" -> "*list" -> "*node_t"; "list(in_func)" -> "*list"; "node_t" -> "*node_t"; "node_t(in_func)" -> "*node_t"; "*node_t" -> head; } ``` :::warning [延伸思考] 若傳入的參數是 list 的指標 ```c static inline void list_add_node_t(node_t *list, node_t *node_t) { node_t->next = list; *list = *node_t; } ``` 下圖是執行 list_add_node_t 後的結果 ```graphviz digraph { rankdir=LR; node [shape=record]; head [label="{ <data> node | <ref> }"]; "*node_t" [label="{ <data> node | <ref> }"]; "list" -> head; "list(in_func)" -> head; "node_t" -> "*node_t"; "node_t(in_func)" -> "*node_t"; "*node_t" -> head; head -> head; } ``` ::: ### list_concat list concat 從部分程式碼與涵式名稱可以推測，其功能是將鏈結串列 right 接在 鏈結串列 left 後面 實際上， left 是用來紀錄 `node_t.next` 的記憶體位址，`node_t.next` 的型態是 `node_t *` ，因此 left 的型態才會是 `node_t **` 此外基於 pass by value 的機制， 引數 left 本身的值沒有改變，還是指向 list 的開頭 ```c= static inline void list_concat(node_t **left, node_t *right) { while (*left) left = &((*left)->next); *left = right; } ``` ```c #1 static inline void list_concat(node_t **left, node_t *right) ``` 下圖是進入 list_concat 後的示意圖 ```graphviz digraph { rankdir=LR; node [shape = box]; "left" [label= "left"]; "left(inFunc)" [label= "left(inFunc)"]; "*left" [label= "*left"]; "right" [label= "right"]; NULL [label= "NULL"]; node [shape = record]; node1 [label="{ <data> node1 | <ref> }"]; node2 [label="{ <data> node2 | <ref> }"]; node3 [label="{ <data> node3 | <ref> }"]; node_n [label="{ <data> node_n | <ref> }"]; { rank="same"; "left" -> "*left"; "left(inFunc)" -> "*left"; } "*left" -> node1 -> node2 -> node3 -> NULL; "right" -> node_n; } ``` ```c #3 left = &((*left)->next); ``` 每次迴圈，都會指派下一個 `node_t.next` 的記憶體位址給 left ```graphviz digraph { rankdir=LR; node [shape = box]; "left" [label= "left"]; "left(inFunc)" [label= "left(inFunc)"]; "*left" [label= "*left"]; NULL [label= "NULL"]; node [shape = record]; node1 [label="{ <data> node1 | <ref> }"]; node2 [label="{ <data> node2 | <ref> }"]; node3 [label="{ <data> node3 | <ref> }"]; { rank="same"; "left" -> "*left"; } "*left" -> node1 -> node2 -> node3 -> NULL; "left(inFunc)" -> node1:ref; } ``` ```c #2 while (*left) ``` 迴圈結束條件是 `*left == NULL`，迴圈結束時 left 的值是最後一個 `node_t.next` 的記憶體位址，如下圖 ```graphviz digraph { rankdir=LR; node [shape = box]; "left" [label= "left"]; "left(inFunc)" [label= "left(inFunc)"]; "*left" [label= "*left"]; NULL [label= "NULL"]; node [shape = record]; node1 [label="{ <data> node1 | <ref> }"]; node2 [label="{ <data> node2 | <ref> }"]; node3 [label="{ <data> node3 | <ref> }"]; { rank="same"; "left" -> "*left"; } "*left" -> node1 -> node2 -> node3 -> NULL; "left(inFunc)" -> node3:ref; } ``` ```c #4 *left = right; ``` ```graphviz digraph { rankdir=LR; node [shape = box]; "left" [label= "left"]; "left(inFunc)" [label= "left(inFunc)"]; "*left" [label= "*left"]; node [shape = record]; node1 [label="{ <data> node1 | <ref> }"]; node2 [label="{ <data> node2 | <ref> }"]; node3 [label="{ <data> node3 | <ref> }"]; node_n [label="{ <data> node_n | <ref> }"]; { rank="same"; "left" -> "*left"; } "*left" -> node1 -> node2 -> node3 -> node_n; "left(inFunc)" -> node3:ref; } ``` ### quicksort 參考 [quicksort wiki](https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F) quicksort 使用 Divide and conquer 的策略 實作分為三個步驟 1. 從數列中選定一個基準 (pivot) 2. 將數列分成兩個子數列，分別是比 pivot 大的數列，和比 pivot 小的數列 3. 遞迴執行 1,2 步驟 ```c＝ void quicksort(node_t **list) { if (!*list) return; node_t *pivot = *list; int value = pivot->value; node_t *p = pivot->next; pivot->next = NULL; node_t *left = NULL, *right = NULL; while (p) { node_t *n = p; p = p->next; list_add_node_t(n->value > value ? AAA : BBB, n); } quicksort(&left); quicksort(&right); node_t *result = NULL; list_concat(&result, left); CCC; *list = result; } ``` 遞迴程式需要設定結束的條件，否則會陷入無窮遞迴 quicksort 在實作上會重複將數列切成左右兩個子數列，直到子數列小到不能再分割，也就是 `NULL` ```c #1 if (!*list) #2 return; ``` 這段程式碼是將 list 的開頭當作 pivot，並且 `pivot->next = NULL` 代表 pivot 是只有一個元素的 linked list，這是為了確保 `list_concat` 的正確性 ```c node_t *pivot = *list; int value = pivot->value; node_t *p = pivot->next; pivot->next = NULL; ``` linked list 的分割比起 array 還要單純，只要走訪一遍linked list，將 value 比 pivot 小的加到left ，大的加到 right ```c node_t *left = NULL, *right = NULL; while (p) { node_t *n = p; p = p->next; list_add_node_t(n->value > value ? &right : &left, n); } ``` 遞迴過程，分別對 left 跟 right 排序 ``` quicksort(&left); quicksort(&right); ``` 在對 left, right 都排序過後，只要將 left, pivot, right 接在一起就好 ```c node_t *result = NULL; list_concat(&result, left); list_concat(&result, pivot); list_concat(&result, right); *list = result; ```