---
# System prepended metadata

title: 2020q3 Homework1 (quiz1)

---

# 2020q3 Homework1 (quiz1)
contributed by < `Holychung` >

[2020q3 第 1 週測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)

## Outline
[TOC]

## 題目
考慮一個單向 linked list，其結構定義為:

```c
typedef struct __node {
    int value;
    struct __node *next;
} node_t;
```

已知不存在 circular (環狀結構)，接下來將對該單向 linked list 進行下列操作:
- add_entry
- remove_entry
- swap_pair
- reverse

## 程式運作原理
### 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);
    while (*indirect)
        indirect = &(*indirect)->next;
    *indirect = new_node;
}
```
head 是指標的指標，指向 linked list 起點的指標位置。
首先建立了一個指標的指標 indirect，指向 head 所指向的位置。
```graphviz
digraph G {
    rankdir=LR
    node [shape="block"]
    node0 [label="node 0"]
    node1 [label="node 1"]
    null0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    ptr [shape=none, label="ptr"]
    
    head->ptr
    ptr->node0
    node0->node1
    node1->null0
    
    {rank=same;node0 ptr head}
}
```
接著 malloc 新增一個節點 new_node 的記憶體空間，這個節點 next 指向 NULL。

```graphviz
digraph G {
    rankdir=LR
    node [shape="block"]
    node0 [label="node 0"]
    node1 [label="node 1"]
    null0 [shape=none, label="NULL"]
    null1 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    ptr [shape=none, label="ptr"]
    
    new_node->null1
    head->ptr
    ptr->node0
    node0->node1
    node1->null0
    
    {rank=same;node0 ptr head}
}
```

經過 while 迴圈走訪 linked list，indirect 會指向最尾端 NULL，此時將最尾端指向 new_node，完成新增節點。

```graphviz
digraph G {
    rankdir=LR
    node [shape="block"]
    node0 [label="node 0"]
    node1 [label="node 1"]
    new_node [label="new_node"]
    null0 [shape=none, label="NULL"]
    
    node0->node1
    node1->new_node
    new_node->null0
    
    {rank=same;null0 }
}
```


### 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);
}
```
### swap_pair
交換一對相鄰的節點，取自 [LeetCode: Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)，給定 `1->2->3->4`，則該回傳 `2->1->4->3`

透過指標的指標 node 指向 linked list 開頭的位址，每一次交換相鄰的兩個節點，完成之後 node 指向下下一個節點的位置，直到 最尾端或是只剩一個節點的時候停止，並且把參數 head 指標傳回去更新新的起點位置。
```c=
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;
}
```

一開始用指標的指標 node 指向起始的位址。
```graphviz
digraph G {
    rankdir=LR
    node [shape="block"]
    null0 [shape=none, label="NULL"]
    node0 [label="node", shape=none]
    head [shape=none, label="head"]
    
    node0->head->node1
    node1->node2->null0
    
    {rank=same;node0 head node1}
}
```
然後用指標 tmp 指向 \*node 的位址。
```graphviz
digraph G {
    rankdir=TB
    node [shape="block"]
    null0 [shape=none, label="NULL"]
    node0 [label="node", shape=none]
    head [shape=none, label="head"]
    tmp [shape=none]
    
    tmp->node1
    node0->head->node1
    node1->node2->null0
    
    {rank=same;node2 null0 node1}
}
```
\*node 移動指向下一個節點。
```graphviz
digraph G {
    rankdir=TB
    node [shape="block"]
    null0 [shape=none, label="NULL"]
    node0 [label="node", shape=none]
    head [shape=none, label="head"]
    tmp [shape=none]
    
    tmp->node1
    node0->head->node2
    node1->node2->null0
    
    {rank=same;node2 null0 node1}
}
```
把第一個節點的 next 指向第二個節點 next，也就是把 tmp 指向的節點的 next 改成 node 節點指向的 next。
```graphviz
digraph G {
    rankdir=TB
    node [shape="block"]
    null0 [shape=none, label="NULL"]
    node0 [label="node", shape=none]
    head [shape=none, label="head"]
    tmp [shape=none]
    
    tmp->node1
    node0->head->node2
    node1:s->null0
    node2->null0
    
    {rank=same;node2 null0 node1}
}
```
再把第二個節點的 next 指向第一個節點，也就是把 node 指向的節點的 next 改成 tmp 指向的位址，完成一對節點的交換。
```graphviz
digraph G {
    rankdir=TB
    node [shape="block"]
    null0 [shape=none, label="NULL"]
    node0 [label="node", shape=none]
    head [shape=none, label="head"]
    tmp [shape=none]
    
    tmp->node1
    node0->head->node2
    node1->null0
    node2->node1
    
    {rank=same;node2 null0 node1}
}
```
原本 node 是指向 head 這個指標，在做完一次 swap 後，head 會更新指到新的起點位置，因此要再把這個指標回傳回去更新開頭位置。
然後 node 就繼續指向下下一個節點，直接把 node 指向下一個節點的指標 next，一直做到最後結束。
```graphviz
digraph G {
    rankdir=TB
    node [shape="block"]
    null0 [shape=none, label="NULL"]
    node0 [label="node", shape=none]
    head [shape=none, label="head"]
    tmp [shape=none]
    
    tmp->node1
    node0->head->null0
    node1->null0
    node2->node1
    
    {rank=same;node2 null0 node1}
}
```

### reverse
將給定的 linked list 其內節點予以反向，即 `1->2->3->4`，則該回傳 `4->3->2->1`

用指標 cursor 紀錄下上一個節點的位置，初始值為 null，用一開始傳進來的起點位置 head 開始對 linked list 每一個節點做反轉，每一次 loop 都把當前的節點 next 指向前一個節點位址，直到最後，再回傳最後一個節點位址，也就是反轉後的開頭位址。
```c=
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;
}
```
先用指標 next 紀錄下一個節點的位置，也就是當前 head->next 指向的位置。
```graphviz
digraph G {
    rankdir=TB
    node [shape="block"]
    cursor [shape=none, label="cursor"]
    null0 [shape=none, label="NULL"]
    null1 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    next [shape=none, label="next"]

    cursor->node1
    head->node2
    next->node3
    node2->node3->null0
    node1->null1
    
    {rank=same;node2 null0 node1 node3 null1}
}
```
然後 head 指向的節點的 next 就可以指向上一個節點，達到反轉。
```graphviz
digraph G {
    rankdir=TB
    node [shape="block"]
    node1
    node2
    cursor [shape=none, label="cursor"]
    null0 [shape=none, label="NULL"]
    null1 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    next [shape=none, label="next"]
    
    cursor->node1
    head->node2
    next->node3
    node3->null0
    node1->null1
    node2:e->node1:w [label=" "]
    null1->node2 [style="invis"]
 
    {rank=same;node2 null0 node1 node3 null1}
}
```
上一個節點 cursor 就可以更新程現在這個節點 head，再把 head 指向剛剛 next 保存下來的下一個節點位置，完成一個節點的反轉。
```graphviz
digraph G {
    rankdir=TB
    node [shape="block"]
    node1
    node2
    cursor [shape=none, label="cursor"]
    null0 [shape=none, label="NULL"]
    null1 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    next [shape=none, label="next"]
    
    cursor->node2
    head->node3
    next->null0
    node3->null0
    node1->null1
    node2->node1
 
    {rank=same;node2 null0 node1 node3 null1}
}
```


## 延伸問題
用指標的指標來改寫 `swap_pair` `reverse`，避免回傳指標。
並且以遞迴改寫上述的 `reverse`。

### swap_pair
原本的寫法是傳入指標，所以在函式結束的時候並不會更新到原本的指標 head，所以需要回傳開頭的位置。修改成指標的指標進行操作，就會更新到原本的 head，就不用回傳指標。
```c=
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;
    }
}
```

### reverse
修改成指標的指標進行操作，就不用回傳指標，只是要注意最後要把 head 指向前一個的 cursor，才是開頭的位置。
```c=
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
把 reverse 整個 linked list 的工作拆成一次只 reverse 當前的節點，然後把剩下的 linked list 丟下去遞迴。
所以遞迴函式`rev_recurive` 需要吃兩個參數，第一個 head 是指向剩下的 linked list 起點位置，第二個 cursor 則是指向上一個節點的位置。然後每次遞迴都更新並傳遞這兩個參數，直到最後指向尾端 NULL，再把 head 指向 cursor 才是開頭的位置。

```c=
void rev_recurive(node_t **head, node_t *cursor)
{
    if (*head == NULL) {
        *head = cursor;
        return;
    }

    node_t *next = (*head)->next;
    (*head)->next = cursor; cursor = *head;
    *head = next;
    rev_recurive(head, cursor);
}

void reverse(node_t **head)
{
    rev_recurive(head, NULL);
}
```
並且有實現老師[上課講解](https://hackmd.io/@sysprog/c-recursion?type=view#Tail-recursion)的[尾端遞迴 (Tail Recursion)](https://en.wikipedia.org/wiki/Tail_call)。

:::info
Tail recursion 是遞迴的一種特殊形式，副程式只有在最後一個動作才呼叫自己。以演算法的角度來說，recursion tree 全部是一脈單傳，所以間複雜度是線性個該副程式的時間。不過遞迴是需要系統使用 stack 來儲存某些資料，於是還是會有 stack overflow 的問題。但是從編譯器的角度來說，因為最後一個動作才呼叫遞迴，所以很多 stack 資料是沒用的，所以他是可以被優化的。基本上，優化以後就不會有時間與空間效率的問題。
:::

### Fisher–Yates shuffle
針對 singly-linked list 的節點，實作 Fisher–Yates shuffle，你應該儘量降低記憶體的使用量。

參考 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 的方法和 [dalaoqi ](https://hackmd.io/C8fRRRctRdGKqr4ezOzDoA?view) 的做法，先計算出 singly-linked list 的長度，然後開始進入迴圈實作。每次挑選一個隨機的節點 `target`，然後把 target 前後的節點接起來，再把 `target` 接到新的 list 開頭的位置，直到迴圈結束。最後再把新的 list 的開頭位址 `new_head` 更新到原本開頭的 head。 
```c=
void shuffle(node_t **head)
{
    if (*head == NULL)
        return;

    srand(time(NULL));
    int len = 0;
    node_t **indirect = head;
    
    while (*indirect) {
        len++;
        indirect = &(*indirect)->next;
    }
    
    node_t *new_head = NULL;
    for (int i = len; i > 0; i--) {
        int random = rand() % i;
        indirect = head;
        while (random--)
            indirect = &(*indirect)->next;
        node_t *target = *indirect;
        *indirect = (*indirect)->next;
        target->next = NULL;
        if (new_head) {
            target->next = new_head;
            new_head = target;
        } else {
            new_head = target;
        }
    }
    *head = new_head;
}
```
首先，indirect 先指向開頭 head，並且透過迴圈計算出 list 長度。
```graphviz
digraph G {
    rankdir=TB
    node [shape="block"]
    node1
    node2
    indirect [shape=none, label="indirect"]
    null0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    ptr [shape=none, label="ptr"]
    
    indirect->ptr
    head->ptr->node1
    node3->null0
    node1->node2->node3
 
    {rank=same;node2 null0 node1 node3}
}
```
接下來進入 for 迴圈，每一次都隨機選取出一個節點，並且用 indirect 去找到該節點，並且用一個指標 target 指向該節點。
```graphviz
digraph G {
    rankdir=TB
    node [shape="block"]
    node1
    node2
    indirect [shape=none, label="*indirect"]
    target [shape=none, label="target"]
    null0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    ptr [shape=none, label="ptr"]
    two [shape=none, label="隨機 2"]
    
    target->node2
    indirect->node2
    head->ptr->node1
    node3->null0
    node1->node2->node3
 
    {rank=same;node2 null0 node1 node3}
}
```
透過 indirect 把 target 前一個節點接到後一個節點上。
```graphviz
digraph G {
    rankdir=TB
    node [shape="block"]
    node1
    node2
    indirect [shape=none, label="*indirect"]
    target [shape=none, label="target"]
    null0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    ptr [shape=none, label="ptr"]
    
    target->node2
    indirect->node2
    head->ptr->node1
    node3->null0
    node1->node2 [style="invis"]
    node2->node3 [style="invis"]
    node1:s->node3:s
 
    {rank=same;node2 null0 node1 node3}
}
```
然後把 target 接到新的 list 的開頭。
```graphviz
digraph G {
    rankdir=TB
    node [shape="block"]
    node1
    node2
    target [shape=none, label="target"]
    null0 [shape=none, label="NULL"]
    null1 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    ptr [shape=none, label="ptr"]
    new_head [shape=none, label="new_head"]
    
    new_head->node2
    target->node2
    head->ptr->node1
    node3->null0
    node1->node3
    node2->null1
 
    {rank=same;node2 null0 node1 node3 null1}
}
```
直到迴圈結束，把指標的指標 head 指向新的開頭 new_head 就結束了。
```graphviz
digraph G {
    rankdir=TB
    node [shape="block"]
    node1
    node2
    null0 [shape=none, label="NULL"]
    head [shape=none, label="head"]
    new_head [shape=none, label="new_head"]
    
    head->new_head
    new_head->node3
    node2->null0
    node3->node1->node2
 
    {rank=same;node2 null0 node1 node3}
}
```
## 延伸閱讀

- [graphviz tutorial](https://www.tonyballantyne.com/graphs.html?fbclid=IwAR3h9wdAUSMxyU8YK_Gl2CEgcHUyCTpfknO-4XpTcLuI3jMY7_ulyVC2MQo)
- [graphviz documentation](http://www.graphviz.org/documentation/)
- [你所不知道的C語言：遞迴呼叫篇](https://hackmd.io/@sysprog/c-recursion?type=view#Tail-recursion)
- [尾端遞迴 (Tail Recursion)](https://en.wikipedia.org/wiki/Tail_call)
- [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
