---
tags: Linux2020
---
# 2020q3 Homework1 (quiz1)
contributed by < `Ylowy` >
## Outline
1. 重新回答[第 1 周測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)，連同附帶的「延伸問題」。
解釋程式運作原理時，應提供對應的 Graphviz 圖例，可參照 Linked List 題目 1 + 分析
2. 比照 課前測驗參考解答:
Q1 和 Linked list 題目分析 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及進行相關實驗。
## 1. 重新回答第一周測驗題
### tpyedef
型態先定義長這樣，很簡單的 structure
```c=
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
### add_entry
```c=
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;
}
```
### find_entry
這個比較簡單就不佳贅述了
```c=
node_t *find_entry(node_t *head, int value)
{
node_t *current = head;
for (; current && current->value != value; current = current->next)
/* interate */;
return current;
}
```
### remove_entry
```c=
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
```
### swap_pair
這邊卡真久，關鍵在for迴圈中的細節
```c=
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;
}
}
```
### reverse
[Ylowy/Lab0-c](https://hackmd.io/1BvGp-2oQuqYUzD1NtZU6g?view) 參考我之前寫的 reverse queue 的方法，省一個空間
```c=
void reverse(node_t **head)
{
node_t * tail = *head;
while(tail->next)
tail = tail->next;
tail->next = *head;
node_t *ptr = (*head)->next->next;
while ((*head)->next != tail) {
(*head)->next->next = tail->next;
tail->next = (*head)->next;
(*head)->next = ptr;
ptr = ptr->next;
}
tail = *head;
*head = (*head)->next;
tail->next = NULL;
}
```
```graphviz
digraph graphname {
rankdir=LR;
A [label="A" color=Blue, fontcolor=Red, fontsize=24, shape=box]
B [label="B" color=Blue, fontcolor=Red, fontsize=24, shape=box]
C [label="C" color=Blue, fontcolor=Red, fontsize=24, shape=box]
D [label="D" color=Blue, fontcolor=Red, fontsize=24, shape=box]
E [label="E" color=Blue, fontcolor=Red, fontsize=24, shape=box]
head[label="Head"]
tail[label="Tail"]
A->B [fontcolor=black]
B->C [fontcolor=black]
C->D [fontcolor=black]
D->E [fontcolor=black]
head->A [fontcolor=black]
tail->E [fontcolor=black]
E->NULL [fontcolor=black]
}
```
q 的 Initial
1. ptr = head->next->next
2. tail->next = head
```graphviz
digraph graphname {
rankdir=LR;
A [label="A" color=Blue, fontcolor=Red, fontsize=24, shape=box]
B [label="B" color=Blue, fontcolor=Red, fontsize=24, shape=box]
C [label="C" color=Blue, fontcolor=Red, fontsize=24, shape=box]
D [label="D" color=Blue, fontcolor=Red, fontsize=24, shape=box]
E [label="E" color=Blue, fontcolor=Red, fontsize=24, shape=box]
head[label="Head"]
tail[label="Tail"]
ptr[label="ptr"]
A->B [fontcolor=black]
B->C [fontcolor=black]
C->D [fontcolor=black]
D->E [fontcolor=black]
ptr->C [fontcolor=black]
head->A [fontcolor=black]
tail->E [fontcolor=black]
E->A [fontcolor=black]
}
```
再來做 while(..)
```graphviz
digraph graphname {
rankdir=LR;
A [label="A" color=Blue, fontcolor=Red, fontsize=24, shape=box]
B [label="B" color=Blue, fontcolor=Red, fontsize=24, shape=box]
C [label="C" color=Blue, fontcolor=Red, fontsize=24, shape=box]
D [label="D" color=Blue, fontcolor=Red, fontsize=24, shape=box]
E [label="E" color=Blue, fontcolor=Red, fontsize=24, shape=box]
head[label="Head"]
tail[label="Tail"]
ptr[label="ptr"]
A->C [fontcolor=black]
B->A [fontcolor=black]
C->D [fontcolor=black]
D->E [fontcolor=black]
E->B [fontcolor=black]
ptr->D [fontcolor=black]
head->A [fontcolor=black]
tail->E [fontcolor=black]
}
```
```graphviz
digraph graphname {
rankdir=LR;
A [label="A" color=Blue, fontcolor=Red, fontsize=24, shape=box]
B [label="B" color=Blue, fontcolor=Red, fontsize=24, shape=box]
C [label="C" color=Blue, fontcolor=Red, fontsize=24, shape=box]
D [label="D" color=Blue, fontcolor=Red, fontsize=24, shape=box]
E [label="E" color=Blue, fontcolor=Red, fontsize=24, shape=box]
head[label="Head"]
tail[label="Tail"]
ptr[label="ptr"]
A->D [fontcolor=black]
B->A [fontcolor=black]
C->B [fontcolor=black]
D->E [fontcolor=black]
E->C [fontcolor=black]
ptr->E [fontcolor=black]
head->A [fontcolor=black]
tail->E [fontcolor=black]
}
```
```graphviz
digraph graphname {
rankdir=LR;
A [label="A" color=Blue, fontcolor=Red, fontsize=24, shape=box]
B [label="B" color=Blue, fontcolor=Red, fontsize=24, shape=box]
C [label="C" color=Blue, fontcolor=Red, fontsize=24, shape=box]
D [label="D" color=Blue, fontcolor=Red, fontsize=24, shape=box]
E [label="E" color=Blue, fontcolor=Red, fontsize=24, shape=box]
head[label="Head"]
tail[label="Tail"]
ptr[label="ptr"]
A->E [fontcolor=black]
B->A [fontcolor=black]
C->B [fontcolor=black]
D->C [fontcolor=black]
E->D [fontcolor=black]
ptr->C [fontcolor=black]
head->A [fontcolor=black]
tail->E [fontcolor=black]
}
```
最後做 head tail調整
```graphviz
digraph graphname {
rankdir=LR;
A [label="A" color=Blue, fontcolor=Red, fontsize=24, shape=box]
B [label="B" color=Blue, fontcolor=Red, fontsize=24, shape=box]
C [label="C" color=Blue, fontcolor=Red, fontsize=24, shape=box]
D [label="D" color=Blue, fontcolor=Red, fontsize=24, shape=box]
E [label="E" color=Blue, fontcolor=Red, fontsize=24, shape=box]
head[label="Head"]
tail[label="Tail"]
A->NULL [fontcolor=black]
B->A [fontcolor=black]
C->B [fontcolor=black]
D->C [fontcolor=black]
E->D [fontcolor=black]
head->E [fontcolor=black]
tail->A [fontcolor=black]
}
```
## 2. 比照課前測驗參考解答
Sign in with Wallet
Connect another wallet