---
title: 2020q3 Homework1 (quiz1)
tags: sysprog
---
# 2020q3 Homework1 (quiz1)
contributed by < `TsundereChen` >
> GitHub Repo: [TsundereChen/sysprog2020-quiz1](https://github.com/TsundereChen/sysprog2020-quiz1)
> [Homework1 (quiz1)](https://hackmd.io/@sysprog/sysprog2020-quiz1)
## Data structure
```cpp
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
## Code
### add_entry()
```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;
}
```
裡面有兩個地方要填補 code， `AA1` 與 `AA2`
而這個 function 的功能是，在一個 linked list 的尾端加上新的 node
如果這個 linked list 都沒有 node 的話，那就建立第一個 node
而 `AA1` 和 `AA2` 只有兩個選項
- `assert(new_node)`
- `*indirect = new_node`
經過搜尋後，得知 `assert()` 並非 function 而是 `MACRO`，被定義在 `assert.h`
這個 `MACRO` 的功能是確認傳進去的值是否為 `true`，若非 `true` 則進行錯誤處理
#### assert.h
`assert()` 這個 `MACRO` 其實在 C99 標準內 7.2 節有定義，以下節錄
```
The assert macro puts diagnostic test into programs; it expands to a void expression.
When it's executed, if expression is false (that is, compares equal to 0),
the assert macro writes information about the particular call that failed
on the standard error stream in an implementation-defined format.
It then calls the abort function
```
這樣就知道上面的 `assert(new_node)` 在做什麼了，是用來檢測 `malloc()` 是否成功
若成功則繼續執行，失敗則退出
而若先 assign 壞掉的東西到 `*indirect` 然後再檢測 `new_node` 是否為 `NULL` 不合理
應該先檢查 `new_node` 是否正確，再更改 `*indirect` 數值
所以 `AA` 段的程式碼應該會長的像這樣
```cpp
assert(new_node)
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node
```
`while` 在這裡一路走訪 linked list 裡的節點，直到 `*indirect` 的數值為 `NULL` 為止
而一旦 `*indirect` 的數值為 `NULL`，便可以把新建立的 node 接上去
利用下面這張圖來輔助理解「指標的指標」
```graphviz
digraph G
{
value [shape=box,label="Value: a\nAddress: 0x1122"];
ptr [shape=box,label="Value: 0x1122\nAddress: 0x2233"];
pptr [shape=box,label="Value: 0x2233\nAddress: 0x3344"];
pptr -> ptr -> value;
pptrTag [label="pointer\nof\npointer"];
ptrTag [label="pointer"];
valTag [label="value"];
pptrTag->pptr;
ptrTag->ptr;
valTag->value;
{rank=same; value;ptr;pptr;}
{rank=same; pptrTag;ptrTag;valTag;}
}
```
`*indirect` 操作的數值是指標，而最終 `*indirect` 會被指去 `NULL`，是 `*indirect` 被指去某個記憶體位置，而這個記憶體位置內的數值為 `NULL`
那這樣的話只要把 `*indirect` 指到新的 node 上就好了
### swap_pair()
```cpp
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; BB1) {
node_t *tmp = *node;
BB2;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
一開始執行這個 function 的時候 `node` 和 linked list 的關係是
```graphviz
digraph G
{
node1[shape=box,label=2];
node2[shape=box,label=3];
node3[shape=box,label=4];
node4[shape=box,label=5];
node1->node2->node3->node4;
nodeTag[label="node"];
nodeTag->node1;
{rank=same;node1;node2;node3;node4;};
}
```
接下來，新增一個 `tmp` 變數，並賦 `*node` 的值，現在關係如下
```graphviz
digraph G
{
node1[shape=box,label=2];
node2[shape=box,label=3];
node3[shape=box,label=4];
node4[shape=box,label=5];
node1->node2->node3->node4;
nodeTag[label="node"];
tmpTag[label="tmp"];
nodeTag->node1;
tmpTag->node1;
{rank=same;node1;node2;node3;node4;};
}
```
接下來要把 `node` 移至下一個
`node` 的 data type 是 `node_t **`，是指標的指標，所以我們可以利用和上面 `add_entry()`
類似的操作，利用「更改指標裡的數值」，以更改指標指向的對象，以達成把 `node` 下移的目的
因為我們要操作的數值是指標，不是指標的指標，一個星號就好
所以這裡會是 `*node = (*node)->next`
再回去看 `BB1` 的部分，再次注意 `node` 的 data type 是 `node_t **`
而 `*node->next` 的 data type 是 `node_t *`，所以即便取出了下一個 node 的資料
我們還是要再取得這個 node 的記憶體地址，然後才能賦值給 `node`
所以是 `node = &(*node)->next->next`
### reverse()
```cpp
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
CCC;
head = next;
}
return cursor;
}
```
下圖為進入 function 後，第一次執行完 `node_t *next = head->next;` 行之狀態
```graphviz
digraph G
{
node0 [shape=box,label=NULL];
node1 [shape=box,label=3];
node2 [shape=box,label=5];
node1->node2;
cursorTag [label=cursor];
headTag [label=head];
nextTag [label=next];
cursorTag->node0;
headTag->node1;
nextTag->node2;
{rank=same;node0;node1;node2;}
}
```
因為是 reverse，所以要把 `next` 都反轉
我們要把 `head` 指向的 node 指到前面那個 node，在這裡的話是 `NULL`
同時也要把 `cursor` 移到下一個 node 上
`CCC` 段執行完後應該會像這樣
```graphviz
digraph G
{
node0 [shape=box,label=NULL];
node1 [shape=box,label=3];
node2 [shape=box,label=5];
node1->node0;
cursorTag [label=cursor];
headTag [label=head];
nextTag [label=next];
cursorTag->node1;
headTag->node1;
nextTag->node2;
{rank=same;node0;node1;node2;}
}
```
再接下來 `head` 就能指去 `next`，然後 `next` 就能再往下走，直到 linked list 反轉完成
## 延伸問題
### swap_pair() & reverse()
:::info
函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = ... 的更新，請用指標的指標來改寫，並避免回傳指標;
:::
#### swap_pair()
只要更改傳入的變數，函數的其他部分可直接沿用
```cpp
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;
}
return;
}
```
#### reverse()
這裡仿照上面「指標的指標」寫法完成
```cpp
void reverse(node_t **head) {
node_t **now = head;
node_t *cursor = NULL;
node_t *next = NULL;
while ((*now)) {
next = (*now)->next;
(*now)->next = cursor;
cursor = *now;
*now = next;
}
*now = cursor;
return;
}
```
### recursive reverse()
:::info
以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_recursive，隨後在 reverse 函式中呼叫 rev_recursive;
:::
:::success
參考 [RinHizakura同學](https://hackmd.io/@RinHizakura/BysgszHNw)在這個延伸問題上的解
:::
如果要遞迴式的反轉 Linked List 的話，我們可以在每次呼叫遞迴時，將過往、當下與下一個 node 的資訊都傳給函式
並且在下一個 node 為 NULL 時終止遞迴，同時將 head 重新指向現在在的 node
```cpp
void recursive_reverse(node_t **head) {
if (!head)
return;
recursive_reverse_step(*head, NULL, head);
}
void recursive_reverse_step(node_t *curr, node_t *prev, node_t **head) {
node_t *next = curr->next;
curr->next = prev;
if (!next) {
*head = curr;
return;
}
recursive_reverse_step(next, curr, head);
}
```
### Fisher-Yates shuffle
:::info
針對 singly-linked list 的節點，實作 Fisher–Yates shuffle，你應該儘量降低記憶體的使用量;
:::
#### Fisher-Yates shuffle
:::success
1. 首先，先取得 Linked List 長度 N，賦值 M 為 N-1
2. 在 0 ~ N-1 之間隨機挑選一個數值 k
3. 將 arr[k] 與 arr[M--] 之數值互換
4. 重複上面步驟，直到 M 為 0 為止
:::
上述是 Fisher-Yates Shuffle，但 Richard Durstenfeld 在 1964 年針對電腦提出了更新的 Shuffle 方法
底下是此方法的 pseudocode
**Pseudocode**
```
-- To shuffle an array a of n elements (indices 0..n-1)
for i from 0 to n-2 do
j <- random integer such that i <= j < n
exchange a[i] and a[j]
```
```cpp
int get_list_length(node_t *head) {
int len = 0;
for (node_t *current = head; current; current = current->next)
len++;
return len;
}
node_t *node_finder(node_t *head, int position) {
node_t *now = head;
for (int i = 0; i < position; i++) {
now = now->next;
}
return now;
}
void swapValue(node_t *a, node_t *b) {
if (a == b)
return;
a->value ^= b->value;
b->value ^= a->value;
a->value ^= b->value;
}
void fisherYatesShuffle(node_t *head, int length) {
node_t *now = head;
for (int i = 0; i < length; i++) {
int randInt = i + (rand() % (length - i));
node_t *targetNode = node_finder(head, randInt);
swapValue(now, targetNode);
now = now->next;
}
}
int main(int argc, char const *argv[]){
/* Create linked list here... */
fisherYatesShuffle(head, get_list_length(head));
print_list(head);
}
```
Sign in with Wallet
Connect another wallet