2020q3 Homework1 (quiz1)

# 2020q3 Homework1 (quiz1) contributed by < `quantabase13` > # :memo: Table of Contents [TOC] --- ## 程式運作原理 ### add_entry ```c= 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 是將新的 node 接到原本的 linked list 尾端。程式碼中的 `while` 迴圈用來遍歷整個 linked list ，其中使用 pointer to pointer `indirect` 。下面為 `add_entry` 的圖解： ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; indirect[label = "{<data> indirect}"] indirect->1:ref[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; indirect[label = "{<data> indirect}"] indirect->3:ref[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; indirect[label = "{<data> indirect}"] indirect->5:ref[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; indirect[label = "{<data> indirect}"] indirect->7:ref[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; indirect[label = "{<data> indirect}"] indirect->NULL:ref[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; new [label = "{<data> new | <ref>}"] indirect[label = "{<data> indirect}"] indirect->new[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->new [arrowtail=dot, dir=both, tailclip=false] new:ref:c ->NULL[arrowtail=dot, dir=both, tailclip=false] } ``` 仔細觀察程式碼，我認為 `assert(new_node)` 應該要在 `malloc` 後立刻執行。必須要確認記憶體分配成功後才能為 `new_node` 中的成員賦值，否則有可能 dereference NULL pointer。 ### find_entry ```c= node_t *find_entry(node_t *head, int value) { node_t *current = head; for (; current && current->value != value; current = current->next) /* interate */; return current; } ``` `find_entry` 函式利用 `pointer` 來遍歷 linked list，如下圖所示： ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; head[label = "{<data> head}"] head->1:data[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; head[label = "{<data> head}"] head->3:data[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; head[label = "{<data> head}"] head->5:data[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; head[label = "{<data> head}"] head->7:data[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; head[label = "{<data> head}"] head->NULL:data[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ### remove_entry ```c= 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` 利用 pointer to pointer 遍歷 linked list 。如下圖： ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> entry }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; head[label = "{<data> head}"] head->1:ref[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> entry }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; head[label = "{<data> head}"] head->3:ref[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; entry->5 head[label = "{<data> head}"] head->3:ref[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; head[label = "{<data> head}"] head->3:ref[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` 如果單純使用 pointer 的話，需要記錄"上一個" node 的位置，也就是需要兩個 pointer 。如下圖： ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> entry }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; prev->1:data[tailclip=false] current->3:data[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> entry }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; prev->3:data[tailclip=false] current->5:data[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> entry }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; prev->3:data[tailclip=false] current->5:data[tailclip=false] 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ### swap_pair 如果依題目描述，實作出 `swap_pair` 的程式碼如下： ```c= 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; } ``` 要注意的是在這種寫法下，pointer to pointer `node` 存的是 pointer `head` 在 stack 中的記憶體位址，所以對 `node` dereference 不會修改到原本傳入的 `head` pointer。如果不 return head ，則需要傳入 `head` pointer 的 address 在對其進行 dereference，程式碼如下： ```c= void *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; } } ``` 圖解如下： ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; node1[label="{<data> node}"]; head [label="{ <data> head}"]; tmp [label="{ <data> tmp}"]; node1->head[tailclip=false] head->1:data[tailclip=false] tmp->1 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; node1[label="{<data> node}"]; head [label="{ <data> head}"]; tmp [label="{ <data> tmp}"]; node1->head[tailclip=false] head->3:data[tailclip=false] tmp->1 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; node1[label="{<data> node}"]; head [label="{ <data> head}"]; tmp [label="{ <data> tmp}"]; node1->head[tailclip=false] head->3:data[tailclip=false] tmp->1 1:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; node1[label="{<data> node}"]; head [label="{ <data> head}"]; tmp [label="{ <data> tmp}"]; node1->head[tailclip=false] head->3:data[tailclip=false] tmp->1 1:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 1:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ### reverse `reverse` 的情況同 `swap_pair` ，必須要把 `head` pointer 的 address 傳入函式中，否則函式跑完後 `head` pointer 不會被更改。 ```c= node_t *reverse(node_t *head) { node_t *cursor = NULL; while (head) { node_t *next = head->next; head->next = cursor; cursor = head; head = next; } return cursor; } ``` 以下是不用return value 的版本： ```c= 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; } ``` 其中 linked list 的指向變化如下圖解： ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; null2[label="{ <data> NULL }"]; next [label="{ <data> next }"]; headaddr[label="{<data> &head}"]; headaddr->head[tailclip = false]; head [label="{ <data> head}"]; head->1:data[tailclip=false] next->3 cursor->null2 1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false]; 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; null2[label="{ <data> NULL }"]; next [label="{ <data> next }"]; headaddr[label="{<data> &head}"]; headaddr->head[tailclip = false]; head [label="{ <data> head}"]; head->1 next->3 cursor->null2 1:ref:c -> null2 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ```graphviz digraph linked_list{ rankdir=LR node [shape=record]; 1 [label="{ <data> 1 | <ref> }"]; 3 [label="{ <data> 3 | <ref> }"]; 5 [label="{ <data> 5 | <ref> }"]; 7 [label="{ <data> 7 | <ref> }"]; null2[label="{ <data> NULL }"]; next [label="{ <data> next }"]; headaddr[label="{<data> &head}"]; headaddr->head[tailclip = false]; head [label="{ <data> head}"]; head->3 next->3 cursor->1 1:ref:c -> null2 3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false]; 5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false]; 7:ref:c ->NULL [arrowtail=dot, dir=both, tailclip=false] } ``` ### TODOLIST: * 用遞迴實現 `reverse` * 實作 Fisher–Yates shuffle

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.