# 2020q3 Homework1 (quiz1)
contributed by < `Veternal1226` >
###### tags: `sysprog2020`
---
:::info
延伸問題:
- [x] 1. 解釋上述程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現;
- [x] 2. 函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = ... 的更新，請用指標的指標來改寫，並避免回傳指標;
- [x] 3. 以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_recursive，隨後在 reverse 函式中呼叫 rev_recursive;
- [ ] 4. 針對 singly-linked list 的節點，實作 Fisher–Yates shuffle，你應該儘量降低記憶體的使用量;
:::
## node_t架構:
```c
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
```graphviz
digraph structs {
rankdir=LR;
node[shape=record]
struct0 [label="{<value> value|<next> next }"];
struct1 [label="{<value> ...|<next> ... }"];
struct0:next:struct1 -> struct1[ tailclip=true]
}
```
---
### add_entry
將新節點加至 list 尾端
```c=10
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;
assert(new_node); // AA1
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node; // AA2
return;
}
```
indirect 這邊使用了 pointer to pointer ，代表指向 \*head 的指標
以下圖為例:
```graphviz
digraph structs {
node[shape=record]
pointer0 [label="{<pointer> indirect}"];
pointer1 [label="{<pointer> head}"];
node0 [shape=box,label=0];
node1 [shape=box,label=1];
node2 [shape=box,label=2];
NULL [shape=box,label=NULL]
node0->node1->node2->NULL
pointer0 -> pointer1 [tailclip=true];
pointer1 -> node0 [tailclip=true];
{rank=same;node0;node1;node2;NULL};
}
```
\*\*indirect 表 list node 0
\*indirect 表 head
indirect 表 &head
第19&20行用來將 indirect 指向 list 最尾端，因此判斷此 function 是實作將新 node 插入 list 尾端。
因此18行應為檢查新節點有沒有 malloc 成功，21行應為把新節點加入 list 中。
:::success
故AA1 = `(a)assert(new_node)`
AA2 = `(b)*indirect = new_node`
:::
圖解插入新 node 前的狀態:
```graphviz
digraph structs {
node[shape=record]
pointer0 [label="{<pointer> indirect}"];
pointer1 [label="{<pointer> ...}"];
pointer2 [label="{<pointer> head}"];
node0 [shape=box,label=0];
node1 [shape=box,label=1];
node2 [shape=box,label=2];
NULL [shape=box,label=NULL]
node0->node1->node2->NULL
pointer0 -> pointer1 [tailclip=true];
pointer1 -> NULL [tailclip=true];
pointer2 -> node0 [tailclip=true];
{rank=same;node0;node1;node2;NULL};
}
```
---
### find_entry
回傳指定值(value) 位在 list 中的哪個 node_t
```c=25
node_t *find_entry(node_t *head, int value)
{
node_t *current = head;
for (; current && current->value != value; current = current->next)
/* interate */;
return current;
}
```
實作方式為遍歷 list 直到 current->value == 指定值，
回傳 current 位置
---
### remove_entry
移除指定位置的一個節點
```c=33
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
return;
}
```
實作方式為遍歷 list 直到 \*indirect == entry
透過將 \*indirect 指標指向 entry->next 來跳過 entry
---
### swap_pair
```c=45
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; /*BB1*/node = &(*node)->next->next/*BB1*/) {
node_t *tmp = *node;
*node = (*node)->next; // BB2
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
for 迴圈的第三個分區用來放做完一次內容後要執行的程式碼，經驗來說通常會放 index 移動或指標移動。
swap_pair 的作用是兩兩相鄰的交換，因此每次移動要移兩次 next ，因此 BB1 要填的內容我一開始的想法是填入`*node = (*node)->next->next`。
但實驗後發現 head 會跑掉，因為改動 \*node會改到 head 的值，因此應該要改的是再上一層的位址，也就是 `node = &(*node)->next->next`
:::success
因此 BB1 = `(e) node = &(*node)->next->next`
:::
BB2 在流程中比較好解釋
流程:
初始狀態:
```graphviz
digraph structs {
node[shape=record]
pointer0 [label="{<pointer> tmp}"];
pointer1 [label="{<pointer> node}"];
node0 [shape=box,label=0];
node1 [shape=box,label=1];
node2 [shape=box,label=2];
NULL [shape=box,label="..."]
node0->node1
node1->node2
node2->NULL
pointer1 -> node0 [tailclip=true];
pointer0 -> node0 [tailclip=true];
{rank=same;node0;node1;node2;NULL};
}
```
\*node = (\*node)->next; //BB2
因為這邊第一次就是要改 head 值，所以直接用 \*node 沒問題，把 \*node 改指到 \*node->next
```graphviz
digraph structs {
node[shape=record];
pointer0 [label="{<pointer> tmp}"];
pointer1 [label="{<pointer> node}"];
node0 [shape=box,label=0];
node1 [shape=box,label=1];
node2 [shape=box,label=2];
NULL [shape=box,label="..."]
node0->node1
node1->node2
node2->NULL
pointer1 -> node1 [tailclip=true];
pointer0 -> node0 [tailclip=true];
{rank=same;node0;node1;node2;NULL};
}
```
tmp->next = (*node)->next;
```graphviz
digraph structs {
node[shape=record];
pointer0 [label="{<pointer> tmp}"];
pointer1 [label="{<pointer> node}"];
node0 [shape=box,label=0];
node1 [shape=box,label=1];
node2 [shape=box,label=2];
NULL [shape=box,label="..."]
node0->node2
node1->node2
node2->NULL
pointer0 -> node0 [tailclip=true];
pointer1 -> node1 [tailclip=true];
{rank=same;node0;node1;node2;NULL};
}
```
(*node)->next = tmp;
```graphviz
digraph structs {
node[shape=record]
pointer0 [label="{<pointer> tmp}"];
pointer1 [label="{<pointer> node}"];
node0 [shape=box,label=0];
node1 [shape=box,label=1];
node2 [shape=box,label=2];
NULL [shape=box,label="..."]
node0->node2
node1->node0
node2->NULL
pointer0 -> node0 [tailclip=true];
pointer1 -> node1 [tailclip=true];
{rank=same;node0;node1;node2;NULL};
}
```
node = &(*node)->next->next
```graphviz
digraph structs {
node[shape=record]
pointer1 [label="{<pointer> node}"];
node0 [shape=box,label=0];
node1 [shape=box,label=1];
node2 [shape=box,label=2];
NULL [shape=box,label="..."]
node0->node2
node1->node0
node2->NULL
pointer1 -> node2 [tailclip=true];
{rank=same;node0;node1;node2;NULL};
}
```
:::success
因此 BB2 = `(c)*node = (*node)->next`
:::
---
### reverse
```c=56
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
/*CCC*/
head->next = cursor;
cursor = head;
/*CCC*/
head = next;
}
return cursor;
}
```
cursor 用來表示新 list 的開頭
每次迴圈將 next 記錄下來
把head所指節點的 next 轉向 cursor 所指位置
> head->next = cursor;
再把 cursor 指到此節點
> cursor = head;
:::success
因此 CCC = `(b)head->next = cursor; cursor = head`
:::
流程:
```graphviz
digraph structs {
node[shape=record];
pointer0 [label="{<pointer> cursor}"];
pointer1 [label="{<pointer> head}"];
NULL0 [shape=box,label="NULL"]
node0 [shape=box,label=0];
node1 [shape=box,label=1];
node2 [shape=box,label=2];
NULL1 [shape=box,label="NULL"]
node0->node1
node1->node2
node2->NULL1
pointer0 -> NULL0 [tailclip=true];
pointer1 -> node0[tailclip=true];
{rank=same;NULL0;node0;node1;node2;NULL1};
}
```
while (head) {
node_t *next = head->next;
```graphviz
digraph structs {
node[shape=record];
pointer0 [label="{<pointer> cursor}"];
pointer1 [label="{<pointer> head}"];
pointer2 [label="{<pointer> next}"];
NULL0 [shape=box,label="NULL"]
node0 [shape=box,label=0];
node1 [shape=box,label=1];
node2 [shape=box,label=2];
NULL1 [shape=box,label="NULL"]
node0->node1
node1->node2
node2->NULL1
pointer0 -> NULL0 [tailclip=true];
pointer1 -> node0[tailclip=true];
pointer2 -> node1 [tailclip=true];
{rank=same;NULL0;node0;node1;node2;NULL1};
}
```
head->next = cursor; //CCC
```graphviz
digraph structs {
node[shape=record];
pointer0 [label="{<pointer> cursor}"];
pointer1 [label="{<pointer> head}"];
pointer2 [label="{<pointer> next}"];
NULL0 [shape=box,label="NULL"]
node0 [shape=box,label=0];
node1 [shape=box,label=1];
node2 [shape=box,label=2];
NULL1 [shape=box,label="NULL"]
node0->NULL0
node1->node2
node2->NULL1
pointer0 -> NULL0 [tailclip=true];
pointer1 -> node0[tailclip=true];
pointer2 -> node1 [tailclip=true];
{rank=same;NULL0;node0;node1;node2;NULL1};
}
```
cursor = head; //CCC
```graphviz
digraph structs {
node[shape=record];
pointer0 [label="{<pointer> cursor}"];
pointer1 [label="{<pointer> head}"];
pointer2 [label="{<pointer> next}"];
NULL0 [shape=box,label="NULL"]
node0 [shape=box,label=0];
node1 [shape=box,label=1];
node2 [shape=box,label=2];
NULL1 [shape=box,label="NULL"]
node0->NULL0
node1->node2
node2->NULL1
pointer0 -> node0 [tailclip=true];
pointer1 -> node0[tailclip=true];
pointer2 -> node1 [tailclip=true];
{rank=same;NULL0;node0;node1;node2;NULL1};
}
```
head = next;
```graphviz
digraph structs {
node[shape=record];
pointer0 [label="{<pointer> cursor}"];
pointer1 [label="{<pointer> head}"];
pointer2 [label="{<pointer> next}"];
NULL0 [shape=box,label="NULL"]
node0 [shape=box,label=0];
node1 [shape=box,label=1];
node2 [shape=box,label=2];
NULL1 [shape=box,label="NULL"]
node0->NULL0
node1->node2
node2->NULL1
pointer0 -> node0 [tailclip=true];
pointer1 -> node1[tailclip=true];
pointer2 -> node1 [tailclip=true];
{rank=same;NULL0;node0;node1;node2;NULL1};
}
```
中間步驟省略，迴圈結束後應該會長這樣
```graphviz
digraph structs {
node[shape=record];
pointer0 [label="{<pointer> cursor}"];
pointer1 [label="{<pointer> head}"];
NULL0 [shape=box,label="NULL"]
node0 [shape=box,label=0];
node1 [shape=box,label=1];
node2 [shape=box,label=2];
NULL1 [shape=box,label="NULL"]
node0->NULL0
node1->node0
node2->node1
pointer0 -> node2 [tailclip=true];
pointer1 -> NULL1[tailclip=true];
{rank=same;NULL0;node0;node1;node2;NULL1};
}
```
cursor 指向 reverse 完後的 list ，這邊直接回傳 cursor。
( 在後面改寫成 pointer to pointer 時，要加一步 \*head=cursor )
---
## swap_pair 和 reverse 改寫
### swap_pair
```c=45
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;
}
```
把 &head 改寫成 \*(&head) 跟 head 都能動
### reverse
```c=56
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;
return;
}
```
把所有 head 改寫成 \*head ，並加上前面說到的 \*head=cursor 後就能動
---
### recursive reverse
參考自[chwchao](https://hackmd.io/@6R35tGUKTmC5_lms3b3V3g/SyGYIBDVw)
```c=56
node_t *rev_recursive(node_t *head)
{
if (!head || !(head)->next) {
return head;
}
node_t *new_head = rev_recursive(head->next);
if (head->next) {
head->next->next = head; // change head->next's next to previous layer's head
}
head->next = NULL; // always set new tail to NULL
return new_head;
}
```
先走到 list 尾端，將尾端指標作為回傳值回傳，每往上一層，將下方一層的 next (head->next->next) 轉向此層的head，所以程式碼為 `head->next->next = head;`
要確保 reverse 完的 list 最後指向 NULL: `head->next = NULL`
原本的reverse改寫成:
```c=70
void reverse(node_t **head)
{
*head = rev_recursive(*head);
return;
}
```
Sign in with Wallet
Connect another wallet