---
# System prepended metadata

title: 2020q3 Homework1 (quiz1)

---

# 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 來繪圖！！！
:::