# 2020q3 Homework1 (quiz1)
contributed by <`howish`>
## Quiz 1
[原問題網址](https://hackmd.io/@sysprog/sysprog2020-quiz1)
[Github](https://github.com/howish/NCKU_Embedded2020Fall/blob/master/quiz/week1/list.c)
## Part 1
> 解釋上述程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現;
### `add_entry`
```c=
void add_entry(node_t **head, int new_value)
{
node_t **indirect = head;
node_t *new_node = malloc(sizeof(node_t));
assert(new_node); // AA1; (應該在的位置)
new_node->value = new_value;
new_node->next = NULL;
//AA1; (題目上的位置)
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node; //AA2
}
```
AA1:
在 [Linux manual](https://linux.die.net/man/3/assert) 中，`assert` 的用法是吃一個 expression ，根據它是否非零來判斷通過與否，在這邊等同於檢查 new_node 是不是NULL值。
所以這邊題目寫錯行了，這個assert要寫在第六行才符合邏輯。
AA2:
把新產生的點加在整個串列的尾端。
### `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;
}
```
這個函式的寫法使用到指標的指標，以避免額外處理 head 指向的節點。
一個串列的表示法如下
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0, s1;
head[shape=none, label= "head"];
nuls[shape=none, label= "..."];
head -> s0;
s0:next -> s1;
s1:next -> nuls;
}
```
#### for 迴圈初始化
```c
node_t **node = &head
```
迴圈的初始化用一個指標的指標存取 head 這個變數的指標。
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
pp[shape=none, label= "node", fontcolor="red"];
head[shape=none, label= "head"];
nuls[shape=none, label= "..."];
pp -> head;
head -> s0;
s0:next -> s1;
s1:next -> nuls;
}
```
#### for 條件式
```c
*node && (*node)->next
```
兩個要交換的節點都要存在(不是 `NULL` ) 才會繼續之後的處理，以下兩個情況都會結束迴圈：
```graphviz
digraph g1 {
rankdir = LR
pp[shape=none, label= "node", fontcolor="red"];
head[shape=none, label= "head"];
nulp[shape=none, label= "NULL"];
pp -> head;
head -> nulp;
}
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
pp[shape=none, label= "node", fontcolor="red"];
head[shape=none, label= "head"];
nulp[shape=none, label= "NULL"];
pp -> head;
head -> s0;
s0:next -> nulp;
}
```
#### for 迴圈內處理
以下逐行圖解串列結構的改變：
```c
node_t *tmp = *node;
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
pp[shape=none, label= "node", fontcolor="red"];
p1[shape=none, label= "tmp", fontcolor="blue"];
head[shape=none, label= "head"];
nuls[shape=none, label= "..."];
head -> s0;
pp -> head;
p1 -> s0;
s0:next -> s1;
s1:next -> nuls;
}
```
```c
*node = (*node)->next; //BB2
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
p1[shape=none, label= "tmp", fontcolor="blue"];
pp[shape=none, label= "node", fontcolor="red"];
head[shape=none, label= "head"];
nuls[shape=none, label= "..."];
p1 -> s0;
pp -> head;
head -> s1;
s0:next -> s1;
s1:next -> nuls;
}
```
```c
tmp->next = (*node)->next;
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
p1[shape=none, label= "tmp", fontcolor="blue"];
pp[shape=none, label= "node", fontcolor="red"];
head[shape=none, label= "head"];
nuls[shape=none, label= "..."];
p1 -> s0;
pp -> head;
head -> s1;
s0:next -> nuls;
s1:next -> nuls;
}
```
```c
(*node)->next = tmp;
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
p1[shape=none, label= "tmp", fontcolor="blue"];
pp[shape=none, label= "node", fontcolor="red"];
head[shape=none, label= "head"];
nuls[shape=none, label= "..."];
p1 -> s0;
pp -> head;
head -> s1;
s0:next -> nuls;
s1:next -> s0;
}
```
#### for 迴圈的更新部分
```c
node = &(*node)->next->next //BB1
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
pp[shape=none, label= "node", fontcolor="red"];
head[shape=none, label= "head"];
nuls[shape=none, label= "..."];
pp -> s0:next;
head -> s1;
s0:next -> nuls;
s1:next -> s0;
}
```
#### 結論
可以看到使用指標的指標後，head指向的節點會自動被更新，不用特別指定。整體的程式碼會更為乾淨，成為[較有品味的程式碼](https://www.ted.com/talks/linus_torvalds_the_mind_behind_linux/transcript?language=en)。
### `reverse`
```c=
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;
}
```
這邊 CCC 的部分是 reverse linked list 的反轉，以下表示逐行執行下串列的結構變化：
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
s2;
p2[shape=none, label= "head", fontcolor="red"];
nuls[shape=none, label= "NULL"];
p2 -> s0;
s0:next -> s1;
s1:next -> s2;
s2:next -> nuls;
}
```
```c
node_t *cursor = NULL;
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
s2;
p1[shape=none, label= "cursor", fontcolor="red"];
p2[shape=none, label= "head", fontcolor="red"];
nuls[shape=none, label= "NULL"];
nulp[shape=none, label= "NULL"];
p1 -> nulp;
p2 -> s0;
s0:next -> s1;
s1:next -> s2;
s2:next -> nuls;
}
```
```c
node_t *next = head->next;
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
s2;
p1[shape=none, label= "cursor", fontcolor="red"];
p2[shape=none, label= "head", fontcolor="red"];
p3[shape=none, label= "next", fontcolor="blue"];
nuls[shape=none, label= "NULL"];
nulp[shape=none, label= "NULL"];
p1 -> nulp;
p2 -> s0;
p3 -> s1;
s0:next -> s1;
s1:next -> s2;
s2:next -> nuls;
}
```
```c
head->next = cursor,
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
s2;
p1[shape=none, label= "cursor", fontcolor="red"];
p2[shape=none, label= "head", fontcolor="red"];
p3[shape=none, label= "next", fontcolor="blue"];
nuls[shape=none, label= "NULL"];
nulp[shape=none, label= "NULL"];
p1 -> nulp;
p2 -> s0;
p3 -> s1;
s0:next -> nulp;
s1:next -> s2;
s2:next -> nuls;
}
```
```c
cursor = head; // CCC
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
s2;
p1[shape=none, label= "cursor", fontcolor="red"];
p2[shape=none, label= "head", fontcolor="red"];
p3[shape=none, label= "next", fontcolor="blue"];
nuls[shape=none, label= "NULL"];
nulp[shape=none, label= "NULL"];
p1 -> s0;
p2 -> s0;
p3 -> s1;
s0:next -> nulp;
s1:next -> s2;
s2:next -> nuls;
}
```
```c
head = next;
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
s2;
p1[shape=none, label= "cursor", fontcolor="red"];
p2[shape=none, label= "head", fontcolor="red"];
p3[shape=none, label= "next", fontcolor="blue"];
nuls[shape=none, label= "NULL"];
nulp[shape=none, label= "NULL"];
p1 -> s0;
p2 -> s1;
p3 -> s1;
s0:next -> nulp;
s1:next -> s2;
s2:next -> nuls;
}
```
```c
node_t *next = head->next;
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
s2;
p1[shape=none, label= "cursor", fontcolor="red"];
p2[shape=none, label= "head", fontcolor="red"];
p3[shape=none, label= "next", fontcolor="blue"];
nuls[shape=none, label= "NULL"];
nulp[shape=none, label= "NULL"];
p1 -> s0;
p2 -> s1;
p3 -> s2;
s0:next -> nulp;
s1:next -> s2;
s2:next -> nuls;
}
```
```c
head->next = cursor,
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
s2;
p1[shape=none, label= "cursor", fontcolor="red"];
p2[shape=none, label= "head", fontcolor="red"];
p3[shape=none, label= "next", fontcolor="blue"];
nuls[shape=none, label= "NULL"];
nulp[shape=none, label= "NULL"];
p1 -> s0;
p2 -> s1;
p3 -> s2;
s0:next -> nulp;
s1:next -> s0;
s2:next -> nuls;
}
```
```c
cursor = head; // CCC
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
s2;
p1[shape=none, label= "cursor", fontcolor="red"];
p2[shape=none, label= "head", fontcolor="red"];
p3[shape=none, label= "next", fontcolor="blue"];
nuls[shape=none, label= "NULL"];
nulp[shape=none, label= "NULL"];
p1 -> s1;
p2 -> s1;
p3 -> s2;
s0:next -> nulp;
s1:next -> s0;
s2:next -> nuls;
}
```
```c
head = next;
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
s2;
p1[shape=none, label= "cursor", fontcolor="red"];
p2[shape=none, label= "head", fontcolor="red"];
p3[shape=none, label= "next", fontcolor="blue"];
nuls[shape=none, label= "NULL"];
nulp[shape=none, label= "NULL"];
p1 -> s1;
p2 -> s2;
p3 -> s2;
s0:next -> nulp;
s1:next -> s0;
s2:next -> nuls;
}
```
```c
node_t *next = head->next;
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
s2;
p1[shape=none, label= "cursor", fontcolor="red"];
p2[shape=none, label= "head", fontcolor="red"];
p3[shape=none, label= "next", fontcolor="blue"];
nuls[shape=none, label= "NULL"];
nulp[shape=none, label= "NULL"];
p1 -> s1;
p2 -> s2;
p3 -> nuls;
s0:next -> nulp;
s1:next -> s0;
s2:next -> nuls;
}
```
```c
head->next = cursor,
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
s2;
p1[shape=none, label= "cursor", fontcolor="red"];
p2[shape=none, label= "head", fontcolor="red"];
p3[shape=none, label= "next", fontcolor="blue"];
nuls[shape=none, label= "NULL"];
nulp[shape=none, label= "NULL"];
p1 -> s1;
p2 -> s2;
p3 -> nuls;
s0:next -> nulp;
s1:next -> s0;
s2:next -> s1;
}
```
```c
cursor = head; // CCC
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
s2;
p1[shape=none, label= "cursor", fontcolor="red"];
p2[shape=none, label= "head", fontcolor="red"];
p3[shape=none, label= "next", fontcolor="blue"];
nuls[shape=none, label= "NULL"];
nulp[shape=none, label= "NULL"];
p1 -> s2;
p2 -> s2;
p3 -> nuls;
s0:next -> nulp;
s1:next -> s0;
s2:next -> s1;
}
```
```c
head = next;
```
```graphviz
digraph g1 {
rankdir = LR
node[shape=record,
label= "{__node|value|<next>next}"];
s0[color=indigo, fontcolor=indigo];
s1[color=brown, fontcolor=brown];
s2;
p1[shape=none, label= "cursor", fontcolor="red"];
p2[shape=none, label= "head", fontcolor="red"];
p3[shape=none, label= "next", fontcolor="blue"];
nuls[shape=none, label= "NULL"];
nulp[shape=none, label= "NULL"];
p1 -> s2;
p2 -> nuls;
p3 -> nuls;
s0:next -> nulp;
s1:next -> s0;
s2:next -> s1;
}
```
此時 head 為空指標，所以會跳出迴圈
```c
while (head) {
...
}
```
然後輸出的 cursor 指標正好就是反轉後的串列新的 head 指標
```c
return cursor;
```
## Part 2
> 函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = ... 的更新，請用指標的指標來改寫，並避免回傳指標
### 改寫 `swap_pair`
```c=
void swap_pair(node_t **head)
{
for (; *head && (*head)->next;
head = &(*head)->next->next
) {
node_t *tmp = *head;
*head = (*head)->next;
tmp->next = (*head)->next;
(*head)->next = tmp;
}
}
```
### 改寫 `reverse`
```c=
void new_reverse(node_t **head)
{
node_t *cursor = NULL;
while (*head) {
node_t *next = (*head)->next;
(*head)->next = cursor, cursor = (*head);
*head = next;
}
*head = cursor;
}
```
這兩個改寫方法減少了變數的使用，同時簡化了函式使用的方法。可以說是一舉雙得。
## Part 3
>以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_recursive，隨後在 reverse 函式中呼叫 rev_recursive;
```c=
void rev_recursive(node_t *cursor, node_t **head)
{
if (!*head) {
*head = cursor;
return;
}
node_t *next = (*head)->next;
(*head)->next = cursor, cursor = (*head);
*head = next;
rev_recursive(cursor, head);
}
void rec_reverse(node_t **head)
{
rev_recursive(NULL, head);
}
```
### Part 4
> 針對 singly-linked list 的節點，實作 Fisher–Yates shuffle，你應該儘量降低記憶體的使用量;
#### Fisher–Yates shuffle簡介：
剩下 n 個的時候，先抽出 0~n-1的 其中一個數字 m ，然後從左邊養右邊數到第 m 個標的，將它劃掉，並且放到新產生的序列中。
#### 實作
Linked-list 的結構很適合此演算法的實作，所以就照著原來演算法的概念去實作就好。需要注意的是這邊與前幾個練習一樣可以使用*指標的指標*的技巧，可以使整個流程簡化很多。
```c=110
void fisher_yates_shuffle(node_t **head)
{
// Compute length
int num = 0;
for (node_t *itr = *head; itr; num++, itr=itr->next)
/*iterate*/;
srand(time(NULL));
node_t *oldhead = *head;
for (; num; num--) {
// Pick the sampled node
node_t **picker = &oldhead;
for (int pos = rand() % num; pos; pos--)
picker = &(*picker)->next;
// Append picked node to result node
*head = *picker;
head = &(*head)->next;
// Remove picked node from old list
*picker = (*picker)->next;
}
}
```
Sign in with Wallet
Connect another wallet