# 2020q3 Homework1 (quiz1)
contributed by < `zzzxxx00019` >
## 作業要求
* 重新回答[第 1 周測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)，連同附帶的「延伸問題」。
* 解釋程式運作原理時，應提供對應的 Graphviz 圖例。
## 題目
考慮一個單向 linked list，其結構定義為:
```cpp
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
已知不存在 circular (環狀結構)，接下來將對該單向 linked list 進行下列操作:
* add_entry: 新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy
* remove_entry: 移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)
* swap_pair: 交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 1->2->3->4，則該回傳 2->1->4->3
* reverse: 將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1
對應的程式碼如下:
```c=
#include <stdio.h>
#include <stdlib.h>
typedef struct __node {
int value;
struct __node *next;
} node_t;
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;
}
node_t *find_entry(node_t *head, int value)
{
node_t *current = head;
for (; current && current->value != value; current = current->next)
/* interate */;
return current;
}
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
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;
}
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
CCC;
head = next;
}
return cursor;
}
void print_list(node_t *head)
{
for (node_t *current = head; current; current = current->next)
printf("%d ", current->value);
printf("\n");
}
int main(int argc, char const *argv[])
{
node_t *head = NULL;
print_list(head);
add_entry(&head, 72);
add_entry(&head, 101);
add_entry(&head, 108);
add_entry(&head, 109);
add_entry(&head, 110);
add_entry(&head, 111);
print_list(head);
node_t *entry = find_entry(head, 101);
remove_entry(&head, entry);
entry = find_entry(head, 111);
remove_entry(&head, entry);
print_list(head);
/* swap pair.
* See https://leetcode.com/problems/swap-nodes-in-pairs/
*/
head = swap_pair(head);
print_list(head);
head = reverse(head);
print_list(head);
return 0;
}
```
參考執行輸出: (第 1 行是換行符號)
```c=
72 101 108 109 110 111
72 108 109 110
108 72 110 109
109 110 72 108
```
請補完程式碼。
參考解答:
* AA1 = assert(new_node)
* AA2 = *indirect = new_node
* BB1 = node = &(*node)->next->next
* BB2 = *node = (*node)->next
* CCC = head->next = cursor; cursor = head
## 程式碼解析
### 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;
assert(new_node);
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node;
}
```
* 功能：建立一個存放new_value的node，如果head不存在，將新建立的node設為list的head，否則將node插入head的尾端。
* 流程：透過`**indirect`，尋找head的尾端，並將最尾端以new_node取代。
* 詳細執行狀況與說明：
* ==測試用程式碼==
```cpp
int main(int argc, char const *argv[])
{
node_t *head = NULL;
print_list(head);
add_entry(&head, 72);
add_entry(&head, 101);
add_entry(&head, 108);
add_entry(&head, 109);
add_entry(&head, 110);
add_entry(&head, 111);
print_list(head);
return 0;
}
```
```cpp
72 101 108 109 110 111
```
程式執行初期，我們建立了一個指標`*head`，並將head指向NULL，即尚未分配記憶體空間。
隨後使用print_list印出linked list內容，因head目前仍為NULL，因此直接執行換行的動作。
接著我們透過add_entry，依序將value以node方式插入head的末端。
下表為建立新的node後，分配給其的記憶體位置：
| value | address |
| - | - |
|72 |0x562d080ad670 |
|101 |0x562d080ad690 |
|108 |0x562d080ad6b0 |
|109 |0x562d080ad6d0 |
|110 |0x562d080ad6f0 |
|111 |0x562d080ad710 |
而最後鏈結型態則為：
| value| address | next |
| --- | ------- | ---- |
|72 |0x562d080ad670|0x562d080ad690|
|101 |0x562d080ad690|0x562d080ad6b0|
|108 |0x562d080ad6b0|0x562d080ad6d0|
|109 |0x562d080ad6d0|0x562d080ad6f0|
|110 |0x562d080ad6f0|0x562d080ad710|
|111 |0x562d080ad710|(nil) |
起初執行add_entry後，因main head尚未指向任何linked list結構，因此new_node被設為linked list的head。
```graphviz
digraph add_entry
{
rankdir=LR ;
node [shape = record]
head [label="{<name> (add_entry)head }"];
main_head [label="{<name> (main)head}"];
indirect [label="{<name> indirect }"];
head -> main_head ;
indirect -> main_head ;
}
```
而後執行add_entry後，indirect將對所有節點依循拜訪，尋找next為NULL的node，並將new_node設為最後一個node->next。
```graphviz
digraph add_new_node
{
rankdir=LR ;
node [shape = record]
node_1 [label = "{ <value>72 | <address>0x562d080ad670 | <ref> }"] ;
node_2 [label = "{ <value>101 | <address>0x562d080ad690 | <ref> }"] ;
node_3 [label = "{ <value>108 | <address>0x562d080ad6b0 | <ref> }"] ;
node_4 [label = "{ <value>Empty | <address>NULL }"] ;
indirect [label = "{<name>indirect}"]
node_1:ref -> node_2 ;
node_2:ref -> node_3 ;
node_3:ref -> node_4 ;
indirect -> node_4 ;
}
```
* 功能：尋找存放value的node，並將該node回傳。
* 流程：特過current尋訪各個節點，如果current->value為目標value，則停止迴圈，否則繼續尋訪直到current為NULL，最終回傳NULL。
### find_entry
```cpp
node_t *find_entry(node_t *head, int value)
{
node_t *current = head;
for (; current && current->value != value; current = current->next);
return current;
}
```
### remove_entry
* 功能：移除linked list中的指定節點。
* 流程：透過find_entry尋找欲刪除的entry，並透過remove_entry將其移除。
```cpp
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
```
* 詳細執行狀況與說明
* ==測試用程式碼==
```cpp
int main(int argc, char const *argv[])
{
node_t *head = NULL;
add_entry(&head, 72);
add_entry(&head, 101);
add_entry(&head, 108);
add_entry(&head, 109);
add_entry(&head, 110);
add_entry(&head, 111);
print_list(head);
node_t *entry = find_entry(head, 101);
remove_entry(&head, entry);
entry = find_entry(head, 111);
remove_entry(&head, entry);
print_list(head);
return 0;
}
```
```cpp
72 101 108 109 110 111
72 108 109 110
```
先透過`find_entry`回傳欲搜尋存放該value的節點指標。
接著在`remove_entry`的部分，透過對照`*indirect`所指向的address是否為entry的值作為對比依據，並透過while迴圈依序尋訪。
找到後讓`*indirect`所存放的內容改為`entry->next`後，刪除目標節點。
### swap_pair
目的：交換一對相鄰的節點，給定`1->2->3->4`，則回傳`2->1->4->3`。
流程：如果`node`與`node->next`都存在，將兩節點交換，否則結束迴圈。
```cpp
node_t *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;
}
```
* 詳細執行狀況說明
* ==測試用程式碼==
```cpp
int main(int argc, char const *argv[])
{
node_t *head = NULL;
add_entry(&head, 72);
add_entry(&head, 101);
add_entry(&head, 108);
add_entry(&head, 109);
add_entry(&head, 110);
add_entry(&head, 111);
print_list(head);
head = swap_pair(head);
print_list(head);
return 0;
}
```
```cpp
72 101 108 109 110 111
101 72 109 108 111 110
```
`進入迴圈初期，符合規則：*node && (*node)->next ;`
```graphviz
digraph
{
rankdir=LR ;
node [shape = record] ;
Null [shape=plaintext, label = "Null"] ;
node_p [shape=plaintext, fontcolor=blue, label = "*node"] ;
node_p ->node_1 -> node_2 -> node_3 -> node_4 -> Null ;
}
```
`node_t *tmp= *node ; *node= (*node)->next ;`
```graphviz
digraph
{
rankdir=LR ;
node [shape = record] ;
Null [shape=plaintext, label = "Null"] ;
node_p [shape=plaintext, fontcolor=blue, label = "*node"] ;
temp [shape=plaintext, fontcolor=red, label = "*temp"] ;
node_1 -> node_2 -> node_3 -> node_4 -> Null ;
temp -> node_1 ;
node_p -> node_2 ;
}
```
`tmp->next = (*node)->next ;`
```graphviz
digraph
{
rankdir=LR ;
node [shape = record] ;
Null [shape=plaintext, label = "Null"] ;
node_p [shape=plaintext, fontcolor=blue, label = "*node"] ;
temp [shape=plaintext, fontcolor=red, label = "*temp"] ;
node_2 -> node_3 -> node_4 -> Null ;
temp -> node_1 -> node_3 ;
node_p -> node_2 ;
}
```
`(*node)->next = tmp`
```graphviz
digraph
{
rankdir=LR ;
node [shape = record] ;
Null [shape=plaintext, label = "Null"] ;
node_p [shape=plaintext, fontcolor=blue, label = "*node"] ;
temp [shape=plaintext, fontcolor=red, label = "*temp"] ;
node_2 -> node_1 -> node_3 -> node_4 -> Null ;
temp -> node_1 ;
node_p -> node_2 ;
}
```
再進入下一次迴圈，`*node`指標狀態
```graphviz
digraph
{
rankdir=LR ;
node [shape = record] ;
Null [shape=plaintext, label = "Null"] ;
node_p [shape=plaintext, fontcolor=blue, label = "*node"] ;
node_2 -> node_1 -> node_3 -> node_4 -> Null ;
node_p -> node_3 ;
}
```
### reverse
* 目的：將linked list反轉。
```cpp
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
head->next = cursor;
cursor = head;
head = next;
}
return cursor;
}
```
* 步驟解析：
`初始狀態`
```graphviz
digraph
{
rankdir=LR ;
node [shape = record] ;
head [shape=plaintext, fontcolor=red, label = "*head"] ;
cursor [shape=plaintext, fontcolor=blue, label = "*cursor"] ;
Nul [shape=plaintext, label = "..."] ;
node_1 [label = "{<name> node_1}"] ;
node_2 [label = "{<name> node_2}"] ;
node_3 [label = "{<name> node_3}"] ;
node_1 -> node_2 -> node_3 -> Nul ;
head -> node_1 ;
cursor -> NULL ;
}
```
`node_t *next=head->next`
```graphviz
digraph
{
rankdir=LR ;
node [shape = record]
head [shape=plaintext, fontcolor=red, label = "*head"] ;
cursor [shape=plaintext, fontcolor=blue, label = "*cursor"] ;
next [shape=plaintext, label = "*next"] ;
Nul [shape=plaintext, label = "..."] ;
node_1 [label = "{<name> node_1}"] ;
node_2 [label = "{<name> node_2}"] ;
node_3 [label = "{<name> node_3}"] ;
node_1 -> node_2 -> node_3 -> Nul ;
head -> node_1 ;
cursor -> NULL ;
next -> node_2 ;
}
```
`head->next = cursor; cursor = head;`
```graphviz
digraph
{
rankdir=LR ;
node [shape = record]
head [shape=plaintext, fontcolor=red, label = "*head"] ;
cursor [shape=plaintext, fontcolor=blue, label = "*cursor"] ;
next [shape=plaintext, label = "*next"] ;
Nul [shape=plaintext, label = "..."] ;
node_1 [label = "{<name> node_1}"] ;
node_2 [label = "{<name> node_2}"] ;
node_3 [label = "{<name> node_3}"] ;
node_2 -> node_3 -> Nul ;
next -> node_2 ;
head -> node_1 ;
cursor -> node_1 -> NULL ;
}
```
`head = next`
```graphviz
digraph
{
rankdir=LR ;
node [shape = record]
head [shape=plaintext, fontcolor=red, label = "*head"] ;
cursor [shape=plaintext, fontcolor=blue, label = "*cursor"] ;
next [shape=plaintext, label = "*next"] ;
Nul [shape=plaintext, label = "..."] ;
node_1 [label = "{<name> node_1}"] ;
node_2 [label = "{<name> node_2}"] ;
node_3 [label = "{<name> node_3}"] ;
next -> node_2 -> node_3 -> Nul ;
head -> node_2 ;
cursor -> node_1 -> NULL ;
}
```
`迴圈執行完最後結果，回傳cursor指標`
```graphviz
digraph
{
rankdir=LR ;
node [shape = record]
head [shape=plaintext, fontcolor=red, label = "*head"] ;
cursor [shape=plaintext, fontcolor=blue, label = "*cursor"] ;
next [shape=plaintext, label = "*next"] ;
Nul [shape=plaintext, label = "..."] ;
node_1 [label = "{<name> node_1}"] ;
node_2 [label = "{<name> node_2}"] ;
node_3 [label = "{<name> node_3}"] ;
cursor -> node_3 -> node_2 -> node_1 -> NULL ;
next -> Nul ;
head -> Nul ;
}
```
### print_list
目的：將所有節點的value印出。
流程：透過迴圈，如果node存在，印出node->value，透過*current尋訪所有節點。
```cpp
void print_list(node_t *head)
{
for (node_t *current = head; current; current = current->next)
printf("%d ", current->value);
printf("\n");
}
```
## pointer to pointer改寫程式碼
### pointer與pointer to pointer兩者差異
* 下面將列出function透過`node_t **head`與`node_t *head`的對照圖。
* 透過`node_t *head`圖示：
```graphviz
digraph
{
rankdir=LR ;
node [shape = record] ;
main_head [shape=plaintext, fontcolor=blue, label = "*main_head"] ;
entry_head [shape=plaintext, fontcolor=red, label = "*entry_head"] ;
Null [shape=plaintext, label="Null"] ;
entry_head -> main_head -> node_1 -> node_2 -> node_3 ->Null ;
}
```
* 即對main_head進行取值運算，得到的是node_1的address，透過`node_t **head`圖示了解：
```graphviz
digraph
{
rankdir=LR ;
node [shape = record] ;
main_head [shape=plaintext, fontcolor=blue, label = "*main_head"] ;
entry_head [shape=plaintext, fontcolor=red, label = "**entry_head"] ;
Null [shape=plaintext, label="Null"] ;
main_head -> node_1 -> node_2 -> node_3 -> Null ;
entry_head -> node_1 ;
}
```
### Swap
* 透過上圖了解，原本程式碼`node_t **node = &head`即是對main_head進行取值得到node_1的實際address，而透過`node_t **head`，entry_head已對main_head進行取值，因此這邊只要直接將這行程式碼改為`node_t **node = head`即可。
```cpp
void swap_pair_p2p(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
* 透過上圖了解，因entry_head為對main_head取值結果，因此效果相當於main_head，透過main_head尋訪並且逐一翻轉，最後再將main_head接回翻轉後的linked list。
```cpp
void reverse_p2p(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相似，不同的是，將while以recursive的方式進行取代，原本的function執行完後會判斷`*head`是否為空指標，現在則是以判斷式的方式檢查是否為空指標，執行完後再呼叫自己本身(`reverse_rec`)，直到結束。
```cpp
void reverse_rec(node_t **head, node_t *cursor)
{
if(*head)
{
node_t *next = (*head)->next ;
(*head)->next = cursor ;
cursor = *head ;
*head = next ;
reverse_rec(head,cursor) ;
}
else *head = cursor ;
}
```
## Fisher–Yates shuffle
* 簡介：洗牌演算法需 $O(n)$ 的時間複雜度去產生設定長度的亂數，又需要$O(n)$的時間複雜度去執行每次的節點的查訪，因此總時間複雜度為 $O(n^2)$
* 流程：
* 透過for迴圈計算linked list總長度
* 透過 `rand()` 取得亂數，範圍為1~length
* 透過與 `head` 做 `value` 的交換，降低記憶體使用量
* 每當產生一筆隨機數，`head` 向後推移一格，`length` 減1
* 實作程式碼：
```cpp=
void shuffle(node_t **head) {
if (!*head)
return;
int length = 0;
node_t **tmp_head = head;
for (; *tmp_head ; tmp_head = &(*tmp_head)->next, length += 1);
srand(time(NULL));
tmp_head = head ;
while (length > 1)
{
int Roll = rand() % length + 1;
node_t **indirect = tmp_head;
for(; Roll!=1 ; Roll--, indirect=&(*indirect)->next) ;
int tmp_value = (*tmp_head)->value;
(*tmp_head)->value = (*indirect)->value;
(*indirect)->value = tmp_value;
tmp_head = &(*tmp_head)->next;
length -= 1;
}
}
```
Sign in with Wallet
Connect another wallet