# 2020q3 Homework1 (quiz1)
contributed by < [WeiCheng14159](https://github.com/WeiCheng14159) >
###### tags: `sysprog2020`
## Index
[TOC]
---
## 指針表示法
* 以下的討論中，指針將如此表示
* 變數值使用==白色==的節點表示
* 指針使用==灰色==節點表示
* 指針的指針將使用==黃色==的節點表示
```graphviz
digraph ptr{
rankdir=LR;
node [shape=record,style=filled];
// nodes
pp [
label="{<name> node_t ** n_pp| <addr> 0xAA | <val> 0xBB}", fillcolor=yellow
];
p [
label="{<name> node_t * n_p | <addr> 0xBB | <val> 0xCC}",
fillcolor=gray
];
n [
label="{<name> node_t n | <addr> 0xCC | <val> ...}",
fillcolor=white
];
// edges
pp:val -> p:addr;
p:val ->n:addr;
}
```
* 指針的指針之重點
* __要在函式裡改變==變數值==時，參數必須為指針__
* __要在函式裡改變==指針值==時，參數必須為指針的指針__
## 函式解析
* 分別使用 Graphviz 和 簡易的記憶體表格解釋指針的操作
### `add_entry()`
```c=1
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;
}
```
* 初始狀態 `indirect` 指向 `head`
```c=1
node_t **indirect = head;
```
```graphviz
digraph g{
rankdir=LR;
node [shape=record, style=filled];
subgraph list{
// node
node_n1 [fillcolor=gray, label="{<name> n1}"];
node_n2 [fillcolor=gray, label="{<name> n2}"];
node_n3 [fillcolor=gray, label="{<name> n3}"];
node_n4 [fillcolor=gray, label="{<name> n4}"];
node_n5 [fillcolor=gray, label="{<name> n5}"];
head_p [fillcolor=gray, label="{<name> *head}"];
// edge
head_p->node_n1->node_n2->node_n3->node_n4->node_n5;
}
subgraph pp{
// node
head_pp [fillcolor=yellow, label="{<name> **head}"];
indirect_pp [fillcolor=yellow, label="{<name> **indirect}"];
// edge
indirect_pp->head_p[headport=n];
head_pp->head_p[headport=n];
}
}
```
對應的記憶體操作：
| pointer2pointer | | | pointer2value | | | value | | |
|:---------------:|---------|------|---------------|---------|------|---------|------------|-----------|
| name | address | data | name | address | data | address | data:value | data:next |
| head | ... | 200 | n1 | 200 | 100 | 100 | 1 | 101 |
| indirect | ... | 200 | n2 | 201 | 101 | 101 | 2 | 102 |
| | | | n3 | 202 | 102 | 102 | 3 | 103 |
| | | | n4 | 203 | 103 | 103 | 4 | 104 |
| | | | n5 | 204 | 104 | 104 | 5 | 0 |
* 建立 `new_node`
```c=1
node_t *new_node = malloc(sizeof(node_t));
new_node->value = new_value;
new_node->next = NULL;
assert(new_node);
```
```graphviz
digraph g{
rankdir=LR;
node [shape=record, style=filled];
subgraph list{
// node
n1 [fillcolor=gray];
n2 [fillcolor=gray];
n3 [fillcolor=gray];
n4 [fillcolor=gray];
n5 [fillcolor=gray];
head_p [fillcolor=gray, label="{<name> *head}"];
new_node [fillcolor=gray];
// edge
head_p->n1->n2->n3->n4->n5;
}
subgraph pp{
// node
head_pp [fillcolor=yellow, label="{<name> **head}"];
indirect_pp [fillcolor=yellow, label="{<name> **indirect}"];
// edge
indirect_pp->head_p[headport=n];
head_pp->head_p[headport=n];
}
}
```
對應的記憶體操作：
| pointer2pointer | | | pointer2value | | | value | | |
|:---------------:|---------|------|---------------|---------|------|---------|------------|-----------|
| name | address | data | name | address | data | address | data:value | data:next |
| head | ... | 200 | n1 | 200 | 100 | 100 | 1 | 101 |
| indirect | ... | 200 | n2 | 201 | 101 | 101 | 2 | 102 |
| | | | n3 | 202 | 102 | 102 | 3 | 103 |
| | | | n4 | 203 | 103 | 103 | 4 | 104 |
| | | | n5 | 204 | 104 | 104 | 5 | 0 |
| | | | new_node | 205 | 105 | 105 | new_value | 0 |
* 尋找適合之插入位置
```c=1
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node;
```
```graphviz
digraph g{
rankdir=LR;
node [shape=record, style=filled];
subgraph list{
// node
n1 [fillcolor=gray];
n2 [fillcolor=gray];
n3 [fillcolor=gray];
n4 [fillcolor=gray];
n5 [fillcolor=gray];
head_p [fillcolor=gray, label="{<name> *head}"];
new_node [fillcolor=gray];
// edge
head_p->n1->n2->n3->n4->n5->new_node;
}
subgraph pp{
// node
head_pp [fillcolor=yellow, label="{<name> **head}"];
indirect_pp [fillcolor=yellow, label="{<name> **indirect}"];
// edge
indirect_pp->new_node[headport=n];
head_pp->head_p[headport=n];
}
}
```
對應的記憶體內容：因為簡易的記憶體表格過於簡略，無法描述一個 `struct` 中不同成員的位址，故此處省略，僅用圖示表達
### `remove_entry()`
```c=1
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
```
* 因為這個函式需要改變 `*head` 指針的值，故須要將 `**head` 傳入
```c=3
node_t **indirect = head;
```
```graphviz
digraph g{
rankdir=LR;
node [shape=record, style=filled];
subgraph list{
// node
node_n1 [fillcolor=gray, label="{<name> n1}"];
node_n2 [fillcolor=gray, label="{<name> n2}"];
node_n3 [fillcolor=gray, label="{<name> n3}"];
node_n4 [fillcolor=gray, label="{<name> n4}"];
node_n5 [fillcolor=gray, label="{<name> n5}"];
head_p [fillcolor=gray, label="{<name> *head}"];
entry_p [fillcolor=gray, label="{<name> *entry}"];
// edge
head_p->node_n1->node_n2->node_n3->node_n4->node_n5;
entry_p->node_n3[headport=n];
}
subgraph pp{
// node
head_pp [fillcolor=yellow, label="{<name> **head}"];
indirect_pp [fillcolor=yellow, label="{<name> **indirect}"];
// edge
indirect_pp->head_p[headport=n];
head_pp->head_p[headport=n];
}
}
```
對應的記憶體操作：
| pointer2pointer | | | pointer2value | | | value | | |
|:---------------:|---------|------|---------------|---------|------|---------|------------|-----------|
| name | address | data | name | address | data | address | data:value | data:next |
| head | ... | 200 | n1 | 200 | 100 | 100 | 1 | 101 |
| indirect | ... | 200 | n2 | 201 | 101 | 101 | 2 | 102 |
| | | | n3 | 202 | 102 | 102 | 3 | 103 |
| | | | n4 | 203 | 103 | 103 | 4 | 104 |
| | | | n5 | 204 | 104 | 104 | 5 | 0 |
| | | | entry | 205 | 102 | | | |
* 當程式離開 `while loop` 之後的情況
```c=5
while ((*indirect) != entry)
indirect = &(*indirect)->next;
```
```graphviz
digraph initial{
rankdir=LR;
node [shape=record, style=filled];
subgraph linked_list{
node_n1 [fillcolor=gray, label="{<name> n1}"];
node_n2 [fillcolor=gray, label="{<name> n2}"];
node_n3 [fillcolor=gray, label="{<name> n3}"];
node_n4 [fillcolor=gray, label="{<name> n4}"];
node_n5 [fillcolor=gray, label="{<name> n5}"];
head_p [fillcolor=gray, label="{<name> *head}"];
entry_p [fillcolor=gray, label="{<name> *entry}"];
head_p->node_n1->node_n2->node_n3->node_n4->node_n5;
entry_p->node_n3[headport=n];
}
subgraph pp{
head_pp [fillcolor=yellow, label="{<name> **head}"];
indirect_pp [fillcolor=yellow, label="{<name> **indirect}"];
indirect_pp->node_n2[headport=n];
head_pp->head_p[headport=n];
}
}
```
對應的記憶體操作：
| pointer2pointer | | | pointer2value | | | value | | |
|:---------------:|---------|---------------|---------------|---------|------|---------|------------|-----------|
| name | address | data | name | address | data | address | data:value | data:next |
| head | ... | 200 | n1 | 200 | 100 | 100 | 1 | 101 |
| indirect | ... | 200=>201=>202 | n2 | 201 | 101 | 101 | 2 | 102 |
| | | | n3 | 202 | 102 | 102 | 3 | 103 |
| | | | n4 | 203 | 103 | 103 | 4 | 104 |
| | | | n5 | 204 | 104 | 104 | 5 | 0 |
| | | | entry | 205 | 102 | | | |
* `*indirect` 指向 `entry->next`
```c=8
*indirect = entry->next;
free(entry);
```
```graphviz
digraph initial{
rankdir=LR;
node [shape=record, style=filled];
subgraph linked_list{
node_n1 [fillcolor=gray, label="{<name> n1}"];
node_n2 [fillcolor=gray, label="{<name> n2}"];
node_n3 [color=red, label="{<name> n3}"];
node_n4 [fillcolor=gray, label="{<name> n4}"];
node_n5 [fillcolor=gray, label="{<name> n5}"];
head_p [fillcolor=gray, label="{<name> *head}"];
entry_p [fillcolor=gray, label="{<name> *entry}"];
head_p->node_n1->node_n2 node_n3 node_n4->node_n5;
entry_p->node_n3[headport=n, tailport=e];
node_n2->node_n4[color=red];
}
subgraph pp{
head_pp [fillcolor=yellow, label="{<name> **head}"];
indirect_pp [fillcolor=yellow, label="{<name> **indirect}"];
indirect_pp->node_n2[headport=n, tailport=s];
head_pp->head_p[headport=n, tailport=s];
}
}
```
對應的記憶體操作：
| pointer2pointer | | | pointer2value | | | value | | |
|:---------------:|---------|---------------|---------------|---------|----------|---------|------------|-----------|
| name | address | data | name | address | data | address | data:value | data:next |
| head | ... | 200 | n1 | 200 | 100 | 100 | 1 | 101 |
| indirect | ... | 200=>201=>202 | n2 | 201 | 101 | 101 | 2 | 102 |
| | | | n3 | 202 | 102=>103 | 102 | 3=>0 | 103=>0 |
| | | | n4 | 203 | 103 | 103 | 4 | 104 |
| | | | n5 | 204 | 104 | 104 | 5 | 0 |
| | | | entry | 205 | 102 | | | |
### `swap_pair()`
```c=1
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;
}
```
* 初始狀況
```c=3
for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next) {
node_t *tmp = *node;
```
```graphviz
digraph initial{
rankdir=LR;
node [shape=record, style=filled];
subgraph linked_list{
n1 [fillcolor=gray, label="{<name> n1}"];
n2 [fillcolor=gray, label="{<name> n2}"];
n3 [fillcolor=gray, label="{<name> n3}"];
n4 [fillcolor=gray, label="{<name> n4}"];
n5 [fillcolor=gray, label="{<name> n5}"];
n1->n2->n3->n4->n5;
}
subgraph pp{
node_pp [fillcolor=yellow, label="{<name> **node}"];
node_pp->head_p[headport=n];
head_p [fillcolor=gray, label="{<name> *head}"];
head_p->n1;
tmp_p [fillcolor=gray, label="{<name> *tmp}"];
tmp_p->n1;
}
}
```
對應的記憶體操作：
| pointer2pointer | | | pointer2value | | | value | | |
|:---------------:|---------|------|---------------|---------|------|---------|------------|-----------|
| name | address | data | name | address | data | address | data:value | data:next |
| node | ... | 205 | n1 | 200 | 100 | 100 | 1 | 101 |
| | | | n2 | 201 | 101 | 101 | 2 | 102 |
| | | | n3 | 202 | 102 | 102 | 3 | 103 |
| | | | n4 | 203 | 103 | 103 | 4 | 104 |
| | | | n5 | 204 | 104 | 104 | 5 | 0 |
| | | | head | 205 | 100 | | | |
| | | | tmp | 206 | 100 | | | |
* 第一個 `iteration`
```c=5
*node = (*node)->next;
tmp->next = (*node)->next;
(*node)->next = tmp;
```
```graphviz
digraph iter1{
rankdir=LR;
node [shape=record, style=filled];
subgraph linked_list{
n1 [fillcolor=gray, label="{<name> n1}"];
n2 [fillcolor=gray, label="{<name> n2}"];
n3 [fillcolor=gray, label="{<name> n3}"];
n4 [fillcolor=gray, label="{<name> n4}"];
n5 [fillcolor=gray, label="{<name> n5}"];
n1 n2 n3->n4->n5;
n1->n3[color=red];
n1->n2[color=gray];
n2->n3[color=gray];
n2->n1[color=red, headport=ne, tailport=e];
}
subgraph pp{
node_pp [fillcolor=yellow, label="{<name> **node}"];
node_pp->head_p[headport=n];
head_p [fillcolor=gray, label="{<name> *head}"];
head_p->n2;
tmp_p [fillcolor=gray, label="{<name> *tmp}"];
tmp_p->n1;
}
}
```
對應的記憶體操作：
| pointer2pointer | | | pointer2value | | | value | | |
|:---------------:|---------|------|---------------|---------|----------|---------|------------|-----------|
| name | address | data | name | address | data | address | data:value | data:next |
| node | ... | 205 | n1 | 200 | 100 | 100 | 1 | 101=>102 |
| | | | n2 | 201 | 101 | 101 | 2 | 102=>100 |
| | | | n3 | 202 | 102 | 102 | 3 | 103 |
| | | | n4 | 203 | 103 | 103 | 4 | 104 |
| | | | n5 | 204 | 104 | 104 | 5 | 0 |
| | | | head | 205 | 100=>101 | | | |
| | | | tmp | 206 | 100 | | | |
* 下一個初始狀況
```c=3
for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next) {
node_t *tmp = *node;
```
```graphviz
digraph g{
rankdir=LR;
node [shape=record, style=filled];
subgraph linked_list{
n1 [fillcolor=gray, label="{<name> n1}"];
n2 [fillcolor=gray, label="{<name> n2}"];
n3 [fillcolor=gray, label="{<name> n3}"];
n4 [fillcolor=gray, label="{<name> n4}"];
n5 [fillcolor=gray, label="{<name> n5}"];
n1->n3->n4->n5;
n2->n1;
}
subgraph pp{
node_pp [fillcolor=yellow, label="{<name> **node}"];
node_pp->n3[headport=n];
head_p [fillcolor=gray, label="{<name> *head}"];
head_p->n2;
tmp_p [fillcolor=gray, label="{<name> *tmp}"];
tmp_p->n3[headport=s];
}
}
```
對應的記憶體操作：
| pointer2pointer | | | pointer2value | | | value | | |
|:---------------:|---------|----------|---------------|---------|----------|---------|------------|-----------|
| name | address | data | name | address | data | address | data:value | data:next |
| node | ... | 205=>202 | n1 | 200 | 100 | 100 | 1 | 101=>102 |
| | | | n2 | 201 | 101 | 101 | 2 | 102=>100 |
| | | | n3 | 202 | 102 | 102 | 3 | 103 |
| | | | n4 | 203 | 103 | 103 | 4 | 104 |
| | | | n5 | 204 | 104 | 104 | 5 | 0 |
| | | | head | 205 | 100=>101 | | | |
| | | | tmp | 206 | 100=>102 | | | |
### `reverse()`
```c=1
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 g{
rankdir=LR;
node [shape=record, style=filled];
subgraph linked_list{
n1 [fillcolor=gray, label="{<name> n1}"];
n2 [fillcolor=gray, label="{<name> n2}"];
n3 [fillcolor=gray, label="{<name> n3}"];
n4 [fillcolor=gray, label="{<name> n4}"];
n5 [fillcolor=gray, label="{<name> n5}"];
n1->n2->n3->n4->n5;
cursor [fillcolor=gray];
}
subgraph pp{
head_p [fillcolor=gray, label="{<name> *head}"];
head_p->n1;
}
}
```
* 第一輪迴圈執行結束
```c=1
while (head) {
node_t *next = head->next;
head->next = cursor;
cursor = head;
head = next;
}
```
```graphviz
digraph g{
rankdir=LR;
node [shape=record, style=filled];
subgraph linked_list{
n1 [fillcolor=gray, label="{<name> n1}"];
n2 [fillcolor=gray, label="{<name> n2}"];
n3 [fillcolor=gray, label="{<name> n3}"];
n4 [fillcolor=gray, label="{<name> n4}"];
n5 [fillcolor=gray, label="{<name> n5}"];
n2->n3->n4->n5;
cursor [fillcolor=gray];
next [fillcolor=gray];
null[fillcolor=gray];
next->n2;
n1->n2 [color=gray];
n1->null[color=red];
}
subgraph pp{
head_p [fillcolor=gray, label="{<name> *head}"];
head_p->n2;
cursor->n1;
}
}
```
* 第二輪迴圈執行結束
```graphviz
digraph h{
rankdir=LR;
node [shape=record, style=filled];
subgraph linked_list{
n1 [fillcolor=gray, label="{<name> n1}"];
n2 [fillcolor=gray, label="{<name> n2}"];
n3 [fillcolor=gray, label="{<name> n3}"];
n4 [fillcolor=gray, label="{<name> n4}"];
n5 [fillcolor=gray, label="{<name> n5}"];
n3->n4->n5;
cursor [fillcolor=gray];
next [fillcolor=gray];
null[fillcolor=gray];
next->n3;
n2->n1[color=red];
n1->null;
n2->n3[color=gray];
}
subgraph pp{
head_p [fillcolor=gray, label="{<name> *head}"];
head_p->n3;
cursor->n2;
}
}
```
* 第三輪迴圈執行結束
```graphviz
digraph h{
rankdir=LR;
node [shape=record, style=filled];
subgraph linked_list{
n1 [fillcolor=gray, label="{<name> n1}"];
n2 [fillcolor=gray, label="{<name> n2}"];
n3 [fillcolor=gray, label="{<name> n3}"];
n4 [fillcolor=gray, label="{<name> n4}"];
n5 [fillcolor=gray, label="{<name> n5}"];
n4->n5;
cursor [fillcolor=gray];
next [fillcolor=gray];
null[fillcolor=gray];
next->n4;
n3->n2[color=red];
n2->n1->null;
n3->n4[color=gray];
}
subgraph pp{
head_p [fillcolor=gray, label="{<name> *head}"];
head_p->n4;
cursor->n3;
}
}
```
* 以此類推直到執行結束
```graphviz
digraph h{
rankdir=LR;
node [shape=record, style=filled];
subgraph linked_list{
n1 [fillcolor=gray, label="{<name> n1}"];
n2 [fillcolor=gray, label="{<name> n2}"];
n3 [fillcolor=gray, label="{<name> n3}"];
n4 [fillcolor=gray, label="{<name> n4}"];
n5 [fillcolor=gray, label="{<name> n5}"];
cursor [fillcolor=gray];
}
subgraph pp{
cursor->n5->n4->n3->n2->n1;
}
}
```
## 改寫 swap_pair 和 reverse
* 運用指標的指標改寫 `swap_pair` 和 `reverse`
### swap_pair 改寫
* swap_pair 原來就運用到指標的指標，稍微改一下就行
```c=1
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 改寫
* reverse 重點是最後一行的 `*head = cursor;` 運用指標的指標更改 `*head` 指標的值，觀念來自老師的[你所不知道的 C 語言：指標篇 (上) (2018-02-05)](https://youtu.be/G7vERppua9o?list=PL6S9AqLQkFpqAHXlqoH2JpvOSmku7WjRU&t=6934)
```c=1
void reverse(node_t **head)
{
node_t *cursor = NULL;
while (*head) {
node_t *next = (*head)->next;
(*head)->next = cursor;
cursor = *head;
*head = next;
}
*head = cursor;
}
```
## Fisher–Yates shuffle
* TBD
Sign in with Wallet
Connect another wallet