# 2020q3 Homework1 (quiz1)
contributed by < ptzling310 >
- 假設
1. 單向 linked list
2. No circular
## 事前作業
由於對 Pointer 不熟悉, 所以另外寫一個 Note：[筆記連結](https://hackmd.io/@ptzling310/pointer)。
- [x] Pointer
- [x] Pointer to pointer
- [ ] 用Pointer 當parameter
:::info
pointer to pointer 指標再移動時，我自己會容易搞混( 有的是移動到 node 的 next ， 有的移動到下一個 node。
:::
## Homework
- [x] 解釋上述程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現
:::info
我其實想把指標指向 node 畫直的， node 間畫成橫的，但目前都是全部箭頭橫向。
要再找時間改正( 我認為我自己這樣畫會比較好區分指標跟 node) 。
:::
- [x] 函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = ... 的更新，請用指標的指標來改寫，並避免回傳指標
- [x] 以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_recursive，隨後在 reverse 函式中呼叫 rev_recursive;
- [ ] 針對 singly-linked list 的節點，實作 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)，你應該儘量降低記憶體的使用量;
## 原程式碼
```c=
#include <stdio.h>
#include <stdlib.h>
typedef struct __node {
//Node 儲存兩個東西
int value; //內容
struct __node *next; //下一個節點
} node_t;
void add_entry(node_t **head, int new_value)
{
//建一個 pointer: indirect 和 head 指向同一個 node
node_t **indirect = head;
//new NODE
node_t *new_node = malloc(sizeof(node_t));
new_node->value = new_value;
new_node->next = NULL;
//要找到尾端插入 node
assert(new_node);
while (*indirect)
indirect = &(*indirect)->next;
//找到則插入
*indirect = new_node;
}
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; node = &(*node)->next->next)
{
node_t *tmp = *node;
*node = (*node)->next;
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;
cursor->next = head; head->next->next = cursor;
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); //NULL
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); //72-101-108-109-110-111
node_t *entry = find_entry(head, 101);//從 head 找 101 在地node
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);
swap_pair(&head);
print_list(head);
//head = reverse(head);
reverse(&head);
print_list(head);
return 0;
}
```
結果
```c=
72 101 108 109 110 111
72 108 109 110
108 72 110 109
109 110 72 108
```
## Struct
### node_t
定義structure,別名node_t
```c=
typedef struct __node {
//Node 儲存兩個東西
int value; //內容
struct __node *next; //下一個節點
} node_t;
```
圖示
```graphviz
digraph structs
{
node[shape=record]
struct1 [label="<f0> value|<f1> next"];
}
```
- 若使用別名,則再建立NODE1: ```node_t NODE1```
```c=
typedef struct __node {
//Node 儲存兩個東西
int value; //內容
struct __node *next; //下一個節點
};
```
若**無**使用別名,則再建立NODE1: `struct __node NODE1`
## Function
在 main() function中：
`node_t *head = NULL;`
表示一個 pointer: head 指向NULL。之後這個 head 會一直指向 list 中的第一個 node。
```
head → NULL
```
---------------------------------------------------
### Add_entry
新增一個 node
#### Paramer
1. `node_t **head`: 想成 `node_t **head = &head(main 中設定的那個 head)`
2. `int new_value`: node 要存的值
#### Code
```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;
}
```
#### 理解
會先建立一個 potiner to pointer: indirect 指向 head 所指的 node。
再來分配空間、值給 new node。最後利用 indirect 走訪 list ，找到 new node 的插入位址(NULL的地方)，再將 new node 丟進去。
#### Graph
##### 1. 情況一： 新增**第一個**node
```c
node_t *head = NULL;
```
```graphviz
digraph structs {
node [shape=record];
struct1 [label="{ head |{ <value>0x0 }}"];
NULL1[label="...",shape=plaintext]
struct1:value -> NULL1
}
```
```c
add_entry(&head, 72)
```
main 中會呼叫 `add_entry(node_t **head, int new_value)`，設定參數
`note_t **head= &head(main)`以及`int new_value=72`，為了方便區分，來自 main 的 head 記為 head(main)。
```graphviz
digraph structs {
node [shape=record];
head_main [label="{ head(main) |{ <addr>0x0 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
NULL1[label="...",shape=plaintext]
head_main:addr -> NULL1
head->head_main;
}
```
```c=1
node_t **indirect = head;
```
再來進入 add_entry 的 function 中。 為了 traversal list ， 所以設一個指標來記錄。
`**indirect = head = &head(main)`
```graphviz
digraph structs {
node [shape=record];
head_main [label="{ head(main) |{ <addr>0x0 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
indirect [label="{ indirect |{ &head}}"];
NULL1[label="...",shape=plaintext]
head_main:addr -> NULL1
head->head_main;
indirect->head_main
}
```
```c=3
node_t *new_node = malloc(sizeof(node_t));
new_node->value = new_value;
new_node->next = NULL;
assert(new_node);
```
這部分用來新增 node ，並設定應該有的值。
```graphviz
digraph structs {
node [shape=record];
head_main[label="{ head(main) |{ <addr> &NULL }}"];
head[label="{ head |{ <addr>&head(main) }}"];
indirect [label="{ indirect |{ &head}}"];
NULL1[label="NULL",shape=plaintext]
head_main->NULL1
indirect->head_main;
head->head_main
rankdir=LR
{
//rankdir=LR;
n1[label=" {72 | <next> }"];
NULL_n1[label="NULL",shape=plaintext];
n1:next->NULL_n1
}
}
```
```c=9
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node;
```
藉由 indirect 去查看他所指向的位址所指向的是否為NULL (也就是 head(main) 的值)，找到後將 indirect 所指的位址的值放入 new node。
```graphviz
digraph structs {
node [shape=record];
rankdir=LR
{
//rankdir=LR;
n1[label=" {72 | <next> }"];
NULL_n1[label="NULL",shape=plaintext];
n1:next->NULL_n1
}
head_main[label="{ head(main) |{ <addr> &72 }}"];
head[label="{ head |{ <addr>&head(main) }}"];
indirect [label="{ indirect |{ &72}}"];
//NULL1[label="NULL",shape=plaintext]
head_main->n1;
head->head_main;
indirect->head_main;
}
```
##### 情況二：在有 node 存在的 list 中插入
承情況一，目前 list 中已經有 72 這個 node，現在要插入 101。
```c
add_entry(&head, 101);
```
main 中會呼叫 add_entry(node_t **head, int new_value)，設定參數
note_t **head= &head(main)以及int new_value=10為了方便區分，來自 main 的 head 記為 head(main)。
```graphviz
digraph structs {
node [shape=record];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
head->head_main;
//rankdir=LR;
n1[label=" {72 | <next> }"];
NULL_n1[label="NULL",shape=plaintext];
n1:next->NULL_n1
head_main:addr->n1
}
}
```
```c=1
node_t **indirect = head;
```
再來進入 add_entry 的 function 中。 為了 traversal list ， 所以設一個指標來記錄。
`**indirect = head = &head(main)`
```graphviz
digraph structs {
node [shape=record];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
head->head_main;
indirect [label="{ indirect |{ &head(main)}}"];
//rankdir=LR;
n1[label=" {72 | <next> }"];
NULL_n1[label="NULL",shape=plaintext];
indirect->head_main;
n1:next->NULL_n1
head_main:addr->n1;
}
}
```
```c=3
node_t *new_node = malloc(sizeof(node_t));
new_node->value = new_value;
new_node->next = NULL;
assert(new_node);
```
這部分用來新增 node ，並設定應該有的值。
```graphviz
digraph structs {
node [shape=record];
n2[label=" {101 | <next> }"];
NULL_n2[label="NULL",shape=plaintext];
n2:next->NULL_n2
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
head->head_main;
indirect [label="{ indirect |{ &head(main)}}"];
//rankdir=LR;
n1[label=" {72 | <next> }"];
NULL_n1[label="NULL",shape=plaintext];
n1:next->NULL_n1
head_main:addr->n1;
indirect->head_main;
}
}
```
```c=9
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node;
```
由於此 list 中已有node，故 indirect 必須往前。
```graphviz
digraph structs {
node [shape=record];
n2[label=" {101 | <next> }"];
NULL_n2[label="NULL",shape=plaintext];
n2:next->NULL_n2
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
head->head_main;
indirect [label="{ indirect |{ &head(main)}}"];
//rankdir=LR;
n1[label=" {72 | <next> }"];
NULL_n1[label="NULL",shape=plaintext];
n1:next->NULL_n1
head_main:addr->n1;
indirect->NULL_n1;
}
}
```
最後找到 NULL ，插入new node。
```graphviz
digraph structs {
node [shape=record];
n2[label=" {101 | <next> }"];
NULL_n2[label="NULL",shape=plaintext];
n2:next->NULL_n2
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
head->head_main;
indirect [label="{ indirect |{ &head(main)}}"];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n1:next->n2;
head_main:addr->n1;
indirect->n2;
}
}
```
---------------------------------------------------
### Find_entry()
去找到 list 中的某個數所在的位址，並且回傳
- Code
```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;
}
```
- 理解
建立一個 pointer: current 指向 head，以記錄 list 第一個 node。
進入 for 迴圈，當 current 所指 node 有值，但不為所尋找的值，則往下一個 node 前進。
- 目前 list 狀態
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n2[label=" {101 | <next> }"];
n3[label=" {108 | <next> }"];
n4[label=" {109 | <next> }"];
n5[label=" {110 | <next> }"];
n6[label=" {111 | <next> }"];
n1:next->n2;
n2:next->n3;
n3:next->n4;
n4:next->n5;
n5:next->n6;
n6:next->NULL;
head_main:addr->n1;
}
}
```
```c
node *entry = find_entry(head,101);
```
在 main 中，利用 pointer：entry 來記錄101的 address。
呼叫 `find_entry(head,101)`時，設定參數`node_t *head=head(main)`以及`int value=101`。
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
head [label="{ head |{ <addr>&72 }}"];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n2[label=" {101 | <next> }"];
n3[label=" {108 | <next> }"];
n4[label=" {109 | <next> }"];
n5[label=" {110 | <next> }"];
n6[label=" {111 | <next> }"];
n1:next->n2;
n2:next->n3;
n3:next->n4;
n4:next->n5;
n5:next->n6;
n6:next->NULL;
head_main:addr->n1;
head->n1;
}
}
```
```c=3
node_t *current = head;
```
建一個 poninter：current 指向 head 所指向的 node。
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
head [label="{ head |{ <addr>&72 }}"];
current [label="{ current |{ <addr>&72 }}"];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n2[label=" {101 | <next> }"];
n3[label=" {108 | <next> }"];
n4[label=" {109 | <next> }"];
n5[label=" {110 | <next> }"];
n6[label=" {111 | <next> }"];
n1:next->n2;
n2:next->n3;
n3:next->n4;
n4:next->n5;
n5:next->n6;
n6:next->NULL;
head_main:addr->n1;
head->n1;
current->n1;
}
}
```
```c=4
for ( ; current && current->value != value; current = current->next)
/* interate */;
return current;
```
當 current 所指向的位址非 NULL 且 current 所指向的值不為要找的，則往前一個 node。找到該值之後，回傳 `current`，在此例就是回傳`&101`，故在 main 中， `node_t *entry = &101`。
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
head [label="{ head |{ <addr>&72 }}"];
current [label="{ current |{ <addr>&101 }}"];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n2[label=" {101 | <next> }"];
n3[label=" {108 | <next> }"];
n4[label=" {109 | <next> }"];
n5[label=" {110 | <next> }"];
n6[label=" {111 | <next> }"];
n1:next->n2;
n2:next->n3;
n3:next->n4;
n4:next->n5;
n5:next->n6;
n6:next->NULL;
head_main:addr->n1;
head->n1;
current->n2;
}
}
```
---------------------------------------------------
### Remove_entry
- 目前 list 狀態
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
entry [label="{ entry |{ <addr>&101 }}"];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n2[label=" {101 | <next> }"];
n3[label=" {108 | <next> }"];
n4[label=" {109 | <next> }"];
n5[label=" {110 | <next> }"];
n6[label=" {111 | <next> }"];
n1:next->n2;
n2:next->n3;
n3:next->n4;
n4:next->n5;
n5:next->n6;
n6:next->NULL;
head_main:addr->n1;
entry->n2;
}
}
```
- Code
```c=
void remove_entry(node_t **head, node_t *entry)
{
//指向 head 所指的 node
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
```
- 理解
建立一個 indirect 指向 head 所指 node (第一個 node )。
當 indirect 與 entry 指向不同 node 時，則在繼續確認下一個 node，
直到找到後，將 indirect 指向 entry 的下一個 node，便可釋放 entry 所指 node。
```c
remove_entry(&head,entry);
```
在 main 中呼叫 remove_entry function，故設定參數`node_t **head = head(main)`及`node_t *entry = entry)`。
```graphviz
digraph structs {
node [shape=record];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
entry_main [label="{ entry(main) |{ <addr>&101 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
entry [label="{ entry |{ <addr>&101 }}"];
more[label="...",shape=plaintext];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n2[label=" {101 | <next> }"];
n3[label=" {108 | <next> }"];
n4[label=" {109 | <next> }"];
n1:next->n2;
n2:next->n3;
n3:next->n4;
n4:next->more;
head_main:addr->n1;
entry_main->n2;
head->head_main;
entry->n2;
}
}
```
```c=4
node_t **indirect = head;
```
建一個 pointer to pointer：indirect 指向 head 。
```graphviz
digraph structs {
node [shape=record];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
entry_main [label="{ entry(main) |{ <addr>&101 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
entry [label="{ entry |{ <addr>&101 }}"];
indirect [label="{ indirect |{ <addr>&head(main) }}"];
more[label="...",shape=plaintext];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n2[label=" {101 | <next> }"];
n3[label=" {108 | <next> }"];
n4[label=" {109 | <next> }"];
n1:next->n2;
n2:next->n3;
n3:next->n4;
n4:next->more;
head_main:addr->n1;
entry_main->n2;
head->head_main;
entry->n2;
indirect->head_main;
}
}
```
```c=6
while ((*indirect) != entry)
indirect = &(*indirect)->next;
```
`*indirect` 意為 indirect所指的 node 所存的值不與 entry 相同(此例中，要為 &101 )。
`indirect = &(*indirect)->next` 第一次時看我會把它會錯意，認為是 indirect 直接指向 head 的下一個node (也就是指向 101)。但在接下來一行程式會發現`*indirect = entry->next;`執行起來怪怪的。 所以這裡其實應該是指向**72的 next** 。所以下圖，`*indirect`的值就為 &101了！ while迴圈結束。
```graphviz
digraph structs {
node [shape=record];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
entry_main [label="{ entry(main) |{ <addr>&101 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
entry [label="{ entry |{ <addr>&101 }}"];
indirect [label="{ indirect |{ <addr> 72-next }}"];
more[label="...",shape=plaintext];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n2[label=" {101 | <next> }"];
n3[label=" {108 | <next> }"];
n4[label=" {109 | <next> }"];
n1:next->n2;
n2:next->n3;
n3:next->n4;
n4:next->more;
head_main:addr->n1;
entry_main->n2;
head->head_main;
entry->n2;
indirect->n1:next;
}
}
```
```c=9
*indirect = entry->next;
```
將 indirect 所指向的位址的**值**改為 entry 所指的下一個位址。
```graphviz
digraph structs {
node [shape=record];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
entry_main [label="{ entry(main) |{ <addr>&101 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
entry [label="{ entry |{ <addr>&101 }}"];
indirect [label="{ indirect |{ <addr> 72-next }}"];
more[label="...",shape=plaintext];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n2[label=" {101 | <next> }"];
n3[label=" {108 | <next> }"];
n4[label=" {109 | <next> }"];
n1:next->n3;
n2:next->n3;
n3:next->n4;
n4:next->more;
head_main:addr->n1;
entry_main->n2;
head->head_main;
entry->n2;
indirect->n1:next;
}
}
```
```c=10
free(entry);
```
```graphviz
digraph structs {
node [shape=record];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
indirect [label="{ indirect |{ <addr> 72-next }}"];
more[label="...",shape=plaintext];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n3[label=" {108 | <next> }"];
n4[label=" {109 | <next> }"];
n1:next->n3;
n3:next->n4;
n4:next->more;
head_main:addr->n1;
head->head_main;
indirect->n1:next;
}
}
```
---------------------------------------------------
### Swap_pair
- 目前 list 狀態
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
//rankdir=LR;
n1[label=" {72 |<next> }"];
n2[label=" {108 |<next> }"];
n3[label=" {109 |<next> }"];
n4[label=" {110 |<next> }"];
n1->n2;
n2->n3;
n3->n4;
n4->NULL;
head_main:addr->n1;
}
}
```
:::spoiler 未改用void之程式
```c=
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;
}
```
:::
- Code 之改寫
想法是：要在 function 裡面改變 pointer 的值。所以利用 pointer to pointer 來控制 main function 中的 head。
```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;
}
}
```
- 理解
從 link list 的第一個 node 開始，一次交換兩個。
```c
//in main function
swap_pair(&head);
```
在main 呼叫 `swap_pair` 應改寫為這樣，在此設定參數`node_t **head = &head(main)`。
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n2[label=" {108 | <next> }"];
n3[label=" {109 | <next> }"];
n4[label=" {110 | <next> }"];
n1->n2;
n2->n3;
n3->n4;
n4->NULL;
head->head_main;
head_main:addr->n1;
}
}
```
`node_t **node = head`：設定 node 指向 head(main)
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
nod [label="{ node |{ <addr>&head(main) }}"];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n2[label=" {108 | <next> }"];
n3[label=" {109 | <next> }"];
n4[label=" {110 | <next> }"];
n1->n2;
n2->n3;
n3->n4;
n4->NULL;
head->head_main;
nod->head_main;
head_main:addr->n1;
}
}
```
`*node && (*node)->next`：當 node 所指向的位址及其下一個點的值不為 NULL
`node = &(*node)->next->next)` node 移到下下一個點。
```c=4
node_t *tmp = *node;
```
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
nod [label="{ node |{ <addr>&head(main) }}"];
tmp [label="{ tmp |{ <addr>&72 }}"];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n2[label=" {108 | <next> }"];
n3[label=" {109 | <next> }"];
n4[label=" {110 | <next> }"];
n1->n2;
n2->n3;
n3->n4;
n4->NULL;
head->head_main;
nod->head_main;
head_main:addr->n1;
tmp->n1;
}
}
```
```c=5
*node = (*node)->next;
```
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&108 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
nod [label="{ node |{ <addr>&head(main) }}"];
tmp [label="{ tmp |{ <addr>&72 }}"];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n2[label=" {108 | <next> }"];
n3[label=" {109 | <next> }"];
n4[label=" {110 | <next> }"];
n1->n2;
n2->n3;
n3->n4;
n4->NULL;
head->head_main;
nod->head_main;
head_main->n2;
tmp->n1;
}
}
```
```c=6
tmp->next = (*node)->next;
```
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&108 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
nod [label="{ node |{ <addr>&head(main) }}"];
tmp [label="{ tmp |{ <addr>&72 }}"];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n2[label=" {108 | <next> }"];
n3[label=" {109 | <next> }"];
n4[label=" {110 | <next> }"];
n1->n3;
n2->n3;
n3->n4;
n4->NULL;
head->head_main;
nod->head_main;
head_main->n2;
tmp->n1;
}
}
```
```c=7
(*node)->next = tmp;
```
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&108 }}"];
head [label="{ head |{ <addr>&head(main) }}"];
nod [label="{ node |{ <addr>&head(main) }}"];
tmp [label="{ tmp |{ <addr>&72 }}"];
//rankdir=LR;
n1[label=" {72 | <next> }"];
n2[label=" {108 | <next> }"];
n3[label=" {109 | <next> }"];
n4[label=" {110 | <next> }"];
n1->n3;
n2->n1;
n3->n4;
n4->NULL;
head->head_main;
nod->head_main;
head_main->n2;
tmp->n1;
}
}
```
---------------------------------------------------
### Reverse
:::spoiler 未改用void之程式碼
```c=
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
cursor->next = head; head->next->next = cursor;
head = next;
}
return cursor;
}
:::
- 目前 list 狀態
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&108 }}"];
//rankdir=LR;
n1[label=" {108 |<next> }"];
n2[label=" {72 |<next> }"];
n3[label=" {110 |<next> }"];
n4[label=" {109 |<next> }"];
n1->n2;
n2->n3;
n3->n4;
n4->NULL;
head_main:addr->n1;
}
}
```
- Code 之改寫： void
```c=
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;
}
```
`reverse(&head);`：在 main 中會呼叫 `reverse`，並設定參數`node_t **head = &head`。
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&108 }}"];
head [label="{ head |{ <addr>&head }}"];
//rankdir=LR;
n1[label=" {108 |<next> }"];
n2[label=" {72 |<next> }"];
n3[label=" {110 |<next> }"];
n4[label=" {109 |<next> }"];
n1->n2;
n2->n3;
n3->n4;
n4->NULL;
head_main:addr->n1;
head->head_main
}
}
```
```c=3
node_t *cursor = NULL;
```
建立一個 pointer：cursor 指向 NULL。
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&108 }}"];
head [label="{ head |{ <addr>&head }}"];
NULL_c[label="NULL",shape=plaintext];
cursor [label="{ cursor |{ <addr>&NULL }}"];
cursor->NULL_c;
//rankdir=LR;
n1[label=" {108 |<next> }"];
n2[label=" {72 |<next> }"];
n3[label=" {110 |<next> }"];
n4[label=" {109 |<next> }"];
n1->n2;
n2->n3;
n3->n4;
n4->NULL;
head_main:addr->n1;
head->head_main
}
}
```
```c=4
while (*head) {
node_t *next = (*head)->next;
(*head)->next = cursor;
cursor = *head;
*head = next;
}
```
當 head(main) 所指的 node 不為 NULL時，進入 while 迴圈。
`node_t *next = (*head)->next;`：建 pointer：next 指向
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&108 }}"];
head [label="{ head |{ <addr>&head }}"];
NULL_c[label="NULL",shape=plaintext];
cursor [label="{ cursor |{ <addr>&NULL }}"];
cursor->NULL_c;
next [label="{ next |{ <addr>&72 }}"];
//rankdir=LR;
n1[label=" {108 |<next> }"];
n2[label=" {72 |<next> }"];
n3[label=" {110 |<next> }"];
n4[label=" {109 |<next> }"];
n1->n2;
n2->n3;
n3->n4;
n4->NULL;
head_main:addr->n1;
head->head_main
next->n2;
}
}
```
`(*head)->next = cursor; `：將 head 所指向的 node 的 next 設為 cursor 所指。
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&108 }}"];
head [label="{ head |{ <addr>&head }}"];
NULL_c[label="NULL",shape=plaintext];
cursor [label="{ cursor |{ <addr>&NULL }}"];
cursor->NULL_c;
next [label="{ next |{ <addr>&72 }}"];
//rankdir=LR;
n1[label=" {108 |<next> }"];
n2[label=" {72 |<next> }"];
n3[label=" {110 |<next> }"];
n4[label=" {109 |<next> }"];
n1->NULL_c;
n2->n3;
n3->n4;
n4->NULL;
head_main:addr->n1;
head->head_main
next->n2;
}
}
```
`cursor = *head;`：cursor 更新到 head 所指的node
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&108 }}"];
head [label="{ head |{ <addr>&head }}"];
NULL_c[label="NULL",shape=plaintext];
cursor [label="{ cursor |{ <addr>&NULL }}"];
next [label="{ next |{ <addr>&72 }}"];
//rankdir=LR;
n1[label=" {108 |<next> }"];
n2[label=" {72 |<next> }"];
n3[label=" {110 |<next> }"];
n4[label=" {109 |<next> }"];
n1->NULL_c;
n2->n3;
n3->n4;
n4->NULL;
head_main:addr->n1;
head->head_main
next->n2;
cursor->n1;
}
}
```
`*head = next;`：head 往前
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
head [label="{ head |{ <addr>&head }}"];
NULL_c[label="NULL",shape=plaintext];
cursor [label="{ cursor |{ <addr>&NULL }}"];
next [label="{ next |{ <addr>&72 }}"];
//rankdir=LR;
n1[label=" {108 |<next> }"];
n2[label=" {72 |<next> }"];
n3[label=" {110 |<next> }"];
n4[label=" {109 |<next> }"];
n1->NULL_c;
n2->n3;
n3->n4;
n4->NULL;
head_main->n2;
head->head_main
next->n2;
cursor->n1;
}
}
```
- Code 之改寫： recursive
- 想法： Recursive 最主要是要有『自己呼叫自己』，所以第一次執行，是只做好一部份，然後在把剩下未完的部分在重新執行一樣的動作。直到執行到最後一個 node ，就結束。
```c=
node_t *reverse_recur(node_t *prev , node_t *head)
{
//recursive 終止條件
if(!head)
return prev;
node_t *next = head->next;
head->next = prev;
return reverse_recur(head,next);
}
void reverse(node_t **head)
{
*head = reverse_recur(NULL,*head);
}
```
在 main 中`reverse(&head)`會呼叫`reverse(node_t **head)`，設定參數`node_t **head(reverse) = &head(main)`
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&108 }}"];
head_reverse[label="{ head(reverse) |{ <addr>&head(main) }}"];
//rankdir=LR;
n1[label=" {108 |<next> }"];
n2[label=" {72 |<next> }"];
n3[label=" {110 |<next> }"];
n4[label=" {109 |<next> }"];
n1->n2;
n2->n3;
n3->n4;
n4->NULL;
head_main:addr->n1;
head_reverse->head_main;
}
}
```
在 reverse 又會呼叫`*reverse_recur(node_t *prev , node_t *head)`，並且設定參數`node_t *prev = NULL`以及`node_t *head= *head(reverse)`
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&108 }}"];
head_reverse[label="{ head(reverse) |{ <addr>&head(main) }}"];
head_recur[label="{ head |{ <addr>&head(main) }}"];
prev[label="{ prev |{ <addr>&NULL }}"];
NULL_prev[label="NULL",shape=plaintext];
//rankdir=LR;
n1[label=" {108 |<next> }"];
n2[label=" {72 |<next> }"];
n3[label=" {110 |<next> }"];
n4[label=" {109 |<next> }"];
n1->n2;
n2->n3;
n3->n4;
n4->NULL;
head_main:addr->n1;
head_reverse->head_main;
head_recur->head_main;
prev->NULL_prev;
}
}
```
```c=7
node_t *next = head->next;
```
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&108 }}"];
head_reverse[label="{ head(reverse) |{ <addr>&head(main) }}"];
head_recur[label="{ head |{ <addr>&head(main) }}"];
prev[label="{ prev |{ <addr>&NULL }}"];
NULL_prev[label="NULL",shape=plaintext];
next[label="{ next |{ <addr>&72 }}"];
//rankdir=LR;
n1[label=" {108 |<next> }"];
n2[label=" {72 |<next> }"];
n3[label=" {110 |<next> }"];
n4[label=" {109 |<next> }"];
n1->n2;
n2->n3;
n3->n4;
n4->NULL;
head_main:addr->n1;
head_reverse->head_main;
head_recur->head_main;
prev->NULL_prev;
next->n2;
}
}
```
```c=8
head->next = prev;
```
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&108 }}"];
head_reverse[label="{ head(reverse) |{ <addr>&head(main) }}"];
head_recur[label="{ head |{ <addr>&head(main) }}"];
prev[label="{ prev |{ <addr>&NULL }}"];
NULL_prev[label="NULL",shape=plaintext];
next[label="{ next |{ <addr>&72 }}"];
//rankdir=LR;
n1[label=" {108 |<next> }"];
n2[label=" {72 |<next> }"];
n3[label=" {110 |<next> }"];
n4[label=" {109 |<next> }"];
n1->NULL_prev;
n2->n3;
n3->n4;
n4->NULL;
head_main:addr->n1;
head_reverse->head_main;
head_recur->head_main;
prev->NULL_prev;
next->n2;
}
}
```
```c=9
return reverse_recur(head,next);
```
retrun 時又在設定參數，`node_t *prev=head`以及`node_t *head=next`。
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&72 }}"];
head_reverse[label="{ head(reverse) |{ <addr>&head(main) }}"];
head_recur[label="{ head |{ <addr>&head(main) }}"];
prev[label="{ prev |{ <addr>&108 }}"];
NULL_prev[label="NULL",shape=plaintext];
next[label="{ next |{ <addr>&72 }}"];
//rankdir=LR;
n1[label=" {108 |<next> }"];
n2[label=" {72 |<next> }"];
n3[label=" {110 |<next> }"];
n4[label=" {109 |<next> }"];
n1->NULL_prev;
n2->n3;
n3->n4;
n4->NULL;
head_main:addr->n2;
head_reverse->head_main;
head_recur->head_main;
prev->n1;
next->n2;
}
}
```
以此類推，重複上述步驟直到最後一個 node ，便可完成 reverse 。
---------------------------------------------------
### Fisher–Yates shuffle 洗牌算法
- Fisher–Yates shuffle 的概念
假設目前有6個數字要做 Fisher–Yates shuffle，每次從前面的數字中選一個與最後一個數字交換位址(也就是說最後一次的交換是決定最前面兩個位址的值)：
| Round |Range |Select | Result |
| -------- | -------- | -------- |-------- |
| Initial || | 1 2 3 4 5 6 |
```graphviz
graph graphname {
rankdir=LR
rank="same"
node [shape = circle];
1 -- 2 --3 -- 4 --5 --6
}
```
| Round |Range| Select | Result |
| -------- | -------- | -------- |-------- |
| 1 |1-6| 3|1 2 6 4 5 3|
```graphviz
graph graphname {
rankdir=LR
rank="same"
node [shape = circle];
3 [label="3", style=filled, fillcolor=grey]
1 -- 2 --6 -- 4 --5 --3
}
```
| Round |Range| Select | Result |
| -------- | -------- | -------- |-------- |
| 1 | 1-6|3|1 2 6 4 5 ++3++|
| 2 | 1-5|1|5 2 6 4 ++1 3++|
```graphviz
graph graphname {
rankdir=LR
rank="same"
node [shape = circle];
3 [label="3", style=filled, fillcolor=grey]
1 [label="1", style=filled, fillcolor=grey]
5 -- 2 --6 -- 4 --1 --3
}
```
| Round |Range| Select | Result |
| -------- | -------- | -------- | -------- |
| 1 | 1-6|3|1 2 6 4 5 ++3++|
| 2 | 1-5|1|5 2 6 4 ++1 3++|
| 3 | 1-4|1|4 2 6 ++5 1 3++|
```graphviz
graph graphname {
rankdir=LR
rank="same"
node [shape = circle];
3 [label="3", style=filled, fillcolor=grey]
1 [label="1", style=filled, fillcolor=grey]
5 [label="5", style=filled, fillcolor=grey]
4 -- 2 --6 -- 5 --1 --3
}
```
| Round |Range| Select | Result |
| -------- | -------- | -------- |-------- |
| 1 |1-6| 3|1 2 6 4 5 ++3++|
| 2 | 1-5|1|5 2 6 4 ++1 3++|
| 3 |1-4| 1|4 2 6 ++5 1 3++|
| 4 | 1-3|2|4 6 ++2 5 1 3++|
```graphviz
graph graphname {
rankdir=LR
rank="same"
node [shape = circle];
3 [label="3", style=filled, fillcolor=grey]
1 [label="1", style=filled, fillcolor=grey]
5 [label="5", style=filled, fillcolor=grey]
2 [label="2", style=filled, fillcolor=grey]
4 -- 6 --2 -- 5 --1 --3
}
```
| Round |Range| Select | Result |
| -------- | -------- | -------- |-------- |
| 1 | 1-6|3|1 2 6 4 5 ++3++|
| 2 | 1-5|1|5 2 6 4 ++1 3++|
| 3 |1-4| 1|4 2 6 ++5 1 3++|
| 4 | 1-3|2|4 6 ++2 5 1 3++|
| 5 | 1-2|2|4 ++6 2 5 1 3++|
```graphviz
graph graphname {
rankdir=LR
rank="same"
node [shape = circle];
3 [label="3", style=filled, fillcolor=grey]
1 [label="1", style=filled, fillcolor=grey]
5 [label="5", style=filled, fillcolor=grey]
2 [label="2", style=filled, fillcolor=grey]
6 [label="6", style=filled, fillcolor=grey]
4 -- 6 --2 -- 5 --1 --3
}
```
最後剩下一個 node ，也就是執行 `n-1` 回合。
所以，我應該先計算 linked list 內的 node 數目，以利改變 Range 的範圍應設在哪裡。
再來考慮的就是位址交換的問題，所以另寫一個 function 處理選好的兩點 swap 的動作。
預想流程： 算長度(回合數) → 隨機挑選一點 → swap → 回合數 - 1 ……
由於上例是使用從 tail 開始換，為了減少每次都還要從 linked list 尋找 tail 的時間，實作就從頭開始插入。
- 目前 list 狀態
```graphviz
digraph structs {
node [shape=record];
NULL[label="NULL",shape=plaintext];
rankdir=LR
{
head_main [label="{ head(main) |{ <addr>&109 }}"];
//rankdir=LR;
n1[label=" {109 |<next> }"];
n2[label=" {110 |<next> }"];
n3[label=" {72 |<next> }"];
n4[label=" {108 |<next> }"];
n1->n2;
n2->n3;
n3->n4;
n4->NULL;
head_main:addr->n1;
}
}
```
- Code
```c=
void fisher_yates(node_t **head)
{
//先算長度
node_t **tmp = head;
int len=0;
for(; *tmp ; tmp = &(*tmp)->next ){
len+=1;
}
//tmp 回到第一個 node
tmp = head;
//fisher_yates 做 (len - 1) 回合
for (int i = len ; i>1 ; i--){
//選第 r 個來和第一個 node 交換
srand(time(NULL)); //希望亂序結果不同
int r = (rand()%i)+1; //從1~i 中選擇
//開始找第 r 個 node 在哪
node_t **target = tmp;
while(r>1){
target = &(*target)->next;
r--;
}
//交換
int value = (*tmp)->value;
(*tmp)->value = (*target)->value;
(*target)->value = value;
tmp = &(*tmp)->next;
}
}
```
###### tags: `sysprog2020`
Sign in with Wallet
Connect another wallet