---
# System prepended metadata

title: 2020q3 Homework1 (quiz1)
tags: [linux2020]

---

# 2020q3 Homework1 (quiz1)
contributed by < `tsengsam` >
[第一週測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)

---
## 測驗 `1`
  題目為一個沒有 circular 的 singly-linked list，其資料結構為 : 
```cpp
typedef struct __node {
    int value;
    struct __node *next;
} node_t;
```
以下將個別介紹函式：
* add_entry()
  + 原本硬頸地想嘗試用單指標當傳入參數並且不回傳，最後竟然用了一天釐清一些基本觀念。
    所以另外做了一個筆記避免再次犯錯 : [「為何一個指標實作 add_entry() 會出事」](https://hackmd.io/@shanvia/BJMFWP8EP)
```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;
    
    AA1;
    while(*indirect)
        indirect = &(*indirect)->next;
    AA2;
}
```
**Q1. AA1 = ?**
若動態配置記憶體需確認是否有成功配置記憶體位址，故此題選 (a) 選項 `assert(new_node)`。
**Q2. AA2 = ?**
為了找到 linked list 最尾端的 `NULL`，前面透過 while 迴圈持續將 `indirect` assign 為指向下個entry位址的指標直到 `(*indirect)` 指向 `NULL`，離開迴圈後應該是將 `indirect` 指向的指標更新為 `new_node`，故此題選 (b) 選項 `*indirect = new_node`。

---

* find_entry()
  這個函式若找不到該 entry 時會回傳 `NULL`，也就表示已經找到 list 的最後面了。
```cpp= 
node_t *find_entry(node_t *head, int value)
{
    node_t *current = head;
    for (; current && current->value != value; current = current->next)
        /*interate*/;
    return current
}
```

---

* remove_entry()
  使用者使用這個函式要小心，想要移除的 entry 需存在於 linked list 中，否則程式會崩潰。
```cpp=
void remove_entry(node_t **head, node_t *entry)
{
    node_t **indirect = head;
    while ((*indirect) != entry)
        indirect = &(*indirect)->next;
        
    *indirect = (*indirect)->next;
    free(entry);
}
```
    
---
    
* swap_pair()
```cpp=
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;
}
```
**Q3. BB1 = ?**
因為 swap_pair 的 for 迴圈每次對兩個 entries 做交換，所以 BB1 的部分應是讓 node 一次前進兩個單位，而又因為 node 為指向指標的指標，故要先對 `node` 取值後才能取得下下個 entry，然後再取址並 assign 給 node。
故這題應為選項 (e) `node = &(*node)->next->next`。
**Q4. BB2 = ?**
假設交換 `A` `B` 兩節點，表示 `A->next` 要改成指向 `B->next`，而 `B->next` 會改指向 `A`。
故 BB2 即是 `*node = (*node)->next` 故可選 c
#### 以下圖形化解釋 swap_pair 流程:
(1) 第一次迴圈 line 4:
```graphviz
digraph G                                                           
{ 
    rankdir=LR;
    {
        A [shape=record,label="{<data> A| <ref> next}"];
        B [shape=record,label="{<data> B| <ref> next}"];
        C [shape=record,label="{<data> C| <ref> next}"];
        D [shape=record,label="{<data> D| <ref> next}"];
        NULL [shape=plaintext]
        A->B->C->D->NULL;
    }    
    {
        n [label="node",shape=plaintext]
        head [shape=box]
        n->head->A
        tmp [shape=plaintext]
        tmp->A
    }
    
}
```
(2) line 5:
```graphviz
digraph G                                                           
{ 
    rankdir=LR;
    {
        node [shape=record]
        A [shape=record,label="{<data> A| <ref> next}"];
        B [shape=record,label="{<data> B| <ref> next}"];
        C [shape=record,label="{<data> C| <ref> next}"];
        D [shape=record,label="{<data> D| <ref> next}"];
        NULL [shape=plaintext]
        A->B->C->D->NULL;
    }    
    {
        node [shape=plaintext]
        n [label="node"]
        head [shape=box]
        tmp [label=tmp]
        tmp->A
        n->head
        head->B [color=red];
    }
}
```
(3) line 6:
```graphviz
digraph G                                                           
{ 
    rankdir=LR;
    {
        node [shape=record]
        A [shape=record,label="{<data> A| <ref> next}"];
        B [shape=record,label="{<data> B| <ref> next}"];
        C [shape=record,label="{<data> C| <ref> next}"];
        D [shape=record,label="{<data> D| <ref> next}"];
        NULL [shape=plaintext]
        A->C [color=red]
        B->C->D->NULL;
    }    
    {
        node [shape=plaintext]
        n [label="node"]
        head [shape=box]
        tmp [label=tmp]
        tmp->A
        n->head->B;
    }
}
```
(4) line 7:
```graphviz
digraph G                                                           
{ 
    rankdir=LR;
    {
        node [shape=record]
        A [shape=record,label="{<data> A| <ref> next}"];
        B [shape=record,label="{<data> B| <ref> next}"];
        C [shape=record,label="{<data> C| <ref> next}"];
        D [shape=record,label="{<data> D| <ref> next}"];
        NULL [shape=plaintext]
        A->C 
        B->A [color=red]
        C->D->NULL;
    }    
    {
        node [shape=plaintext]
        n [label="node"]
        head [shape=box]
        tmp [label=tmp]
        tmp->A
        n->head->B;
    }
}
```
(5) 第二次迴圈 line 3:
* node 改指向A next 指標的位址
```graphviz
digraph G                                                           
{ 
    rankdir=LR;
    {
        node [shape=record]
        A [shape=record,label="{<data> A| <ref> next}"];
        B [shape=record,label="{<data> B| <ref> next}"];
        C [shape=record,label="{<data> C| <ref> next}"];
        D [shape=record,label="{<data> D| <ref> next}"];
        NULL [shape=plaintext]
        A->C 
        B->A
        C->D->NULL;
    }    
    {
        node [shape=plaintext]
        n [label="node"]
        head [shape=box]
        tmp [label=tmp]
        tmp->A
        n->A:next [color=red]
        head->B;
    }
}
```
(6) line 4:
```graphviz
digraph G                                                           
{ 
    rankdir=LR;
    {
        node [shape=record]
        A [shape=record,label="{<data> A| <ref> next}"];
        B [shape=record,label="{<data> B| <ref> next}"];
        C [shape=record,label="{<data> C| <ref> next}"];
        D [shape=record,label="{<data> D| <ref> next}"];
        NULL [shape=plaintext]
        A->C 
        B->A
        C->D->NULL;
    }    
    {
        n [label="node"]
        node [shape=plaintext]
        head [shape=box]
        tmp [label=tmp]
        tmp->C [color=red]
        n->A:next
        head->B;
    }    
}
```
(7) line 5:
```graphviz
digraph G                                                           
{ 
    rankdir=LR;
    {
        node [shape=record]
        n [label="node"]
        n->A:next
        A [shape=record,label="{<data> A| <ref> next}"];
        B [shape=record,label="{<data> B| <ref> next}"];
        C [shape=record,label="{<data> C| <ref> next}"];
        D [shape=record,label="{<data> D| <ref> next}"];
        NULL [shape=plaintext]
        A->D [color=red]
        B->A
        C->D->NULL;
    }    
    {
        node [shape=plaintext]
        head [shape=box]
        tmp [label=tmp]
        tmp->C
        head->B;
    }    
}
```
(8) line 6:
```graphviz
digraph G                                                           
{ 
    rankdir=LR;
    {
        node [shape=record]
        n [label="node"]
        n->A:next
        A [shape=record,label="{<data> A| <ref> next}"];
        B [shape=record,label="{<data> B| <ref> next}"];
        C [shape=record,label="{<data> C| <ref> next}"];
        D [shape=record,label="{<data> D| <ref> next}"];
        NULL [shape=plaintext]
        B->A
        A->D 
        C->NULL [color=red]
        D->NULL;
    }    
    {
        node [shape=plaintext]
        head [shape=box]
        tmp [label=tmp]
        tmp->C
        head->B;
    }    
}
```
(9) line 7:
```graphviz
digraph G                                                           
{ 
    rankdir=LR;
    {
        node [shape=record]
        n [label="node"]
        n->A:next
        A [shape=record,label="{<data> A| <ref> next}"];
        B [shape=record,label="{<data> B| <ref> next}"];
        C [shape=record,label="{<data> C| <ref> next}"];
        D [shape=record,label="{<data> D| <ref> next}"];
        NULL [shape=plaintext]
        B->A
        A->D 
        C->NULL 
        D->C [color=red]
    }    
    {
        node [shape=plaintext]
        head [shape=box]
        tmp [label=tmp]
        tmp->C
        head->B;
    }    
}
```
(10) line 3:
* 此時便跳出迴圈，完成交換
```graphviz
digraph G                                                           
{ 
    rankdir=LR;
    {
        node [shape=record]
        A [shape=record,label="{<data> A| <ref> next}"];
        B [shape=record,label="{<data> B| <ref> next}"];
        C [shape=record,label="{<data> C| <ref> next}"];
        D [shape=record,label="{<data> D| <ref> next}"];
        NULL [shape=plaintext]
        B->A
        A->D 
        C->NULL 
        D->C 
    }    
    {
        node [shape=plaintext]
        head [shape=box]
        head->B;
    }    
}
```
#### ※ 延伸問題 改寫 `swap_pair` 函式回傳型態為 `void`
因為這個函式是和交換有關，一時和 value 的交換有錯誤的聯想，以為本來就不用回傳，故只修改型態及 `return` : 
```cpp=
void swap_pair(node_t *h)
{
    for (node_t **node = &h; *node && (*node)->next; node = &(*node)->next->next) {
        node_t *tmp = *node;
        *node = (*node)->next;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
}
```
這部份踩了一個雷，鑑於 [add_entry()](https://hackmd.io/@shanvia/BJMFWP8EP) 的錯誤讓我想到原因依舊是 `head` 指向的位址在第六行的 `*node` 會改變。
故還是得用指標的指標來進行改寫 : 
```cpp=
void swap_pair(node_t **pp)
{
    for (node_t **node = pp; *node && (*node)->next; node = &(*node)->next->next) {
        node_t *tmp = *node;
        *node = (*node)->next;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
}
```

---

* reverse()
```cpp=
node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    while (head) {
        node_t *next = head->next;
        CCC;
        head = next;
    }
    return cursor;
}
```
**Q5. CCC = ?**
這邊的作法是創造一逆轉 ~~(Tenet)~~ 的 linked list，因為此函式會更改 `head` 指向的位址且以指向 `node_t` 的指標作為參數，故有必要再將新的位址傳回給 `head` 。
`cursor` 指標代表的是目前已經反轉好的 linked list 的 head，透過每回合的 while 逐個反轉，故可將流程分為 4 步驟：
```
1. 紀錄下回合要反轉的 node 
2. 將這回合指標的 next 改指向 cursor
3. 把 cursor 指向這回合的指標，表示反轉好的節點又多一個
4. 最後取回下回合的 node 準備給下回合使用

對照程式碼可知 CCC 為步驟 2. `head->next = cursor` ，及步驟 3. `cursor = head` 。故本題為選項 (b) 。

#### ※ 延伸問題 改寫 `reverse` 函式回傳型態為 `void`
透過指向指標的指標可以來指向新的 head 位址，而不用再將新的位址回傳。其餘作法皆相同。
```cpp=
void reverse(node_t **pp)
{
    node_t *cursor = NULL;

    while (*pp) {
        node_t *next = (*pp)->next;
        (*pp)->next = cursor;
        cursor = *pp;
        *pp = next;
    }
    *pp = cursor;
}
```
#### ※ 延伸問題 將 `reverse` 用遞迴改寫
遞迴函式需要注意**回傳條件**以及**回傳什麼**，與 iterative 不同於反轉的起始點，遞迴從尾巴開始，迭代則是由頭；且要注意當遞迴進 `NULL` 前的節點時便要回傳。
```cpp=
node_t *rev_recursive(node_t *h)
{
    if (!h || h->next == NULL)
        return h;
    node_t *cursor = rev_recursive(h->next);
    node_t *tmp = cursor;
    while (tmp->next)
        tmp = tmp->next;
    tmp->next = h;
    h->next = NULL;
    return cursor;
}

node_t *reverse(node_t *head)
{
    return rev_recursive(head);
}
```
---

* print_list()
```cpp=
void print_list(node *head)
{
    for(node_t *current = head; current; current = current->next)
        printf("%d ", current->value);
    printf("\n");
}
```

---
## 針對 singly-linked list 實作 Fisher–Yates shuffle
### 簡介
* 是將一個有限長度的序列進行隨機置換的演算法，核心作法是從 random table 挑選一個數字，而這個數字介於 **1 到尚未被選中的元素數量**並且作為序列的 index number，對該 index 的元素作下面提到的兩種不同的 permutation
* Original method
```
/*
 * 假設序列名字為 S, 長度為 N
 * 建立長度和 S 相同的空序列 S'
 */
1. 從 random table 中挑選一個數字 k 作為當前序列的 index
2. 將 S 中從頭數來第 k 個數取出並放入 S'最尾端
3. 回到步驟1. 直到所有元素皆被取出並放入 S'
4. S' 即為一個 random permutaion
```
  
  
* Modern method
  和 Original最大差別在於沒有新建一個序列，而是在原序列中把挑中的 k 和由左至右(或相反)的元素作交換，參見如下維基百科中由右至左的演算法 : 
```
-- 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]
  ```
  
### 程式碼
* singly-linked list 每次取得任意節點的時間複雜度為 O(n) 又執行 O(n)，故時間複雜度為 O(n^2^)
* 空間複雜度原作法為 O(n)，modern 則為 O(1)
* 透過減少變數的宣告來降低記憶體使用量
```cpp=
void FYshuffle(node_t **h)
{
    /*Calculate length of the linked list*/
    int len = 0;
    node_t **pivot = h;
    for (; *pivot; pivot = &(*pivot)->next)
        ++len;

    /*Reuse pivot pointer*/
    pivot = h;
    for (int i = len; i>1; i--) {
        /*Pick a random number k from 1 to i*/
        int k = (rand() % i) + 1;
        /*Find the kth node*/
        node_t **kNode = pivot;
        while (k>1) {
            kNode = &(*kNode)->next;
            k--;
        }
        /*Swap values of pivot node and kNode*/
        int val = (*pivot)->value;
        (*pivot)->value = (*kNode)->value;
        (*kNode)->value = val;
        
        pivot = &(*pivot)->next;
    }
}
```

## 靜態記憶體分析
```shell
$ cppcheck -DA quie1.c --enable=all --supㄣress=missingIncludeSystem
Checking quiz1.c ...
Checking quiz1.c: A=1...
```
* `--enable=all`: 檢查所有項目
* `--suㄣpress=missingIncludeSystem`: 根據 [這篇討論](https://) 提到 cppcheck 不擅長找標準函式庫的 path ，因此可用這個命令使它忽視這個問題，否則會跳出第四行: 
  ```shell=
  $ cppcheck -DA quie1.c --enable=all
  Checking quiz1.c ...
  Checking quiz1.c: A=1...
  nofile:0:0: information: Cppcheck cannot find all the include files (use --check-config for details) [missingIncludeSystem]
  ```
###### tags: `linux2020`