# 2020q3 Homework1 (quiz1)
contributed by <[haoyu0970624763](https://github.com/haoyu0970624763/sysprog21-quiz1)>
延伸問題一:程式運作原理
===
## add_entry
```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 = "assert(new_node)" */
assert(new_node);
while (*indirect)
indirect = &(*indirect)->next;
/* AA2 = "*indirect = new_node" */
*indirect = new_node;
}
```
` 功能：新增節點在 list 最後面 `
#### **運作原理解說**
1. 動態新增新的 node，將參數 `new_value` 賦值給
`new_node->value`， `new_node->next` 指向 `NULL`
2. 檢查剛剛動態新增的 node 是否成功
3. 將新節點插入到 list 最尾端
`AA1` 跟 `AA2` 選項很少,很好判斷
## find_entry
```c
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
```c
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
```
`功能：刪除特定節點並釋放空間`
## swap_pair
```c=
node_t *swap_pair(node_t *head)
{
/* BB1 = "node = &(*node)->next->next" */
for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next) {
node_t *tmp = *node;
/* BB2 = "*node = (*node)->next" */
*node = (*node)->next;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
`功能：交換 list 中第 i 個節點跟第 i+1 節點的位置（i屬於奇數）`
#### ***運作原理解說***
4-5 行
`node` 為指向 `＆head` 的 pointer
`tmp` 先紀錄 node pointer 指向的位址 , 也就是`&list[i]`
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
{
A[label="node"]
B[label="tmp"]
C[label="head"]
}
{
D[label="list[i]"]
E[label="list[i+1]"]
F[label=""]
}
D->E->F
{
rank=same
B->D
}
{
rank=same
A->C->D
}
}
```
第 8 行 `tmp->next = (*node)->next ;`
由於函式為 swap_pair , 所以 `tmp->next` 應為 `list[i+1]->next`
因此我們可判斷 `BB2` 為 `*node = (*node)->next;`
執行完 `*node = (*node)->next;`
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
{
A[label="node"]
}
{
B[label="tmp"]
C[label="head"]
}
{
D[label="list[i]"]
E[label="list[i+1]"]
F[label=""]
}
D->E->F
{
rank=same
B->D
}
{
rank=same
A->C->E
}
}
```
執行完 `tmp->next = (*node)->next;`
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
{
A[label="node"]
B[label="head"]
C[label="list[i+1]"]
}
{
rank=same
A->B->C
}
}
```
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
{
B[label="tmp"]
}
{
D[label="list[i]"]
E[label=""]
}
D->E
{
rank=same
B->D
}
}
```
執行完 `(*node)->next = tmp;`
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
{
A[label="node"]
B[label="tmp"]
C[label="head"]
}
{
D[label="list[i+1]"]
E[label="list[i]"]
F[label=""]
}
D->E->F
{
rank=same
B->E
}
{
rank=same
A->C->D
}
}
```
**迴圈下一層**
已經換完前面兩個 , node 變數應跳到 list 中 , 指向後兩個成員的位址 , 進行下一次的 swap
所以 `BB1`為 `node = &((*node)->next->next)`
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
{
A[label="node"]
C[label="head"]
}
{
D[label="list[i+1]"]
E[label="list[i]"]
F[label=""]
}
D->E->F
{
rank=same
C->D
}
{
rank=same
A->F
}
}
```
## reverse
```c=
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
/* CCC = "head->next = cursor; cursor = head;" */
head->next = cursor; cursor = head;
head = next;
}
return cursor;
}
```
`功能：把 list 反過來連接`
#### ***運作原理解說***
`head` 表走訪 list 過程中的當前節點 , 從 list 最前端開始
`cursor` 表示上次走訪的節點
`next` 表當前節點的下一個節點
```graphviz
digraph {
node[shape=box]
rankdir = LR
{
A[label="node1"]
B[label="node2"]
C[label="node3"]
}
{
cursor[shape=none]
cursor->NULL
A->B->C
}
{
rank=same;
head[shape=none]
head->A
}
{
rank=same;
next[shape=none]
next->B
}
}
```
從第 8 行 `head = next;`
我們可以推斷出 CCC 應將上次走訪的節點串接在當前節點後面,還有更新上次走訪的節點以利用在下次迴圈中
所以 `CCC` = `head->next = cursor; cursor = head;`
概念如下
執行 `head->next = cursor;`
```graphviz
digraph {
node[shape=box]
rankdir = LR
{
A[label="node1"]
}
{
A->NULL
}
{
rank=same;
D[shape=none,label="head"]
D->A
}
}
```
```graphviz
digraph {
node[shape=box]
rankdir = LR
{
A[label="node2"]
B[label="node3"]
}
A->B
{
rank=same;
D[shape=none,label="next"]
D->A
}
}
```
執行 `cursor = head;` 與 `head = next;`
```graphviz
digraph {
node[shape=box]
rankdir = LR
{
A[label="node1"]
B[label="node2"]
C[label="node3"]
}
{
A->NULL
B->C
}
{
rank=same;
D[shape=none,label="cursor"]
D->A
}
{
rank=same;
next[shape=none,label="next & head "]
next->B
}
}
```
執行迴圈下一層
```graphviz
digraph {
node[shape=box]
rankdir = LR
{
A[label="node1"]
B[label="node2"]
C[label="node3"]
}
{
A->NULL
B->C
}
{
rank=same;
D[shape=none,label="cursor"]
D->A
}
{
rank=same;
head[shape=none]
head->B
}
{
rank=same;
next[shape=none]
next->C
}
}
```
執行第二次的 `head->next = cursor;`
```graphviz
digraph {
node[shape=box]
rankdir = LR
{
A[label="node1"]
B[label="node2"]
C[label="node3"]
}
{
B->A->NULL
C
}
{
rank=same;
D[shape=none,label="cursor"]
D->A
}
{
rank=same;
head[shape=none]
head->B
}
{
rank=same;
next[shape=none]
next->C
}
}
```
:::warning
**同樣的邏輯繼續下去即可求的反的 list**
:::
## print_list
```c
void print_list(node_t *head)
{
for (node_t *current = head; current; current = current->next)
printf("%d ", current->value);
printf("\n");
}
```
`功能：印出節點的值`
延伸問題二：指標的指標改寫
===
## swap_pair
原本的 `swap_pair` 中的 `head` 在函式內部採用 **call by value** , 改動 `head` 時 , 實際上不會改動到原本的`head` , 是更改複製出來的 `head`
可以用**call by reference** 的方式來避免此狀況
下面是改寫的程式碼
```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;
}
}
```
## reverse
透過 **call by reference** 取代原本 **call by value** 的參數傳遞方式
```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;
}
```
延伸問題三：recursive_reverse
===
將上面的 reverse 函式的概念用遞迴的方式加以實做
```c
void recursive_reverse_step(node_t *curr, node_t *prev, node_t **head)
{
/* next represent the element behind the current element in the list
* if next equal to NULL , then the element we traced is last in the list
*/
node_t *next = curr->next;
if (!next) {
*head = curr;
return;
}
/* prev represent the previous recursive function parameter curr
* it should be linked behind the current element
*/
curr->next = prev;
recursive_rev_step(next, curr, head);
}
void recursive_reverse(node_t **head)
{
if (!head)
return;
recursive_reverse_step(*head, NULL, head);
}
```
延伸問題三： Fisher–Yates shuffle
===
```c
void shuffle(node_t **head) {
srand(time(NULL));
/* Trace the length of the linked list */
int len = 0;
node_t **indirect = head;
while (*indirect) {
len++;
indirect = &(*indirect)->next;
}
/* Append shuffling result to another linked list */
node_t *new = NULL;
node_t **new_head = &new;
while (len) {
int random = rand() % len;
indirect = head;
while (random--)
indirect = &(*indirect)->next;
/* tmp means the node we randomly chosen */
node_t *tmp = *indirect;
/* Shift the element behind tmp to the position of tmp */
*indirect = (*indirect)->next;
/* put the node we chosen to the head of new list */
tmp->next = *new_head;
*new_head = tmp;
len--;
}
*head = *new_head;
}
```
* Step1 : 首先，先走訪整個原始的 linked list，算出原本的 linked list 有多長
* Step2 : 根據 舊linked list 長度生成一個不大於串列長度之隨機亂數並找到相對應節點
* Step3 : 將對應節點從舊 linked list 刪除 , 並將其新增至新的 linked list 的最前面 (也可以選擇新增至串列的最後面,但需要額外紀錄最後面的節點 )
* 回到 stpe2
Sign in with Wallet
Connect another wallet