# 2020q3 Homework1 (quiz1)
###### tags: `sysprog2020` `homework`
contributed by <`JKChun`>
- [**Linked List** 2020q3 第一周測驗題連結](https://hackmd.io/@sysprog/sysprog2020-quiz1)
- [繳交作業區](https://hackmd.io/@sysprog/sysprog2020-quiz1)
## 程式運作原理
### Function 1 : `add_entry`
- Function 的功能為：
>新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy
- Source Code：
```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); #(AA1)
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node; #(AA2)
}
```
- Function 的 input 為**指向 node 的指標的指標** `head` 和一個整數型別的變數`new_value`
- **第1行** 建立一個**指向 node 的指標的指標** `indirect` ，並指派 `head` 給`indirect`
```graphviz
digraph graphname{
node[shape=box];
rankdir=LR;
subgraph list{
rankdir = LR;
A[label=head_node];
B[label=node_2];
C[label=node_3];
NULL1[label=NULL,shape=plaintext];
A->B->C->NULL1;
}
subgraph pointer{
rank=LR;
indirect[shape=plaintext, fontcolor=blue, label="**indrect"];
head[shape=plaintext, fontcolor=blue, label="**head"];
head_pointer[shape=plaintext, fontcolor=red];
head->head_pointer[headport=n];
indirect->head_pointer[headport=n];
head_pointer->A;
}
}
```
- **2到4行** 用 `malloc` 分配記憶體空間給 new_node，並指派 `new value` 以及指向 `NULL`
- **AA1** `assert(new_node)` 確定 new_node 有成功建立
- **6到7行** 讓`indriect`指向 `linked_list` 最後一個節點的 `next`
- **AA2** `*indirect = new_node` 最後將 new_node 指派給 `next` ，讓 new_node 變成 `linked_list` 的最後一個 node
### Function 2 : `remove_entry`
- Function 的功能為：
>移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)
- Source Code：
```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);
}
```
- **第1行** 建立一個**指向 node 的指標的指標** `indirect` ，並指派 `head` 給 `indirect`
- **第2到3行** 此部分是要將 `indirect` 指向 `entry node` 前一個 node 的 `next`
```graphviz
digraph {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="<ptr> node_2|{ <data> 2 | <ref> } "];
node_3 [label="<ptr> entry|{ <data> 3 | <ref> } "];
node_4 [label="<ptr> node_4|{ <data> 4 | <ref> } "];
head[shape=plaintext, fontcolor=blue, label="**head"];
indirect[shape=plaintext, fontcolor=blue, label="**indirect"];
head_pointer[shape=plaintext, fontcolor=red];
NULL1[label=NULL,shape=plaintext];
node_1:ref:c -> node_2:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:ref:c -> node_3:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_3:ref:c -> node_4:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_4:ref:c -> NULL1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
indirect -> node_2:ref
head -> head_pointer[headport=n];
head_pointer -> node_1:ptr;
}
```
- **第4行** 利用 `indirect` 更改 `entry node` 前一個 node 的 `next` ，讓它直接指向 `entry node` 的下一個 node
```graphviz
digraph {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="<ptr> node_2|{ <data> 2 | <ref> } "];
node_3 [label="<ptr> entry|{ <data> 3 | <ref> } "];
node_4 [label="<ptr> node_4|{ <data> 4 | <ref> } "];
head[shape=plaintext, fontcolor=blue, label="**head"];
indirect[shape=plaintext, fontcolor=blue, label="**indirect"];
head_pointer[shape=plaintext, fontcolor=red];
NULL1[label=NULL,shape=plaintext];
node_1:ref:c -> node_2:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:ref:c -> node_4:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, fontcolor=red];
node_3:ref:c -> node_4:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_4:ref:c -> NULL1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
indirect -> node_2:ref
head -> head_pointer[headport=n];
head_pointer -> node_1:ptr;
}
```
- **第5行** 用 `free` 釋放 entry 占用的記憶體
```graphviz
digraph {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="<ptr> node_2|{ <data> 2 | <ref> } "];
node_4 [label="<ptr> node_4|{ <data> 4 | <ref> } "];
head[shape=plaintext, fontcolor=blue, label="**head"];
indirect[shape=plaintext, fontcolor=blue, label="**indirect"];
head_pointer[shape=plaintext, fontcolor=red];
NULL1[label=NULL,shape=plaintext];
node_1:ref:c -> node_2:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:ref:c -> node_4:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, fontcolor=red];
node_4:ref:c -> NULL1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
indirect -> node_2:ref
head -> head_pointer[headport=n];
head_pointer -> node_1:ptr;
}
```
### Function 3 : `swap_pair`
- Function 的功能為：
>交換一對相鄰的節點，給定 1->2->3->4，則該回傳 2->1->4->3
- Source Code：
```cpp
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next (#BB1)) {
node_t *tmp = *node;
*node = (*node)->next; (#BB2)
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
- 此 function 的功能就是把 `linked list` 裡的 node 按照順序兩兩一組，把順序反過來，所以 `for 迴圈` 的判斷條件很簡單，就是沒有成對的 node 就跳出迴圈
- 也因為是一次操作兩個 node ，所以 **BB1** 一次跳過兩個 node
- 和一般的 swap function 思維一樣，在 `for 迴圈` 裡先額外建一個 `temp` 指標
- 流程如下：
`node_t *tmp = *node;`
```graphviz
digraph {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="<ptr> node_2|{ <data> 2 | <ref> } "];
node_3 [label="<ptr> node_3|{ <data> 3 | <ref> } "];
head[shape=plaintext, fontcolor=blue, label="*head"];
node_p[shape=plaintext, fontcolor=blue, label="**node"];
temp[shape=plaintext, fontcolor=blue, label="*temp"];
NULL1[label=NULL,shape=plaintext];
node_1:ref:c -> node_2:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:ref:c -> node_3:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, fontcolor=red];
node_3:ref:c -> NULL1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_p -> head;
head -> node_1:ref[headport=n];
temp -> node_1:ref[headport=n];
}
```
`*node = (*node)->next; (#BB2)`
```graphviz
digraph {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="<ptr> node_2|{ <data> 2 | <ref> } "];
node_3 [label="<ptr> node_3|{ <data> 3 | <ref> } "];
head[shape=plaintext, fontcolor=blue, label="*head"];
node_p[shape=plaintext, fontcolor=blue, label="**node"];
temp[shape=plaintext, fontcolor=blue, label="*temp"];
NULL1[label=NULL,shape=plaintext];
node_1:ref:c -> node_2:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:ref:c -> node_3:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, fontcolor=red];
node_3:ref:c -> NULL1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_p -> head;
head -> node_2:ptr;
temp -> node_1:ptr;
}
```
`tmp->next = (*node)->next;`
```graphviz
digraph {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="<ptr> node_2|{ <data> 2 | <ref> } "];
node_3 [label="<ptr> node_3|{ <data> 3 | <ref> } "];
head[shape=plaintext, fontcolor=blue, label="*head"];
node_p[shape=plaintext, fontcolor=blue, label="**node"];
temp[shape=plaintext, fontcolor=blue, label="*temp"];
NULL1[label=NULL,shape=plaintext];
node_1:ref:c -> node_3:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:ref:c -> node_3:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, fontcolor=red];
node_3:ref:c -> NULL1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_p -> head;
head -> node_2:ptr;
temp -> node_1:ref[headport=n];
}
```
`(*node)->next = tmp;`
```graphviz
digraph {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="<ptr> node_2|{ <data> 2 | <ref> } "];
node_3 [label="<ptr> node_3|{ <data> 3 | <ref> } "];
head[shape=plaintext, fontcolor=blue, label="*head"];
node_p[shape=plaintext, fontcolor=blue, label="**node"];
temp[shape=plaintext, fontcolor=blue, label="*temp"];
NULL1[label=NULL,shape=plaintext];
node_1:ref:c -> node_3:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:ref:c -> node_1:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, fontcolor=red];
node_3:ref:c -> NULL1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_p -> head;
head -> node_2:ptr;
temp -> node_1:ptr;
}
```
`node = &(*node)->next->next (#BB1)`
```graphviz
digraph {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="<ptr> node_2|{ <data> 2 | <ref> } "];
node_3 [label="<ptr> node_3|{ <data> 3 | <ref> } "];
head[shape=plaintext, fontcolor=blue, label="*head"];
node_p[shape=plaintext, fontcolor=blue, label="**node"];
temp[shape=plaintext, fontcolor=blue, label="*temp"];
NULL1[label=NULL,shape=plaintext];
node_1:ref:c -> node_3:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:ref:c -> node_1:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, fontcolor=red];
node_3:ref:c -> NULL1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_p -> node_1:ref;
head -> node_2:ptr;
temp -> node_1:ptr;
}
```
- 讓`**node` 指向第一個 node 的 next ，這樣做的話，假如有第四個 node ，就可以像上面操作 `*head` 一樣，讓 head node 的 next 可以指向第四個 node
- 最後跳出 `for 迴圈` 並回傳 `head`
### Function 4 : `reverse`
- Function 的功能為：
>將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1
- Source Code：
```cpp
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
head->next = cursor; cursor = head; (#CCC)
head = next;
}
return cursor;
}
```
- 流程如下：
`node_t *cursor = NULL;`
```graphviz
digraph {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="<ptr> node_2|{ <data> 2 | <ref> } "];
node_3 [label="<ptr> node_3|{ <data> 3 | <ref> } "];
head[shape=plaintext, fontcolor=blue, label="*head"];
cursor[shape=plaintext, fontcolor=blue, label="cursor"];
NULL1[label=NULL,shape=plaintext];
NULL2[label=NULL,shape=plaintext];
node_1:ref:c -> node_2:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:ref:c -> node_3:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, fontcolor=red];
node_3:ref:c -> NULL1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cursor -> NULL2;
head -> node_1:ref[headport=n];
}
```
`node_t *next = head->next;`
```graphviz
digraph {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="<ptr> node_2|{ <data> 2 | <ref> } "];
node_3 [label="<ptr> node_3|{ <data> 3 | <ref> } "];
head[shape=plaintext, fontcolor=blue, label="*head"];
cursor[shape=plaintext, fontcolor=blue, label="cursor"];
next[shape=plaintext, fontcolor=blue, label="*next"];
NULL1[label=NULL,shape=plaintext];
NULL2[label=NULL,shape=plaintext];
node_1:ref:c -> node_2:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, headport=n];
node_2:ref:c -> node_3:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, fontcolor=red];
node_3:ref:c -> NULL1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cursor -> NULL2;
next -> node_2:ptr;
head -> node_1:ptr;
}
```
`head->next = cursor; cursor = head; (#CCC)`
```graphviz
digraph {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="<ptr> node_2|{ <data> 2 | <ref> } "];
node_3 [label="<ptr> node_3|{ <data> 3 | <ref> } "];
head[shape=plaintext, fontcolor=blue, label="*head"];
cursor[shape=plaintext, fontcolor=blue, label="cursor"];
next[shape=plaintext, fontcolor=blue, label="*next"];
NULL1[label=NULL,shape=plaintext];
NULL2[label=NULL,shape=plaintext];
node_1:ref:c -> NULL2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, headport=n];
node_2:ref:c -> node_3:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, fontcolor=red];
node_3:ref:c -> NULL1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cursor -> node_1:ptr;
next -> node_2:ptr;
head -> node_1:ptr;
}
```
`head = next;`
```graphviz
digraph {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr> head|{ <data> 1 | <ref> } "];
node_2 [label="<ptr> node_2|{ <data> 2 | <ref> } "];
node_3 [label="<ptr> node_3|{ <data> 3 | <ref> } "];
head[shape=plaintext, fontcolor=blue, label="*head"];
cursor[shape=plaintext, fontcolor=blue, label="cursor"];
next[shape=plaintext, fontcolor=blue, label="*next"];
NULL1[label=NULL,shape=plaintext];
NULL2[label=NULL,shape=plaintext];
node_1:ref:c -> NULL2 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, headport=n];
node_2:ref:c -> node_3:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, fontcolor=red];
node_3:ref:c -> NULL1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cursor -> node_1:ptr;
next -> node_2:ptr;
head -> node_2:ptr;
}
```
- 程式的思路是：
- 讓 `cursor` 指向 `*head 指向的 node` 在反轉後要指向的地方，拿上面舉例，`head->node_2->node_3` ，在反轉後 `head node` 應該要指向 NULL ，所以一開始 `cursor` 為指向 NULL 的 pointer ，接著讓 `head->next = cursor` ，再讓 `cursor` 指向 `head node` ，因為 `head node` 是下一個 node `node_2` 要指向的 node
- 讓 `*head` 指向 `自己原本指向的 node` 再下一個順位的 node 也就是 `node_2`
- 一直重複循環到 `*head` 指向 NULL ，然後回傳 `cursor` 結束
## 改寫 `swap_pair` 和 `reverse`
>函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = ... 的更新，請用指標的指標來改寫，並避免回傳指標;
### 改寫 `swap_pair`
- 原本的 code：
```cpp
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next (#BB1)) {
node_t *tmp = *node;
*node = (*node)->next; (#BB2)
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
- pointer to pointer 版：
```cpp
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;
}
}
```
- 原本的 code 本來就會將原本指向 head node 的指標指向第二個 node (前面解釋 swap_pair 時有畫出圖)， 所以改成 pass by reference 的方式就不必回傳 head pointer 了
### 改寫 reverse
- 原本的 code：
```cpp
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
head->next = cursor; cursor = head; (#CCC)
head = next;
}
return cursor;
}
```
- pointer to pointer 版：
```cpp
void reverse(node_t **head)
{
node_t *cursor = NULL;
while (*head) {
node_t *next = (*head)->next;
(*head)->next = cursor; cursor = *head; (#CCC)
*head = next;
}
*head = cursor;
}
```
## reverse recursive 版
- reverse function
```cpp
void reverse(node_t **head)
{
*head = rev_recursive( *head )
}
```
- recursive function
```cpp
node_t *rev_recursive( node_t *original_head )
{
if( original_head == NULL )
return NULL;
if( original_head->next == NULL )
return original_head;
node_t *rev_head = rev_recursive( original_head->next );
original_head->next->next = original_head;
original_head->next = NULL;
return rev_head;
}
```
recursive function 裡的：
```cpp
if( original_head == NULL )
return NULL;
if( original_head->next == NULL )
return original_head;
node_t *rev_head = rev_recursive( original_head- >next );
return rev_head;
```
是用來找到指向 `linked list` 最後一個 node 的指標並不停的回傳，到最後的 `reverse function` 更新 head 指標
假設有3個 node ，程式會呼叫3次 recursive function
1. 第3次的 recursive function 回傳 C node 的指標( rev_head )
2. 第2次的 recursive function 運用 original_head_2 `讓 C 指向 B，B 指向 NULL` ，回傳 C node 的指標
3. 第1次的 recursive function 運用 original_head_1 `讓 B 指向 A，A 指向 NULL` ，回傳 C node 的指標
最後的 `reverse function` 更新 head 指標
```graphviz
digraph {
rankdir=LR;
node [shape=record];
node_1 [label="<ptr> A|{ <data> 1 | <ref> } "];
node_2 [label="<ptr> B|{ <data> 2 | <ref> } "];
node_3 [label="<ptr> C|{ <data> 3 | <ref> } "];
head[shape=plaintext, fontcolor=blue, label="*head"];
oh1[shape=plaintext, fontcolor=blue, label="*original_head_1"];
oh2[shape=plaintext, fontcolor=blue, label="*original_head_2"];
oh3[shape=plaintext, fontcolor=blue, label="*original_head_3( rev_ head )"];
NULL1[label=NULL,shape=plaintext];
node_1:ref:c -> node_2:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
node_2:ref:c -> node_3:ptr [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, fontcolor=red];
node_3:ref:c -> NULL1 [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head -> node_1:ptr;
oh1 -> node_1:ptr;
oh2 -> node_2:ptr;
oh3 -> node_3:ptr;
}
```
## 實作 Fisher–Yates shuffle
>針對 singly-linked list 的節點，實作 Fisher–Yates shuffle，你應該儘量降低記憶體的使用量;
- 演算法：(節自維基百科 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle))
```
To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
```
```cpp
void Shuffle( node_t **head ){
// count the number of node in the list
int num_of_node = 0;
node_t *indirect = *head;
while (indirect){
num_of_node++;
indirect = indirect -> next;
}
srand ( time(NULL) );
node_t *cursor = *head;
node_t *prev_cursor = NULL;
node_t *prev_indirect = NULL;
indirect = *head;
// Fisher–Yates shuffle
for(;num_of_node > 1; --num_of_node){
prev_cursor = NULL;
cursor = head;
prev_indirect = NULL;
indirect = head;
// move cursor and indirect pointers to the node to be changed
// move prev_cursor and prev_indirect pointers to the previous node of
// node to be changed
for(int i = rand() % num_of_node; i > 1; --i){
prev_cursor = cursor;
cursor = cursor -> next;
}
for(int i = num_of_node; i > 1; --i){
prev_indirect = indirect;
indirect = indirect -> next;
}
// down below is swapping two node
if (prev_cursor != NULL)
prev_cursor->next = indirect;
else
*head = indirect;
prev_indirect->next = cursor;
// Swap next pointers
Node *temp = indirect->next;
indirect->next = cursor->next;
cursor->next = temp;
}
}
```
- 用了5個 pointer
- 處理是 head node 要交換的情況
```cpp
// down below is swapping two node
if (prev_cursor != NULL)
prev_cursor->next = indirect;
else
*head = indirect;
```
Sign in with Wallet
Connect another wallet