# 2020q3 Homework1 (quiz1)
contributed by <`Sisker1111`>
###### tags: `進階電腦系統理論與實作`
[TOC]
## add_entry
```c=1
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;
}
```
### AA1
1. 第 3 行使用 pointer to pointer 的技巧存取 address of head.
2. 第 10~11 行是為了走到link-list的最後一個節點.
此處選擇(b)`*indirect = new_node`明顯不合理，new_node是準備要插入的新點，如果將`*indirect = new_node`的話，`(*indirect)->next`永遠都會是`NULL`，無法走訪 link-list.
### AA2
走訪到最後一個節點時，因 `*indirect == NULL`所以跳出 while，此時我們需要將`*indirect`指向要加入的新點，故選擇`*indirect = new_node`.
## swap_pair
```c=1
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;
}
```
### BB1
1. `swap_pair` 的功能為兩兩掉換，故for迴圈內條件是希望連跳兩個node.
2. 考試時這邊我原本選 `(b)` ` *node = (*node)->next->next`，但仔細想想此處只是要改變node指向的address而不是要修改 Link-list 的連接，故等號左邊要是`node`.
3. 因為 node 使用 pointer to pointer的技巧，此處要取 address of pointer，故答案選擇 `(e)` `node = &(*node)->next->next`
### BB2
1. 接著我們要開始對 node 做 swap 的工作，以下圖演示整個iteration 的第一步:
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
NULL1[label="...",shape=plaintext]
}
{
rank="same";
n[shape=plaintext,label="node"]
n->head->A
}
A->B->C->NULL1
}
```
* 第45行 `node_t *tmp = *node`
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red,label="head(tmp)"]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
NULL1[label="...",shape=plaintext]
}
{
rank="same";
n[shape=plaintext,label="node"]
n->head->A
}
A->B->C->NULL1
}
```
* 接著，此處是把 `*node` 指到的地址換成下一個節點的地址。因此 `BB2` 會是 `*node = (*node)->next;`，注意因為這邊是交換節點的位址，因此 是把`head`的 address 變成 B 的 address，也就是讓 head 指向 B，此時 B 變成新的開頭。
```graphviz
digraph graphname{
node[shape=box]
tmp[shape=plaintext]
n[shape=plaintext,label="node"]
m[shape=plaintext,label="head\n",fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
NULL1[label="...",shape=plaintext]
}
{
rank="same";
tmp->A
}
{
rank="same";
n->m->B
}
A->B->C->NULL1
}
```
* 然後把`tmp->next`指向`(*node)->next`，再把`*node->next`指回舊的 head，注意此時`*node`已經變成這個 link-list 新的 head，指標圖如下：
```graphviz
digraph graphname{
node[shape=box]
tmp[shape=plaintext]
n[shape=plaintext,label="node"]
m[shape=plaintext,label="head\n",fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
NULL[label="...",shape=plaintext]
}
{
rank="same";
tmp->A
}
{
rank="same";
n->m->B
}
B->A->C->NULL
}
```
## reverse
```c=1
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
CCC;
head = next;
}
return cursor;
}
```
### CCC
1. `cursor` 用來暫存每次 iterative 時舊的`head`.
2. `node_t *next = head->next`用來暫存新的 `head` .
3. 在更新`head`前，需先將 `head->next`指到舊的`head`，並且用`cursor`暫存舊的`head`，符合的選項指有`(e)` `head->next = cursor; cursor = head`
## 延伸問題 2
### reverse 的 pointer to pointer 版本
```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;
}
```
只要將傳入參數改成`&head`，function內的`head` 都換成 `*head` 即好，因為在function內直接設定`*head`了，因此不需要回傳值，最後一行`*head = cursor;`是為了避免最後`*head`被設為NULL.
### swap_pair 的 pointer to pointer 版本
```c=
void swap_pair(node_t **head)
{
node_t *tmp = NULL;
for(; *head && (*head)->next; head = &(*head)->next->next ){
tmp = *head;
*head = (*head)->next;
tmp->next = (*head)->next;
(*head)->next = tmp;
}
}
```
因為直接使用 pointer to pointer 的技巧，不需要原來的`node_t **node = &head`，最後`head`會自然的指向了新的`head`，不需要用額外的程式碼來處理。
## 延伸問題 3 - recursive reverse
```c=
node_t *rev_reverse(node_t **head, node_t *node)
{
if (!node->next) {
*head = node;
return node;
}
rev_reverse(head, node->next);
node->next->next = node;
node->next = NULL ;
return node;
}
void recursive_reverse(node_t **head)
{
if(*head && (*head)->next){
node_t *cursor = *head;
rev_reverse(head, (*head)->next);
cursor->next->next = cursor;
cursor->next = NULL;
}
}
```
### 程式解說
思考流程是這樣的:
1. 先判斷此link-list是否為NULL或是只有一個Element，如果不是以上兩種情況則進入遞迴.
2. 一直遞迴到link-list最後一個node，`*head = node;`會把 head 指向最後一個node，接著把最後一個return.
3. `node->next->next = node;`將此時`node->next`的pointer反向指回來，並把`node->next`設為`NULL`，同理，整個recursive做完後，也要將原本`head`的`next`指回原本的`head`.
* 這個部分寫得並不好，為了讓 recursive 到最後時更新 head 的指向的 address，我在 recursive 內不斷傳入 head 這個 pointer 的 address，程式看起來並不美.
## 延伸問題 4 - Fisher-Yates Shuffle
```c=
void shuffle(node_t **head){
int link_length=0;
srand(time(NULL));
node_t *cursor, *old_head, **indirect;
cursor = old_head = *head;
for (; cursor ; cursor = cursor->next)
link_length++; /* interate */
*head = NULL;
while(link_length){ // link-list is non-empty
indirect = &old_head;
for(int i = rand()%link_length; i > 0; i--){
indirect = &(*indirect)->next;
}
cursor = *indirect;
*indirect = (*indirect)->next;
cursor->next = *head;
*head = cursor;
link_length--;
}
}
```
### 程式解說
+ 6: 取得 link-list 的長度
+ 10~14:用`indirect`來走訪原本的link-list，找到隨機出來的節點
+ 15: cursor 在前面用來走訪link-list計算長度，在這用來暫存節點
+ 16~18: 將這個節點從舊 link-list remove 並新增到新 link-list 的head
+ 19: 舊 link-list 長度-1.
Sign in with Wallet
Connect another wallet