2021q1 Homework1 (quiz1)

--- tags: Linux --- # 2021q1 Homework1 (quiz1) contribute by < `Chiliang86` > ## 作業要求 - [x] 1. 解釋上述程式運作原理，搭配 [Graphviz](https://graphviz.org/)，比照 [Linked List 練習題](https://hackmd.io/@sysprog/linux2021-quiz1)在 HackMD 筆記上視覺化展現，附帶的[「延伸問題」](https://graphviz.org/)也需要完成 - [ ] 2. 參考 Optimized QuickSort — C Implementation (Non-Recursive) 並重寫上述 quick sort 程式碼，避免使用遞迴呼叫 - [ ] 3. Linux 核心內部也有 linked list 實作，但是 circulr doubly-linked list，linux-list 仿效 Linux 核心的實作並予以簡化，在 examples/ 目錄提供 quick sort 實作，請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫 - [ ] 4. 研讀 Ching-Kuang Shene (冼鏡光] 教授撰寫的 A Comparative Study of Linked List Sorting Algorithms，思考高效率的 linked list 排序演算法，並落實於上述 (3) 的程式碼中 ## 第一周測驗題 (quiz1) ### 題目 - [測驗題目連結](https://hackmd.io/@sysprog/linux2021-quiz1) ### 答案 ### 1. LLL = ? ```c static inline void list_concat(node_t **left, node_t *right) { while (*left) LLL; *left = right; } ``` * `(a)` `left = left->next` * `(b)` `left = (*left)->next` * `(c)` `left = &((*left)->next)` * `(d)` `*left = (*left)->next` - ans : `(c)` `left = &((*left)->next)` ### 分析 #### **假設兩個 list 各含 3 個 node_t 元素** - 走訪 while 之前 left 指標指向左邊 list 的頭 ```graphviz digraph G { rankdir=LR; node [shape=record,width=.1,height=.1] noder [label = "{<n> rigth | rigth_ptr0}"] noder1 [label = "{<n> right_1 | right_ptr1}"] noder2 [label = "{<n> right_2 | right_ptr2}"] nodel1 [label = "{<n> left_0 | left_ptr0}"] nodel2 [label = "{<n> left_1 | left_ptr1}"] nodel3 [label = "{<n> left_2 | left_ptr2}"] nodel [label = "{<n> left | }"] N1 [shape=plaintext,label=NULL] N2 [shape=plaintext,label=NULL] nodel->nodel1:nw nodel1->nodel2 nodel2->nodel3 nodel3->N1 noder -> noder1 noder1->noder2 noder2->N2 } ``` - while step 1 ```graphviz digraph G { rankdir=LR; node [shape=record,width=.1,height=.1] noder [label = "{<n> rigth | rigth_ptr0}"] noder1 [label = "{<n> right_1 | right_ptr1}"] noder2 [label = "{<n> right_2 | right_ptr2}"] nodel1 [label = "{<n> left_0 | left_ptr0}"] nodel2 [label = "{<n> left_1 | left_ptr1}"] nodel3 [label = "{<n> left_2 | left_ptr2}"] nodel [label = "{<n> left | }"] N1 [shape=plaintext,label=NULL] N2 [shape=plaintext,label=NULL] nodel->nodel2:nw nodel1->nodel2 nodel2->nodel3 nodel3->N1 noder -> noder1 noder1->noder2 noder2->N2 } ``` - while step 2 ```graphviz digraph G { rankdir=LR; node [shape=record,width=.1,height=.1] noder [label = "{<n> rigth | rigth_ptr0}"] noder1 [label = "{<n> right_1 | right_ptr1}"] noder2 [label = "{<n> right_2 | right_ptr2}"] nodel1 [label = "{<n> left_0 | left_ptr0}"] nodel2 [label = "{<n> left_1 | left_ptr1}"] nodel3 [label = "{<n> left_2 | left_ptr2}"] nodel [label = "{<n> left | }"] N1 [shape=plaintext,label=NULL] N2 [shape=plaintext,label=NULL] nodel->nodel3:nw nodel1->nodel2 nodel2->nodel3 nodel3->N1 noder -> noder1 noder1->noder2 noder2->N2 } ``` - while step 3 ，結束後跳出 while 迴圈 ```graphviz digraph G { rankdir=LR; node [shape=record,width=.1,height=.1] noder [label = "{<n> rigth | rigth_ptr0}"] noder1 [label = "{<n> right_1 | right_ptr1}"] noder2 [label = "{<n> right_2 | right_ptr2}"] nodel1 [label = "{<n> left_0 | left_ptr0}"] nodel2 [label = "{<n> left_1 | left_ptr1}"] nodel3 [label = "{<n> left_2 | left_ptr2}"] nodel [label = "{<n> left | }"] N1 [shape=plaintext,label=NULL] N2 [shape=plaintext,label=NULL] nodel->N1:nw nodel1->nodel2 nodel2->nodel3 nodel3->N1 noder -> noder1 noder1->noder2 noder2->N2 } ``` - 由 `*left = right` 把兩個 list 做串接 ```graphviz digraph G { rankdir=LR; node [shape=record,width=.1,height=.1] noder [label = "{<n> rigth | rigth_ptr0}"] noder1 [label = "{<n> right_1 | right_ptr1}"] noder2 [label = "{<n> right_2 | right_ptr2}"] nodel1 [label = "{<n> left_0 | left_ptr0}"] nodel2 [label = "{<n> left_1 | left_ptr1}"] nodel3 [label = "{<n> left_2 | left_ptr2}"] nodel [label = "{<n> left | }"] N2 [shape=plaintext,label=NULL] nodel->noder:nw nodel1->nodel2 nodel2->nodel3 nodel3->noder noder -> noder1 noder1->noder2 noder2->N2 } ``` #### 若選則最具爭議的`(d)` `*left = (*left)->next` #### **以剛才的範例做分析** - 進入 while 迴圈之前 ```graphviz digraph G { rankdir=LR; node [shape=record,width=.1,height=.1] noder [label = "{<n> rigth | rigth_ptr0}"] noder1 [label = "{<n> right_1 | right_ptr1}"] noder2 [label = "{<n> right_2 | right_ptr2}"] nodel1 [label = "{<n> left_0 | left_ptr0}"] nodel2 [label = "{<n> left_1 | left_ptr1}"] nodel3 [label = "{<n> left_2 | left_ptr2}"] nodel [label = "{<n> left | }"] N1 [shape=plaintext,label=NULL] N2 [shape=plaintext,label=NULL] nodel->nodel1:nw nodel1->nodel2 nodel2->nodel3 nodel3->N1 noder -> noder1 noder1->noder2 noder2->N2 } ``` - while step 1 : left_0 不再指向 left_1, 而是指向 left_2 ```graphviz digraph G { rankdir=LR; node [shape=record,width=.1,height=.1] noder [label = "{<n> rigth | rigth_ptr0}"] noder1 [label = "{<n> right_1 | right_ptr1}"] noder2 [label = "{<n> right_2 | right_ptr2}"] nodel2 [label = "{<n> left_0 | left_ptr1}"] nodel3 [label = "{<n> left_2 | left_ptr2}"] nodel [label = "{<n> left | }"] N1 [shape=plaintext,label=NULL] N2 [shape=plaintext,label=NULL] nodel->nodel2:nw nodel2->nodel3 nodel3->N1 noder -> noder1 noder1->noder2 noder2->N2 } ``` - while step 2 : left_0 不再指向 left_2, 而是指向 left_3 ```graphviz digraph G { rankdir=LR; node [shape=record,width=.1,height=.1] noder [label = "{<n> rigth | rigth_ptr0}"] noder1 [label = "{<n> right_1 | right_ptr1}"] noder2 [label = "{<n> right_2 | right_ptr2}"] nodel3 [label = "{<n> left_0 | left_ptr2}"] nodel [label = "{<n> left | }"] N1 [shape=plaintext,label=NULL] N2 [shape=plaintext,label=NULL] nodel->nodel3:nw nodel3->N1 noder -> noder1 noder1->noder2 noder2->N2 } ``` - while step 3 : left_0 不再指向 left_3, 而是指向 NULL ，此時也跳出迴圈 ```graphviz digraph G { rankdir=LR; node [shape=record,width=.1,height=.1] noder [label = "{<n> rigth | rigth_ptr0}"] noder1 [label = "{<n> right_1 | right_ptr1}"] noder2 [label = "{<n> right_2 | right_ptr2}"] nodel [label = "{<n> left | }"] N1 [shape=plaintext,label=NULL] N2 [shape=plaintext,label=NULL] nodel->N1:nw noder -> noder1 noder1->noder2 noder2->N2 } ``` - 由 `*left = right` 把 left 指向的位址設成 right ```graphviz digraph G { rankdir=LR; node [shape=record,width=.1,height=.1] noder [label = "{<n> rigth | rigth_ptr0}"] noder1 [label = "{<n> right_1 | right_ptr1}"] noder2 [label = "{<n> right_2 | right_ptr2}"] nodel [label = "{<n> left | }"] N2 [shape=plaintext,label=NULL] nodel->noder:nw noder -> noder1 noder1->noder2 noder2->N2 } ``` - 由上可以發現，程式在 `while` 的過程中 `*left` 的值不斷被更改成 `(*left)->next`，也就是說，同一個 `*left` 指向的空間不斷被更改成`(*left)->next`，最後只有最初的 `*left` 位址上的值指向 `right` ，原本左邊的 list 記憶體空間失去追蹤（沒有指標指向這些空間），且記憶體也沒有被釋放。 ```c= while (p) { node_t *n = p; p = p->next; list_add_node_t(n->value > value ? AAA : BBB, n); } ``` ### 2. AAA = ? - ans : `(e)` `&right` :::danger 選擇題只是讓授課教師易於評分，你不該拘泥在選項，相反地，你該思考「若要我憑空撰寫程式碼，我該怎麼做？」選項不用列出於開發紀錄。 :notes: jserv ::: :::info 了解，以後撰寫共筆我會著重在教授說的思路。 ::: ### 3. BBB = ? - ans : `(c)` `&left` ```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 的參數 (parameter) 來分析，由上面一段程式碼可知函數的第一個參數為 `node_t **list` ，為一指標的指標。 - 經過程式也可以分析出， `while` 迴圈主要目的是將 `n->value` 和 `value` 做一個比較來進行二元分類，並交由 `list_add_node_t` 來分別將 `node_t` 加入左右兩 list ，即此區段的程式碼是進行 quick sort 中遞增排序將 list 中大於 pivot 的值放在右；反之則放在左，因此應將 AAA 代換為 `&right`； BBB 代換為 `&left` 。 :::danger 沒有解題思路，怎會有答案？誠實面對自己 :notes: jserv ::: :::info 2, 3, 4 解題思路已補上。 ::: ### 4. CCC = ? - ans : `(b)` `list_concat(&result, pivot); list_concat(&result, right)` ```c= node_t *result = NULL; list_concat(&result, left); CCC; *list = result; ``` - 以上程式碼擷取自 quicksort 函數的倒數幾行，由 `list_concat(&result, left);` 已將可以略為明白他是將排序完的 list 進行複製給 `result` 的動作，因為 quick sort 採取 [divide and conquer](https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm) 的策略，因此在此段程式碼前已將 list 進行左右兩個子 list 的排序，最後準備採取 combine 的動作，分別要合併 `left` , `pivot`, 和 `right` ，故已經可以選出答案為 `(b)` `list_concat(&result, pivot); list_concat(&result, right)` 。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.