---
# System prepended metadata

title: 2020q3 Homework1 (quiz1)
tags: [sysprog-2020]

---

# 2020q3 Homework1 (quiz1)
contributed by < `jonec76` >
###### tags: `sysprog-2020`

> [作業說明](https://hackmd.io/@sysprog/rJ7WDWNVv)

## 開發環境
```shell
$ uname -a
Linux jonec76-Aspire-M7720 5.4.0-47-generic #51-Ubuntu SMP GNU/Linux
```

## 參考解答

AA1 = assert(new_node)
AA2 = *indirect = new_node
BB1 = node = &(*node)->next->next
BB2 = *node = (*node)->next
CCC = head->next = cursor; cursor = head

## 作業要求

- 重新回答 [第 1 周測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)，連同附帶的「延伸問題」。
解釋程式運作原理時，應提供對應的 [Graphviz](https://graphviz.org/) 圖例，可參照 [Linked List 題目 1 + 分析](https://hackmd.io/@sysprog/linked-list-quiz)
- 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb) : Q1 和  [Linked list 題目分析](https://hackmd.io/s/HyELy5bTz) 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及進行相關實驗。
### Q1
填入 `assert()`，參考 [man page](https://man7.org/linux/man-pages/man3/assert.3.html) 提到，當傳入的值為 false 時，程式會暫停並且印出錯誤訊息。題目中的 assert(new_node) 指出，在配置記憶體給 `new_node` 時，若 `malloc` 失敗的話會回傳 `NULL`，此時表示沒有配置成功，這時透過 `assert` 檢測就能將程式暫停並且印出錯誤訊息。
### Q2

填入 `*indirect = new_node`，這裡使用到了 pointer to pointer 的方式，使得不用回傳 `node_t*` 也能夠更改 caller 的 list。
        
- pointer to pointer 參數

    callee 函式是如何更改 caller 的 linked-list 呢？
    在 callee 的參數是 `node_t **head`，且在 caller 是傳入 `&head`，也就是 head 指標的位址，當 callee 的 head 在做 `*head`，也就是對這個 pointer to pointer 做 dereference 時，所得到的就是 caller 的記憶體位置，可從下方程式碼清楚看出

    ```c=1
    void add_entry(node_t **head, int new_value){
        printf("callee: %p\n", &*head);
        ...
    }

    int main(){
        node_t *head = NULL;
        printf("caller: %p\n", &head);
        ...
    }
    ```
    這樣的好處是，在 callee 透過 dereference 之後所操作的指標位址，跟外部的 caller 的指標位址是相同的，是同一個指標。
    然而，若不使用 pointer to pointer 的方式，而改成傳入 `node_t* head`，此時 caller 跟 callee 的指標是不同的，參考 [Passing Reference to a Pointer in C++](https://www.geeksforgeeks.org/passing-reference-to-a-pointer-in-c/) 裡頭說到
    > “pass by pointer” is passing a pointer by value.

    也就是將值複製給 caller 指標，但是 caller 的變動無法改變 callee 的指標。

在 `add_entry` 裡頭，也透過 pointer to pointer `indirect` 指標，指到該 list 的最後一個位置（`NULL`），並且更新該位置為新配置的節點 `new_node`，圖示如下

```graphviz
digraph linked_list{
    rankdir=LR
        node [shape=record];
        1 [label="{ <data> 1 | <ref>  }"];
        3 [label="{ <data> 3 | <ref>  }"];
        5 [label="{ <data> 5 | <ref>  }"];
        7 [label="{ <data> 7 | <ref>  }"];
        h1[label = "{<data> head}"];
        new[label = "{<data> new node| <ref>}"];
        ind[label = "{<data> indirect| <ref>  }"];
        h1->1
        1:ref:c -> 3:data [arrowtail=dot, dir=both, tailclip=false];
        3:ref:c -> 5:data [arrowtail=dot, dir=both, tailclip=false];
        5:ref:c -> 7:data [arrowtail=dot, dir=both, tailclip=false];
        7:ref:c ->new [arrowtail=dot,
dir=both, tailclip=false]   
        ind:ref:c -> new[arrowtail=dot,
dir=both, tailclip=false];
        new:ref:c -> NULL
    }
```
### Q3

這部分要填入的是讓該指標能往 `next` 移動的選項，自己選了 (b)`*node = (*node)->next->next` 選項，但其實跟 (c) 是一樣的都是錯，錯在這樣寫會更改到 head 指標，使得最後 head 等於 `NULL` 並且回傳 `head`。正確寫法應該是使用 pointer to pointer 的指標去遍歷整條 list，如此才能不更改到 head 的位置，且對 node 做兩兩交換
        
### Q4
這裡希望達到兩個 node 互相交換，步驟示意圖如下：
首先，先讓 `*node` 到 `*node->next`的位址

```graphviz
    digraph linked_list{
    rankdir=LR
        node [shape=record];
        n1 [ fillcolor=gray style=filled label="{ <data> 4 | <ref>  }"];
        head [ label="{ <data> head}"];
        n2 [fillcolor=gray style=filled label="{ <data> 12 | <ref>  }"];
        null [fillcolor=gray style=filled label="{ <data> NULL  }"];
        h1[ label = "{<data> *node}"];                     pp[label = "{<data> node}"];
        tmp[label = "{<data> tmp}"];
        n1:ref:c -> n2:data [arrowtail=dot, dir=both, tailclip=false];
        n2:ref:c -> null;
        h1:c -> n2:n
        tmp:ref:c -> n1:n
        pp:c -> h1:n  [label="dereference"]
        head->n2:n
    }
```
接著，更改這兩個 node 的 next pointer：

```graphviz
    digraph linked_list{
    rankdir=LR
        node [shape=record];
        head [ label="{ <data> head | <ref>  }"];
        n1 [ fillcolor=gray style=filled label="{ <data> 4 | <ref>  }"];
        n2 [fillcolor=gray style=filled label="{ <data> 12 | <ref>  }"];
        null [fillcolor=gray style=filled label="{ <data> NULL  }"];
        h1[ label = "{<data> *node}"];                       pp[label = "{<data> node}"];
        tmp[label = "{<data> tmp}"];
        n1:ref:c -> null;

        h1:c -> n2:n
        n2:ref:c -> n1;
        tmp:ref:c -> n1:n
        pp:c -> h1:n [label="dereference"]
        head->n2:n
    }
```
接著，`node` 往下兩步（參考第 (3) 題）
```graphviz
    digraph linked_list{
    rankdir=LR
        node [shape=record];
        n1 [ fillcolor=gray style=filled label="{ <data> 4 | <ref>  }"];
        n2 [fillcolor=gray style=filled label="{ <data> 12 | <ref>  }"];
        null [fillcolor=gray style=filled label="{ <data> NULL  }"];
        h1[ label = "{<data> *node}"];                       pp[label = "{<data> node}"];
        tmp[label = "{<data> tmp}"];
        n1:ref:e -> null:w;
        n2:ref:e -> n1:w;
        h1:c -> null:n;
        tmp:e -> null:n
        head->n2:w
        pp:c -> h1:n [label="dereference"]

    }
```
### Q5

這題考 reverse list，動畫示意圖參考 [reverse a linked list](https://www.geeksforgeeks.org/reverse-a-linked-list/)

![](https://i.imgur.com/sg9cbr8.gif =400x400)

圖中的 prev 指標對應到題目的 cursor，curr 指標對應到 head。因為 current->next 會指向前一個 node 的位址，於是需要 next 指標先去紀錄 current->next 的位址，接著才能改動 current->next 指到前一個 node，前一個 node 由 prev(cursor) 紀錄著。


## 延伸問題

- [x] 解釋上述程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現;
- [x] 函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = ... 的更新，請用指標的指標來改寫，並避免回傳指標;

    - 要避免回傳指標，解法就是讓 pointer to pointer 指向傳進來的參數的位址，如此一來就能透過 dereference 直接對 caller 的那指標做操作，改後程式碼如下
    
    ```c=1
    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;
        }
    }

    void reverse(node_t **head){
        node_t *cursor = NULL;
        node_t *next = NULL;

        while (*head) {
            next = (*head)->next;
            (*head)->next = cursor;
            cursor = *head;
            *head = next;
        }
        *head = cursor;
    }
    ```


- [x] 以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_recursive，隨後在 reverse 函式中呼叫 rev_recursive;

    想法是先遞迴到 list 的最後一個 node（在 `NULL` 的前一個）。而這個最後一個 node 將會是新的 head 位置，所以使用了 `rev_h` 去紀錄
    > 這邊不確定是否有更好的寫法，譬如說不需要多一個參數 `rev_h`，而是只用一個參數即可

    接著在遞迴的 backtracking 階段，所拿到的 node 都是前一個遞迴回傳的 node，該回傳 node 取做 `prev`，表示他是前一個 node 要來指向我現在的 node。
    
    這邊值得注意的是 `curr->next = NULL;`，沒加這行之前執行 `print_list` 會是無限迴圈，這是因為假設下方是原始 list
    ```graphviz
    digraph linked_list{
    rankdir=LR
        node [shape=record];
        
        head [ label="{ <data> head }"];


        n1 [ fillcolor=gray style=filled label="{ <data> 4 | <ref>  }"];
        n2 [fillcolor=gray style=filled label="{ <data> 12 | <ref>  }"];
        n3 [fillcolor=gray style=filled label="{ <data> 17 | <ref>  }"];
        n4 [fillcolor=gray style=filled label="{ <data> 21 | <ref>  }"];
        
        head->n1:n
        n1:ref:c->n2[arrowtail=dot, dir=both, tailclip=false];
        n2:ref:c->n3[arrowtail=dot, dir=both, tailclip=false];
        n3:ref:c->n4[arrowtail=dot, dir=both, tailclip=false];
        n4->NULL
    }
    ```
    接著若沒有處理 `curr->next = NULL;`，就會得到下方的圖。接著若再跑 `print_list(newh)` 的話，就會產生無限迴圈
    
    
    
    ```graphviz
    digraph linked_list{
    rankdir=LR
        node [shape=record];
        
        head [ label="{ <data> newh }"];

        n1 [ fillcolor=gray style=filled label="{ <data> 4 | <ref>  }"];
        n2 [fillcolor=gray style=filled label="{ <data> 12 | <ref>  }"];
        n3 [fillcolor=gray style=filled label="{ <data> 17 | <ref>  }"];
        n4 [fillcolor=gray style=filled label="{ <data> 21 | <ref>  }"];
        
        head->n4:n
        n4:ref:c->n3[arrowtail=dot, dir=both, tailclip=false];
        n3:ref:c->n2[arrowtail=dot, dir=both, tailclip=false];
        n2:ref:c->n1[arrowtail=dot, dir=both, tailclip=false];
        n1:ref:n->n2:n[arrowtail=dot, dir=both, tailclip=false];
    }
    ```
    以下附上程式碼
    
    ```c=1
    node_t* rev_recursive(node_t *curr, node_t **rev_h){
        if(!(curr)->next){
            *rev_h = curr;
            return curr;
        }
        node_t* prev = rev_recursive(curr->next, rev_h);
        prev->next = curr;
        curr->next = NULL;
        return curr;
    }

    void reverse(node_t **head)
    {
        node_t* rev_h;
        rev_recursive(*head, &rev_h);
        *head = rev_h;
    }
    ```
    
- [x] 針對 singly-linked list 的節點，實作 Fisher–Yates shuffle，你應該儘量降低記憶體的使用量;

```c=1
void fy_shuffle(node_t** head){
    node_t* tail = NULL, *rand_ptr = NULL;
    node_t** tmp;
    time_t t;
    int len, tmp_value, rand_idx;

    while(tail != *head){
        tmp = head;
        len = 1;

        // find the tail of the list
        while((*tmp)->next != tail){
            len++;
            tmp = &((*tmp)->next); 
        }
        tail = *tmp;

        // find the random index pointer
        srand((unsigned) time(&t));
        rand_idx = (rand() % len);
        rand_ptr = *head;
        for(int i=0;i<rand_idx;i++){
            rand_ptr = rand_ptr->next;
        }

        // swap the value of two nodes
        tmp_value = rand_ptr->value;
        rand_ptr->value = tail->value;
        tail->value = tmp_value;
    }
}
```

用最直觀的方法將演算法實作出來，因為不能用多餘的 array 儲存每個值，所以時間複雜度是 $o(n^2)$。下面附上檢測時間複雜度的實驗結果，讓 `fy_shuffle` 執行從長度為 1 到 15000 的 list （以 50 為單位向上增加）

![](https://i.imgur.com/rAQAKjE.png =450x400)


