---
# System prepended metadata

title: 2020q3 Homework1 (quiz1)
tags: [進階電腦系統理論與實作]

---

# 2020q3 Homework1 (quiz1)
contributed by < `joey3639570` >
###### tags: `進階電腦系統理論與實作`
- [**Linked List** 測驗題連結](https://hackmd.io/@sysprog/sysprog2020-quiz1)
- [作業區](https://hackmd.io/@sysprog/sysprog2020-quiz1)

### Linked List 之定義
```cpp
typedef struct __node {                   
    int value;
    struct __node *next;
} node_t;
```

### 測驗題目需注意之重點
- Linked List 為**單向**
- 已知不存在 **circular (環狀結構)**

:::warning
**注意** :zap:
參考到 `RinHizakura` 的作業，提出一個很重要的觀點:
>**main(caller) 裡的 head pointer 的角度跟做為參數的 pointer to pointer 的 head 是完全不同的**
>
`node_t *head = NULL;` 此為 main(Caller)內的
`void add_entry(node_t **head, int new_value)` 參數的
:::


於20200913參考到，讓困惑已久的自己終於解惑了

### Graphviz範例參考
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> 12 | <ref>  }", width=1.2]
        b [label="{ <data> 99 | <ref>  }"];
        c [label="{ <data> 37 | <ref>  }"];
        d [shape=box];
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d      [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

### 針對運算子的複習
由於發現自己在上次測驗中，對於運算子，尤其是`&`和`*`及`->`的位階，相當不理解，故決定實驗看看讓自己理解，希望能搭配 Graphviz 讓自己理解。<br>
[Pointer to Pointer ~~Double Pointer~~ 參考資料](https://www.geeksforgeeks.org/double-pointer-pointer-pointer-c/)
假設今天有一段程式碼如下:
```cpp=
node_t *new_node = malloc(sizeof(node_t));
node_t *new_node_2 = malloc(sizeof(node_t));
node_t *head = &new_node;
node_t **indirect = head;
new_node->value = 1;
new_node->next = &new_node_2;
new_node_2->value = 2;
new_node_2->next = NULL;
```
呈現如下:
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        i [label="indirect|<ref> "];
        a [label="head | <ref> "];
        b [label="new_node |{ <data> 1 | <ref>  }"];
        c [label="new_node_2 |{ <data> 2 | <ref>  }"];
        d [label="Null"];
        i:ref:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d      [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
與宅色夫老師畫的圖相比：
```mermaid
graph LR
    subgraph linked list
        head==>node1==>node2
    end
    subgraph pointer to pointer
        indirect==>head
    end
```
釐清並且整理觀念如下:
- `*new_node`得到的是一個`node_t`的 struct
- `*head`得到的是一個`node_t`的struct
- `(*new_node)->value`不等於`*new_node->value`，因為`->`的位階大於`*`
- `head = &new_node` 等於 `*indirect = new_node`(請務必記得最上面的**注意**)

### 針對原始測驗題的思考及理解
- `add_entry`
>新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy
#### 原始碼
```cpp=
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`的流程如下：
1. **第3行** 建立指向 node 指標(`head`)的指標`indirect`
2. **第5行** 使用`malloc`分配記憶體空間給`new_node`
3. **第6~7行** 初始化`new_node`
4. **(AA1)** 確定`new_node`是合法的
5. **第10~11行** 當取值 indirect 不是 NULL 時，indirect設為指向下一個值的位址的指標(`&(*indirect)->next`) 
6. **(AA2)** 將此指標的值設為`new_node`
:::warning
**注意** :zap:
- 此部分的Code使用於加 entry 於 linked list 的最後端(由**步驟五**可以得知)
- -> 的位階大於 & ，所以要先進行->運算再運算&
:::
如果**AA1**填入`*indirect = new_node`，會變成接在head指到的node的後方。

---
- `remove_entry`
>移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)
```cpp=
void remove_entry(node_t **head, node_t *entry)
{
    node_t **indirect = head;

    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    *indirect = entry->next;
    free(entry);
}
```
`remove_entry`的流程如下：
1. **第3行** 建立指向 node 指標(`head`)的指標`indirect`
2. **第5~6行** 此部分是要將`indirect`指向 entry ，方法是利用`while`從`head`開始找到指定的 entry ，若不是entry，則走 next 往下一個。
3. **第8行** 將 Linked List 銜接回去
4. **第9行** 用`free`釋放 entry 占用的記憶體

---
- `swap_pair`
>交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 1->2->3->4，則該回傳 2->1->4->3
#### 原始程式碼
```cpp=
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;
}
```
:::warning
:zap:**務必注意傳入函式內的是`node_t *head`**
:::
`swap_pair`的流程如下：
1. **第3行** `for`迴圈分別講解:
    - `node_t **node = &head` 從`head`開始，此為建立指向 node 指標(`head`)的指標
    - `*node && (*node)->next` 若無法形成兩兩一組，則結束for迴圈
    - **BB1** 因為是要兩個為一組進行操作，所以每個迴圈結束要跳兩個，根據運算子優先次序選擇`node = &(*node)->next->next`
2. **第4行** 複製`node`為暫存`tmp`
3. **第5~7行** 此為執行 swap 的部分，參見底下Graphviz呈現:
    - **BB2** `node = &(*node)->next`
    - `tmp->next = (*node)->next` 
    - `(*node)->next = tmp`
5. **第9行** 回傳`head`
#### Graphviz呈現
(取一部分當範例)
**第4行**前的狀況:
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        n [label="node | <ref> "];
        node_1 [label="<ptr> head|{ <data> 1 | <ref>  } "];
        node_2 [label="{ <data> 2 | <ref>  } "];
        node_3 [label="{ <data> 3 | <ref>  } "];

        n:ref:c -> node_1:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_2:ref:c -> node_3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```
**第4行`node_t *tmp = *node;`後**的狀況:
*node 可以取得head
head->next跟node_1->next是一樣的
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        n [label="node | <ref> "];
        node_1 [label="<ptr> head|{ <data> 1 | <ref>  } "];
        node_2 [label="{ <data> 2 | <ref>  } "];
        node_3 [label="{ <data> 3 | <ref>  } "];
        tmp [label="<ptr> tmp | { <data> 1 | <ref>  } "];
        node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        n:ref:c -> node_1:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        tmp:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_2:ref:c -> node_3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```
`node = &(*node)->next`
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        node_1 [label="<ptr> head|{ <data> 1 | <ref>  } "];
        node_2 [label="node|{ <data> 2 | <ref>  } "];
        node_3 [label="{ <data> 3 | <ref>  } "];
        tmp [label="tmp | { <data> 1 | <ref>  } "];
        node_1:ref:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        tmp:ref:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_2:ref:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```
`tmp->next = (*node)->next`
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        node_1 [label="<ptr> head|{ <data> 1 | <ref>  } "];
        node_2 [label="<ptr> node|{ <data> 2 | <ref>  } "];
        node_3 [label="{ <data> 3 | <ref>  } "];
        tmp [label="tmp | { <data> 1 | <ref>  } "];
        node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];

        tmp:ref:c -> node_3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_2:ref:c -> node_3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```
`(*node)->next = tmp`
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        node_1 [label="<ptr>head|{ <data> 1(可忽略) | <ref>  } "];
        node_2 [label="<ptr> node|{ <data> 2 | <ref>  } "];
        node_3 [label="{ <data> 3 | <ref>  } "];
        tmp [label="tmp | { <data> 1 | <ref>  } "];
        node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        tmp:ref:c -> node_3 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_2:ref:c -> tmp [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```
---

- `reverse`: 
>將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1
#### 原始程式碼
```cpp=
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;
}
```
:::warning
:zap:**務必注意傳入函式內的是`node_t *head`**
:::
`reverse`的流程如下：
1. **第3行** 建立一指向`node_t`物件的指標`cursor`，先指向NULL
2. **第4~8行** 當 head 還有指向東西時，執行以下:
    - 建立一指向`node_t`物件的指標`next`，指向 head 的 next
    - **CCC** `head->next = cursor; cursor = head`這其實是兩行
        - 將 head 的 next 設為 cursor 
        - 再把 cursor 變 head
        - head 再接下去下一個物件

#### Graphviz呈現
`node_t *cursor = NULL;`
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        
        node_1 [label="head |{ <data> 1 | <ref>  } "];
        node_2 [label="{ <data> 2 | <ref>  } "];
        cursor [label="cursor |  "];

        node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`node_t *next = head->next;`
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        node_1 [label="head |{ <data> 1 | <ref>  } "];
        node_2 [label="{ <data> 2 | <ref>  } "];
        next [label="next |{<data> 2 |<ref> }"]
        cursor [label="cursor |<data>  "];
        node_1:ref:c -> node_2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`head->next = cursor`
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        node_1 [label="head |{ <data> 1 | <ref>  } "];
        node_2 [label="{ <data> 2 | <ref>  } "];
        next [label="next |{<data> 2 |<ref> }"]
        cursor [label="cursor | <ref> "];
        node_1:ref:c -> cursor:ref [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```
`cursor = head`
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        node_1 [label="head(cursor) |{ <data> 1 | <ref>  } "];
        node_2 [label="{ <data> 2 | <ref>  } "];
        next [label="next |{<data> 2 |<ref> }"]
        cursor [label=" <ref> "];
        node_1:ref:c -> cursor:ref [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
`head = next`
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        node_1 [label="head|{ <data> 1 | <ref>  } "];
        node_2 [label="{ <data> 2 | <ref>  } "];
        next [label="next(head) |{<data> 2 |<ref> }"]
        cursor [label=" <ref> "];
        node_1:ref:c -> cursor:ref [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
## 延伸問題
- 函式 `swap_pair` 和 `reverse` 對於指標的操作方式顯然異於 `add_entry` 及 `remove_entry`，需要額外做 `head = ...` 的更新，請用**指標的指標**來改寫，並避免回傳指標;

```cpp=
void 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;
    }
}
```
:::warning
參考 `sammer1107` 
:zap: 括號 head 代表在 main 中的 head。
:::
進入`for`迴圈:
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        n [label="node"];
        head [label="head"];
        head_main [label="(head)"];
        node_1 [label="{node_1|<next>}"];
        node_2 [label="{node_2|<next>}"];
        node_3 [label="{node_3|<next>}"];
        head -> head_main [arrowhead=vee, arrowtail=tail];
        n -> head_main [arrowhead=vee, arrowtail=tail];
        head_main -> node_1;
        node_1:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_2:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```
`node_t *tmp = *node;`
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        n [label="node"];
        head [label="head"];
        head_main [label="(head)"];
        tmp [label="tmp"];
        node_1 [label="{node_1|<next>}"];
        node_2 [label="{node_2|<next>}"];
        node_3 [label="{node_3|<next>}"];
        head -> head_main [arrowhead=vee, arrowtail=tail];
        n -> head_main [arrowhead=vee, arrowtail=tail];
        head_main -> node_1;
        tmp -> node_1;
        node_1:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_2:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```
`*node = (*node)->next;`
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        n [label="node"];
        head [label="head"];
        head_main [label="(head)"];
        tmp [label="tmp"];
        node_1 [label="{node_1|<next>}"];
        node_2 [label="{node_2|<next>}"];
        node_3 [label="{node_3|<next>}"];
        head -> head_main [arrowhead=vee, arrowtail=tail];
        n -> head_main [arrowhead=vee, arrowtail=tail];
        head_main -> node_2;
        tmp -> node_1;
        node_1:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_2:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```
`tmp->next = (*node)->next;`
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        n [label="node"];
        head [label="head"];
        head_main [label="(head)"];
        tmp [label="tmp"];
        node_1 [label="{node_1|<next>}"];
        node_2 [label="{node_2|<next>}"];
        node_3 [label="{node_3|<next>}"];
        head -> head_main [arrowhead=vee, arrowtail=tail];
        n -> head_main [arrowhead=vee, arrowtail=tail];
        head_main -> node_2;
        tmp -> node_1;
        node_1:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_2:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```
`(*node)->next = tmp`
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        n [label="node"];
        head [label="head"];
        head_main [label="(head)"];
        tmp [label="tmp"];
        node_1 [label="{node_1|<next>}"];
        node_2 [label="{node_2|<next>}"];
        node_3 [label="{node_3|<next>}"];
        head -> head_main [arrowhead=vee, arrowtail=tail];
        n -> head_main [arrowhead=vee, arrowtail=tail];
        head_main -> node_2;
        tmp -> node_1;
        node_1:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_2:next:c -> node_1[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```
---
```cpp=
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;
}
```
---
- 以遞迴改寫上述的 `reverse`，注意，你可能因此需要建立新的函式，如 `rev_recursive`，隨後在 `reverse` 函式中呼叫 `rev_recursive`;
```cpp=
node_t *rev_reverse(node_t *head)
{
    # If there isn't any node left or not even node, return head.
    if(!head || !head->next){
        return head;
    }
    node_t *rev_head = reverse_recursive(head->next);
    head->next->next = head;
    head->next = NULL;
    return rev_head;
}
```
藉著 rev_recursive 函式`node_t *rev_head = reverse_recursive(head->next);`把 linked list 拆成第一個節點以及後面整個節點 List <br>
原圖:
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [label="head"];
        node_1 [label="{node_1|<next>}"];
        node_2 [label="{node_2|<next>}"];
        node_3 [label="{node_3|<next>}"];
        head -> node_1;
        node_1:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_2:next:c -> node_3[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_3:next:c -> null[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```
經前面 recursive 的部分後:
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [label="head"];
        node_1 [label="{node_1|<next>}"];
        node_2 [label="{node_2|<next>}"];
        node_3 [label="{node_3|<next>}"];
        head -> node_1;
        node_1:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_2:next:c -> null[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_3:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        rev_head -> node_3
        }
```
`head->next->next = head;`
`head->next = NULL;`
`head->next->next`便是`node_2->next`，將其設為`head`，然後再將最後的`next`指向NULL如底下:
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [label="head"];
        node_1 [label="{node_1|<next>}"];
        node_2 [label="{node_2|<next>}"];
        node_3 [label="{node_3|<next>}"];
        head -> node_1;
        node_1:next:c -> null[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_2:next:c -> node_1[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_3:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        rev_head -> node_3
        }
```
利用上面完成了 reverse，最後用`void reverse`配合**pointer to pointer**修飾，程式碼如下:
```cpp=
void reverse(node_t **head)
{
    *head = rev_recursive(*head);
}
```
```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [label="(head)"];
        head_ptr [label="head"];
        node_1 [label="{node_1|<next>}"];
        node_2 [label="{node_2|<next>}"];
        node_3 [label="{node_3|<next>}"];
        head -> node_1;
        head_ptr -> rev_head
        node_1:next:c -> null[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_2:next:c -> node_1[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        node_3:next:c -> node_2[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        rev_head -> node_3
        }
```
可藉此發現原始的 main 中的`head`並不會動到！

---
- 針對 `singly-linked list` 的節點，實作 **Fisher–Yates shuffle**，你應該儘量降低記憶體的使用量;
[Wikipedia: Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher–Yates_shuffle)
演算法如下：
```
To shuffle an array a of n elements (indices 0..n-1):
  for i from n - 1 downto 1 do
       j = random integer with 0 <= j <= i
       exchange a[j] and a[i]
```
```cpp=
void randomize ( node_t **head ){ 
    // Use a different seed value so that we don't get same 
    // result each time we run this program 
    srand ( time(NULL) ); 
    node_t *old_head, *cursor, **indirect;
    int range = 0;
    old_head = cursor = *head;
    // get list length
    while(cursor){
        range += 1;
        cursor = cursor->next;
    }
    *head = NULL;
    for(;range > 0; --range){
        // Start from old head
        indirect = &old_head;
        // move to selected node
        for(int i = rand() % range;i > 0; --i)
            indirect = &(*indirect)->next;
        // move selected node to new list
        // Down below is the part for swapping
        node_t *tmp = *indirect;
        *indirect = (*indirect)->next;
        tmp->next = *head;
        *head = tmp;
    }
}
```

:::warning
最後在 main 中使用 `swap_pair` 及 `reverse` 時，只要是用到pointer to pointer 的，要傳入 `head` 的地址，也就是`&head`
e.g. `swap_pair(&head)`
:::