# 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
Sign in with Wallet
Connect another wallet