2020q3 Homework1 (quiz1)

# 2020q3 Homework1 (quiz1) contributed by < `joey3639570` > ###### tags: `進階電腦系統理論與實作` - [**Linked List** 測驗題連結](https://hackmd.io/@sysprog/sysprog2020-quiz1) - [作業區](https://hackmd.io/@sysprog/sysprog2020-quiz1) ### Linked List 之定義 ```cpp typedef struct __node { int value; struct __node *next; } node_t; ``` ### 測驗題目需注意之重點 - Linked List 為**單向** - 已知不存在 **circular (環狀結構)** :::warning **注意** :zap: 參考到 `RinHizakura` 的作業，提出一個很重要的觀點: >**main(caller) 裡的 head pointer 的角度跟做為參數的 pointer to pointer 的 head 是完全不同的** > `node_t *head = NULL;` 此為 main(Caller)內的 `void add_entry(node_t **head, int new_value)` 參數的 ::: 於20200913參考到，讓困惑已久的自己終於解惑了 ### Graphviz範例參考 ```graphviz digraph foo { rankdir=LR; node [shape=record]; a [label="{ <data> 12 | <ref> }", width=1.2] b [label="{ <data> 99 | <ref> }"]; c [label="{ <data> 37 | <ref> }"]; d [shape=box]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` ### 針對運算子的複習由於發現自己在上次測驗中，對於運算子，尤其是`&`和`*`及`->`的位階，相當不理解，故決定實驗看看讓自己理解，希望能搭配 Graphviz 讓自己理解。<br> [Pointer to Pointer ~~Double Pointer~~ 參考資料](https://www.geeksforgeeks.org/double-pointer-pointer-pointer-c/) 假設今天有一段程式碼如下: ```cpp= node_t *new_node = malloc(sizeof(node_t)); node_t *new_node_2 = malloc(sizeof(node_t)); node_t *head = &new_node; node_t **indirect = head; new_node->value = 1; new_node->next = &new_node_2; new_node_2->value = 2; new_node_2->next = NULL; ``` 呈現如下: ```graphviz digraph foo { rankdir=LR; node [shape=record]; i [label="indirect|<ref> "]; a [label="head | <ref> "]; b [label="new_node |{ <data> 1 | <ref> }"]; c [label="new_node_2 |{ <data> 2 | <ref> }"]; d [label="Null"]; i:ref:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` 與宅色夫老師畫的圖相比： ```mermaid graph LR subgraph linked list head==>node1==>node2 end subgraph pointer to pointer indirect==>head end ``` 釐清並且整理觀念如下: - `*new_node`得到的是一個`node_t`的 struct - `*head`得到的是一個`node_t`的struct - `(*new_node)->value`不等於`*new_node->value`，因為`->`的位階大於`*` - `head = &new_node` 等於 `*indirect = new_node`(請務必記得最上面的**注意**) ### 針對原始測驗題的思考及理解 - `add_entry` >新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy #### 原始碼 ```cpp= void add_entry(node_t **head, int new_value) { node_t **indirect = head; node_t *new_node = malloc(sizeof(node_t)); new_node->value = new_value; new_node->next = NULL; assert(new_node) #(AA1); while (*indirect) indirect = &(*indirect)->next; *indirect = new_node #(AA2); } ``` `add_entry`的流程如下： 1. **第3行** 建立指向 node 指標(`head`)的指標`indirect` 2. **第5行** 使用`malloc`分配記憶體空間給`new_node` 3. **第6~7行** 初始化`new_node` 4. **(AA1)** 確定`new_node`是合法的 5. **第10~11行** 當取值 indirect 不是 NULL 時，indirect設為指向下一個值的位址的指標(`&(*indirect)->next`) 6. **(AA2)** 將此指標的值設為`new_node` :::warning **注意** :zap: - 此部分的Code使用於加 entry 於 linked list 的最後端(由**步驟五**可以得知) - -> 的位階大於 & ，所以要先進行->運算再運算& ::: 如果**AA1**填入`*indirect = new_node`，會變成接在head指到的node的後方。 --- - `remove_entry` >移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標) ```cpp= void remove_entry(node_t **head, node_t *entry) { node_t **indirect = head; while ((*indirect) != entry) indirect = &(*indirect)->next; *indirect = entry->next; free(entry); } ``` `remove_entry`的流程如下： 1. **第3行** 建立指向 node 指標(`head`)的指標`indirect` 2. **第5~6行** 此部分是要將`indirect`指向 entry ，方法是利用`while`從`head`開始找到指定的 entry ，若不是entry，則走 next 往下一個。 3. **第8行** 將 Linked List 銜接回去 4. **第9行** 用`free`釋放 entry 占用的記憶體 --- - `swap_pair` >交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 1->2->3->4，則該回傳 2->1->4->3 #### 原始程式碼 ```cpp= node_t *swap_pair(node_t *head) { for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next #BB1) { node_t *tmp = *node; node = &(*node)->next #BB2; tmp->next = (*node)->next; (*node)->next = tmp; } return head; } ``` :::warning :zap:**務必注意傳入函式內的是`node_t *head`** ::: `swap_pair`的流程如下： 1. **第3行** `for`迴圈分別講解: - `node_t **node = &head` 從`head`開始，此為建立指向 node 指標(`head`)的指標 - `*node && (*node)->next` 若無法形成兩兩一組，則結束for迴圈 - **BB1** 因為是要兩個為一組進行操作，所以每個迴圈結束要跳兩個，根據運算子優先次序選擇`node = &(*node)->next->next` 2. **第4行** 複製`node`為暫存`tmp` 3. **第5~7行** 此為執行 swap 的部分，參見底下Graphviz呈現: - **BB2** `node = &(*node)->next` - `tmp->next = (*node)->next` - `(*node)->next = tmp` 5. **第9行** 回傳`head` #### Graphviz呈現 (取一部分當範例) **第4行**前的狀況: ```graphviz digraph foo { rankdir=LR; node [shape=record]; n [label="node | <ref> "]; node_1 [label="<ptr> head|{ <data> 1 | <ref> } "]; node_2 [label="{ <data> 2 | <ref> } "]; node_3 [label="{ <data> 3 | <ref> } "]; n:ref:c -> node_1:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_2:ref:c -> node_3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` **第4行`node_t *tmp = *node;`後**的狀況: *node 可以取得head head->next跟node_1->next是一樣的 ```graphviz digraph foo { rankdir=LR; node [shape=record]; n [label="node | <ref> "]; node_1 [label="<ptr> head|{ <data> 1 | <ref> } "]; node_2 [label="{ <data> 2 | <ref> } "]; node_3 [label="{ <data> 3 | <ref> } "]; tmp [label="<ptr> tmp | { <data> 1 | <ref> } "]; node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; n:ref:c -> node_1:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; tmp:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_2:ref:c -> node_3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` `node = &(*node)->next` ```graphviz digraph foo { rankdir=LR; node [shape=record]; node_1 [label="<ptr> head|{ <data> 1 | <ref> } "]; node_2 [label="node|{ <data> 2 | <ref> } "]; node_3 [label="{ <data> 3 | <ref> } "]; tmp [label="tmp | { <data> 1 | <ref> } "]; node_1:ref:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; tmp:ref:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_2:ref:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` `tmp->next = (*node)->next` ```graphviz digraph foo { rankdir=LR; node [shape=record]; node_1 [label="<ptr> head|{ <data> 1 | <ref> } "]; node_2 [label="<ptr> node|{ <data> 2 | <ref> } "]; node_3 [label="{ <data> 3 | <ref> } "]; tmp [label="tmp | { <data> 1 | <ref> } "]; node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; tmp:ref:c -> node_3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_2:ref:c -> node_3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` `(*node)->next = tmp` ```graphviz digraph foo { rankdir=LR; node [shape=record]; node_1 [label="<ptr>head|{ <data> 1(可忽略) | <ref> } "]; node_2 [label="<ptr> node|{ <data> 2 | <ref> } "]; node_3 [label="{ <data> 3 | <ref> } "]; tmp [label="tmp | { <data> 1 | <ref> } "]; node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; tmp:ref:c -> node_3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_2:ref:c -> tmp [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` --- - `reverse`: >將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1 #### 原始程式碼 ```cpp= node_t *reverse(node_t *head) { node_t *cursor = NULL; while (head) { node_t *next = head->next; head->next = cursor; cursor = head #CCC; head = next; } return cursor; } ``` :::warning :zap:**務必注意傳入函式內的是`node_t *head`** ::: `reverse`的流程如下： 1. **第3行** 建立一指向`node_t`物件的指標`cursor`，先指向NULL 2. **第4~8行** 當 head 還有指向東西時，執行以下: - 建立一指向`node_t`物件的指標`next`，指向 head 的 next - **CCC** `head->next = cursor; cursor = head`這其實是兩行 - 將 head 的 next 設為 cursor - 再把 cursor 變 head - head 再接下去下一個物件 #### Graphviz呈現 `node_t *cursor = NULL;` ```graphviz digraph foo { rankdir=LR; node [shape=record]; node_1 [label="head |{ <data> 1 | <ref> } "]; node_2 [label="{ <data> 2 | <ref> } "]; cursor [label="cursor | "]; node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` `node_t *next = head->next;` ```graphviz digraph foo { rankdir=LR; node [shape=record]; node_1 [label="head |{ <data> 1 | <ref> } "]; node_2 [label="{ <data> 2 | <ref> } "]; next [label="next |{<data> 2 |<ref> }"] cursor [label="cursor |<data> "]; node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` `head->next = cursor` ```graphviz digraph foo { rankdir=LR; node [shape=record]; node_1 [label="head |{ <data> 1 | <ref> } "]; node_2 [label="{ <data> 2 | <ref> } "]; next [label="next |{<data> 2 |<ref> }"] cursor [label="cursor | <ref> "]; node_1:ref:c -> cursor:ref [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` `cursor = head` ```graphviz digraph foo { rankdir=LR; node [shape=record]; node_1 [label="head(cursor) |{ <data> 1 | <ref> } "]; node_2 [label="{ <data> 2 | <ref> } "]; next [label="next |{<data> 2 |<ref> }"] cursor [label=" <ref> "]; node_1:ref:c -> cursor:ref [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` `head = next` ```graphviz digraph foo { rankdir=LR; node [shape=record]; node_1 [label="head|{ <data> 1 | <ref> } "]; node_2 [label="{ <data> 2 | <ref> } "]; next [label="next(head) |{<data> 2 |<ref> }"] cursor [label=" <ref> "]; node_1:ref:c -> cursor:ref [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` ## 延伸問題 - 函式 `swap_pair` 和 `reverse` 對於指標的操作方式顯然異於 `add_entry` 及 `remove_entry`，需要額外做 `head = ...` 的更新，請用**指標的指標**來改寫，並避免回傳指標; ```cpp= void swap_pair(node_t **head) { for (node_t **node = head; *node && (*node)->next;node = &(*node)->next->next) { node_t *tmp = *node; *node = (*node)->next; tmp->next = (*node)->next; (*node)->next = tmp; } } ``` :::warning 參考 `sammer1107` :zap: 括號 head 代表在 main 中的 head。 ::: 進入`for`迴圈: ```graphviz digraph foo { rankdir=LR; node [shape=record]; n [label="node"]; head [label="head"]; head_main [label="(head)"]; node_1 [label="{node_1|<next>}"]; node_2 [label="{node_2|<next>}"]; node_3 [label="{node_3|<next>}"]; head -> head_main [arrowhead=vee, arrowtail=tail]; n -> head_main [arrowhead=vee, arrowtail=tail]; head_main -> node_1; node_1:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_2:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` `node_t *tmp = *node;` ```graphviz digraph foo { rankdir=LR; node [shape=record]; n [label="node"]; head [label="head"]; head_main [label="(head)"]; tmp [label="tmp"]; node_1 [label="{node_1|<next>}"]; node_2 [label="{node_2|<next>}"]; node_3 [label="{node_3|<next>}"]; head -> head_main [arrowhead=vee, arrowtail=tail]; n -> head_main [arrowhead=vee, arrowtail=tail]; head_main -> node_1; tmp -> node_1; node_1:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_2:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` `*node = (*node)->next;` ```graphviz digraph foo { rankdir=LR; node [shape=record]; n [label="node"]; head [label="head"]; head_main [label="(head)"]; tmp [label="tmp"]; node_1 [label="{node_1|<next>}"]; node_2 [label="{node_2|<next>}"]; node_3 [label="{node_3|<next>}"]; head -> head_main [arrowhead=vee, arrowtail=tail]; n -> head_main [arrowhead=vee, arrowtail=tail]; head_main -> node_2; tmp -> node_1; node_1:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_2:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` `tmp->next = (*node)->next;` ```graphviz digraph foo { rankdir=LR; node [shape=record]; n [label="node"]; head [label="head"]; head_main [label="(head)"]; tmp [label="tmp"]; node_1 [label="{node_1|<next>}"]; node_2 [label="{node_2|<next>}"]; node_3 [label="{node_3|<next>}"]; head -> head_main [arrowhead=vee, arrowtail=tail]; n -> head_main [arrowhead=vee, arrowtail=tail]; head_main -> node_2; tmp -> node_1; node_1:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_2:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` `(*node)->next = tmp` ```graphviz digraph foo { rankdir=LR; node [shape=record]; n [label="node"]; head [label="head"]; head_main [label="(head)"]; tmp [label="tmp"]; node_1 [label="{node_1|<next>}"]; node_2 [label="{node_2|<next>}"]; node_3 [label="{node_3|<next>}"]; head -> head_main [arrowhead=vee, arrowtail=tail]; n -> head_main [arrowhead=vee, arrowtail=tail]; head_main -> node_2; tmp -> node_1; node_1:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_2:next:c -> node_1[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` --- ```cpp= void reverse(node_t **head) { node_t *cursor = NULL; while (*head) { node_t *next = (*head)->next; (*head)->next = cursor; cursor = *head; *head = next; } *head = cursor; } ``` --- - 以遞迴改寫上述的 `reverse`，注意，你可能因此需要建立新的函式，如 `rev_recursive`，隨後在 `reverse` 函式中呼叫 `rev_recursive`; ```cpp= node_t *rev_reverse(node_t *head) { # If there isn't any node left or not even node, return head. if(!head || !head->next){ return head; } node_t *rev_head = reverse_recursive(head->next); head->next->next = head; head->next = NULL; return rev_head; } ``` 藉著 rev_recursive 函式`node_t *rev_head = reverse_recursive(head->next);`把 linked list 拆成第一個節點以及後面整個節點 List <br> 原圖: ```graphviz digraph foo { rankdir=LR; node [shape=record]; head [label="head"]; node_1 [label="{node_1|<next>}"]; node_2 [label="{node_2|<next>}"]; node_3 [label="{node_3|<next>}"]; head -> node_1; node_1:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_2:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_3:next:c -> null[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` 經前面 recursive 的部分後: ```graphviz digraph foo { rankdir=LR; node [shape=record]; head [label="head"]; node_1 [label="{node_1|<next>}"]; node_2 [label="{node_2|<next>}"]; node_3 [label="{node_3|<next>}"]; head -> node_1; node_1:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_2:next:c -> null[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_3:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; rev_head -> node_3 } ``` `head->next->next = head;` `head->next = NULL;` `head->next->next`便是`node_2->next`，將其設為`head`，然後再將最後的`next`指向NULL如底下: ```graphviz digraph foo { rankdir=LR; node [shape=record]; head [label="head"]; node_1 [label="{node_1|<next>}"]; node_2 [label="{node_2|<next>}"]; node_3 [label="{node_3|<next>}"]; head -> node_1; node_1:next:c -> null[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_2:next:c -> node_1[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_3:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; rev_head -> node_3 } ``` 利用上面完成了 reverse，最後用`void reverse`配合**pointer to pointer**修飾，程式碼如下: ```cpp= void reverse(node_t **head) { *head = rev_recursive(*head); } ``` ```graphviz digraph foo { rankdir=LR; node [shape=record]; head [label="(head)"]; head_ptr [label="head"]; node_1 [label="{node_1|<next>}"]; node_2 [label="{node_2|<next>}"]; node_3 [label="{node_3|<next>}"]; head -> node_1; head_ptr -> rev_head node_1:next:c -> null[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_2:next:c -> node_1[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; node_3:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; rev_head -> node_3 } ``` 可藉此發現原始的 main 中的`head`並不會動到！ --- - 針對 `singly-linked list` 的節點，實作 **Fisher–Yates shuffle**，你應該儘量降低記憶體的使用量; [Wikipedia: Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher–Yates_shuffle) 演算法如下： ``` To shuffle an array a of n elements (indices 0..n-1): for i from n - 1 downto 1 do j = random integer with 0 <= j <= i exchange a[j] and a[i] ``` ```cpp= void randomize ( node_t **head ){ // Use a different seed value so that we don't get same // result each time we run this program srand ( time(NULL) ); node_t *old_head, *cursor, **indirect; int range = 0; old_head = cursor = *head; // get list length while(cursor){ range += 1; cursor = cursor->next; } *head = NULL; for(;range > 0; --range){ // Start from old head indirect = &old_head; // move to selected node for(int i = rand() % range;i > 0; --i) indirect = &(*indirect)->next; // move selected node to new list // Down below is the part for swapping node_t *tmp = *indirect; *indirect = (*indirect)->next; tmp->next = *head; *head = tmp; } } ``` :::warning 最後在 main 中使用 `swap_pair` 及 `reverse` 時，只要是用到pointer to pointer 的，要傳入 `head` 的地址，也就是`&head` e.g. `swap_pair(&head)` :::

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.