# 2020q3 Homework1 (quiz1)
contributed by < `ZhuMon` >
###### tags: `sysprog2020`, `quiz`
## :memo: Table of Contents
[TOC]
---
## :page_facing_up: 題目
:::spoiler
考慮一個單向 linked list，其結構定義為:
```c
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
```
請補完程式碼。
:::
---
## 程式運作原理
以 `add_entry()`, `find_entry()`, `remove_entry()`, `swap_pair()`, `reverse()`, `print_list()` 等六個 function 組成
----
### `add_entry()`
```c=9
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;
}
```
* 目的： 在 `*head` 所指向 linked list 的尾端插入一個 value 為 `new_value` 的 node
* 流程： 使用 pointer to pointer (`**indirect`) 來找尋 linked list (`**head`) 的尾端，當 `*indirect` 到達尾端(`*indirect == NULL`)後，將新的 node (`new_node`) 插入linked list
* 詳細說明：
:::info
以三個 column 分別代表某一變數的 address, name, value
```graphviz
digraph {
node [shape=record];
rankdir=LR;
ex [label="{address|name|value}"]
}
```
:::
在呼叫 `add_entry()` 之前，可以看到 `main()` 先定義了一個指標 `*head`，並且沒有分配記憶體。
接著呼叫 `print_list(head)`，將 `head` 所指向的 linked list 印出來，由於目前`head` 為 NULL 因此只會印出一個換行符號。(稍後介紹 `print_list`)
然後呼叫 `add_entry(&head, 72)`，將 72 作為第一個 node 的值插入 linked list，並且藉由 pointer to pointer 的技巧，傳入 `&head` 直接在 `add_entry()` 中修改 `main()` 的 `head` 所指向的空間
```c=71
int main(int argc, char const *argv[])
{
node_t *head = NULL;
print_list(head);
add_entry(&head, 72);
```
| Frame |Address | Parameter name | Value |
| --- | ----- | -------- | -------- |
| main |0x7fffffffe2e8 | head | 0x0 |
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
head [label="{ <addr> 0x7fffffffe2e8|(main)head|0x0}"];
}
```
---
```c=9
void add_entry(node_t **head, int new_value)
{
node_t **indirect = head;
```
進入 `add_entry` 後，將 `indirect` 存放原先 `head` 的 address
| Frame | Address | Parameter name | Value |
| ---- | -------- | -------- | -------- |
| main | 0x7fffffffe2e8 | head | 0x0 |
| add_entry | 0x7fffffffe2a8 | head | 0x7fffffffe2e8 |
| add_entry | 0x7fffffffe2b0 | indirect | 0x7fffffffe2e8 |
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
head [label="{ <addr> 0x7fffffffe2e8|<data> (main)head| <ref> 0x0}"];
now_head [label="{ <addr> 0x7fffffffe2a8|<data> (add_entry)head| <ref> }"];
indirect [label="{<addr> 0x7fffffffe2b0| <data> indirect| <ref> }"];
now_head:ref -> head:addr;
indirect:ref -> head:addr;
}
```
---
```c=13
node_t *new_node = malloc(sizeof(node_t));
new_node->value = new_value;
new_node->next = NULL;
```
接著建立一個新的 node (`new_node`)，並且分配記憶體
| Frame | Address | Parameter name | Value |
| ---- | -------- | -------- | -------- |
| main | 0x7fffffffe2e8 | head | 0x0 |
| add_entry | 0x7fffffffe2a8 | head | 0x7fffffffe2e8 |
| add_entry | 0x7fffffffe2b0 | indirect | 0x7fffffffe2e8 |
| add_entry | 0x7fffffffe2b8 | new_node | 0x555555757670 |
| add_entry | 0x555555757670 | *new_node | {value = 72, next = 0x0} |
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
now_head [label="{ <addr> 0x7fffffffe2a8|<data> (add_entry)head| <ref> }"];
indirect [label="{<addr> 0x7fffffffe2b0| <data> indirect| <ref> }"];
head [label="{ <addr> 0x7fffffffe2e8|<data> (main)head| <ref> 0x0}"];
new_node [label="{ <addr> 0x7fffffffe2b8 | <data> new_node| <ref> }"];
node_value [label="{ <addr> 0x555555757670 | <data> \{value = 72, next = 0x0\}}"]
now_head:ref -> head:addr;
indirect:ref -> head:addr;
new_node:ref -> node_value;
}
```
---
```c=17
assert(new_node);
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node;
}
```
`assert` 確保 `new_node` 正確分配記憶體(也可以將 `assert` 移至 `malloc` 後)
由於是建立第一個 node，所以會直接跳到第 21 行，將 `indirect` 所存放的 value 作為 adrress，更改該 address 存放的 value，將該 value 改為 `new_node` 的 value
| Frame | Address | Parameter name | Value |
| ---- | -------- | -------- | -------- |
| main | 0x7fffffffe2e8 | head | 0x555555757670 |
| add_entry | 0x7fffffffe2a8 | head | 0x7fffffffe2e8 |
| add_entry | 0x7fffffffe2b0 | indirect | 0x7fffffffe2e8 |
| add_entry | 0x7fffffffe2e8 | *indirect | 0x555555757670|
| add_entry | 0x7fffffffe2b8 | new_node | 0x555555757670 |
| add_entry | 0x555555757670 | *new_node | {value = 72, next = 0x0} |
由於 address 太長，會導致圖變小，因此將 address 省略前半段
```graphviz
digraph add_entry{
rankdir=LR;
node [shape=record];
now_head [label="{ <addr> e2a8|<data> (add_entry)head| <ref> }"];
indirect [label="{<addr> e2b0| <data> indirect| <ref> }"];
head [label="{ <addr> e2e8|<data> (main)head| <ref> }"];
new_node [label="{ <addr> e2b8 | <data> new_node| <ref> }"];
node_value [label="{ <addr> 7670 | <data> \{value = 72, next = 0x0\}}"]
now_head:ref -> head:addr;
indirect:ref -> head:addr;
new_node:ref -> node_value:addr;
head:ref->node_value:addr;
}
```
---
### `find_entry()`
```c=23
node_t *find_entry(node_t *head, int value)
{
node_t *current = head;
for (; current && current->value != value; current = current->next)
/* interate */;
return current;
}
```
從傳入的 linked list node (`*head`)，以 for-loop 找到在該 node 後，傳回存放的值為 `value` 的 node，用於刪除某一個 node
---
### `remove_entry()`
```c=31
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
```
* 目的：在 linked list (`**head`) 中，找到 node (`*entry`)，並且刪除
* 方法：因為需要更動的 pointer，只有指向 `entry` 的 pointer，因此以 `**indirect` 存放該 pointer 的 address，最後只要藉由將該 pointer 指向 `entry->next`，便沒有其他 pointer 指向該處，因此便可以優雅地達到目的
* 實例：
:::info
* 由於不管是變數或指標都是由 `address` 和 `value` 所組成，因此以兩個 column 分別代表 `address` 和 `value`
* 以下用箭頭連起來的兩個格子內容相同，並且格子左邊代表 address，右邊代表 value
若有第二個 row 則代表存放 next 的資訊
```graphviz
digraph b{
node [shape=record];
rankdir=UD;
ptr [label="{addr}|{value}"]
ex [label="{addr|next_addr}|{value|next}"];
}
```
:::
```c=77
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);
```
此處先執行到 86 行，接著將 `head` 的 address，與要刪除的 node 的 address 作為參數，一起傳入`remove_entry()`
```graphviz
digraph a{
node [shape=record];
rankdir=LR
entry [label="{<addr>(entry)|<ref>}"]
head [label="{<addr>(main_head)|}"];
A [label="{{<addr>|<next_addr>}|{72|<ref>}}"];
B [label="{{<addr>|<next_addr>}|{101|<ref>}}"];
C [label="{{<addr>|<next_addr>}|{108|<ref>}}"];
D [label="{{<addr>|<next_addr>}|{109|<ref>}}"];
E [label="{{<addr>|<next_addr>}|{110|<ref>}}"];
F [label="{{<addr>|<next_addr>}|{111|<ref>}}"];
head->A:addr;
A:ref->B:addr;
entry:ref->B:addr;
B:ref->C:addr;
C:ref->D:addr;
D:ref->E:addr;
E:ref->F:addr;
/*head [label="{<addr>(head)|<data>}"];
head:data->A:addr;
entry [label="{<addr>(entry)|<data>}"];
entry:data->B:addr;*/
}
```
---
傳入的 `head` 的 value 是 `main` 的 `head` 的 address
此處讓 `indirect` 存放 `head` 存放的 value
```c=31
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
```
```graphviz
digraph a{
node [shape=record];
rankdir=LR
A [label="{{<addr>|<next_addr>}|{72|<ref>}}"];
B [label="{{<addr>|<next_addr>}|{101|<ref>}}"];
C [label="{{<addr>|<next_addr>}|{108|<ref>}}"];
D [label="{{<addr>|<next_addr>}|{109|<ref>}}"];
E [label="{{<addr>|<next_addr>}|{110|<ref>}}"];
F [label="{{<addr>|<next_addr>}|{111|<ref>}}"];
A:ref->B:addr;
B:ref->C:addr;
C:ref->D:addr;
D:ref->E:addr;
E:ref->F:addr;
now_head [label="{<addr>(head)|<data>}"]
head [label="{<addr>(main_head)|<data>}"];
now_head:data->head:addr;
head:data->A:addr;
indirect [label="{<addr>(indirect)|<data>}"];
indirect:data->head:addr;
entry [label="{<addr>(entry)|<data>}"];
entry:data->B:addr;
}
```
---
若是 `(*indirect) != entry` 便會進入 while，並且讓 `indirect` 的值為 `*indirect` 所指向的 object 的 `next` address，接著因為 `*indirect` 的值是否與 entry 的值相同，所以跳出 while
```c=35
while ((*indirect) != entry)
indirect = &(*indirect)->next;
```
```graphviz
digraph a{
node [shape=record];
rankdir=LR
A [label="{{<addr>|<next_addr>}|{72|<ref>}}"];
B [label="{{<addr>|<next_addr>}|{101|<ref>}}"];
C [label="{{<addr>|<next_addr>}|{108|<ref>}}"];
D [label="{{<addr>|<next_addr>}|{109|<ref>}}"];
E [label="{{<addr>|<next_addr>}|{110|<ref>}}"];
F [label="{{<addr>|<next_addr>}|{111|<ref>}}"];
A:ref->B:addr;
B:ref->C:addr;
C:ref->D:addr;
D:ref->E:addr;
E:ref->F:addr;
main_head [label="{<addr>(main_head)|<data>}"];
main_head->A:addr;
head [label="{<addr>(head)|<data>}"];
head:data->main_head:addr;
indirect [label="{<addr>(indirect)|<data>}"];
indirect:data->A:next_addr;
entry [label="{<addr>(entry)|<data>}"];
entry:data->B:addr;
}
```
---
讓 `*indirect` 所存放的值換為 `entry->next`，如此便可以達到刪除的目的
```c=38
*indirect = entry->next;
```
```graphviz
digraph a{
node [shape=record];
rankdir=LR
A [label="{{<addr>|<next_addr>}|{72|<ref>}}"];
B [label="{{<addr>|<next_addr>}|{101|<ref>}}"];
C [label="{{<addr>|<next_addr>}|{108|<ref>}}"];
D [label="{{<addr>|<next_addr>}|{109|<ref>}}"];
E [label="{{<addr>|<next_addr>}|{110|<ref>}}"];
F [label="{{<addr>|<next_addr>}|{111|<ref>}}"];
A:ref->C:addr [color=red];
B:ref->C:addr;
C:ref->D:addr;
D:ref->E:addr;
E:ref->F:addr;
main_head [label="{<addr>(main_head)|<data>}"];
main_head->A:addr;
head [label="{<addr>(head)|<data>}"];
head:data->main_head:addr;
indirect [label="{<addr>(indirect)|<data>}"];
indirect:data->A:next_addr;
entry [label="{<addr>(entry)|<data>}"];
entry:data->B:addr;
}
```
---
將刪除的 node 的記憶體釋放，由於只是釋放 `entry` 所指向的記憶體空間，因此存放 pointer `entry` 的空間並沒有釋放，不過在這個 function 結束後，就會自動釋放
```c=39
free(entry);
```
```graphviz
digraph a{
node [shape=record];
rankdir=LR
A [label="{{<addr>|<next_addr>}|{72|<ref>}}"];
//B [label="{{<addr>|<next_addr>}|{101|<ref>}}"];
C [label="{{<addr>|<next_addr>}|{108|<ref>}}"];
D [label="{{<addr>|<next_addr>}|{109|<ref>}}"];
E [label="{{<addr>|<next_addr>}|{110|<ref>}}"];
F [label="{{<addr>|<next_addr>}|{111|<ref>}}"];
A:ref->C:addr;
//B:ref->C:addr;
C:ref->D:addr;
D:ref->E:addr;
E:ref->F:addr;
main_head [label="{<addr>(main_head)|<data>}"];
main_head->A:addr;
head [label="{<addr>(head)|<data>}"];
head:data->main_head:addr;
indirect [label="{<addr>(indirect)|<data>}"];
indirect:data->A:next_addr;
entry [label="{<addr>(entry)|<data>}"];
//entry:data->B:addr;
}
```
---
### `swap_pair()`
```c=42
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;
}
```
:::info
BB1 = ?
* `(a)` `node = (*node)->next->next`
* `(b)` `*node = (*node)->next->next`
* `(c)` `*node = ((*node)->next)->next`
* `(d)` `*node = &((*node)->next)->next`
* `(e)` `node = &(*node)->next->next`
* `(f)` `*node = &(*node)->next->next`
BB2 = ?
* `(a)` `node = (*node)->next`
* `(b)` `node = &(*node)->next`
* `(c)` `*node = (*node)->next`
* `(d)` `*node = &(*node)->next`
* `(e)` `*node = &((*node)->next)`
:::
* 目的：交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 1->2->3->4，則該回傳 2->1->4->3
* 方法
```graphviz
digraph swap{
node [shape="record"]
rankdir=LR;
A [label="{{<addr>|<next_addr>}|{72|<ref>}}"];
//B [label="{{<addr>|<next_addr>}|{101|<ref>}}"];
C [label="{{<addr>|<next_addr>}|{108|<ref>}}"];
D [label="{{<addr>|<next_addr>}|{109|<ref>}}"];
E [label="{{<addr>|<next_addr>}|{110|<ref>}}"];
//F [label="{{<addr>|<next_addr>}|{111|<ref>}}"];
A:ref->C:addr;
//B:ref->C:addr;
C:ref->D:addr;
D:ref->E:addr;
//E:ref->F:addr;
main_head [label="{<addr>(main_head)|<data>}"];
main_head->A:addr;
//head [label="{<addr>(head)|<data>}"];
//head:data->main_head:addr;
//indirect [label="{<addr>(indirect)|<data>}"];
//indirect:data->A:next_addr;
//entry [label="{<addr>(entry)|<data>}"];
}
```
Sign in with Wallet
Connect another wallet