2020q3 Homework1 (quiz1)
===
contributed by < `osdream` >
###### tags: `sysprog2020`
---
# 題目與答案
## 題目
:::spoiler
```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;
}
```
:::
## 輸出
:::spoiler
```
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`
## 補充
題目程式碼需要加上：
```diff
@@ -1,5 +1,6 @@
#include <stdio.h>
#include <stdlib.h>
+#include <assert.h>
typedef struct __node {
int value;
```
方能編過。否則編譯時會遇上像這樣的錯誤訊息：
（環境：Ubuntu 18.04，編譯器版本`gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0`）
```
quiz1.c: In function 'add_entry':
quiz1.c:18:5: warning: implicit declaration of function 'assert'; did you mean qsort'? [-Wimplicit-function-declaration]
assert(new_node);
^~~~~~
qsort
/tmp/ccmDX2Rv.o: In function `add_entry':
quiz1.c:(.text+0x47): undefined reference to `assert'
collect2: error: ld returned 1 exit status
```
# 程式運作原理
## `add_entry(node_t **head, int new_value)`
### 功能
在 linked list 尾端新增一個值為`new_value`的 node。
### 運作流程
```c
void add_entry(node_t **head, int new_value)
{
// 1. 建立指向指標 head 記憶體位置的指標 indirect
node_t **indirect = head;
// 2. 建立值為 new_value 的新 node new_node，
// 令其 next 指向 NULL
node_t *new_node = malloc(sizeof(node_t));
new_node->value = new_value;
new_node->next = NULL;
// 3. 用 assert 這一 macro 確定 new_node 不指向 NULL，
// 否則回傳 assertion failed 結束程式
assert(new_node);
// 4. 從 indirecrt = head 開始，一路指向 indirect->next
// 的記憶體位置直到 *indirect
// （indirect 指向的指標）指向 NULL 為止
while (*indirect)
indirect = &(*indirect)->next;
// 5. 讓 *indirect 指向新 node new_node
*indirect = new_node;
}
```
### 示意圖
1. 建立指向指標`head`記憶體位置的指標`indirect`。
```graphviz
digraph graph_name {
node [
shape = record,
fontname = "Migu 1M",
fontsize = 9,
];
// node define
head [label = "head"];
indirect [label = "indirect"]
node_addr [label = "address\nto\nnode"];
some_node [label = "{some_node|{val|next}}"];
// edge define
head -> node_addr;
indirect -> node_addr;
node_addr -> some_node;
}
```
2. 建立值為`new_value`的`new_node`，令其`next`指向`NULL`。
```graphviz
digraph graph_name {
node [
shape = record,
fontname = "Migu 1M",
fontsize = 9,
];
// node define
head [label = "head"];
indirect [label = "indirect"]
node_addr [label = "address\nto\nnode"];
new_node [label = "{new_node|{new_val|<pn>next}}"];
node_1 [label = "{node 1|{val|next}}"];
// edge define
head -> node_addr;
indirect -> node_addr;
node_addr -> node_1;
new_node:pn -> NULL;
}
```
4.
- `indirect`一路沿著每個 node 的`next`往下爬更新其指向的指標。
```graphviz
digraph graph_name {
node [
shape = record,
fontname = "Migu 1M",
fontsize = 9,
];
// node define
indirect [label = "indirect"]
node_addr [label = "address\nto\nnode"];
node1 [label = "{<ps>node1|{val|<pn>next}}"];
node2 [label = "{node2|{val|<pn>next}}"];
// edge define
indirect -> node_addr;
node_addr -> node1;
node1:pn -> indirect [style = dashed, label = "update"];
node1:pn -> node2;
node2:pn -> indirect [style = dashed, label = "update"];
}
```
- 跳出`while`迴圈時，`indirect`指向的記憶體指標位置指向`NULL`，為 linked list 的最後 node 中的`next`之記憶體位置。
```graphviz
digraph graph_name {
node [
shape = record,
fontname = "Migu 1M",
fontsize = 9,
];
// node define
head [label = "head"];
indirect [label = "indirect"]
node_addr [label = "address\nto\nnode"];
new_node [label = "{new_node|{new_val|<pn>next}}"];
node1 [label = "{node 1|{val|next}}"];
noden [label = "{node n|{val|<pn>next}}"];
// edge define
head -> node_addr;
indirect -> noden:pn;
node_addr -> node1;
noden:pn -> NULL;
new_node:pn ->NULL;
}
```
5. 讓`indirect`指向的指標指向`new_node`，收工。
```graphviz
digraph graph_name {
node [
shape = record,
fontname = "Migu 1M",
fontsize = 9,
];
// node define
head [label = "head"];
indirect [label = "indirect"]
node_addr [label = "address\nto\nnode"];
new_node [label = "{new_node|{new_val|<pn>next}}"];
node1 [label = "{node 1|{val|next}}"];
noden [label = "{node n|{val|<pn>next}}"];
// edge define
head -> node_addr;
indirect -> noden:pn;
node_addr -> node1;
noden:pn -> new_node;
new_node:pn -> NULL;
}
```
## `find_entry(node_t *head, int value)`
### 功能
### 運作流程
### 示意圖
## `remove_entry(node_t **head, node_t *entry)`
### 功能
### 運作流程
### 示意圖
## `swap_pair(node_t *head)`
### 功能
### 運作流程
### 示意圖
## `reverse(node_t *head)`
### 功能
### 運作流程
### 示意圖
## `print_list(node_t *head)`
### 功能
### 運作流程
### 示意圖
Google Drive
Gist
Clipboard
Sign in with Wallet
