# 2021q1 Homework1 (quiz1) contributed by < `Shanola` > [第一周題目](https://hackmd.io/@sysprog/linux2021-quiz1) [GitHub程式碼](https://github.com/Shanola/NCKU-Linux2021-Quiz1) ## 測驗 `1` ### 程式碼 考慮**單向** linked list 結構，已知**無 circular**，嘗試以**遞增**順序進行 Quick sort，以下為有進行新增或修改的程式碼片段 ```cpp= static inline void list_concat(node_t **left, node_t *right) { while (*left) left = &((*left)->next);// LLL *left = right; } 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 ? &right/*AAA*/ : &left/*BBB*/, n); } quicksort(&left); quicksort(&right); node_t *result = NULL; list_concat(&result, left); list_concat(&result, pivot); list_concat(&result, right); ///CCC *list = result; } node_t *list_make_node_t(node_t *list, int value) { node_t *n = malloc(1 * sizeof(node_t)); if (!n) { assert(n && "malloc error"); return NULL; } n->value = value; n->next = NULL; n->prev = NULL; if (!list) { return n; } else { node_t *tmp = list; while (tmp->next) { tmp = (tmp->next); } tmp->next = n; n->prev = tmp; return list; } } void list_free(node_t **list) { if (!(*list)->next) { free(*list); } else { list_free(&((*list)->next)); } } ``` ### 程式碼解析 首先 `list_add_node_t` 是一個沒有回傳值 (void) 且在編譯時被展開到呼叫位置 (static inline) 的函式，具有一個指向 node_t 指標的指標 `list`，及指向 node_t 的指標 `node` 兩個參數，負責**將節點加到 list 前方**： ```cpp= static inline void list_add_node_t(node_t **list, node_t *node) { node->next = *list; *list = node; } ``` ```graphviz digraph G { rankdir=LR; { listp [label="*list"]; listpp [label="list"]; n [label="node"]; node_t [shape=record,label="{<data> *node| <ref> next}"]; list [shape=record,label="{<data> **list| <ref> next}"]; other [shape=record,label="..."]; n->node_t; listpp->listp; listp->list [color=blue]; list->other } } ``` ```graphviz digraph G { rankdir=LR; { listp [label="*list"]; listpp [label="list"]; n [label="node"]; node_t [shape=record,label="{<data> *node| <ref> next}"]; list [shape=record,label="{<data> **list| <ref> next}"]; other [shape=record,label="..."]; n->node_t->list->other; listpp->listp; listp->node_t [color=red]; } } ``` 再來 `list_concat` **負責將兩個 list 連接起來**： ```cpp static inline void list_concat(node_t **left, node_t *right) { while (*left) left = &((*left))->next;// LLL *left = right; } ``` 在這個遞迴式的 `quicksort` 函式中，會先以 list 中的第一個節點當作 pivot，將所有比 pivot 小的值連接到 `left` list 上，而比較大的則會接到 `right` list 上，然後再對這兩個 list 遞迴做 quick sort，最後再將 left, pivot, right 連接起來。 ### Random 問題 `long int random(void)` 是屬於 stdlib.h 標準函式庫中的函式，該函式根據 `seed` 去 table 找大小為 31 的 long int 的序列的其中一個值來回傳，但這個 seed 若沒有被指定時會自動餵入 1，也因此使得 random 每次回傳的亂數看似是固定的。 有一個常見的解決方法是使用 `void srandom(unsigned int seed)` 來填入 seed，填入的 seed 可以用一個**隨時**變化的值(譬如時間），如此一來 random 回傳的值所屬的序列便會隨時間變換，每次回傳的值的序列也不一樣。 ### Optimized q-sort 將 `__node` 結構多一個指標以指向前一個節點： ```cpp= typedef struct __node { int value; struct __node *next; struct __node *prev; } node_t; ``` 有改寫過後的函式變成： `list_make_node_t` ```cpp node_t *list_make_node_t(node_t *list, int value) { node_t *n = malloc(1 * sizeof(node_t)); if (!n) { assert(n && "malloc error"); return NULL; } n->value = value; n->next = NULL; n->prev = NULL; if (!list) { return n; } else { node_t *tmp = list; while (tmp->next) { tmp = (tmp->next); } tmp->next = n; n->prev = tmp; return list; } } ``` ###### tags: `linux2021`