# 2020q3 Homework1 (quiz1)
contributed by < `shauming1020` >
###### tags: `homework`
## Q1. 解釋程式運作原理
> 解釋上述程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現;
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> value | <next> next} | node name "];
ptr1 [label= "<name> pointer_name | <value> &node"];
pptr1 [label= "<name> pointer to pointer_name | <value> Address"];
ptr1:value -> node1:value
pptr1:value -> ptr1:name
pptr1:value -> node1:value
pptr1:value -> node1:next
}
```
---
### 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); // AA1
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node; // AA2
}
```
- AA1 檢查是否成功 malloc 空間給 new_node 指向
:::info
ISO/IEC 9899:TC3 規格書 p.169 提到 assert
if expression (which shall have a scalar type) is false (that is, compares equal to 0),
the assert macro writes information about the particular call that failed on the standard error stream in an implementation-defined format.165).
It then calls the abort function.
:::
- AA2 當 *indirect 取值為 NULL 時，表 indirect 正指向尾端節點的 next，因此要讓尾端節點指向 新節點的位址，故選 *indirect = new_node;
- 示意流程
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node2} | node1"];
node2 [label= " {<value> 2 | <next> NULL} | node2"];
node3 [label= " {<value> new_value | <next> NULL} | node3 "];
ptr1 [label= "<name> head | <value> &node1"];
ptr2 [label= "<name> new_node | <value> &node3"];
pptr1 [label= "<name> indirect | <value> &head"];
node1:next -> node2:value
ptr1:value -> node1:value
ptr2:value -> node3:value
pptr1:value -> ptr1:name
}
```
``` #10 condition: while (*indirect)```
- 從 indirect 所存位址取值不為 NULL 時，表尚未走訪到尾端節點
``` #11 indirect = &(*indirect)->next```
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node2} | node1 "];
node2 [label= " {<value> 2 | <next> NULL} | node2 "];
node3 [label= " {<value> new_value | <next> NULL} | node3 "];
ptr1 [label= "<name> head | <value> &node1"];
ptr2 [label= "<name> new_node | <value> &node3"];
pptr1 [label= "<name> indirect | <value> &(node1.next)"];
node1:next -> node2:value
ptr1:value -> node1:value
ptr2:value -> node3:value
pptr1:value -> node1:next
}
```
- 取的值為 NULL 時，表走訪到尾端節點的 next
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node2} | node1 "];
node2 [label= " {<value> 2 | <next> NULL} | node2 "];
node3 [label= " {<value> new_value | <next> NULL} | node3 "];
ptr1 [label= "<name> head | <value> &node1"];
ptr2 [label= "<name> new_node | <value> &node3"];
pptr1 [label= "<name> indirect | <value> &(node2.next)"];
node1:next -> node2:value
ptr1:value -> node1:value
ptr2:value -> node3:value
pptr1:value -> node2:next
}
```
``` #12 *indirect = new_node```
- 讓他的 next 指向 new_node (即 &node3)
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node2} | node1 "];
node2 [label= " {<value> 2 | <next> &node3} | node2 "];
node3 [label= " {<value> new_value | <next> NULL} | node3 "];
ptr1 [label= "<name> head | <value> &node1"];
ptr2 [label= "<name> new_node | <value> &node3"];
pptr1 [label= "<name> indirect | <value> &(node2.next)"];
node1:next -> node2:value
node2:next -> node3:value
ptr1:value -> node1:value
ptr2:value -> node3:value
pptr1:value -> node2:next
}
```
---
### find_entry
> 搜尋節點，成功則回傳找到的目標節點，否則回傳 NULL
``` 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;
}
```
```#4 condition: current && current->value != value ```
- 若 current 未指向 NULL 且 current 的 value 不為目標值，則往 next 繼續走訪
- 當找到目標值，表 current 指向目標節點位址，回傳 current，否則回傳 NULL
---
### 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);
}
```
- 示意流程
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node2} | node1"];
node2 [label= " {<value> 2 | <next> &node3} | node2"];
node3 [label= " {<value> 3 | <next> NULL} | node3"];
ptr1 [label= "<name> head | <value> &node1"];
ptr2 [label= "<name> entry | <value> &node3"];
pptr1 [label= "<name> indirect | <value> &head"];
node1:next -> node2:value
node2:next -> node3:value
ptr1:value -> node1:value
ptr2:value -> node3:value
pptr1:value -> ptr1
}
```
``` #5 condition: while ((*indirect) != entry) ```
- 當 *indirect 與 entry 指向不同的節點位址時
``` #6 indirect = &(*indirect)->next ```
- 則往下繼續遍歷，直到 *indirect 恰指向目標節點的位址
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node2} | node1 "];
node2 [label= " {<value> 2 | <next> &node3} | node2"];
node3 [label= " {<value> 3 | <next> NULL} | node3"];
ptr1 [label= "<name> head | <value> &node1"];
ptr2 [label= "<name> entry | <value> &node3"];
pptr1 [label= "<name> indirect | <value> &(node2.next)"];
node1:next -> node2:value
node2:next -> node3:value
ptr1:value -> node1:value
ptr2:value -> node3:value
pptr1:value -> node2:next
}
```
``` #8 *indirect = entry->next ```
- 讓 *indirect 指向 entry 的 next
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node2} | node1"];
node2 [label= " {<value> 2 | <next> NULL} | node2"];
node3 [label= " {<value> 3 | <next> NULL} | node3"];
ptr1 [label= "<name> head | <value> &node1"];
ptr2 [label= "<name> entry | <value> &node3"];
pptr1 [label= "<name> indirect | <value> &(node2.next)"];
node1:next -> node2:value
ptr1:value -> node1:value
ptr2:value -> node3:value
pptr1:value -> node2:next
}
```
``` #9 free(entry) ```
- 釋放 entry 所指向 heap 的空間
---
### swap_pair
> 交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 1->2->3->4，則該回傳 2->1->4->3
``` 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;
}
```
- BB1 解讀成 node = &(((*node)->next)->next)，完成一對的交換後，將 *node 往下走訪兩節點
- BB2 *node 為新一對當中的開頭者，因此要先讓 *node 往下一個節點去抓新的開頭
- 示意流程
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node2} | node1 "];
node2 [label= " {<value> 2 | <next> &node3} | node2 "];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node1"];
pptr1 [label= "<name> node | <value> &head"];
node1:next -> node2:value
node2:next -> node3:value
node3:next -> node4:value
ptr1:value -> node1:value
pptr1:value -> ptr1
}
```
``` #3 condition: if *node && (*node)->next ```
* 判斷當前與下一個指向是否為空，若非空則可以進行成對的交換
``` #4 node_t *tmp = *node```
- 讓一個 tmp 指標指向與 *node 相同的位址
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node2} | node1"];
node2 [label= " {<value> 2 | <next> &node3} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node1"];
ptr2 [label= "<name> tmp | <value> &node1"];
pptr1 [label= "<name> node | <value> &head"];
node1:next -> node2:value
node2:next -> node3:value
node3:next -> node4:value
ptr1:value -> node1:value
ptr2:value -> node1:value
pptr1:value -> ptr1
}
```
``` #5 *node = (*node)->next```
- (*node)->next 為 &node2 指派給 *node，即讓 *node，也就是 head 往下走訪一個節點
- 往下個節點抓新對的開頭
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node2} | node1"];
node2 [label= " {<value> 2 | <next> &node3} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node2"];
ptr2 [label= "<name> tmp | <value> &node1"];
pptr1 [label= "<name> node | <value> &head"];
node1:next -> node2:value
node2:next -> node3:value
node3:next -> node4:value
ptr1:value -> node2:value
ptr2:value -> node1:value
pptr1:value -> ptr1:name
}
```
``` #6 tmp->next = (*node)->next```
- 這時 (*node)->next 為 &node3，指派到 tmp->next，也就讓 (*node) 的下一個節點成為 tmp 的下一個節點
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node3} | node1"];
node2 [label= " {<value> 2 | <next> &node3} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node2"];
ptr2 [label= "<name> tmp | <value> &node1"];
pptr1 [label= "<name> node | <value> &head"];
node1:next -> node3:value
node2:next -> node3:value
node3:next -> node4:value
ptr1:value -> node2:value
ptr2:value -> node1:value
pptr1:value -> ptr1:name
}
```
``` #7 (*node)->next = tmp```
- 將 tmp 的值指派到 (*node)->next，也就是 (*node)->next 的值改為 tmp 所存的節點位址
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node3} | node1 "];
node2 [label= " {<value> 2 | <next> &node1} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node2"];
ptr2 [label= "<name> tmp | <value> &node1"];
pptr1 [label= "<name> node | <value> &head"];
node1:next -> node3:value
node2:next -> node1:value
node3:next -> node4:value
ptr1:value -> node2:value
ptr2:value -> node1:value
pptr1:value -> ptr1:name
}
```
``` node = &(*node)->next->next```
- &(*node)->next->next 解讀成 &(((*node)->next)->next)
- 因此先得到 (*node)->next) 的值 &node1
- 再將 node1->next 的位址指派給 node
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node3} | node1 "];
node2 [label= " {<value> 2 | <next> &node1} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node2"];
ptr2 [label= "<name> tmp | <value> &node1"];
pptr1 [label= "<name> node | <value> &(node1.next)"];
node1:next -> node3:value
node2:next -> node1:value
node3:next -> node4:value
ptr1:value -> node2:value
ptr2:value -> node1:value
pptr1:value -> node1:next
}
```
- 執行直到跳出迴圈 ，最後回傳 head
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node4} | node1 "];
node2 [label= " {<value> 2 | <next> &node1} | node2"];
node3 [label= " {<value> 3 | <next> NULL} | node3 "];
node4 [label= " {<value> 4 | <next> &node3} | node4 "];
ptr1 [label= "<name> head | <value> &node2"];
pptr1 [label= "<name> node | <value> &(node3.next)"];
node1:next -> node4:value
node2:next -> node1:value
node4:next -> node3:value
ptr1:value -> node2:value
pptr1:value -> node3:next
}
```
---
### reverse
> 將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1
``` 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;
}
```
- 從最後 return cursor 得知，cursor 是新 list 的 head，因此 head->next = cursor 是讓舊的 head 去指向新的 head (i.e. cursor)，再透過 cursor = head 讓 cursor 移動到新接上來的節點上，達到反向的效果
- 示意流程
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node2} | node1 "];
node2 [label= " {<value> 2 | <next> &node3} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node1"];
ptr2 [label= "<name> cursor | <value> NULL"];
node1:next -> node2:value
node2:next -> node3:value
node3:next -> node4:value
ptr1:value -> node1:value
}
```
```#5 node_t *next = head->next;```
- head->next 取值 &node2，指派到 next
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node2} | node1 "];
node2 [label= " {<value> 2 | <next> &node3} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4 "];
ptr1 [label= "<name> head | <value> &node1"];
ptr2 [label= "<name> cursor | <value> NULL"];
ptr3 [label= "<name> next | <value> &node2"];
node1:next -> node2:value
node2:next -> node3:value
node3:next -> node4:value
ptr1:value -> node1:value
ptr3:value -> node2:value
}
```
```#6 head->next = cursor```
- 將 cursor 值 NULL，指派到 head->next
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> NULL} | node1 "];
node2 [label= " {<value> 2 | <next> &node3} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node1"];
ptr2 [label= "<name> cursor | <value> NULL"];
ptr3 [label= "<name> next | <value> &node2"];
node2:next -> node3:value
node3:next -> node4:value
ptr1:value -> node1:value
ptr3:value -> node2:value
}
```
```#6 cursor = head ```
- 將 head 值 &node1，指派給 cursor
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> NULL} | node1 "];
node2 [label= " {<value> 2 | <next> &node3} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4 "];
ptr1 [label= "<name> head | <value> &node1"];
ptr2 [label= "<name> cursor | <value> &node1"];
ptr3 [label= "<name> next | <value> &node2"];
node2:next -> node3:value
node3:next -> node4:value
ptr1:value -> node1:value
ptr3:value -> node2:value
ptr2:value -> node1:value
}
```
```#7 head = next```
- 將 next 值 &node2，指派給 head
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> NULL} | node1 "];
node2 [label= " {<value> 2 | <next> &node3} | node2 "];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4 "];
ptr1 [label= "<name> head | <value> &node2"];
ptr2 [label= "<name> cursor | <value> &node1"];
ptr3 [label= "<name> next | <value> &node2"];
node2:next -> node3:value
node3:next -> node4:value
ptr1:value -> node2:value
ptr3:value -> node2:value
ptr2:value -> node1:value
}
```
- 直到 head 值為 NULL，跳出迴圈並回傳 cursor，即成為新的 head
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> NULL} | node1"];
node2 [label= " {<value> 2 | <next> &node1} | node2"];
node3 [label= " {<value> 3 | <next> &node2} | node3"];
node4 [label= " {<value> 4 | <next> &node3} | node4"];
ptr1 [label= "<name> head | <value> NULL"];
ptr2 [label= "<name> cursor | <value> &node4"];
node4:next -> node3:value
node3:next -> node2:value
node2:next -> node1:value
ptr2:value -> node4:value
}
```
---
## Q2. 請用指標的指標來改寫，並避免回傳指標
> 函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = ... 的更新，請用指標的指標來改寫，並避免回傳指標;
### 1. 改寫 swap_pair
```c=
void swap_pair_v2(node_t **node)
{
for (; *node && (*node)->next; node = &(*node)->next->next) {
node_t *tmp = *node;
*node = (*node)->next;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
}
...
swap_pair_v2(&head);
```
- 原來的程式碼輸入 node_t *head 後再調用 node_t **node = &head 去進行操作，最後回傳 head 指標
- 因為 call-by-value，執行函式呼叫後會宣告一個 node_t *head 與輸入的指標指向相同的節點，函式內是對該 head 進行操作，因此實際上並沒有更動到原先輸入的指標，故最後還要回傳完成操作後的 head
- 參考 [你所不知道的C語言:指標篇](https://hackmd.io/@sysprog/c-pointer?type=view#%E6%B2%92%E6%9C%89%E3%80%8C%E9%9B%99%E6%8C%87%E6%A8%99%E3%80%8D%E5%8F%AA%E6%9C%89%E3%80%8C%E6%8C%87%E6%A8%99%E7%9A%84%E6%8C%87%E6%A8%99%E3%80%8D)
- 而一開始若把 &head 當作引數輸入給 node_t **node，則會直接對原 head 操作
### 2. 改寫 reverse
```c=
void reverse_v2(node_t **node)
{
node_t *cursor = NULL;
while (*node) {
node_t *next = (*node)->next;
(*node)->next = cursor; cursor = *node;
*node = next;
}
*node = cursor;
}
...
reverse_v2(&head);
```
- 原理與上述相同，而最後操作完 head 會指向 NULL，因此要讓 head 重新指向新的 head (i.e. cursor)
- 示意流程
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node2} | node1 "];
node2 [label= " {<value> 2 | <next> &node3} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node1"];
ptr2 [label= "<name> cursor | <value> NULL"];
pptr1 [label= "<name> node | <value> &head"];
node1:next -> node2:value
node2:next -> node3:value
node3:next -> node4:value
ptr1:value -> node1:value
pptr1:value -> ptr1:name
}
```
``` #5 node_t *next = (*node)->next ```
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node2} | node1"];
node2 [label= " {<value> 2 | <next> &node3} | node2 "];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node1"];
ptr2 [label= "<name> cursor | <value> NULL"];
ptr3 [label= "<name> next | <value> &node2"];
pptr1 [label= "<name> node | <value> &head"];
node1:next -> node2:value
node2:next -> node3:value
node3:next -> node4:value
ptr1:value -> node1:value
ptr3:value -> node2:value
pptr1:value -> ptr1:name
}
```
``` #6 (*node)->next = cursor; cursor = *node; ```
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> NULL} | node1"];
node2 [label= " {<value> 2 | <next> &node3} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node1"];
ptr2 [label= "<name> cursor | <value> &node1"];
ptr3 [label= "<name> next | <value> &node2"];
pptr1 [label= "<name> node | <value> &head"];
node2:next -> node3:value
node3:next -> node4:value
ptr1:value -> node1:value
ptr3:value -> node2:value
ptr2:value -> node1:value
pptr1:value -> ptr1:name
}
```
``` #7 *node = next ```
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> NULL} | node1"];
node2 [label= " {<value> 2 | <next> &node3} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node2"];
ptr2 [label= "<name> cursor | <value> &node1"];
ptr3 [label= "<name> next | <value> &node2"];
pptr1 [label= "<name> node | <value> &head"];
node2:next -> node3:value
node3:next -> node4:value
ptr1:value -> node2:value
ptr3:value -> node2:value
ptr2:value -> node1:value
pptr1:value -> ptr1:name
}
```
- 下個迴圈
``` #5 node_t *next = (*node)->next ```
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> NULL} | node1"];
node2 [label= " {<value> 2 | <next> &node3} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node2"];
ptr2 [label= "<name> cursor | <value> &node1"];
ptr3 [label= "<name> next | <value> &node3"];
pptr1 [label= "<name> node | <value> &head"];
node2:next -> node3:value
node3:next -> node4:value
ptr1:value -> node2:value
ptr3:value -> node3:value
ptr2:value -> node1:value
pptr1:value -> ptr1:name
}
```
``` #6 (*node)->next = cursor ```
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> NULL} | node1"];
node2 [label= " {<value> 2 | <next> &node1} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node2"];
ptr2 [label= "<name> cursor | <value> &node1"];
ptr3 [label= "<name> next | <value> &node3"];
pptr1 [label= "<name> node | <value> &head"];
node2:next -> node1:value
node3:next -> node4:value
ptr1:value -> node2:value
ptr3:value -> node3:value
ptr2:value -> node1:value
pptr1:value -> ptr1:name
}
```
``` #6 cursor = *node ```
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> NULL} | node1"];
node2 [label= " {<value> 2 | <next> &node1} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node2"];
ptr2 [label= "<name> cursor | <value> &node2"];
ptr3 [label= "<name> next | <value> &node3"];
pptr1 [label= "<name> node | <value> &head"];
node2:next -> node1:value
node3:next -> node4:value
ptr1:value -> node2:value
ptr3:value -> node3:value
ptr2:value -> node2:value
pptr1:value -> ptr1:name
}
```
``` #7 *node = next ```
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> NULL} | node1"];
node2 [label= " {<value> 2 | <next> &node1} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node3"];
ptr2 [label= "<name> cursor | <value> &node2"];
ptr3 [label= "<name> next | <value> &node3"];
pptr1 [label= "<name> node | <value> &head"];
node2:next -> node1:value
node3:next -> node4:value
ptr1:value -> node3:value
ptr3:value -> node3:value
ptr2:value -> node2:value
pptr1:value -> ptr1:name
}
```
- 依序做下去直到跳出迴圈
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> NULL} | node1"];
node2 [label= " {<value> 2 | <next> &node1} | node2"];
node3 [label= " {<value> 3 | <next> &node2} | node3"];
node4 [label= " {<value> 4 | <next> &node3} | node4"];
ptr1 [label= "<name> head | <value> NULL"];
ptr2 [label= "<name> cursor | <value> &node4"];
pptr1 [label= "<name> node | <value> &head"];
node4:next -> node3:value
node3:next -> node2:value
node2:next -> node1:value
ptr2:value -> node4:value
pptr1:value -> ptr1:name
}
```
``` #9 *node = cursor```
- 最後要將 cursor 值指派給 *node
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> NULL} | node1"];
node2 [label= " {<value> 2 | <next> &node1} | node2"];
node3 [label= " {<value> 3 | <next> &node2} | node3"];
node4 [label= " {<value> 4 | <next> &node3} | node4"];
ptr1 [label= "<name> head | <value> &node4"];
ptr2 [label= "<name> cursor | <value> &node4"];
pptr1 [label= "<name> node | <value> &head"];
node4:next -> node3:value
node3:next -> node2:value
node2:next -> node1:value
ptr1:value -> node4:value
ptr2:value -> node4:value
pptr1:value -> ptr1:name
}
```
---
## Q3. 以遞迴改寫上述的 reverse
> 以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_resersive，隨後在 reverse 函式中呼叫 rev_resersive;
>
```c=
node_t *rev_resersive(node_t **node, node_t **cursor) {
if (*node) {
node_t *next = (*node)->next;
(*node)->next = *cursor; *cursor = *node;
*node = next;
*cursor = rev_resersive(node, cursor);
}
return *cursor;
}
void reverse_v3(node_t **node)
{
node_t *cursor = NULL;
*node = rev_resersive(node, &cursor);
}
...
reverse_v3(&head);
```
- 將 while 迴圈內會重複執行的程式部份改用遞迴方式呼叫執行，最後在回傳 cursor 即可
---
## Q4. Fisher–Yates shuffle
> 針對 singly-linked list 的節點，實作 Fisher–Yates shuffle，你應該儘量降低記憶體的使用量;
:::info
The modern algorithm
```
-- To shuffle an array a of n elements (indices 0..n-1):
** for i from n−1 downto 1 do **
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
```
假設rand()時間複雜度為O(1)
採用array實作時間複雜度為O(n)，但需要一額外與數組大小相同的空間，用來存放隨機取出的值，因此空間複雜度為O(2n)
---
| Range | Roll | Scratch | Result |
| -------- | -------- | -------- | -------- |
| | |1 2 3 4 5 6 7 8 | |
| 1–8 | 6 |1 2 3 4 5 **8** 7 | **6** |
| 1–7 | 2 |1 **7** 3 4 5 8 | **2** 6 |
| 1-6 | 6 |1 7 3 4 5 | **8** 2 6 |
| ... |
:::
### 實作
#### create_list
> 生成 n 個值為 {1, ..., n} 升冪排列的 list node
``` c=
void create_list(node_t **node, int n)
{
for (int i = 1; !(*node) && i <= n; node = &(*node)->next, i++) {
node_t *new_node = malloc(sizeof(node_t));
new_node->value = i;
new_node->next = NULL;
*node = new_node;
}
}
```
- n = 4
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> &node2} | node1"];
node2 [label= " {<value> 2 | <next> &node3} | node2"];
node3 [label= " {<value> 3 | <next> &node4} | node3"];
node4 [label= " {<value> 4 | <next> NULL} | node4"];
ptr1 [label= "<name> head | <value> &node1"];
pptr1 [label= "<name> node | <value> &head"];
node1:next -> node2:value
node2:next -> node3:value
node3:next -> node4:value
ptr1:value -> node1:value
pptr1:value -> ptr1:name
}
```
#### swap_value
> 交換兩 node_t 的值
``` c=
void swap_value(node_t **a, node_t **b) {
int tmp = (*a)->value;
(*a)->value = (*b)->value;
(*b)->value = tmp;
}
```
#### FYshuffle
- 參考 [Shuffle a given array using Fisher–Yates shuffle Algorithm](https://www.geeksforgeeks.org/shuffle-a-given-array-using-fisher-yates-shuffle-algorithm/) 矩陣版本修改
```c=
void FYshuffle (node_t **head, int n)
{
srand(time(NULL));
reverse(head);
node_t **start = head;
node_t **pick = head;
for (int i = n-1; i > 0; i--) {
// select a random index from 0 to i
int j = rand() % (i+1);
// shift pick to this index
for (;j && (*pick); j--, pick = &(*pick)->next);
// swap the pick value with start value.
swap_value(start, pick);
// update the start and pick
start = &(*start)->next; pick = start;
}
}
```
| Range | Roll | Scratch |
| -------- | -------- | -------- |
| | |1 2 3 4 5 6 7 8 |
| reverse | - |8 7 6 5 4 3 2 1 |
| 1–8 | 3 |[6] 7 8 5 4 3 2 1 |
| 1–7 | 6 |[6 2] 8 5 4 3 7 1 |
| 1-6 | 6 |[6 2 1] 5 4 3 7 8 |
| 1-5 | 0 |[6 2 1 5] 4 3 7 8 |
| ... | | |
``` #4 reverse(head) ```
- 演算法會從**數組尾端往前取值**，但作業要求是單向的list，因此需先對 list 反向
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> NULL} | node1"];
node2 [label= " {<value> 2 | <next> &node1} | node2"];
node3 [label= " {<value> 3 | <next> &node2} | node3"];
node4 [label= " {<value> 4 | <next> &node3} | node4"];
ptr1 [label= "<name> head | <value> &node4"];
pptr1 [label= "<name> head | <value> &head"];
pptr2 [label= "<name> start | <value> &head"];
pptr3 [label= "<name> pick | <value> &head"];
node4:next -> node3:value
node3:next -> node2:value
node2:next -> node1:value
ptr1:value -> node4:value
pptr1:value -> ptr1:name
pptr2:value -> ptr1:name
pptr3:value -> ptr1:name
}
```
``` #5 condition: for (int i = n-1; i > 0; i--) ```
``` #11 int j = rand() % (i+1) ```
- 從 [0, i] 隨機取出一個值，i + 1 為當前可取的 list 長度，且會逐漸縮短
``` #14 for (;j && (*pick); j--, pick = &(*pick)->next); ```
- 移動 pick 使其指向目標 node
- 假設 j = 3，則將 pick 往 next 移動 3 次
- 若 j = 0，則不需要移動 pick
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 1 | <next> NULL} | node1"];
node2 [label= " {<value> 2 | <next> &node1} | node2"];
node3 [label= " {<value> 3 | <next> &node2} | node3"];
node4 [label= " {<value> 4 | <next> &node3} | node4"];
ptr1 [label= "<name> head | <value> &node4"];
pptr1 [label= "<name> head | <value> &head"];
pptr2 [label= "<name> start | <value> &head"];
pptr3 [label= "<name> pick | <value> &(node2.next)"];
node4:next -> node3:value
node3:next -> node2:value
node2:next -> node1:value
ptr1:value -> node4:value
pptr1:value -> ptr1:name
pptr2:value -> ptr1:name
pptr3:value -> node2:next
}
```
``` #17 swap_value(start, pick) ```
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 4 | <next> NULL} | node1"];
node2 [label= " {<value> 2 | <next> &node1} | node2"];
node3 [label= " {<value> 3 | <next> &node2} | node3"];
node4 [label= " {<value> 1 | <next> &node3} | node4"];
ptr1 [label= "<name> head | <value> &node4"];
pptr1 [label= "<name> head | <value> &head"];
pptr2 [label= "<name> start | <value> &head"];
pptr3 [label= "<name> pick | <value> &(node2.next)"];
node4:next -> node3:value
node3:next -> node2:value
node2:next -> node1:value
ptr1:value -> node4:value
pptr1:value -> ptr1:name
pptr2:value -> ptr1:name
pptr3:value -> node2:next
}
```
``` #20 start = &(*start)->next ```
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 4 | <next> NULL} | node1"];
node2 [label= " {<value> 2 | <next> &node1} | node2"];
node3 [label= " {<value> 3 | <next> &node2} | node3"];
node4 [label= " {<value> 1 | <next> &node3} | node4"];
ptr1 [label= "<name> head | <value> &node4"];
pptr1 [label= "<name> head | <value> &head"];
pptr2 [label= "<name> start | <value> &(node4.next)"];
pptr3 [label= "<name> pick | <value> &(node2.next)"];
node4:next -> node3:value
node3:next -> node2:value
node2:next -> node1:value
ptr1:value -> node4:value
pptr1:value -> ptr1:name
pptr2:value -> node4:next
pptr3:value -> node2:next
}
```
``` #20 pick = start ```
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 4 | <next> NULL} | node1"];
node2 [label= " {<value> 2 | <next> &node1} | node2"];
node3 [label= " {<value> 3 | <next> &node2} | node3"];
node4 [label= " {<value> 1 | <next> &node3} | node4"];
ptr1 [label= "<name> head | <value> &node4"];
pptr1 [label= "<name> head | <value> &head"];
pptr2 [label= "<name> start | <value> &(node4.next)"];
pptr3 [label= "<name> pick | <value> &(node4.next)"];
node4:next -> node3:value
node3:next -> node2:value
node2:next -> node1:value
ptr1:value -> node4:value
pptr1:value -> ptr1:name
pptr2:value -> node4:next
pptr3:value -> node4:next
}
```
- 假設每回都取到自己，即 j = 0
- 執行完 n - 1 個 iteration，此例 n = 4，故 start 會移動 3 次
```graphviz
digraph structs {
rankdir=LR;
node[shape=record];
node1 [label= " {<value> 4 | <next> NULL} | node1"];
node2 [label= " {<value> 2 | <next> &node1} | node2"];
node3 [label= " {<value> 3 | <next> &node2} | node3"];
node4 [label= " {<value> 1 | <next> &node3} | node4"];
ptr1 [label= "<name> head | <value> &node4"];
pptr1 [label= "<name> head | <value> &head"];
pptr2 [label= "<name> start | <value> &(node2.next)"];
pptr3 [label= "<name> pick | <value> &(node2.next)"];
node4:next -> node3:value
node3:next -> node2:value
node2:next -> node1:value
ptr1:value -> node4:value
pptr1:value -> ptr1:name
pptr2:value -> node2:next
pptr3:value -> node2:next
}
```
### 分析
- 假設 rand() 為 $O(1)$ 和 reverse() 為 $O(n)$
- 時間複雜度
* **Worst Case** : 每次取到最遠的值做交換，每回移動 pick $O(n)$，共 n 回，$O(n^2)$
* **Best Case** : 每次取到最近的值交換，每回移動 pick $O(1)$，共 n 回，$O(n)$
* **Average Case** : $O$(($n^2$ + $n$) / 2) = $O(n^2)$
- 空間複雜度
* 只使用 n 個 node 和 3 個 pointer to pointer 變數，故 $O(n)$
### 完整測試程式碼如下
```c=
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct __node {
int value;
struct __node *next;
} node_t;
void create_list(node_t **node, int n)
{
for (int i = 1; !(*node) && i <= n; node = &(*node)->next, i++) {
node_t *new_node = malloc(sizeof(node_t));
new_node->value = i;
new_node->next = NULL;
*node = new_node;
}
}
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;
}
void swap_value(node_t **a, node_t **b) {
int tmp = (*a)->value;
(*a)->value = (*b)->value;
(*b)->value = tmp;
}
void FYshuffle (node_t **head, int n)
{
srand(time(NULL));
reverse(head); printf("reverse as initial ... "); print_list(*head);
node_t **start = head;
node_t **pick = head;
for (int i = n-1; i > 0; i--) {
// select a random index from 0 to i
int j = rand() % (i+1);
// shift pick to this index
for (;j && (*pick); j--, pick = &(*pick)->next);
printf("[iter %d] start at %d ,and swap with %d ... ", n-i, (*start)->value, (*pick)->value);
// swap the pick value with start value.
swap_value(start, pick); print_list(*head);
// update the start and pick
start = &(*start)->next; pick = start;
}
printf("[final] start at %d \n", (*start)->value);
}
void print_list(node_t *head)
{
for (node_t *current = head; current; current = current->next)
printf("%d ", current->value);
printf("\n");
}
int main() {
int len = 8;
node_t *head = NULL;
create_list(&head, len);
printf("before shuffle "); print_list(head);
FYshuffle(&head, len);
printf("after shuffle "); print_list(head);
}
```
```
before shuffle 1 2 3 4 5 6 7 8
reverse as initial ... 8 7 6 5 4 3 2 1
[iter 1] start at 8 ,and swap with 8 ... 8 7 6 5 4 3 2 1
[iter 2] start at 7 ,and swap with 4 ... 8 4 6 5 7 3 2 1
[iter 3] start at 6 ,and swap with 3 ... 8 4 3 5 7 6 2 1
[iter 4] start at 5 ,and swap with 6 ... 8 4 3 6 7 5 2 1
[iter 5] start at 7 ,and swap with 5 ... 8 4 3 6 5 7 2 1
[iter 6] start at 7 ,and swap with 7 ... 8 4 3 6 5 7 2 1
[iter 7] start at 2 ,and swap with 1 ... 8 4 3 6 5 7 1 2
[final] start at 2
after shuffle 8 4 3 6 5 7 1 2
```
---
Sign in with Wallet
Connect another wallet