owned this note
owned this note
Published
Linked with GitHub
# 2020q3 Homework1 (quiz1)
contributed by < `dalaoqi` >
## Outline
[TOC]
考慮一個單向 linked list，其結構定義為:
```cpp
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
## 程式運作原理
### add_entry
```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);
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node;
}
```
新增一個節點到 linked list 的尾端：
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
indirect[shape=none];
head[shape=none];
node_0[shape=box];
node_1[shape=box];
node_2[shape=box];
NULL_1[shape=none,label="NULL"];
NULL_2[shape=none,label="NULL"];
new_node[shape=box];
node_0->node_1->node_2->NULL_2;
new_node->NULL_1;
{rank=same;indirect->head->node_0;}
}
```
在這函式裡，首先建立了一個 `indirect` 指標指向 `head` 指標， `head` 則指向 linked list 的起點。
接著透過 malloc 新增一個節點的記憶體空間，這個節點會指向 NULL，經過 while 迴圈 ， `indirect` 會指向 linked list 最尾端NULL，此時將新節點指派給 `indirect` 完成新增節點。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
indirect[shape=none];
head[shape=none];
node_0[shape=box];
node_1[shape=box];
node_2[shape=box];
NULL_1[shape=none,label="NULL"];
NULL_2[shape=none,label="NULL"];
new_node[shape=box];
node_0->node_1->node_2->NULL_2;
new_node->NULL_1;
{rank=same;head->node_0;}
{rank=same;indirect->NULL_2;}
}
```
```graphviz
digraph G {
graph[pencolor=transparent];
indirect[shape=none];
head[shape=none];
node_0[shape=box];
node_1[shape=box];
node_2[shape=box];
NULL_1[shape=none,label="NULL"];
new_node[shape=box];
{rank=same;
node_0->node_1->node_2->new_node->NULL_1;}
head->node_0;
indirect->new_node;
}
```
* 此函式中的 `assert(new_node);` 目的是為了要確保新的節點有成功 malloc (NULL 失敗)，因此 `AA1` 為 `assert(new_node);`
* `AA2` 答案為 `*indirect = new_node` 是因為需要得知 linked list 最尾端的位置在何處。
### find_entry
```cpp
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 的頭開始遍歷，直到找到符合的節點後回傳該節點。
### remove_entry
```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);
}
```
移除某個節點（entry），類似 `add_entry` 的做法，詳細如下：
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
indirect[shape=none];
head[shape=none];
node_0[shape=box];
node_1[shape=box];
node_2[shape=box];
node_3[shape=box];
NULL_1[shape=none,label="NULL"];
delete[shape=none,label="want_to_delete"];
node_0->node_1->node_2->node_3->NULL_1;
{rank=same;indirect->head->node_0;}
{rank=same; delete->node_2}
}
```
經由 while 迴圈找到該 entry
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
indirect[shape=none];
head[shape=none];
node_0[shape=box];
node_1[shape=box];
node_2[shape=box];
node_3[shape=box];
NULL_1[shape=none,label="NULL"];
delete[shape=none,label="want_to_delete_entry"];
node_0->node_1->node_2->node_3->NULL_1;
{rank=same;head->node_0;}
{rank=same; indirect->delete->node_2}
}
```
更換 indirect 指向的記憶體空間，再 free entry。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
indirect[shape=none];
head[shape=none];
node_0[shape=box];
node_1[shape=box];
node_2[shape=box];
node_3[shape=box];
NULL_1[shape=none,label="NULL"];
delete[shape=none,label="want_to_delete_entry"];
node_0->node_1->node_3->NULL_1;
{rank=same;head->node_0;}
{rank=same; delete->node_2}
{rank=same; indirect->node_3}
}
```
### swap_pair
```cpp
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;
}
```
`node_0` 和 `node_1` 交換， `node_2` 和 `node_3` 交換，以次類推。
這裡的做法也是使用指標的指標來做操作。
一開始進入迴圈時長這樣， node 指標指向 head 指標。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
head[shape=none];
n[shape=none,label="node"];
node_0[shape=box];
node_1[shape=box];
node_2[shape=box];
node_3[shape=box];
NULL_1[shape=none,label="NULL"];
node_0->node_1->node_2->node_3->NULL_1;
{rank=same;n->head->node_0;}
}
```
宣告 tmp 指向 *node（head 指標）。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
head[shape=none];
n[shape=none,label="node"];
node_0[shape=box];
tmp[shape=none]
node_1[shape=box];
node_2[shape=box];
node_3[shape=box];
NULL_1[shape=none,label="NULL"];
node_0->node_1->node_2->node_3->NULL_1;
{rank=same;n->head->node_0;}
tmp->node_0;
}
```
`*node = (*node)->next;`
node 新位址指向 node 的下個節點的位址。因此 `BB2` 答案為 `*node = (*node)->next;`
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
head[shape=none];
n[shape=none,label="node"];
node_0[shape=box];
tmp[shape=none]
node_1[shape=box];
node_2[shape=box];
node_3[shape=box];
NULL_1[shape=none,label="NULL"];
node_0->node_1->node_2->node_3->NULL_1;
{rank=same;n->head->node_1}
{rank=same;tmp->node_0;}
}
```
`tmp->next = (*node)->next;`
tmp 新位址指向 node 下一個的位址。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
head[shape=none];
n[shape=none,label="node"];
node_0[shape=box];
tmp[shape=none]
node_1[shape=box];
node_2[shape=box];
node_3[shape=box];
NULL_1[shape=none,label="NULL"];
node_1->node_2->node_3->NULL_1;
{rank=same;n->head->node_1}
{rank=same;tmp->node_0->node_2;}
}
```
node 指向 tmp 完成交換。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
head[shape=none];
n[shape=none,label="node"];
node_0[shape=box];
tmp[shape=none]
node_1[shape=box];
node_2[shape=box];
node_3[shape=box];
NULL_1[shape=none,label="NULL"];
node_1->node_0->node_2->node_3->NULL_1;
{rank=same;n->head->node_1}
{rank=same;tmp->node_0}
}
```
因為是兩倆交換，因此 node 在每次 iteration 完都要 往前兩格，所以 `BB1` 為 `node = &(*node)->next->next`
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
head[shape=none];
n[shape=none,label="node"];
node_0[shape=box];
tmp[shape=none]
node_1[shape=box];
node_2[shape=box];
node_3[shape=box];
NULL_1[shape=none,label="NULL"];
node_1->node_0->node_2->node_3->NULL_1;
{rank=same;head->node_1}
{rank=same;tmp->node_0}
{rank=same;n->node_2}
}
```
### reverse
```cpp
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;
}
```
做 linked list 反轉，一開始大概是長這樣。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
head[shape=none];
node_0[shape=box];
cursor[shape=none];
node_1[shape=box];
node_2[shape=box];
node_3[shape=box];
NULL_1[shape=none,label="NULL"];
NULL_2[shape=none,label="NULL"];
node_0->node_1->node_2->node_3->NULL_1;
{rank=same;head->node_0}
rank=same;cursor->NULL_2
}
```
`node_t *next = head->next;` ， next 指標指向 head 的 next。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
head[shape=none];
next[shape=none];
node_0[shape=box];
cursor[shape=none];
node_1[shape=box];
node_2[shape=box];
node_3[shape=box];
NULL_1[shape=none,label="NULL"];
NULL_2[shape=none,label="NULL"];
node_0->node_1->node_2->node_3->NULL_1;
{rank=same;head->node_0}
{rank=same;next->node_1}
cursor->NULL_2
}
```
`CCC` 是 `head->next = cursor; cursor = head;` ，其中 cursor 是用來記住 head 前一個節點使得之後可以被指向，達成反轉的效果。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
head[shape=none];
next[shape=none];
node_0[shape=box];
cursor[shape=none];
node_1[shape=box];
node_2[shape=box];
node_3[shape=box];
NULL_1[shape=none,label="NULL"];
NULL_2[shape=none,label="NULL"];
node_0->node_1->node_2->node_3->NULL_1;
{rank=same;head->node_0}
{rank=same;next->node_1}
{rank=same;cursor->node_0;}
rank=same;node_0->NULL_2;
}
```
`head = next;` ，遍歷下去後直到 head = NULL，回傳 cursor 做為新的 head。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
next[shape=none,label="next(head)"];
node_0[shape=box];
cursor[shape=none];
node_1[shape=box];
node_2[shape=box];
node_3[shape=box];
NULL_1[shape=none,label="NULL"];
NULL_2[shape=none,label="NULL"];
node_0->node_1->node_2->node_3->NULL_1;
{rank=same;next->node_1}
{rank=same;cursor->node_0;}
rank=same;node_0->NULL_2;
}
```
## 延伸問題
避免函式回傳指標。
### swap_pair
```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;
}
}
```
其實原本的寫法就可以說是指標的指標的操作，只是還需要回傳 head ，因此稍微改一下，將傳入的參數改成是傳位址，用 node 去接這個傳入的參數，變相利用 node 當作 head 進行操作。
### reverse
```cpp
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;
}
```
一樣也是傳 head 的位址參數到函式中，概念就和原先的方式一樣，比較要注意的地方是在最後要把 cursor 指標 指派給 *head 。
### 遞迴版 reverse
```cpp
void reverse(node_t **head)
{
rev_recurive(*head, head);
}
void rev_recurive(node_t *head, node_t **headRef)
{
if (head == NULL) {
return;
}
node_t *first = head;
node_t *rest = head->next;
if (rest == NULL) {
*headRef = first;
return;
}
rev_recurive(rest, headRef);
rest->next = first;
first->next = NULL;
}
```
遞迴的概念是將 linked list 分成 第一個節點 ( `first` ) 和剩下其他的節點們 ( `rest` ) 遞迴拆解下去。遞迴函式傳入的會是 `head` 指標和 `head` 指標的位址，此方式是為了避免回傳指標。
從 `reverse` call `rev_recurive` 函式後，在進入 `rev_recurive` 函式之前的狀態會長這樣。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
rest[shape=none];
node_0[shape=box];
head[shape=none,label="first"];
node_1[shape=box];
node_2[shape=box];
NULL_1[shape=none, label="NULL"];
node_0->node_1->node_2->NULL_1;
{rank=same;head->node_0}
{rank=same;rest->node_1}
}
```
進入 `rev_recurive` 後， `first` 和 `rest` 會更新成下面這樣。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
rest[shape=none];
node_0[shape=box];
head[shape=none,label="first"];
node_1[shape=box];
node_2[shape=box];
NULL_1[shape=none, label="NULL"];
node_0->node_1->node_2->NULL_1;
{rank=same;head->node_1}
{rank=same;rest->node_2}
}
```
一直遞迴下去，直到 `rest` 碰到 `NULL` 進入 if 判斷式。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
rest[shape=none];
node_0[shape=box];
head[shape=none,label="first"];
node_1[shape=box];
node_2[shape=box];
NULL_1[shape=none, label="NULL"];
node_0->node_1->node_2->NULL_1;
{rank=same;head->node_2}
{rank=same;rest->NULL_1}
}
```
在 if 在判斷式中將目前 `first` 節點的位址指派給 `headRef` 目的是為了將 linked list 最後面節點的位址指派給原先傳進來的 head 位址。之後return 。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
rest[shape=none];
node_0[shape=box];
head[shape=none,label="first"];
headRef[shape=none];
node_1[shape=box];
node_2[shape=box];
NULL_1[shape=none, label="NULL"];
node_0->node_1->node_2->NULL_1;
{rank=same;headRef->head->node_2}
{rank=same;rest->NULL_1}
}
```
return 之後，繼續往下做還沒做完的事情，因為 return 回到遞迴的前一層，所以 `rest` 跑回 `first` 的位置， `first` 跑回指向前一個 node（回到進到函式前的狀態）。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
rest[shape=none];
node_0[shape=box];
head[shape=none,label="first"];
headRef[shape=none];
node_1[shape=box];
node_2[shape=box];
NULL_1[shape=none, label="NULL"];
node_0->node_1->node_2->NULL_1;
{rank=same;headRef->rest->node_2}
{rank=same;head->node_1}
}
```
繼續完成沒做完的事， `rest` 指向 `first` 指向的節點， `first` 指向的節點指向 `NULL`。此次的函式執行完畢，返回上一層遞迴。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR;
rest[shape=none];
node_0[shape=box];
NULL_1[shape=none, label="NULL"];
head[shape=none,label="first"];
headRef[shape=none];
node_1[shape=box];
node_2[shape=box];
node_0->node_1;
{rank=same;headRef->rest->node_2}
{rank=same;head->node_1}
node_2->node_1->NULL_1
}
```
一樣 `rest` 跑回 `first` 的位置， `first` 跑回指向前一個 node。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR;
rest[shape=none];
node_0[shape=box];
NULL_1[shape=none, label="NULL"];
head[shape=none,label="first"];
headRef[shape=none];
node_1[shape=box];
node_2[shape=box];
node_0->node_1;
{rank=same;headRef->node_2};
{rank=same;rest->node_1}
{rank=same;head->node_0}
node_2->node_1->NULL_1
}
```
和前一次的遞迴一樣做完剩下的工作。
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR;
rest[shape=none];
node_0[shape=box];
NULL_1[shape=none, label="NULL"];
head[shape=none,label="first"];
headRef[shape=none];
node_1[shape=box];
node_2[shape=box];
node_1->node_0->NULL_1;
{rank=same;headRef->node_2};
{rank=same;rest->node_1}
{rank=same;head->node_0}
node_2->node_1
}
```
### Fisher–Yates shuffle
參考 [wiki, Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)進行實作。
```cpp
void shuffle(node_t **head)
{
int len = 0;
srand(time(NULL));
node_t **cursor = head;
while(*cursor) {
len++;
cursor = &(*cursor)->next;
}
node_t *first = NULL;
for (int i = len; i > 0; i--) {
int random = rand() % i;
cursor = head;
while (random--) {
cursor = &(*cursor)->next;
}
node_t *new_node = *cursor;
*cursor = (*cursor)->next;
new_node->next = NULL;
if (first) {
new_node->next = first;
first = new_node;
} else {
first = new_node;
}
}
*head = first;
}
```
* 一開始會去計算整個 linked list 的長度有多長。知道長度後就開始進入該演算法的實作。
* 一開始會宣告 `first` ，這是待會要指派給 head 的新的 linked list 的頭。
* 隨後 `cursor` 會去找被挑選中的 node 。
* 找到後會有一個 `new_node` 指標去指向這個被找到的 node 。而 `cursor` 則將此 node 的前一個和後一個的 node 連接。
* `new_node` append 到剛剛的 `first` 。直到迴圈結束。
* 迴圈結束後，將原先的 `head` 的更換為 `first` 。
:::warning
延伸問題 :fire: :fire: :fire:
* 思考可能的更好的寫法，能否降低時間複雜度。
* 或是其他更好的洗牌演算法。
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
