# 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`
Sign in with Wallet
Connect another wallet