---
tags: 進階電腦系統理論與實作, NCKU Linux Kernel Internals, 作業系統
---
# 2020q3 Homework1 (quiz1)
contributed by <`RusselCK` >
###### tags: `RusselCK`
> [題目描述](https://hackmd.io/@sysprog/sysprog2020-quiz1)
### Q1. 考慮一個單向 linked list，其結構定義為:
```c
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
已知不存在 circular (環狀結構)
#### 1. `append_entry` : 新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference ，而非 copy
```c=
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;
}
```
* 程式碼(已知部分)：
```c
#1 node_t **indirect = head;
```
* * 建立一個指向`head` 的指標`indirect`
```graphviz
digraph {
node[shape=box]
head[shape=plaintext,fontcolor=black]
indirect[shape=plaintext,fontcolor=blue]
rankdir=LR
{
NULL[label=NULL,shape=plaintext]
}
{
rank="same";
indirect->head->A
}
A->B->C->NULL
}
```
```c
#5 node_t *new_node = malloc(sizeof(node_t));
#6 new_node->value = new_value;
#7 new_node->next = NULL;
```
* * 配置一個新增的節點 `new_node`
```graphviz
digraph {
node[shape=box]
rankdir=LR
{
new_node[label=new_node]
NULL[label=NULL,shape=plaintext]
}
new_node->NULL
}
```
```c
#10 while (*indirect)
#11 indirect = &(*indirect)->next;
```
* * 迴圈測試 `*indirect` 取值是否為NULL，
若不為 NULL，則將 `indirect` 設為指向 `(*indirect)->next` 的指標
(即 將indirect設為指向`(最後一個node)->next`的指標)
```graphviz
digraph {
node[shape=box]
head[shape=plaintext,fontcolor=black]
indirect[shape=plaintext,fontcolor=red]
rankdir=LR
new_node{
NULL1[label=NULL,shape=plaintext]
new_node->NULL1
}
{
NULL[label=NULL,shape=plaintext]
}
{
rank="same";
head->A
}
{
rank="same";
indirect->NULL
}
A->B->C->NULL
}
```
* 補完程式碼：
1. 由已知部分及 `append_entry` 的功能定義來推論， `#10#11` 完成後還缺少將 new_node 放置在linked list 的步驟。因此先考慮 `*indirect = new_node` 的位置：
* 若將 `*indirect = new_node` 放置在 AA1，則無法達成 `append_entry` 的功能。
```graphviz
digraph {
node[shape=box]
head[shape=plaintext,fontcolor=black]
indirect[shape=plaintext,fontcolor=red]
rankdir=LR
new_node{
NULL[label=NULL,shape=plaintext]
new_node->NULL
}
{
rank="same";
indirect->new_node
head->A
}
{
NULL1[label=NULL,shape=plaintext]
A->B->C->NULL1
}
}
```
* * 若將 `*indirect = new_node` 放置在 AA2，可將 new_node 完美接在 linked list 之後。
```graphviz
digraph {
node[shape=box]
head[shape=plaintext,fontcolor=black]
indirect[shape=plaintext,fontcolor=blue]
rankdir=LR
{
new_node[color=red,fontcolor=red]
}
{
rank="same";
head->A
}
{
rank="same";
indirect->new_node
}
A->B->C->new_node
}
```
* * 因此， AA2 為 `*indirect = new_node`
2. 由刪去法可知， AA1 為 `assert(new_node)`
:::info
The C library macro void assert(int expression) allows diagnostic information to be written to the standard error file. In other words, it can be used to add diagnostics in your C program.
```#include <assert.h>```
* ```assert(int expression)```
* Expression can be a variable or any C expression.
* If expression evaluates to TRUE, assert() does nothing. If expression evaluates to FALSE, assert() displays an error message on stderr (standard error stream to display error messages and diagnostics) and aborts program execution.
Source：https://www.tutorialspoint.com/c_standard_library/c_macro_assert.htm
:::
#### 2. `swap_pair` : 交換一對相鄰的節點，取自 [LeetCode: Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)，給定 1->2->3->4，則該回傳 2->1->4->3
```c=
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;
}
```
* 程式碼(已知部分)：
```c
#3 for (node_t **node = &head; *node && (*node)->next; BB1)
```
* `for`迴圈
* 起始狀態 `node_t **node = &head` ：建立一個指向 `head` 的指標
* testExpression `*node && (*node)->next` ：確認 `*node` 及 `(*node)->next` 是否為 NULL ，皆不為 NULL 才可進入迴圈
* 更新狀態 `BB1`
```graphviz
digraph{
node[shape=box]
n[shape=plaintext,label="node",fontcolor=red]
head[shape=plaintext]
rankdir=LR
{
NULL[shape=plaintext,fontcolor=black]
A->B->C->NULL
}
{
rank="same"
n->head
head->A
}
}
```
* 組內交換
```c
#4 node_t *tmp = *node;
```
```graphviz
digraph{
node[shape=box]
n[shape=plaintext,label="node",fontcolor=black]
head[shape=plaintext]
tmp[shape=plaintext,fontcolor=red]
rankdir=LR
{
NULL[shape=plaintext,fontcolor=black]
A->B->C->NULL
}
{
rank="same"
n->head
head->A
}
{
rank=same
tmp->A
}
}
```
```c
#5 BB2; //*node=(*node)->next
```
```graphviz
digraph{
node[shape=box]
n[shape=plaintext,label="node",fontcolor=black]
head[shape=plaintext,fontcolor=red]
tmp[shape=plaintext,fontcolor=black]
rankdir=LR
{
NULL[shape=plaintext,fontcolor=black]
A->B->C->NULL
}
{
rank="same"
n->head
head->B
}
{
rank=same
tmp->A
}
}
```
```c
#6 tmp->next = (*node)->next;
```
```graphviz
digraph{
node[shape=box]
n[shape=plaintext,label="node",fontcolor=black]
head[shape=plaintext,fontcolor=black]
tmp[shape=plaintext,fontcolor=red]
rankdir=LR
{
A[color=red,fontcolor=red]
NULL[shape=plaintext,fontcolor=black]
B->C->NULL
A->C
}
{
rank="same"
n->head
head->B
}
{
rank=same
tmp->A
}
}
```
```c
#7 (*node)->next = tmp;
```
```graphviz
digraph{
node[shape=box]
n[shape=plaintext,label="node",fontcolor=red]
head[shape=plaintext,fontcolor=red]
tmp[shape=plaintext,fontcolor=black]
rankdir=LR
{
B[color=red,fontcolor=red]
NULL[shape=plaintext,fontcolor=black]
B->A
C->NULL
A->C
}
{
rank="same"
n->head
head->B
}
{
rank=same
tmp->A
}
}
```
* 補完程式碼：
3. 根據 `swap_pair` 功能定義且已知BB1為迴圈的更新狀態，可推得BB1的效果為將 `node` 所指向的位址由 `*node` 的位址改為 `(*node)->next->next` 的位址
因此， BB1 為 `node = &(*node)->next->next`
4. 為使組內交換成功，可推得 BB2 為 `*node=(*node)->next`
#### 3. `reverse`: 將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1
```c=
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
CCC;
head = next;
}
return cursor;
}
```
* 程式碼(已知部分)
```c
#3 node_t *cursor = NULL;
```
* * 建立一個空的node_t `cursor`
```graphviz
digraph{
cursor[shape=plaintext,fontcolor=red]
NULL[shape=plaintext,fontcolor=black]
rankdir=LR
cursor->NULL
}
```
* * 反序
```c
#4 while (head)
```
* * `while` 回圈： `head` 不為 NULL 時可進入迴圈
```c
#5 node_t *next = head->next;
```
```graphviz
digraph{
node[shape=box]
next[shape=plaintext,fontcolor=red]
head[shape=plaintext,fontcolor=black]
rankdir=LR
{
NULL[shape=plaintext,fontcolor=black]
A->B->C->NULL
}
{
rank=same
head->A
}
{
rank=same
next->B
}
}
```
```c
#6 CCC; //head->next = cursor; cursor = head
```
```graphviz
digraph{
cursor[shape=plaintext,fontcolor=red]
node[shape=box]
next[shape=plaintext,fontcolor=black]
head[shape=plaintext,fontcolor=black]
rankdir=LR
{
NULL[shape=plaintext,fontcolor=black]
B->C->NULL
}
{
rank=same
head->A
}
{
rank=same
next->B
}
{
rankdir=RL
A->cursor->A
}
}
```
```c
#7 head = next;
```
```graphviz
digraph{
cursor[shape=plaintext,fontcolor=red]
node[shape=box]
next[shape=plaintext,fontcolor=black]
head[shape=plaintext,fontcolor=red]
rankdir=LR
{
NULL[shape=plaintext,fontcolor=black]
B->C->NULL
}
{
rank=same
head->B
}
{
rank=same
next->B
}
{
rankdir=RL
A->cursor->A
}
}
```
* 補完程式碼
5. 為使反序成功，可推得 CCC 為` head->next = cursor; cursor = head`
#### 4.`remove_entry`: 移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)
### Q2. 請用指標的指標來改寫`swap_pair` 和 `reverse`，並避免回傳指標
#### 1. `swap_pair`
```c=
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;
}
}
```
* 主程式呼叫
```c=
swap_pair(&head);
```
#### 2. `reverse`
```c=
void reverse(node_t **head)
{
node_t *cursor = NULL;
while(*head)
{
node_t *next = (*head)->next;
(*head)->next = cursor;
cursor = *head;
*head = next;
}
*head = cursor;
}
```
* 主程式呼叫
```c=
reverse(&head);
```
### Q3. 以遞迴改寫上述的 `reverse`
:::warning
注意，你可能因此需要建立新的函式，如 `rev_recursive` ，隨後在 `reverse` 函式中呼叫 `rev_recursive`
:::
```c=
void rev_recursive(node_t *head,node_t *cursor,node_t **list)
{
node_t *next = head->next;
head->next = cursor;
if (!next) {
*list = head;
return;
}else
rev_recursive(next, head, list);
}
void reverse(node_t **head)
{
node_t *cursor = NULL;
if(*head)
rev_recursive(*head,cursor,head);
}
```
* 運作原理(簡單示意)：
* 初始狀態
```graphviz
digraph {
node[shape=box]
head[label="head(list)", shape=plaintext,fontcolor=black]
cursor[shape=plaintext,fontcolor=black]
rankdir=LR
{
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
head->A
}
cursor->NULL1
A->B->C->NULL2
}
```
* * `rev_recursive(*head,cursor,head);`
```graphviz
digraph {
node[shape=box]
head[label="head(list)",shape=plaintext,fontcolor=black]
cursor[shape=plaintext,fontcolor=black]
next[shape=plaintext,fontcolor=blue]
rankdir=LR
{
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
head->A
}
{
rank="same";
next->B
}
cursor->NULL1
A->NULL1
B->C->NULL2
}
```
* * `rev_recursive(next, head, list);`
```graphviz
digraph {
node[shape=box]
head[label="head(list)",shape=plaintext,fontcolor=black]
cursor[shape=plaintext,fontcolor=black]
next[shape=plaintext,fontcolor=blue]
next1[shape=plaintext,fontcolor=blue]
rankdir=LR
{
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
head->A
}
{
rank="same";
next->B
}
{
rank=same
next1->C
}
cursor->NULL1
B->A->NULL1
C->NULL2
}
```
* * `rev_recursive(next1, next, list);`
```c=
if (!next) {
*list = head;
return;
}
// in this case,
// next is next2,
// list is head,
// head is next1
```
```graphviz
digraph {
node[shape=box]
head[label="head(list)", shape=plaintext,fontcolor=red]
cursor[shape=plaintext,fontcolor=black]
next[shape=plaintext,fontcolor=blue]
next1[shape=plaintext,fontcolor=blue]
next2[shape=plaintext,fontcolor=blue]
rankdir=LR
{
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
head->C
}
{
rank="same";
next->B
}
{
rank=same
next1->C
}
{
rank=same
next2->NULL2
}
cursor->NULL1
C->B->A->NULL1
}
```
* 結束遞迴，完成 reverse
```graphviz
digraph {
node[shape=box]
head[label="head(list)", shape=plaintext,fontcolor=black]
rankdir=LR
{
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
head->C
}
C->B->A->NULL1
}
```
### Q4. 針對 singly-linked list 的節點，實作 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)，你應該儘量降低記憶體的使用量
* The basic method given for generating a random permutation of the numbers 1 through N goes as follows:
1. Write down the numbers from 1 through N.
2. Pick a random number k between one and the number of unstruck numbers remaining (inclusive).
3. Counting from the low end, strike out the kth number not yet struck out, and write it down at the end of a separate list.
4. Repeat from step 2 until all the numbers have been struck out.
5. The sequence of numbers written down in step 3 is now a random permutation of the original numbers.
* Example (pancil-and-paper method)：
| Range | Roll | Scratch | Result |
|:-----:|:----:|:-----------------------------------------------:| --------------- |
| | | 1 2 3 4 5 6 7 8 | |
| 1-8 | 3 | 1 2 ~~3~~ 4 5 6 7 8 | 3 |
| 1-7 | 4 | 1 2 ~~3~~ 4 ~~5~~ 6 7 8 | 3 5 |
| 1-6 | 5 | 1 2 ~~3~~ 4 ~~5~~ 6 ~~7~~ 8 | 3 5 7 |
| 1-5 | 3 | 1 2 ~~3~~ ~~4~~ ~~5~~ 6 ~~7~~ 8 | 3 5 7 4 |
| 1-4 | 4 | 1 2 ~~3~~ ~~4~~ ~~5~~ 6 ~~7~~ ~~8~~ | 3 5 7 4 8 |
| 1-3 | 1 | ~~1~~ 2 ~~3~~ 4 ~~5~~ 6 ~~7~~ ~~8~~ | 3 5 7 4 8 1 |
| 1-2 | 2 | ~~1~~ 2 ~~3~~ ~~4~~ ~~5~~ ~~6~~ ~~7~~ ~~8~~ | 3 5 7 4 8 1 6 |
| | | ~~1~~ ~~2~~ ~~3~~ ~~4~~ ~~5~~ ~~6~~ ~~7~~ ~~8~~ | 3 5 7 4 8 1 6 2 |
#### 實作：
```c=
#include <time.h>
void shuffle(node_t **head)
{
//Initial Range
int range = 0;
node_t **indirect = head;
while (*indirect) {
range++;
indirect = &(*indirect)->next;
}
srand(time(NULL));
node_t *cursor = NULL;
while (range)
{
// roll
int roll = rand()%range;
// strick out the number
indirect = head;
while(roll)
{
indirect = &(*indirect)->next;
roll--;
}
// upadate the result
add_entry(&cursor,(*indirect)->value);
// remmove the struck out number
remove_entry(&(*head), *indirect);
range--;
}
*head = cursor;
}
```
#### 程式碼概述：
```c
//Initial Range
# 6 int range = 0;
# 7 node_t **indirect = head;
# 8 while (*indirect) {
# 9 range++;
#10 indirect = &(*indirect)->next;
}
```
* 首先，先取得 Range ，即 linked list 長度 `range`
* 接下來會有重複`range`次的動作，依次取得結果，每完成一次，`range`就減 1
```c
#15 node_t *cursor = NULL;
```
* 先建立 `cursor` 用來存放洗牌後的結果 ( Result )
```c
#19 int roll = rand()%range;
```
* 1~`range` 隨機選出編號 `roll`
```c
#22 indirect = head;
#23 while(roll)
{
#25 indirect = &(*indirect)->next;
#26 roll--;
}
```
* 找出編號 `roll` 的 node
```c
#29 add_entry(&cursor,(*indirect)->value);
```
* 將找到的 node 的 `value` 加入 `cursor`
```c
#31 remove_entry(&(*head), *indirect);
```
* 將找到的 node 從 `head` 刪除
* 迴圈結束後， `cursor` 即為結果
Sign in with Wallet
Connect another wallet