# 2020q3 Homework1 (quiz1)
contributed by < `unknowntpo` >
:::success
TODO:
參考 [RinHizakura 同學的題解與實驗](https://hackmd.io/@RinHizakura/BysgszHNw)
1. 繪製 Graphiz
2. 重做實驗並驗證
:::
## 重點:
* Pointer to pointer 的使用
# 延伸問題
:::success
延伸問題:
1. 解釋上述程式運作原理，搭配 Graphviz 在 HackMD 筆記上視覺化展現;
1. 函式 `swap_pair` 和 `reverse` 對於指標的操作方式顯然異於 `add_entry` 及 `remove_entry`，需要額外做 `head = ...` 的更新，請用指標的指標來改寫，並避免回傳指標;
1. 以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_resersive，隨後在 reverse 函式中呼叫 rev_resersive;
1. 針對 singly-linked list 的節點，實作 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)，你應該儘量降低記憶體的使用量;
:::
## 結構體
```cpp=4
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
### 分析
* `__node` 的命名慣例是？
:::warning
`__node` 的命名沒有什麼特別，你可以換成偏好的方式，但需要避免 conflicts，這也是為何有 `__`
:notes: jserv
:::
## `add_entry`
```cpp=10
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(&head, 72);`
`main()` 呼叫 `add_entry()` 時傳入
1.`head` 指標本身的地址，也就是 `&head`，並由 `**head` 來接收
2. 要新增的數值 `new_value`
* line 12
* 宣告 `node_t **indirect` 並指向 pointer `head` ，用來把 pointer `head` 移動到 linked list 末端 `NULL` 的位置
* line 14-18
* 配置記憶體空間
* 大小為 1 個 node
* 使用 pointer `new_node` 來指向他
* 使用 `assert()` macro 來檢查是否配置記憶體成功
* 當 `new_node == NULL` 時，會呼叫 `abort(3)` 並把 error message 輸出到 stderr， 請參考 [man-page](https://man7.org/linux/man-pages/man3/assert.3.html)
* line 19-20
* 使用 while 迴圈，透過不斷操作 `indirect` 來將 pointer `head` 移動至 linked list 尾端，
* 當也就是 `NULL`
* line 21
* 此時 `indirect` 指向末端節點的 `next` 指標的地址，所以直接使用 `*indirect` 來更新 `next`，使他指向我們新做出來的 node
----
:::success
TODO:
* 舉例並繪圖解釋 indirect 跑道尾端的情況
* 不使用 pointer to pointer 改寫 `add_entry()`，分析優缺點
* 需要判斷 是否為 empty list，因為 empty list 需要做特殊處理
* 如果是 empty list
* 就 assign `head` 到新的 node 上
* 如果不是 empty list
* 就修改末端 node 的 next 指標指向 `new_node`,
* 並更新
* `**head` 其實是不必要的，試著用 `**indirect_h` 當作 argument 改寫 `add_entry()`
:::
## find_entry
```cpp=23
node_t *find_entry(node_t *head, int value)
{
node_t *current = head;
for (; current && current->value != value; current = current->next)
/* iterate */;
return current;
}
```
### 分析
* line 25:
* 宣告我們要用來走訪 linked list 的指標 `current` 並把 head 的位置 assign 給他
* line 26-27
* 依序走訪個節點，並比較節點內的 value 跟我們要找的 value 是否相同
* 之後會回傳我們找到的那個節點
## remove_entry
```cpp=31
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
```
### 分析
* line 33: assign `head` 指向的位置給 `indirect`
* 在這之後 `node_t **head` 就沒用了
* line 35-36:
* 走訪 linked list，逐一比對indirect 現在指向的地址是否就是我們要刪除的節點地址
* 如果不是的話就把 `indirect` 指向下個節點的 next 指標 (indirect 只會在各個指標之間跳躍)
* line 38:
* 當找到 entry 後，就把當下這個 pointer 指向 entry 的下一個 node, 由於 entry 指向我們要刪除的節點，所以不用擔心 memory leak
* line 39: 直接釋放 entry 指向的記憶體，也就是刪除節點
## swap_pair
```cpp=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; // BB2
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
### 分析
```shell
// at line 44: 假設我們要 swap position 0 1
====== 正在處理的 pair =======
| pos 0 pos 1 | pos 2
| |
node | tmp |
| | | |
v | v |
head ------ |-> [4 |next]--> [5 |next]-|->[1 |next]--> NULL
| |
| |
// 第二輪: 已經 swap 4 5 了
// at line 44: 假設我們要 swap position 1 2
====== 正在處理的 pair =======
pos 0 | pos 1 pos 2 | pos 3
node | |
| | tmp |
| | | |
v | v |
[5 |next]--- |-> [4 |next]--> [1 |next]-|->[3 |next]--> NULL
| |
| |
```
:::success
TODO:
1. 修正敘述方法，使之更為清晰
2. 驗證自己的說法是否有誤
3. 嘗試使用 graphviz 來繪製圖形
:::
:::info
我的理解：
從要更新的 pattern 來理解 pointer to pointer 的用法，不要被指標的名字給困惑，
e.g. `head` 指標與 `head->next` 指標 本質上都使指向 `node_t` 結構體 的指標
:::
以第二輪 舉例:
* line 44:
* 判斷 `(*node)` 和 `(*node)->next` 是否都存在
* 不存在就代表已經走到末端，不需要再交換了
* line 45:
* assign `tmp` 指標指向我們正在處理的 `pair` 中前面的那個 node (pos 1)
* line 46:
* 修改 head 指標指向我們正在處理的 pair 中後面的那個 node (pos 2)
* line 47: `tmp->next = (*node)->next;`
* 修改 tmp 指向的那個 node 的 next 指標，使他指向我們正在處理的 pair 的之外，位於 pos 3 的那個 node
* line 48: `(*node)->next = tmp;`
* 修改我們正在處理的 pair 中，後面的那個node 的 next 指標，使他指向我們正在處理的 pair 中，前面的那個 node
* line 44:
* 更新 node 指標，指向下一個 pair 前面 的 next 指標
## reverse
```cpp=53
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;
}
```
### 分析
```shell
# after line 57
head next
| |
x 5 -> 4 -> 1 -> 3 -> x
|
cursor
# after line 58:
head next
| |
x <- 5 -> 4 -> 1 -> 3 -> x
|
cursor
# after line 59:
next == head
|
x <- 5 4 -> 1 -> 3 -> x
|
cursor
```
* cursor 的意思
* 指向我們已經 reverse 過的 linked list 的開頭
* head 的意義
* 指向尚未 reverse 的 linked list 的開頭
* line 55
* 一開始先讓 cursor 指向 null (因為尚未開始修改 next 指標所以 cursor 沒有指向任何 linked list)
* line 56
* head 永遠指向尚未 reverse 的 linked list 的開頭，
* 當 head 還存在時就進入迴圈
* line 57 `node_t *next = head->next`
* 讓 next 來指向 `head->next`, 避免下一步更動 `head->next` 時失去 `head` 之後的節點，發生 memory leak
* line 58
* head->next = cursor; cursor = head;
* 把 head->next 修正為 cursor 的位置，達成 reverse 的目的
* 並讓 cursor 指向我們已經 reverse 過的 linked list 的開頭, 也就是 `head` 指向的位置
* line 59
* head = next;
* 把 head 重新指向尚未 reverse 的 linked list 的開頭，也就是 next 指向的位置
* line 61
* 到這裡代表 `head == NULL`
* 也就是說我們沒有尚未 reverse 的 linked list 了，
* 所以 return `cursor`
* 也就是我們已經 reverse 過的 linked list 的開頭
## print_list
```cpp=64
void print_list(node_t *head)
{
for (node_t *current = head; current; current = current->next)
printf("%d ", current->value);
printf("\n");
}
```
### 分析
## main
```cpp=71
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;
}
```
### 分析
## 完整程式碼
```cpp=1
#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;
}
```
## 改寫 `swap_pair` 與 `reverse()`
### swap_pair()
* 思路
* 把原本傳送 head 指摽進去 function，現在直接把 head 指標本身的地址傳進去，用 pointer to pointer 接收，這樣就不需要回傳值了
* 優點
* 保持函數使用上的一致性，不用特別考慮哪個 function 有回傳值
* `print_list(head);`
* `remove_entry(&head, entry);`
* `reverse(&head);`
* `swap_pair(&head);`
* 可參考 Functional Programming 的設計理念
原本
`node_t *swap_pair(node_t *head)`
現在
`void swap_pair(node_t **indirect_head)`
```diff
-node_t *swap_pair(node_t *head)
+void swap_pair(node_t **indirect_head)
{
- for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next) {
+ for (node_t **node = indirect_head; *node && (*node)->next;
+ node = &(*node)->next->next) {
node_t *tmp = *node;
*node = (*node)->next;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
- return head;
+ return;
}
```
### reverse()
```diff
-node_t *reverse(node_t *head)
+void reverse(node_t **indirect_head)
{
node_t *cursor = NULL;
- while (head) {
- node_t *next = head->next;
- head->next = cursor; cursor = head;
- head = next;
+ while (*indirect_head) {
+ node_t *next = (*indirect_head)->next;
+ (*indirect_head)->next = cursor;
+ cursor = (*indirect_head);
+ (*indirect_head) = next;
}
- return cursor;
+
+ *indirect_head = cursor;
+
+ return;
}
```
----
Reference
[2020q3 第 1 週測驗題](/@sysprog/sysprog2020-quiz1)
# sandbox
graphviz syntax
```graphviz
digraph structs {
node[shape=record]
struct0 [label= "<start>start"]
struct1 [label="<prev> prev|<data> data|<next> next"];
struct0:start -> struct1:data[arrowhead=vee, tailclip=true, arrowsize=1];
struct1:prev -> struct1[arrowhead=vee, tailclip=true, arrowsize=1];
struct1:next -> struct1[arrowhead=vee, tailclip=true, arrowsize=1];
}
```
# 錯誤回報
示範:
:::danger
Error:
at [`add_entry()`](https://hackmd.io/tBv4csGaQhqFeY4c2P6fYw?both#add_entry
)
沒有使用 graphviz 來繪圖！！！
:::
Sign in with Wallet
Connect another wallet