# [2021q1](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 1 週測驗題 ###### tags: `linux2021` :::info 目的: 檢驗學員對 **[linked list](https://hackmd.io/@sysprog/c-linked-list)** 的認知 ::: ==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSdO1db0ubx7Aw08_9XBOyxbhd7vfj6kRgUnYXQxOSjf2vJ2DA/viewform)== ### 測驗 `1` 考慮一個單向 linked list,其結構定義為: ```cpp typedef struct __node { int value; struct __node *next; } node_t; ``` 已知不存在 circular (環狀結構),下方程式碼嘗試對該單向 linked list 進行 Quick sort,預期依據遞增順序。 ```cpp static inline void list_add_node_t(node_t **list, node_t *node_t) { node_t->next = *list; *list = node_t; } static inline void list_concat(node_t **left, node_t *right) { while (*left) 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 ? AAA : BBB, n); } quicksort(&left); quicksort(&right); node_t *result = NULL; list_concat(&result, left); CCC; *list = result; } ``` 對應的測試程式如下: ```cpp static bool list_is_ordered(node_t *list) { bool first = true; int value; while (list) { if (first) { value = list->value; first = false; } else { if (list->value < value) return false; value = list->value; } list = list->next; } return true; } static void list_display(node_t *list) { printf("%s IN ORDER : ", list_is_ordered(list) ? " " : "NOT"); while (list) { printf("%d ", list->value); list = list->next; } printf("\n"); } int main(int argc, char **argv) { size_t count = 20; node_t *list = NULL; while (count--) list = list_make_node_t(list, random() % 1024); list_display(list); quicksort(&list); list_display(list); if (!list_is_ordered(list)) return EXIT_FAILURE; list_free(&list); return EXIT_SUCCESS; } ``` 參考執行輸出: ``` NOT IN ORDER : 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359 IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016 ``` 請補完程式碼,使得執行符合預期。 ==作答區== LLL = ? * `(a)` `left = left->next` * `(b)` `left = (*left)->next` * `(c)` `left = &((*left)->next)` * `(d)` `*left = (*left)->next` AAA = ? * `(a)` `&pivot` * `(b)` `pivot` * `(c)` `&left` * `(d)` `left` * `(e)` `&right` * `(f)` `right` BBB = ? * `(a)` `&pivot` * `(b)` `pivot` * `(c)` `&left` * `(d)` `left` * `(e)` `&right` * `(f)` `right` CCC = ? * `(a)` `llist_concat(&result, right)` * `(b)` `list_concat(&result, pivot); list_concat(&result, right)` * `(c)` `list_concat(&result, right); list_concat(&result, pivot)` :::success 延伸問題: 1. 解釋上述程式運作原理,搭配 [Graphviz](https://graphviz.org/),比照 [Linked List 練習題](https://hackmd.io/@sysprog/linked-list-quiz) 在 HackMD 筆記上視覺化展現; * 測試程式使用到 [random](https://linux.die.net/man/3/random),多執行幾次可發現輸出結果相仿,請修正,並引入其他 [Pseudorandom number generator ](https://en.wikipedia.org/wiki/Pseudorandom_number_generator) 2. 參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 並重寫上述 quick sort 程式碼,避免使用遞迴呼叫 3. Linux 核心內部也有 linked list 實作,但是 circular doubly-linked list,[linux-list](https://github.com/sysprog21/linux-list) 仿效 Linux 核心的實作並予以簡化,在 `examples/` 目錄提供 quick sort 實作,請探討 Linux 的 linked list 和上述程式碼的落差,並改寫 [linux-list](https://github.com/sysprog21/linux-list) 的 quick sort 範例,避免使用遞迴呼叫 * 參考資料: [The Linux Kernel API - List Management Functions](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) 4. 研讀 Ching-Kuang Shene ([冼鏡光](https://zh.wikipedia.org/zh-tw/%E5%86%BC%E9%8F%A1%E5%85%89)) 教授撰寫的 [A Comparative Study of Linked List Sorting Algorithms](https://pages.mtu.edu/~shene/PUBLICATIONS/1996/3Conline.pdf),思考高效率的 linked list 排序演算法,並落實於上述 (3) 的程式碼中 :::