# 2020q3 Homework1 (quiz1)
contributed by < `Holychung` >
[2020q3 第 1 週測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)
## Outline
[TOC]
## 題目
考慮一個單向 linked list，其結構定義為:
```c
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
已知不存在 circular (環狀結構)，接下來將對該單向 linked list 進行下列操作:
- add_entry
- remove_entry
- swap_pair
- reverse
## 程式運作原理
### add_entry
新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy
```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);
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node;
}
```
head 是指標的指標，指向 linked list 起點的指標位置。
首先建立了一個指標的指標 indirect，指向 head 所指向的位置。
```graphviz
digraph G {
rankdir=LR
node [shape="block"]
node0 [label="node 0"]
node1 [label="node 1"]
null0 [shape=none, label="NULL"]
head [shape=none, label="head"]
ptr [shape=none, label="ptr"]
head->ptr
ptr->node0
node0->node1
node1->null0
{rank=same;node0 ptr head}
}
```
接著 malloc 新增一個節點 new_node 的記憶體空間，這個節點 next 指向 NULL。
```graphviz
digraph G {
rankdir=LR
node [shape="block"]
node0 [label="node 0"]
node1 [label="node 1"]
null0 [shape=none, label="NULL"]
null1 [shape=none, label="NULL"]
head [shape=none, label="head"]
ptr [shape=none, label="ptr"]
new_node->null1
head->ptr
ptr->node0
node0->node1
node1->null0
{rank=same;node0 ptr head}
}
```
經過 while 迴圈走訪 linked list，indirect 會指向最尾端 NULL，此時將最尾端指向 new_node，完成新增節點。
```graphviz
digraph G {
rankdir=LR
node [shape="block"]
node0 [label="node 0"]
node1 [label="node 1"]
new_node [label="new_node"]
null0 [shape=none, label="NULL"]
node0->node1
node1->new_node
new_node->null0
{rank=same;null0 }
}
```
### remove_entry
移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)
```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);
}
```
### swap_pair
交換一對相鄰的節點，取自 [LeetCode: Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)，給定 `1->2->3->4`，則該回傳 `2->1->4->3`
透過指標的指標 node 指向 linked list 開頭的位址，每一次交換相鄰的兩個節點，完成之後 node 指向下下一個節點的位置，直到 最尾端或是只剩一個節點的時候停止，並且把參數 head 指標傳回去更新新的起點位置。
```c=
node_t *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;
}
return head;
}
```
一開始用指標的指標 node 指向起始的位址。
```graphviz
digraph G {
rankdir=LR
node [shape="block"]
null0 [shape=none, label="NULL"]
node0 [label="node", shape=none]
head [shape=none, label="head"]
node0->head->node1
node1->node2->null0
{rank=same;node0 head node1}
}
```
然後用指標 tmp 指向 \*node 的位址。
```graphviz
digraph G {
rankdir=TB
node [shape="block"]
null0 [shape=none, label="NULL"]
node0 [label="node", shape=none]
head [shape=none, label="head"]
tmp [shape=none]
tmp->node1
node0->head->node1
node1->node2->null0
{rank=same;node2 null0 node1}
}
```
\*node 移動指向下一個節點。
```graphviz
digraph G {
rankdir=TB
node [shape="block"]
null0 [shape=none, label="NULL"]
node0 [label="node", shape=none]
head [shape=none, label="head"]
tmp [shape=none]
tmp->node1
node0->head->node2
node1->node2->null0
{rank=same;node2 null0 node1}
}
```
把第一個節點的 next 指向第二個節點 next，也就是把 tmp 指向的節點的 next 改成 node 節點指向的 next。
```graphviz
digraph G {
rankdir=TB
node [shape="block"]
null0 [shape=none, label="NULL"]
node0 [label="node", shape=none]
head [shape=none, label="head"]
tmp [shape=none]
tmp->node1
node0->head->node2
node1:s->null0
node2->null0
{rank=same;node2 null0 node1}
}
```
再把第二個節點的 next 指向第一個節點，也就是把 node 指向的節點的 next 改成 tmp 指向的位址，完成一對節點的交換。
```graphviz
digraph G {
rankdir=TB
node [shape="block"]
null0 [shape=none, label="NULL"]
node0 [label="node", shape=none]
head [shape=none, label="head"]
tmp [shape=none]
tmp->node1
node0->head->node2
node1->null0
node2->node1
{rank=same;node2 null0 node1}
}
```
原本 node 是指向 head 這個指標，在做完一次 swap 後，head 會更新指到新的起點位置，因此要再把這個指標回傳回去更新開頭位置。
然後 node 就繼續指向下下一個節點，直接把 node 指向下一個節點的指標 next，一直做到最後結束。
```graphviz
digraph G {
rankdir=TB
node [shape="block"]
null0 [shape=none, label="NULL"]
node0 [label="node", shape=none]
head [shape=none, label="head"]
tmp [shape=none]
tmp->node1
node0->head->null0
node1->null0
node2->node1
{rank=same;node2 null0 node1}
}
```
### reverse
將給定的 linked list 其內節點予以反向，即 `1->2->3->4`，則該回傳 `4->3->2->1`
用指標 cursor 紀錄下上一個節點的位置，初始值為 null，用一開始傳進來的起點位置 head 開始對 linked list 每一個節點做反轉，每一次 loop 都把當前的節點 next 指向前一個節點位址，直到最後，再回傳最後一個節點位址，也就是反轉後的開頭位址。
```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;
}
```
先用指標 next 紀錄下一個節點的位置，也就是當前 head->next 指向的位置。
```graphviz
digraph G {
rankdir=TB
node [shape="block"]
cursor [shape=none, label="cursor"]
null0 [shape=none, label="NULL"]
null1 [shape=none, label="NULL"]
head [shape=none, label="head"]
next [shape=none, label="next"]
cursor->node1
head->node2
next->node3
node2->node3->null0
node1->null1
{rank=same;node2 null0 node1 node3 null1}
}
```
然後 head 指向的節點的 next 就可以指向上一個節點，達到反轉。
```graphviz
digraph G {
rankdir=TB
node [shape="block"]
node1
node2
cursor [shape=none, label="cursor"]
null0 [shape=none, label="NULL"]
null1 [shape=none, label="NULL"]
head [shape=none, label="head"]
next [shape=none, label="next"]
cursor->node1
head->node2
next->node3
node3->null0
node1->null1
node2:e->node1:w [label=" "]
null1->node2 [style="invis"]
{rank=same;node2 null0 node1 node3 null1}
}
```
上一個節點 cursor 就可以更新程現在這個節點 head，再把 head 指向剛剛 next 保存下來的下一個節點位置，完成一個節點的反轉。
```graphviz
digraph G {
rankdir=TB
node [shape="block"]
node1
node2
cursor [shape=none, label="cursor"]
null0 [shape=none, label="NULL"]
null1 [shape=none, label="NULL"]
head [shape=none, label="head"]
next [shape=none, label="next"]
cursor->node2
head->node3
next->null0
node3->null0
node1->null1
node2->node1
{rank=same;node2 null0 node1 node3 null1}
}
```
## 延伸問題
用指標的指標來改寫 `swap_pair` `reverse`，避免回傳指標。
並且以遞迴改寫上述的 `reverse`。
### swap_pair
原本的寫法是傳入指標，所以在函式結束的時候並不會更新到原本的指標 head，所以需要回傳開頭的位置。修改成指標的指標進行操作，就會更新到原本的 head，就不用回傳指標。
```c=
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;
}
}
```
### reverse
修改成指標的指標進行操作，就不用回傳指標，只是要注意最後要把 head 指向前一個的 cursor，才是開頭的位置。
```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;
}
```
### 遞迴版 reverse
把 reverse 整個 linked list 的工作拆成一次只 reverse 當前的節點，然後把剩下的 linked list 丟下去遞迴。
所以遞迴函式`rev_recurive` 需要吃兩個參數，第一個 head 是指向剩下的 linked list 起點位置，第二個 cursor 則是指向上一個節點的位置。然後每次遞迴都更新並傳遞這兩個參數，直到最後指向尾端 NULL，再把 head 指向 cursor 才是開頭的位置。
```c=
void rev_recurive(node_t **head, node_t *cursor)
{
if (*head == NULL) {
*head = cursor;
return;
}
node_t *next = (*head)->next;
(*head)->next = cursor; cursor = *head;
*head = next;
rev_recurive(head, cursor);
}
void reverse(node_t **head)
{
rev_recurive(head, NULL);
}
```
並且有實現老師[上課講解](https://hackmd.io/@sysprog/c-recursion?type=view#Tail-recursion)的[尾端遞迴 (Tail Recursion)](https://en.wikipedia.org/wiki/Tail_call)。
:::info
Tail recursion 是遞迴的一種特殊形式，副程式只有在最後一個動作才呼叫自己。以演算法的角度來說，recursion tree 全部是一脈單傳，所以間複雜度是線性個該副程式的時間。不過遞迴是需要系統使用 stack 來儲存某些資料，於是還是會有 stack overflow 的問題。但是從編譯器的角度來說，因為最後一個動作才呼叫遞迴，所以很多 stack 資料是沒用的，所以他是可以被優化的。基本上，優化以後就不會有時間與空間效率的問題。
:::
### Fisher–Yates shuffle
針對 singly-linked list 的節點，實作 Fisher–Yates shuffle，你應該儘量降低記憶體的使用量。
參考 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 的方法和 [dalaoqi ](https://hackmd.io/C8fRRRctRdGKqr4ezOzDoA?view) 的做法，先計算出 singly-linked list 的長度，然後開始進入迴圈實作。每次挑選一個隨機的節點 `target`，然後把 target 前後的節點接起來，再把 `target` 接到新的 list 開頭的位置，直到迴圈結束。最後再把新的 list 的開頭位址 `new_head` 更新到原本開頭的 head。
```c=
void shuffle(node_t **head)
{
if (*head == NULL)
return;
srand(time(NULL));
int len = 0;
node_t **indirect = head;
while (*indirect) {
len++;
indirect = &(*indirect)->next;
}
node_t *new_head = NULL;
for (int i = len; i > 0; i--) {
int random = rand() % i;
indirect = head;
while (random--)
indirect = &(*indirect)->next;
node_t *target = *indirect;
*indirect = (*indirect)->next;
target->next = NULL;
if (new_head) {
target->next = new_head;
new_head = target;
} else {
new_head = target;
}
}
*head = new_head;
}
```
首先，indirect 先指向開頭 head，並且透過迴圈計算出 list 長度。
```graphviz
digraph G {
rankdir=TB
node [shape="block"]
node1
node2
indirect [shape=none, label="indirect"]
null0 [shape=none, label="NULL"]
head [shape=none, label="head"]
ptr [shape=none, label="ptr"]
indirect->ptr
head->ptr->node1
node3->null0
node1->node2->node3
{rank=same;node2 null0 node1 node3}
}
```
接下來進入 for 迴圈，每一次都隨機選取出一個節點，並且用 indirect 去找到該節點，並且用一個指標 target 指向該節點。
```graphviz
digraph G {
rankdir=TB
node [shape="block"]
node1
node2
indirect [shape=none, label="*indirect"]
target [shape=none, label="target"]
null0 [shape=none, label="NULL"]
head [shape=none, label="head"]
ptr [shape=none, label="ptr"]
two [shape=none, label="隨機 2"]
target->node2
indirect->node2
head->ptr->node1
node3->null0
node1->node2->node3
{rank=same;node2 null0 node1 node3}
}
```
透過 indirect 把 target 前一個節點接到後一個節點上。
```graphviz
digraph G {
rankdir=TB
node [shape="block"]
node1
node2
indirect [shape=none, label="*indirect"]
target [shape=none, label="target"]
null0 [shape=none, label="NULL"]
head [shape=none, label="head"]
ptr [shape=none, label="ptr"]
target->node2
indirect->node2
head->ptr->node1
node3->null0
node1->node2 [style="invis"]
node2->node3 [style="invis"]
node1:s->node3:s
{rank=same;node2 null0 node1 node3}
}
```
然後把 target 接到新的 list 的開頭。
```graphviz
digraph G {
rankdir=TB
node [shape="block"]
node1
node2
target [shape=none, label="target"]
null0 [shape=none, label="NULL"]
null1 [shape=none, label="NULL"]
head [shape=none, label="head"]
ptr [shape=none, label="ptr"]
new_head [shape=none, label="new_head"]
new_head->node2
target->node2
head->ptr->node1
node3->null0
node1->node3
node2->null1
{rank=same;node2 null0 node1 node3 null1}
}
```
直到迴圈結束，把指標的指標 head 指向新的開頭 new_head 就結束了。
```graphviz
digraph G {
rankdir=TB
node [shape="block"]
node1
node2
null0 [shape=none, label="NULL"]
head [shape=none, label="head"]
new_head [shape=none, label="new_head"]
head->new_head
new_head->node3
node2->null0
node3->node1->node2
{rank=same;node2 null0 node1 node3}
}
```
## 延伸閱讀
- [graphviz tutorial](https://www.tonyballantyne.com/graphs.html?fbclid=IwAR3h9wdAUSMxyU8YK_Gl2CEgcHUyCTpfknO-4XpTcLuI3jMY7_ulyVC2MQo)
- [graphviz documentation](http://www.graphviz.org/documentation/)
- [你所不知道的C語言：遞迴呼叫篇](https://hackmd.io/@sysprog/c-recursion?type=view#Tail-recursion)
- [尾端遞迴 (Tail Recursion)](https://en.wikipedia.org/wiki/Tail_call)
- [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
Sign in with Wallet
Connect another wallet