--- tags: linus2021 --- # 2021q1 Homework1 (quiz1) contributed by < `yellow951321` > ## 程式原理解說 ### list_add_node_t 新增一個 node 到 list 的頭，並將 list 的指標變更為新增的 node ### list_concat 找到 left 的最右端的 node ，並接上 left ```graphviz digraph structs { node[shape=record] struct0 [label="<left> left | <> node1| <tail> tail"] struct1 [label="<right> right | <next> | <>"]; struct0:tail -> struct1:right[arrowhead=vee, tailclip=true, arrowsize=1]; } ``` 因此LLL要做到能夠找到left的最右端的 node 其中的 next 的位址，並將其值指到 right 因此答案為 (c) left = &((*left)->next) 。 ### quicksort 以list的第一個值作為 pivot 值，遍歷整個 list ，將比 pivot 還要大的值放入 right ，剩下的放入 left 兩個 list 中（題目要求由小排到大）。 ```graphviz digraph structs { node[shape=record] struct0 [label="<pivot> pivot"] struct1 [label="<right> right | <> | <>"]; struct2 [label="<left> left | <> | <>"]; } ``` 並且遞迴呼叫直到 right 或是 left 已經沒有值時藉由以下判斷式跳出迴圈並且使用 list_concat 函式連接起已排序好的 list 。 ``` c= if (!*list) return; ``` 由此可知 AAA 和 BBB 分別為對應的 left 和 right list ，並且藉由 list_add_node_t 的 變數型態可知道要傳入的是 node_t 的指標的指標，並且是由小排到大，因此 AAA 答案為 &right， BBB 為 &left。 接著 CCC 的工作為連接起 pivor, right, 以及 left 。根據 list_concat 的功能以及選項判斷，只有 (b) list_concat(&result, pivot); list_concat(&result, right) 可以做到這件事情。 ## 導入其他 Pseudorandom number generator ## 重寫 quick sort 程式碼，避免使用遞迴呼叫