# [2020q3 Homework1 (quiz1)](https://hackmd.io/@sysprog/rJ7WDWNVv)
contributed by < `zhu849` >
## 題目解析
考慮一個單向 linked list，其結構定義為:
```c=4
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
```graphviz
digraph structs {
rankdir = LR
node[shape=record]
struct0 [label= "{__node|{<value>value|<next>next}}"]
struct1 [label= "{__node|{<value>value|<next>next}}"]
struct0:next -> struct1
}
```
:::info
已知條件：
1. 不存在 circular (環狀結構)
2. link 是單向結構
:::
### Sub Function 說明
1. `add_entry`: 新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy
2. `remove_entry`: 移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)
3. `swap_pair`: 交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 1->2->3->4，則該回傳 2->1->4->3
4. `reverse`: 將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1
### 題目程式碼
:::spoiler
```c=
#include <stdio.h>
#include <stdlib.h>
typedef struct __node {
int value;
struct __node *next;
} node_t;
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;
AA1;
while (*indirect)
indirect = &(*indirect)->next;
AA2;
}
node_t *find_entry(node_t *head, int value)
{
node_t *current = head;
for (; current && current->value != value; current = current->next)
/* interate */;
return current;
}
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; BB1) {
node_t *tmp = *node;
BB2;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
CCC;
head = next;
}
return cursor;
}
void print_list(node_t *head)
{
for (node_t *current = head; current; current = current->next)
printf("%d ", current->value);
printf("\n");
}
int main(int argc, char const *argv[])
{
node_t *head = NULL;
print_list(head);
add_entry(&head, 72);
add_entry(&head, 101);
add_entry(&head, 108);
add_entry(&head, 109);
add_entry(&head, 110);
add_entry(&head, 111);
print_list(head);
node_t *entry = find_entry(head, 101);
remove_entry(&head, entry);
entry = find_entry(head, 111);
remove_entry(&head, entry);
print_list(head);
/* swap pair.
* See https://leetcode.com/problems/swap-nodes-in-pairs/
*/
head = swap_pair(head);
print_list(head);
head = reverse(head);
print_list(head);
return 0;
}
```
* 執行時記得要在開頭先加上 `#include <assert.h>` ，才能讓系統知道 assert function 在哪裡
:::
### 各個 Function 分析
* 在了解程式功能前，我們需要先了解 pointer to pointer 的結構是像這樣，pointer 內存放的是記憶體的位址
```graphviz
digraph structs {
node [shape=record];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="address"];
struct2 [label="address"];
struct3 [label="value"];
struct4 [shape=plaintext, label="pointer"];
struct5 [shape=plaintext, label="pointer"];
struct6 [shape=plaintext, label="variable"];
rankdir = LR
struct1 -> struct2;
struct2 -> struct3;
struct3 -> NULL
struct4 -> struct5 [style=invisible,dir=none]
struct5 -> struct6 [style=invisible,dir=none]
}
```
### ==add_entry ( )==
```c=9
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;
AA1;
while (*indirect)
indirect = &(*indirect)->next;
AA2;
}
```
* line 11：宣告一個 node_t 型態的指標的指標 indirect 指向傳入的 head 的位址
* line 13：向記憶體要求一塊 node_t 型態的空間，且利用 new_node 指標紀錄位址
* line 18：當 indirect 所指向的位址不是NULL，就持續做 line 19 內容
* line 19：取 indirect 所指到的 pointer varible 中 next 的值，再對這個值取它的位址
* 這邊需要注意的是根據 [operator 的優先順序規則](https://en.cppreference.com/w/c/language/operator_precedence)：**->** 的優先順序較 **&** 還高，所以這行 code 也可視為
```c=19
indirect = &((*indirect)->next);
```
```graphviz
digraph structs {
node [shape=record];
head[shape=plaintext,fontcolor=darkgreen];
indirect[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> newnode|{109|<next>next}}"];
rankdir = LR
struct1:next -> struct2:thenode;
struct2:next -> struct3:thenode;
struct3:next -> NULL
struct4:next -> NULL
head -> struct1:next
indirect -> struct1:next
}
```
```graphviz
digraph structs {
node [shape=record];
head[shape=plaintext,fontcolor=darkgreen];
indirect[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> newnode|{109|<next>next}}"];
rankdir = LR
struct1:next -> struct2:thenode;
struct2:next -> struct3:thenode;
struct3:next -> NULL
struct4:next -> NULL
head -> struct1:next
indirect -> struct2:next
}
```
```graphviz
digraph structs {
node [shape=record];
head[shape=plaintext,fontcolor=darkgreen];
indirect[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> newnode|{109|<next>next}}"];
rankdir = LR
struct1:next -> struct2:thenode;
struct2:next -> struct3:thenode;
struct3:next -> NULL
struct4:next -> NULL
head -> struct1:next
indirect -> struct3:next
}
```
```graphviz
digraph structs {
node [shape=record];
head[shape=plaintext,fontcolor=darkgreen];
indirect[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> newnode|{109|<next>next}}"];
rankdir = LR
struct1:next -> struct2:thenode;
struct2:next -> struct3:thenode;
struct3:next -> NULL
struct4:next -> NULL
head -> struct1:next
indirect -> NULL
}
```
因為NULL的記憶體位址為0，所以跳出 while 迴圈
#### ==AA1：==
* `(a)` `assert(new_node)`
* `(b)` `*indirect = new_node`
如果選`b`：代表 indirect 指向的記憶體位址會先指向 newnode，乍看之下確實新增了一個 entry，但是這麼一做就會發現 node 2, 3 也隨著指標改變變成了孤兒，造成 [memory leak](https://en.wikipedia.org/wiki/Memory_leak) 的現象(沒有其他方法可以再找到 node 2,3 在記憶體的哪個位置)。
```graphviz
digraph structs {
node [shape=record];
head[shape=plaintext,fontcolor=darkgreen];
indirect[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> newnode|{109|<next>next}}"];
rankdir = LR
struct1:next -> struct4;
struct2:next -> struct3:thenode;
struct3:next -> NULL
struct4:next -> NULL
head -> struct1:next
indirect -> struct1:next
}
```
如果選`a`：[C lib 提供的 assert](https://www.tutorialspoint.com/c_standard_library/c_macro_assert.htm)會去幫我們檢查newnode是否正確成立，若 `assert(expression)` 中 expression 為 false 代表 newnode 為 NULL，則當錯誤發生時系統會主動告知我們。
==所以AA1選擇 (a)==
#### ==AA2：==
* `(a)` `assert(new_node)`
* `(b)` `*indirect = new_node`
因為做完 line 18, 19 兩行後 node 之間的狀態會如下
```graphviz
digraph structs {
node [shape=record];
head[shape=plaintext,fontcolor=darkgreen];
indirect[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> newnode|{109|<next>next}}"];
rankdir = LR
struct1:next -> struct2:thenode;
struct2:next -> struct3:thenode;
struct3:next -> NULL
struct4:next -> NULL
head -> struct1:next
indirect -> NULL
}
```
如果選`a`：同 ==AA1== 解釋，因為 line 18, 19 並不會影響 newnode ，但是這樣 newnode 並沒有成功的被任何指標所記錄，在 `add_entry()` 結束後會造成 newnode 的點會產生 [ memory leak ](https://en.wikipedia.org/wiki/Memory_leak)現象。
如果選`b`：indirect 會將 node 3 的 next 指向 newnode ,順利加入新的 entry
```graphviz
digraph structs {
node [shape=record];
head[shape=plaintext,fontcolor=darkgreen];
indirect[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> newnode|{109|<next>next}}"];
rankdir = LR
struct1:next -> struct2:thenode;
struct2:next -> struct3:thenode;
struct3:next -> struct4
struct4:next -> NULL
head -> struct1:next
indirect -> struct4
}
```
==所以AA2選擇 (b)==
### ==swap_pair ( )==
```c=42
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; BB1) {
node_t *tmp = *node;
BB2;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
* 從 line 44 可以得知終止條件有兩種
1. ```*node == NULL``` 或是
2. ```(*node)->next == NULL```
* 其中第1種狀況屬於邊界狀況，僅有傳入head == NULL 時會判斷成立
* line 45：用一個 tmp pointer 指向 node 所指向的指標的位址
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
tmp[shape=plaintext,fontcolor=blue];
"node"[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct1:next -> struct2:thenode;
struct2:next -> NULL
"node"->head
tmp->struct1
head -> struct1
}
```
#### ==BB2：==
```(a)``` ```node = (*node)->next```
```(b)``` ```node = &(*node)->next```
```(c)``` ```*node = (*node)->next```
```(d)``` ```*node = &(*node)->next```
```(e)``` ```*node = &((*node)->next)```
如果選 ```a``` ：無法達成交換，且程式根本無法 work，因為 node 是一個 pointer to pointer的結構，但指向的 node 2 型態並不是一個指向 __node 型態的 pointer，所以 line 47 無法執行。
line 46：
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
tmp[shape=plaintext,fontcolor=blue];
"node"[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct1:next -> struct2:thenode;
struct2:next -> NULL
struct2:thenode -> "__node ???"
"node"->struct2
tmp->struct1
head -> struct1
}
```
如果選 ```b``` ：會產生兩種狀況
1. node 1 和 node 3 產生 loop，這個程式會進入無限迴圈狀態
2. node 2 會變成孤兒，一樣會有 memory leak 的問題
line 46：
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
tmp[shape=plaintext,fontcolor=blue];
"node"[shape=plaintext,fontcolor=red];
pointer[shape=plaintext];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct1:next -> struct2:thenode;
struct2:next -> struct3:thenode;
struct3:next -> NULL;
"node"-> pointer -> struct2
tmp->struct1
head -> struct1
}
```
line 47：
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
tmp[shape=plaintext,fontcolor=blue];
"node"[shape=plaintext,fontcolor=red];
pointer[shape=plaintext];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct1:next -> struct3:thenode;
struct2:next -> struct3:thenode;
struct3:next -> NULL;
"node"-> pointer -> struct3
tmp->struct1
head -> struct1
}
```
line 48：
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
tmp[shape=plaintext,fontcolor=blue];
"node"[shape=plaintext,fontcolor=red];
pointer[shape=plaintext];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct1:next -> struct3:thenode;
struct2:next -> struct3:thenode;
struct3:next -> struct1:thenode;
"node"-> pointer -> struct3
tmp->struct1
head -> struct1
}
```
如果選 ```c``` ：可以正確的 swap 兩個元素的位置
line 46：
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
tmp[shape=plaintext,fontcolor=blue];
"node"[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct1:next -> struct2:thenode;
struct2:next -> NULL
"node"->head
tmp->struct1
head -> struct2
}
```
line 47：
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
tmp[shape=plaintext,fontcolor=blue];
"node"[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct1:next -> NULL;
struct2:next -> NULL
"node"->head
tmp->struct1
head -> struct2
}
```
line 48：
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
tmp[shape=plaintext,fontcolor=blue];
"node"[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct1:next -> NULL;
struct2:next -> struct1
"node"->head
tmp->struct1
head -> struct2
}
```
如果選 ```d``` ：因為讓 head 指向一個「指向 __node 的 pointer」，但是 head 的型態為 指向 __node 的 pointer，所以程式會產生錯誤無法 work。
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
tmp[shape=plaintext,fontcolor=blue];
"address of node 2"[shape=plaintext];
"node"[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct1:next -> struct2:thenode;
struct2:next -> NULL
"node"->head
tmp->struct1
head -> "address of node 2" -> struct2
}
```
如果選 ```e``` ：我們在上述有提到因為 operator 優先順序的關係，所以這個選項可以視為和 ```d``` 選項同義。
==所以BB2選擇 \(c\)==
#### ==BB1==
```(a)``` ```node = (*node)->next->next```
```(b)``` ```*node = (*node)->next->next```
```(c)``` ```*node = ((*node)->next)->next```
```(d)``` ```*node = &((*node)->next)->next```
```(e)``` ```node = &(*node)->next->next```
```(f)``` ```*node = &(*node)->next->next```
* 每次交換完的結果會如下，如果想要繼續交換的話我們必須將 head 移動到下一個要交換的節點上
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
"node"[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct1:next -> struct3;
struct2:next -> struct1;
struct3:next -> NULL
"node"->head
head -> struct2
}
```
如果選```a```：程式無法 work，因為 node 是一個 pointer to pointer的結構，但指向的 node 3 型態並不是一個指向 __node 型態的 pointer，所以進行第一次 swap 結束後就會無法執行。
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
"node"[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct1:next -> struct3;
struct2:next -> struct1;
struct3:next -> NULL
struct3 -> "___node???"
"node"->struct3
head -> struct2
}
```
如果選```b```：因為我們如果直接挪動了 \*node 指標，就會造成 node 1, 2 變成孤兒。所以 swap 結束後回傳的 head 會之後的元素。
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
"node"[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> node 4|{109|<next>next}}"];
struct1:next -> struct3;
struct2:next -> struct1;
struct3:next -> struct4;
struct4:next -> NULL
"node"->head
head -> struct2
}
```
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
"node"[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> node 4|{109|<next>next}}"];
struct1:next -> struct4;
struct2:next -> struct1;
struct3:next -> NULL;
struct4:next -> struct3
"node"->head
head -> struct4
}
```
如果選```c```：狀況和 ```b```同義，存在一樣的問題。
如果選```d```：因為讓 head 指向一個「指向 __node 的 pointer」，但是 head 的型態為指向 __node 的 pointer，所以程式會產生錯誤無法 work。
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
"node"[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
"address of node 3"[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> node 4|{109|<next>next}}"];
struct1:next -> struct3;
struct2:next -> struct1;
struct3:next -> struct4;
struct4:next -> NULL
"node"->head
head -> "address of node 3" -> struct3
}
```
如果選```e```：head 仍然能正確的紀錄起始位置，透過 node 的變動去兩兩做調整可以完成 swap
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
"node"[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
"address of node 3"[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> node 4|{109|<next>next}}"];
struct1:next -> struct3;
struct2:next -> struct1;
struct3:next -> struct4;
struct4:next -> NULL
"node"->"address of node 3" -> struct3
head ->struct2;
}
```
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
"node"[shape=plaintext,fontcolor=red];
NULL[shape=plaintext,fontcolor=black];
"address of node 4"[shape=plaintext,fontcolor=black];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> node 4|{109|<next>next}}"];
struct1:next -> struct4;
struct2:next -> struct1;
struct3:next -> NULL;
struct4:next -> struct3
"node"->"address of node 4" -> struct4
head ->struct2;
}
```
如果選```f```：同選項 ```d``` ，會有相同的問題
==所以BB2選擇 \(e\)==
### ==reverse( )==
```c=53
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
CCC;
head = next;
}
return cursor;
}
```
* line 57：宣告一個 next 指標指向 head->next
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
next[shape=plaintext,fontcolor=blue];
NULL[shape=plaintext,fontcolor=black];
cursor[shape=plaintext,fontcolor=purple];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> node 4|{109|<next>next}}"];
struct1:next -> struct2;
struct2:next -> struct3;
struct3:next -> struct4;
struct4:next -> NULL;
cursor -> NULL
head -> struct1
next -> struct2
}
```
#### ==CCC：==
```(a)``` ```cursor = head; head->next = cursor```
```(b)``` ```head->next = cursor; cursor = head```
```(c)``` ```cursor = head```
```(d)``` ```head->next = cursor```
```(e)``` ```head->next->next = cursor; cursor->next = head```
```(f)``` ```cursor->next = head; head->next->next = cursor```
如果選 ```a```：這樣會變成 node 都會產生一個 self-loop ，並沒有達到 reverse 的功能，且每個點在 ```reverse()```結束後都會有 memory leak 的問題。
```graphviz
digraph structs {
node [shape=record];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> node 4|{109|<next>next}}"];
struct1:next -> struct1
struct2:next -> struct2;
struct3:next -> struct3;
struct4:next -> NULL;
head -> struct4
next -> struct4
cursor -> struct3
head[shape=plaintext,fontcolor=darkgreen];
next[shape=plaintext,fontcolor=blue];
NULL[shape=plaintext,fontcolor=black];
cursor[shape=plaintext,fontcolor=purple];
}
```
如果選 ```b```： 能夠正確的 reverse list，注意是回傳 cursor 不是 head
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
next[shape=plaintext,fontcolor=blue];
NULL[shape=plaintext,fontcolor=black];
cursor[shape=plaintext,fontcolor=purple];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> node 4|{109|<next>next}}"];
struct1:next -> NULL;
struct2:next -> struct3;
struct3:next -> struct4;
struct4:next -> NULL;
cursor -> struct1
head -> struct2
next -> struct2
}
```
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
next[shape=plaintext,fontcolor=blue];
NULL[shape=plaintext,fontcolor=black];
cursor[shape=plaintext,fontcolor=purple];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> node 4|{109|<next>next}}"];
struct1:next -> NULL;
struct2:next -> struct1;
struct3:next -> struct2;
struct4:next -> struct3;
cursor -> struct4
head -> NULL
next -> NULL
}
```
如果選 ```c```： 完全沒有動到原本的 list 結構，僅是單純的移動 pointer
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
next[shape=plaintext,fontcolor=blue];
NULL[shape=plaintext,fontcolor=black];
cursor[shape=plaintext,fontcolor=purple];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> node 4|{109|<next>next}}"];
struct1:next -> struct2;
struct2:next -> struct3;
struct3:next -> struct4;
struct4:next -> NULL;
cursor -> struct4
head -> NULL
next -> NULL
}
```
如果選 ```d```： 因為 cursor 都沒有改變，僅是移動 head 和 next 的話最後所有 node 都會指向 NULL
```graphviz
digraph structs {
node [shape=record];
head[shape=plaintext,fontcolor=darkgreen];
next[shape=plaintext,fontcolor=blue];
NULL[shape=plaintext,fontcolor=black];
cursor[shape=plaintext,fontcolor=purple];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> node 4|{109|<next>next}}"];
struct1:next -> NULL;
struct2:next -> NULL;
struct3:next -> NULL;
struct4:next -> NULL;
cursor -> NULL
head -> NULL
next -> NULL
}
```
如果選 ```e```：cursor 指向 NULL ， NULL中並沒有 next 的成員可以使用，所以程式無法運行
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
head[shape=plaintext,fontcolor=darkgreen];
next[shape=plaintext,fontcolor=blue];
NULL[shape=plaintext,fontcolor=black];
cursor[shape=plaintext,fontcolor=purple];
struct1 [label="{<thenode> node 1|{72|<next>next}}"];
struct2 [label="{<thenode> node 2|{101|<next>next}}"];
struct3 [label="{<thenode> node 3|{108|<next>next}}"];
struct4 [label="{<thenode> node 4|{109|<next>next}}"];
struct1:next -> struct2;
struct2:next -> struct3;
struct3:next -> NULL;
struct4:next -> NULL;
cursor -> NULL -> "next ???"
head -> struct1
next -> struct2
}
```
如果選 ```f```： 和 ```d```選項有相同的問題，NULL 中並沒有 next 可供使用，所以程式也無法運行
==所以CCC選擇 \(b\)==
## 延伸問題 2 - 改寫 swap_pair( ) 與 reverse( )
:::info
函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = ... 的更新，請用指標的指標來改寫，並避免回傳指標;
:::
### ==new_swap_pair( )==
原始版本：
```c=42
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;
}
// call swap_pair() function
head = swap_pair(head);
```
* 我們可以發現 head 傳進來後只被使用過一次，就是被 node 用來參考指向 head 的 address，考慮 head 和 node 可能可以達到相同的功能，將 node 的使用替代成 head 方向做改寫
修改版本：
```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;
}
}
// call new_swap_pair() function
new_swap_pair(&head);
```
* 如此一來呼叫函式可以少利用一個 head 接 function 所傳回來的指標
* 在 `new_swap_pair()` function 中也省去了惱人的 node pointer，讓整體的可讀性更好
### ==new_reverse( )==
原始版本：
```c=53
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;
}
// call reverse() function
head = reverse(head);
```
* 修改和 swap_pair() 的出發點相似，但是 function 內使用到的 cursor, next 皆沒辦法再省略
* line 62 的地方將回傳改成用 \*head 指向 cursor 達到相同的效果
```c=53
void reverse_v2(node_t **head)
{
node_t *cursor = NULL;
while (*head) {
node_t *next = (*head)->next;
(*head)->next = cursor;
cursor = *head;
*head = next;
}
*head = cursor;
}
// call new_reverse() function
new_reverse(&head);
```
:::warning
自問自答：這樣的修改方法除了可讀性和封裝性較強，那對效能有好處嗎?
// TODO
:::
## 延伸問題 3 - 利用遞迴改寫 reverse( )
:::info
以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_recursive，隨後在 reverse 函式中呼叫 rev_recursive;
:::
* 思考：要換成遞迴，代表某段程式具有重複性，我們可以觀察到 line 56 ~ line 61 (while迴圈內容)具有這種特性
版本一：將 while 拆解放入 rev_recursive( ) 做
```c=
node_t* rev_recursive(node_t *cursor, node_t *head){
if (!(head))
return cursor;
node_t *next = head->next;
head->next = cursor;
cursor = head;
head = next;
return rev_recursive(cursor, head);
}
void new_reverse(node_t **head)
{
*head = rev_recursive(NULL, *head);
}
// call new_reverse()function
new_reverse(&head);
```
* 用反射的寫法就是將 while 直接丟到 recursive function 裡面做，但是會發現這麼做沒得到任何好處，甚至程式碼變得更醜了
版本二：直接傳入 \*\*head 的方法讓 function 內部有更多資訊，且富有更好的靈活度
```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 new_reverse(node_t **head)
{
rev_recursive(NULL, head);
}
// call new_reverse()function
new_reverse(&head);
```
* 本來想要想辦法節省 line 8, 9，經過一番嘗試後發現仍然沒辦法去除這兩行，但程式感覺還能再提升
版本三：利用多呼叫一個變數，減少 assign 和指標操作次數
```c=
void rev_recursive(node_t *cursor, node_t *now, node_t **head){
if (!now) {
*head = cursor;
return;
}
node_t *next = now->next;
now->next = cursor;
rev_recursive(now, next, head);
}
void new_reverse(node_t **head)
{
rev_recursive(NULL, *head, head);
}
// call new_reverse()function
new_reverse(&head);
```
* 如上面所說，程式更簡短了，犧牲多輸入一個變數的空間換取兩次 assign 的效能
:::warning
自問自答：版本二和版本三的效能取捨是可以討論的
// TODO
:::
## 延伸問題 4 - 利用 singly-linked list 實作 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
:::info
針對 singly-linked list 的節點，實作 Fisher–Yates shuffle，你應該儘量降低記憶體的使用量;
:::
### Fisher–Yates shuffle 特性分析
* 一種在**有限**序列上產生**隨機排序**的演算法
* 每一種排列的機率相同，不會偏執某種排列順序
* 計算複雜度和輸入大小成等比例關係
* 若有 N 個 item 則需要 N-1 輪做處理
* 是一種 [In-place algorithm](https://en.wikipedia.org/wiki/In-place_algorithm)
* 衍伸：Sattolo's algorithm：一種在長度n情況下產生亂序尋懷排列的演算法
* 傳統的 Fisher–Yates shuffle 演算法時間複雜度為 $\ O(n^2)$ ，改良過用於當代計算機中的演算法為 $\ O(n)$
* 傳統演算法會需要 $\ O(n^2)$ 的原因是每次選擇挑選出一個數，原序列皆需重新調整
### Modern method
* 假設 N = 10
* Initial state
```graphviz
digraph structs {
node [shape=record];
tail[shape=plaintext,fontcolor=black];
"random number"[shape=plaintext,fontcolor=black];
struct1 [label="{index|content}|{0|5}|{1|3}|{2|4}|{3|2}|{4|9}|{5|7}|{6|8}|{7|1}|{8|6}|{<0>9|0}"];
struct2 [label=""];
"random number" -> struct2;
tail ->struct1:0;
}
```
* round start - select a number from 0 to N - 1
```graphviz
digraph structs {
node [shape=record];
tail[shape=plaintext,fontcolor=black];
pointer[shape=plaintext,fontcolor=black];
"random number"[shape=plaintext,fontcolor=blue];
struct1 [label="{index|content}|{0|5}|{1|3}|{2|4}|{<3>3|2}|{4|9}|{5|7}|{6|8}|{7|1}|{8|6}|{<0>9|0}"];
struct2 [label="3"];
"random number" -> struct2;
tail -> struct1:0;
pointer ->struct1:3
}
```
* swap pointer <-> tail
```graphviz
digraph structs {
node [shape=record];
tail[shape=plaintext,fontcolor=blue];
pointer[shape=plaintext,fontcolor=darkgreen];
"random number"[shape=plaintext,fontcolor=black];
struct1 [label="{index|content}|{0|5}|{1|3}|{2|4}|{<3>3|0}|{4|9}|{5|7}|{6|8}|{7|1}|{<8>8|6}|{<9>9|2}"];
struct2 [label="3"];
"random number" -> struct2;
tail -> struct1:9;
pointer ->struct1:3
}
```
* round over - tail move
```graphviz
digraph structs {
node [shape=record];
tail[shape=plaintext,fontcolor=blue];
"random number"[shape=plaintext,fontcolor=black];
struct1 [label="{index|content}|{0|5}|{1|3}|{2|4}|{<3>3|0}|{4|9}|{5|7}|{6|8}|{7|1}|{<8>8|6}|{<9>9|2}"];
struct2 [label="3"];
"random number" -> struct2;
tail -> struct1:8;
}
```
* after 9 rounds - select number sequence = [ 3, 5, 7, 0, 4, 4, 0, 1, 1 ]
* final state
```graphviz
digraph structs {
node [shape=record];
tail[shape=plaintext,fontcolor=blue];
"random number"[shape=plaintext,fontcolor=black];
struct1 [label="{index|content}|{0|0}|{<1>1|4}|{2|3}|{<3>3|8}|{4|6}|{5|9}|{6|5}|{7|1}|{<8>8|7}|{<9>9|2}"];
struct2 [label="1"];
"random number" -> struct2;
tail -> struct1:1;
}
```
### 程式實現
```c=
void FYshuffle(node_t **head) {
srand((unsigned)time(NULL));
int randnum;
int lens = 0; // number of items
node_t *p = *head;
node_t *nhead = NULL;
node_t *prev;
// count number of items
while (p) {
lens++;
p = p->next;
}
// do shuffle
while (lens - 1) {
randnum = rand() % lens; // select number from 0 to (lens - 1)
p = *head;
prev = NULL;
while (randnum) {
prev = p;
p = p->next;
randnum--;
}
if (prev)
prev->next = p->next;
else
*head = (*head)->next;
p->next = nhead;
nhead = p;
lens--;
}
(*head)->next = nhead;
}
```
* 雖然我們想像中它是做 swap 的動作，但是因為 linked-list 具有良好的修改特性，所以我們實際上是將選擇到的 node->next 指向新的指標 nhead ，再將 nhead 更新指向選擇的 node
* line 11 - 14：單純計算 list 長度並記錄在 lens 中
* line 17 ：判斷條件為 (lens - 1) ，因為我們僅需要做 N - 1 輪便可以知道結果，即使是做 N 輪結果仍相同
* line 19 - 20：初始化 p 和 prev 指標的位置
* line 21 - 25：將指標移動到 list 第 k 個位置(k = random nubmer)
* line 26 - 29：prev 初始指向 NULL，所以需要判斷 random number = 0 的情況做處理
* 若 prev = NULL 代表 p 指向 \*head 所指向的位置, 則將 \*head 移動到下一格
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
prev[shape=plaintext,fontcolor=darkgreen];
p[shape=plaintext,fontcolor=brown];
NULL[shape=plaintext,fontcolor=black];
"*head"[shape=plaintext,fontcolor=black];
head[shape=plaintext,fontcolor=blue];
nhead[shape=plaintext,fontcolor=purple];
struct1 [label="{<thenode> node 1|72|<next>}"];
struct2 [label="{<thenode> node 2|101|<next>}"];
struct3 [label="{<thenode> node 3|108|<next>}"];
struct1:next ->struct2;
struct2:next ->struct3;
struct3:next -> NULL
"*head" -> struct1
head -> "*head"
p -> struct1
prev -> NULL
nhead -> NULL
}
```
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
prev[shape=plaintext,fontcolor=darkgreen];
p[shape=plaintext,fontcolor=brown];
NULL[shape=plaintext,fontcolor=black];
"*head"[shape=plaintext,fontcolor=black];
head[shape=plaintext,fontcolor=blue];
nhead[shape=plaintext,fontcolor=purple];
struct1 [label="{<thenode> node 1|72|<next>}"];
struct2 [label="{<thenode> node 2|101|<next>}"];
struct3 [label="{<thenode> node 3|108|<next>}"];
struct1:next ->struct2;
struct2:next ->struct3;
struct3:next -> NULL
"*head" -> struct2
head -> "*head"
p -> struct1
prev -> NULL
nhead -> NULL
}
```
* line 30：將 p 指標的 next 指向 nhead 的位置
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
prev[shape=plaintext,fontcolor=darkgreen];
p[shape=plaintext,fontcolor=brown];
NULL[shape=plaintext,fontcolor=black];
"*head"[shape=plaintext,fontcolor=black];
head[shape=plaintext,fontcolor=blue];
nhead[shape=plaintext,fontcolor=purple];
struct1 [label="{<thenode> node 1|72|<next>}"];
struct2 [label="{<thenode> node 2|101|<next>}"];
struct3 [label="{<thenode> node 3|108|<next>}"];
struct1:next -> NULL;
struct2:next ->struct3;
struct3:next -> NULL
"*head" -> struct2
head -> "*head"
p -> struct1
prev -> NULL
nhead -> NULL
}
```
* line 31：再將 nhead 的位置更新成 p 的位置，這樣可以保持 nhead 永遠指向最前端
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
prev[shape=plaintext,fontcolor=darkgreen];
p[shape=plaintext,fontcolor=brown];
NULL[shape=plaintext,fontcolor=black];
"*head"[shape=plaintext,fontcolor=black];
head[shape=plaintext,fontcolor=blue];
nhead[shape=plaintext,fontcolor=purple];
struct1 [label="{<thenode> node 1|72|<next>}"];
struct2 [label="{<thenode> node 2|101|<next>}"];
struct3 [label="{<thenode> node 3|108|<next>}"];
struct1:next -> NULL;
struct2:next ->struct3;
struct3:next -> NULL
"*head" -> struct2
head -> "*head"
p -> struct1
prev -> NULL
nhead -> struct1
}
```
* line 34：做完 N - 1 輪後，\*head 所指向的 list 應該僅剩一個元素，將這個元素的 next 指向亂序排列的 list 的頭(nhead)就可以使 head 拿到完整的亂序排列了
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
NULL[shape=plaintext,fontcolor=black];
"*head"[shape=plaintext,fontcolor=black];
head[shape=plaintext,fontcolor=blue];
nhead[shape=plaintext,fontcolor=purple];
struct1 [label="{<thenode> node 1|72|<next>}"];
struct2 [label="{<thenode> node 2|101|<next>}"];
struct3 [label="{<thenode> node 3|108|<next>}"];
struct1:next ->NULL;
struct2:next ->struct1;
struct3:next -> NULL
"*head" -> struct3
head -> "*head"
nhead -> struct2
}
```
```graphviz
digraph structs {
node [shape=record];
rankdir = LR
NULL[shape=plaintext,fontcolor=black];
"*head"[shape=plaintext,fontcolor=black];
head[shape=plaintext,fontcolor=blue];
nhead[shape=plaintext,fontcolor=purple];
struct1 [label="{<thenode> node 1|72|<next>}"];
struct2 [label="{<thenode> node 2|101|<next>}"];
struct3 [label="{<thenode> node 3|108|<next>}"];
struct1:next ->NULL;
struct2:next ->struct1;
struct3:next -> NULL
struct3:next -> struct2 [color="red"]
"*head" -> struct3
head -> "*head"
nhead -> struct2
}
```
Sign in with Wallet
Connect another wallet