# 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/)
圖中的 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 為單位向上增加）
Sign in with Wallet
Connect another wallet