owned this note
owned this note
Published
Linked with GitHub
---
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)` 。
Sign in with Wallet
