# 2020q3 Homework1 (quiz1)
contributed by < `fennecJ` >
> [2020q3 第 1 週測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)
## 第一題 (AA1)
```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;
AA1;
while (*indirect)
indirect = &(*indirect)->next;
AA2;
}
```
AA1 = ?
* `(a)` `assert(new_node)`
* `(b)` `*indirect = new_node`
<s> 這題是二選一，我們先看 `b` 選項，若 `b` 選項為正確答案，則程式第三行就顯得多餘，不符合**優雅**的精神，因此排除 `b` 選項，此題應選 `a` 。</s>
後來重新檢視題目發現我一開始對於這題的認知有誤，我原本認為 *indrect = new_node 和 indrect = &new_node 是等價的，因此說第三行是多餘的，但 *indrect = new_node 是有作用的，效果是將 head 指向 new_node ，即使如此，這個 function 的作用是加入新的節點，而不是覆寫掉 head 因此本題仍應選 `a` 。
因為我不知道 assert 巨集的作用，所以我去查了C99的規格書:我參考的版本為:
`Committee Draft — Septermber 7, 2007 ISO/IEC 9899:TC3`
翻到 `p.169` ，可以看到以下的說明。
> #include <assert.h>
> void assert(scalar expression);
> Description
> The assert macro puts diagnostic tests into programs; it expands to a void expression. When it is executed, if expression (which shall have a scalar type) is false (that is, compares equal to 0), the assert macro writes information about the particular call that failed (including the text of the argument, the name of the source file, the source line number, and the name of the enclosing function — the latter are respectively the values of the preprocessing macros _ _FILE_ _ and _ _LINE_ _ and of the identifier
_ _func_ _) on the standard error stream in an implementation-defined format.
It then calls the abort function.
看來他會 check 放在 assert(expression) 裡面的 expression 是否為 false ，如果為 false 則會 call 一個叫做 abort 的 function 。我也不知道 abort 是什麼，望文生義，推測其作用為讓某種東西終止，在這裡指的應為程式。
我繼續查規格書，看到 `p.315` ，關於 `abort` function的描述:
> The abort function causes abnormal program termination to occur...
所以 assert 的作用機制應為:檢查某個 expression ，若 expression 不成立，則終止程序。現在看回選項 `(a)`
* `(a)` `assert(new_node)`
判斷這裡的作用為檢查程式是否成功為 new_node 配置了合理的記憶體空間。
## 第二題 (AA2)
AA2 = ?
* `(a)` `assert(new_node)`
* `(b)` `*indirect = new_node`
我們在第一題的時候已經對 new_node 進行了記憶體的確認，而當程式執行至此時並未對 new_node 有其他操作，因此再進行一次檢查沒有意義，刪去 `(a)` 選項，此題應選 `(b)` 。
從另一方面看來， (b) 的作用為把最後一個 node 的 next 指向 new node 。
以下我們逐步檢視函式的運作情形:
```cpp=
node_t **indirect = head;
node_t *new_node = malloc(sizeof(node_t));
new_node->value = new_value;
new_node->next = NULL;
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
A[label="{<f0>A|<f1>next}"]
B[label="{<f0>B|<f1>next}"]
C[label="{<f0>C|<f1>next}"]
NN[label="{<f0>new_node|<f1>next}"]
NULL1[label="NULL",shape=plaintext]
NULL2[label="NULL",shape=plaintext]
head[label="head",shape=plaintext]
indir[label="indirect",shape=plaintext]
NN:f1->NULL2
indir->head
head->A:f0
A:f1->B:f0
B:f1->C:f0
C:f1->NULL1
}
```
```cpp=
while (*indirect)
indirect = &(*indirect)->next;
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
A[label="{<f0>A|<f1>next}"]
B[label="{<f0>B|<f1>next}"]
C[label="{<f0>C|<f1>next}"]
NN[label="{<f0>new_node|<f1>next}"]
NULL1[label="NULL",shape=plaintext]
NULL2[label="NULL",shape=plaintext]
head[label="head",shape=plaintext]
indir[label="indirect",shape=plaintext,fontcolor=blue]
indir->A:f1
head->A:f0
A:f1->B:f0
B:f1->C:f0
C:f1->NULL1
NN:f1->NULL2
}
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
A[label="{<f0>A|<f1>next}"]
B[label="{<f0>B|<f1>next}"]
C[label="{<f0>C|<f1>next}"]
NN[label="{<f0>new_node|<f1>next}"]
NULL1[label="NULL",shape=plaintext]
NULL2[label="NULL",shape=plaintext]
head[label="head",shape=plaintext]
indir[label="indirect",shape=plaintext,fontcolor=blue]
NN:f1->NULL2
indir->B:f1
head->A:f0
A:f1->B:f0
B:f1->C:f0
C:f1->NULL1
}
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
A[label="{<f0>A|<f1>next}"]
B[label="{<f0>B|<f1>next}"]
C[label="{<f0>C|<f1>next}"]
NN[label="{<f0>new_node|<f1>next}"]
NULL1[label="NULL",shape=plaintext]
NULL2[label="NULL",shape=plaintext]
head[label="head",shape=plaintext]
indir[label="indirect",shape=plaintext,fontcolor=blue]
NN:f1->NULL2
indir->C:f1
head->A:f0
A:f1->B:f0
B:f1->C:f0
C:f1->NULL1
}
```
```cpp
*indirect = new_node
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
A[label="{<f0>A|<f1>next}"]
B[label="{<f0>B|<f1>next}"]
C[label="{<f0>C|<f1>next}"]
NN[label="{<f0>new_node|<f1>next}"]
NULL2[label="NULL",shape=plaintext]
head[label="head",shape=plaintext]
indir[label="indirect",shape=plaintext,fontcolor=blue]
NN:f1->NULL2
indir->C:f1
head->A:f0
A:f1->B:f0
B:f1->C:f0
C:f1->NN
}
```
## 第三題 (BB1)
```cpp=
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;
}
```
BB1 = ?
* `(a)` `node = (*node)->next->next`
* `(b)` `*node = (*node)->next->next`
* `(c)` `*node = ((*node)->next)->next`
* `(d)` `*node = &((*node)->next)->next`
* `(e)` `node = &(*node)->next->next`
* `(f)` `*node = &(*node)->next->next`
<s>偷吃步:刪去法
`(b)` `(c)` 兩個選項是相等的，表單為單選題，因此刪去這兩個選項。
`(d)` `(f)` 兩個選項是相等的，表單為單選題，因此刪去這兩個選項。
剩下 `(a)` 和 `(e)` 兩個選項，這兩個選項看似一樣，唯一的差別在於 `(e)` 選項有 & 。
</s>
:::danger
:warning: 不該糾結於選項，畢竟出選擇題只是為了批改方便，這個測驗的目的是確認學員的認知，因此你該想「如果讓我憑空寫出類似的程式碼，我會怎麼做？」中學那些考試技巧就不要提了。
:notes: jserv
:::
>了解！謝謝老師指教
> [name=fennecJ]
我們可以在第 3 行程式看到 node 是怎麼被宣告的:
```cpp
for (node_t **node = &head; *node && (*node)->next; BB1)
```
node 是指標的指標，存 &head
這裡應選 `(e)` 。
從另一方面來看，我們可以參考程式呼叫 swap 前後的輸出情況：
```cpp=
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;
}
```
參考執行輸出: (第 1 行是換行符號)
```=
72 101 108 109 110 111
72 108 109 110 // <- 呼叫swap前
108 72 110 109 // <- 呼叫swap後
109 110 72 108
```
可以看到， swap 的作用為把相鄰的兩個node交換，且一直進行交換直到 linked list 的結尾。
以下為 linked list 和 node 視覺化後的結果： ( 假設 head 指向 A )
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
struct1[label="{<f0>A|<f1>next}"]
struct2[label="{<f0>B|<f1>next}"]
struct3[label="{<f0>C|<f1>next}"]
struct1:f1->struct2:f0
struct2:f1->struct3:f0
NULL[label=NULL,shape=plaintext]
Ellipsis[label=●●●,shape=plaintext]
node1[label="node",shape=plaintext]
head[label="head",shape=plaintext]
node1->head
head->struct1:f0
struct3->Ellipsis->NULL
}
```
我們要更新 node 的值，才有辦法達到 for 迴圈的終止條件 :
```cpp=
(*node == NULL || (*node)->next == NULL)
```
而當我們要更新 node ，我們希望 node 藉由各節點的 next 往後移動，因此我們要先 *node(dereference) ，再取其中的 next->next ，但不要忘了，原本 node 為 node_t 的指標的指標 ， 而 *node->next->next 則是 node_t 的指標 ，因此最後還要再加上一個 & ，所以此題答案應選:
`(e)` `node = &(*node)->next->next`
## 第四題 (BB2)
* `(a)` `node = (*node)->next`
* `(b)` `node = &(*node)->next`
* `(c)` `*node = (*node)->next`
* `(d)` `*node = &(*node)->next`
* `(e)` `*node = &((*node)->next)`
`(a)` 選項等號兩邊的型別對不上 ( node 存 node_t 形別的指標的指標，但 (*node)->next 存的是 node_t 型別的指標 ) 因此排除此選項
同理， `(d)` ， `(e)` 選項也被排除。
剩下 `(b)` ， `(c)` 兩選項
`(b)` 選項等號兩邊的型別雖然相同，但若答案為 `(b)` 選項的話 head 無法被更新，在交換後會指向 linked list 的第二個節點，故此選項不是正確答案
因此此題選 `(c)`
以下我們逐行檢視 swap 的運作情形：
```cpp
node_t *tmp = *node;
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
struct1[label="{<f0>A|<f1>next}"]
struct2[label="{<f0>B|<f1>next}"]
struct3[label="{<f0>C|<f1>next}"]
NULL[label=NULL,shape=plaintext]
Ellipsis[label=●●●,shape=plaintext]
//node1[label="node",shape=plaintext]
node2[label="node",shape=plaintext]
head[label="head",shape=plaintext]
tmp[label="tmp",shape=plaintext,fontcolor=blue]
struct1:f1->struct2:f0
struct2:f1->struct3:f0
node2->head
head->struct1:f0
tmp->struct1:f0
struct3->Ellipsis->NULL
}
```
```cpp
*node = (*node)->next
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
struct1[label="{<f0>A|<f1>next}"]
struct2[label="{<f0>B|<f1>next}"]
struct3[label="{<f0>C|<f1>next}"]
node2[label="node",shape=plaintext,fontcolor=blue]
head[label="head",shape=plaintext]
NULL[label=NULL,shape=plaintext]
Ellipsis[label=●●●,shape=plaintext]
tmp[label="tmp",shape=plaintext]
struct1:f1->struct2:f0
struct2:f1->struct3:f0
node2->head
head->struct2:f0
tmp->struct1:f0
struct3->Ellipsis->NULL
}
```
```cpp
tmp->next = (*node)->next;
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
struct1[label="{<f0>A|<f1>next}", fontcolor=Blue,color=Blue]
struct2[label="{<f0>B|<f1>next}"]
struct3[label="{<f0>C|<f1>next}"]
NULL[label=NULL,shape=plaintext]
Ellipsis[label=●●●,shape=plaintext]
node2[label="node",shape=plaintext]
head[label="head",shape=plaintext]
tmp[label="tmp",shape=plaintext]
node2->head
head->struct2:f0
tmp->struct1:f0
struct1:f1->struct3:f0
struct2:f1->struct3:f0
struct3->Ellipsis->NULL
}
```
```cpp
(*node)->next = tmp;
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
struct1[label="{<f0>A|<f2>next}"]
struct2[label="{<f0>B|<f2>next}", fontcolor=Blue,color=Blue]
struct3[label="{<f0>C|<f2>next}"]
NULL[label=NULL,shape=plaintext]
Ellipsis[label=●●●,shape=plaintext]
node2[label="node",shape=plaintext]
head[label="head",shape=plaintext]
tmp[label="tmp",shape=plaintext]
node2->head
head->struct2:f0
tmp->struct1:f0
struct1:f2->struct3:f0
struct2:f2->struct1:f0
struct3->Ellipsis->NULL
}
```
再來 node 會被 for 迴圈更新為 &(*node)->next->next ( 也就是 C ) 直到剩下一個節點或是沒有剩下節點未被 swap 為止。
## 第五題 (CCC)
```cpp=
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
CCC;
head = next;
}
return cursor;
}
```
CCC = ?
* `(a)` `cursor = head; head->next = cursor`
* `(b)` `head->next = cursor; cursor = head`
* `(c)` `cursor = head`
* `(d)` `head->next = cursor`
* `(e)` `head->next->next = cursor; cursor->next = head`
* `(f)` `cursor->next = head; head->next->next = cursor`
由於會 reverse 整個 linked list ，所以一開始的 head->next 應該會指向 NULL ，因此我們應該把沒有 head->next = cursor 或是先改動 cursor 指向才用 head->next 的選項排除掉 ( 排除 `(a)` `(c)` `(e)` `(f)` ) 而最後函式回傳 cursor 作為新的 head ，因此 `(d)` 也被排除，因為此選項沒對 cursor 進行改動，最後 cursor 仍指向 NULL 。最後剩下 `(b)` 選項，因此本題應選 `(b)` 。
以下我們逐步檢視函式運作2圈的情形:
```cpp
node_t *cursor = NULL;
node_t *next = head->next;
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
A[label="{<f0>A|<f1>next}"]
B[label="{<f0>B|<f1>next}"]
C[label="{<f0>C|<f1>next}"]
D[label="{<f0>D|<f1>next}"]
//NULL1[label="NULL",shape=plaintext]
NULL2[label="NULL",shape=plaintext]
cursor[label="cursor(NULL)",shape=plaintext,fontcolor=blue]
head[label="head",shape=plaintext]
next[label="next",shape=plaintext,fontcolor=blue]
eps[label="●●●",shape=plaintext]
head->A:f0
next->B:f0
A:f1->B:f0
B:f1->C:f0
C:f1->D
D:f1->eps
eps->NULL2
}
```
```cpp
head->next = cursor;
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
A[label="{<f0>A|<f1>next}", fontcolor=Blue,color=Blue]
B[label="{<f0>B|<f1>next}"]
C[label="{<f0>C|<f1>next}"]
D[label="{<f0>D|<f1>next}"]
//NULL1[label="NULL",shape=plaintext]
NULL2[label="NULL",shape=plaintext]
cursor[label="cursor(NULL)",shape=plaintext]
head[label="head",shape=plaintext]
next[label="next",shape=plaintext]
eps[label="●●●",shape=plaintext]
head->A:f0
next->B:f0
A:f1->cursor
B:f1->C:f0
C:f1->D:f0
D->eps
eps->NULL2
}
```
```cpp
cursor = head;
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
A[label="{<f0>A|<f1>next}"]
B[label="{<f0>B|<f1>next}"]
C[label="{<f0>C|<f1>next}"]
D[label="{<f0>D|<f1>next}"]
NULL1[label="NULL",shape=plaintext]
NULL2[label="NULL",shape=plaintext]
cursor[label="cursor",shape=plaintext, fontcolor=Blue]
head[label="head",shape=plaintext]
next[label="next",shape=plaintext]
eps[label="●●●",shape=plaintext]
cursor->A:f0
head->A:f0
next->B:f0
A:f1->NULL1
B:f1->C:f0
C:f1->D:f0
D:f1->eps
eps->NULL2
}
```
```cpp
head = next;
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
A[label="{<f0>A|<f1>next}"]
B[label="{<f0>B|<f1>next}"]
C[label="{<f0>C|<f1>next}"]
D[label="{<f0>D|<f1>next}"]
NULL1[label="NULL",shape=plaintext]
NULL2[label="NULL",shape=plaintext]
cursor[label="cursor",shape=plaintext]
head[label="head",shape=plaintext, fontcolor=Blue]
next[label="next",shape=plaintext]
eps[label="●●●",shape=plaintext]
cursor->A:f0
head->B:f0
next->B:f0
A:f1->NULL1
B:f1->C:f0
C:f1->D:f0
D:f1->eps
eps->NULL2
}
```
至此第一次迴圈結束，接下來進入第二圈:
```cpp
node_t *next = head->next;
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
A[label="{<f0>A|<f1>next}"]
B[label="{<f0>B|<f1>next}"]
C[label="{<f0>C|<f1>next}"]
D[label="{<f0>D|<f1>next}"]
NULL1[label="NULL",shape=plaintext]
NULL2[label="NULL",shape=plaintext]
cursor[label="cursor",shape=plaintext]
head[label="head",shape=plaintext]
next[label="next",shape=plaintext, fontcolor=Blue]
eps[label="●●●",shape=plaintext]
cursor->A:f0
head->B:f0
next->C:f0
A:f1->NULL1
B:f1->C:f0
C:f1->D:f0
D:f1->eps
eps->NULL2
}
```
```cpp
head->next = cursor;
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
A[label="{<f0>A|<f1>next}"]
B[label="{<f0>B|<f1>next}", fontcolor=Blue,color=Blue]
C[label="{<f0>C|<f1>next}"]
D[label="{<f0>D|<f1>next}"]
NULL1[label="NULL",shape=plaintext]
NULL2[label="NULL",shape=plaintext]
cursor[label="cursor",shape=plaintext]
head[label="head",shape=plaintext]
next[label="next",shape=plaintext]
eps[label="●●●",shape=plaintext]
cursor->A:f0
head->B:f0
next->C:f0
A:f1->NULL1
B:f1->A:f0
C:f1->D:f0
D:f1->eps
eps->NULL2
}
```
```cpp
cursor = head;
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
A[label="{<f0>A|<f1>next}"]
B[label="{<f0>B|<f1>next}"]
C[label="{<f0>C|<f1>next}"]
D[label="{<f0>D|<f1>next}"]
NULL1[label="NULL",shape=plaintext]
NULL2[label="NULL",shape=plaintext]
cursor[label="cursor",shape=plaintext, fontcolor=Blue]
head[label="head",shape=plaintext]
next[label="next",shape=plaintext]
eps[label="●●●",shape=plaintext]
cursor->B:f0
head->B:f0
next->C:f0
A:f1->NULL1
B:f1->A:f0
C:f1->D:f0
D:f1->eps
eps->NULL2
}
```
```cpp
head = next;
```
```graphviz
digraph structs {
rankdir=LR
node[shape = record]
A[label="{<f0>A|<f1>next}"]
B[label="{<f0>B|<f1>next}"]
C[label="{<f0>C|<f1>next}"]
D[label="{<f0>D|<f1>next}"]
NULL1[label="NULL",shape=plaintext]
NULL2[label="NULL",shape=plaintext]
cursor[label="cursor",shape=plaintext]
head[label="head",shape=plaintext, fontcolor=Blue]
next[label="next",shape=plaintext]
eps[label="●●●",shape=plaintext]
cursor->B:f0
head->C:f0
next->C:f0
A:f1->NULL1
B:f1->A:f0
C:f1->D:f0
D:f1->eps
eps->NULL2
}
```
之後迴圈會一質重複直到 cursor 指向原來的最後一個節點，這個節點會是新的 head ，因此最後回傳 cursor 。
## 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;
}
}
```
注意改寫後呼叫 swap_pair() 時要傳 &head 而不是 head 。
## reverse() 改寫為傳 **head
```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;
}
```
注意改寫後呼叫 reverse() 時要傳 &head 而不是 head 。
## reverse() 改寫為 recursive
我設了兩個函式： reverse2 和 re_reverse ，其中， re_reverse 為遞迴主體而 reverse2 則用來呼叫 re_reverse :
```cpp=
void re_reverse(node_t **head,node_t **cursor){
if(*head == NULL){
*head = *cursor;
return;
}
node_t *next = (*head)->next;
(*head)->next = (*cursor);
*cursor = *head;
*head = next;
re_reverse(head,cursor);
}
```
```cpp=
void reverse2(node_t **head)
{
node_t *tmp = NULL;
re_reverse(head,&tmp);
}
```
我最初想要直接把 reverse2 拔掉直接以 re_reverse(&head,NULL) 呼叫函式，但不知為何這種用法在程式執行到第三行 (*head)->next = (*cursor); 時會出錯。原因待確認。
後來仔細想想傳 &tmp 和直接傳 NULL 的差別我就想通了，傳 &tmp 時，傳入的會是一個指向 tmp 的記憶體位址，因此可以 dereference ；而若直接傳 NULL ，傳入的時候不會是一個指向 NULL 的記憶體位址，而是本身就是 NULL ，在 deference 時就像嘗試從一個空的箱子裡拿東西出來，所以會出錯。
我希望能以一個函式就解決這個問題所以我把兩個函式合再一起:
```cpp=
void re_reverse(node_t **head,node_t **cursor){
if(!cursor){
node_t *tmp = NULL;
cursor = &tmp;
}
if(*head == NULL){
*head = *cursor;
return;
}
node_t *next = (*head)->next;
(*head)->next = (*cursor);
*cursor = *head;
*head = next;
re_reverse(head,cursor);
}
```
目前可直接以 re_reverse(&head,NULL) 呼叫函式。不過我覺得 if(!cursor) 那一段有些多餘。
後來想想， cursor 的作用是用來紀錄前一個 node ，他不需要作為指標的指標傳入便能達成這個目的，因此修改函式的參數，並把原本判斷 if(!cursor) 的部分拔掉:
```cpp=
void re_reverse(node_t **head,node_t *cursor){
if(*head == NULL){
*head = cursor;
return;
}
node_t *next = (*head)->next;
(*head)->next = cursor;
cursor = *head;
*head = next;
re_reverse(head,cursor);
}
```
以 re_reverse(&head,NULL) 呼叫這個函式。
## Fisher–Yates shuffle
```cpp=
void FYsfl(node_t **head)
{
srand(time(NULL));
node_t **tmp = head;
int len = 0;
while(*tmp){
tmp = &(*tmp)->next;
len++;
}
while(len){
int tar = (rand()%len);
reverse(head); //從尾端抽取
tmp = head;
for(int i = 0; i < tar; i++)
tmp = &(*tmp)->next;
node_t *tmp2 = *tmp;
*tmp = (*tmp)->next;
reverse(head); //從前端放置
tmp2->next = *head;
*head = tmp2;
len--;
}
}
```
一開始我的實作概念很簡單，我把從頭端向尾看過去當作一個沒放東西的容器，從尾端向頭看過去當作抽取庫。
可以想像在整個 linked list 中有一隔板(圖內以------表示)，我們在隨機抽選時可選元素的範圍從隔板一直到 NULL ，而放置則從頭端開始往內放置，已被放置的 (隔板以上的元素) 元素則不會再被抽取。
一開始未有任何元素被抽選，因此圖中隔板以上沒有任何元素。
```graphviz
digraph structs {
node[shape = record]
head[label="head",shape=plaintext]
A[label="{<f0>A|<f1>next}"]
line[label="------------------",shape=plaintext]
eps2[label="●●●",shape=plaintext]
NULL[label="NULL",shape=plaintext]
line->head->A:f0
A:f1->eps2->NULL
}
```
假設目前依序抽到了 B 和 D ，則:
```graphviz
digraph structs {
node[shape = record]
head[label="head",shape=plaintext]
A[label="{<f0>A|<f1>next}"]
B[label="{<f0>B|<f1>next}"]
D[label="{<f0>D|<f1>next}"]
line[label="------------------",shape=plaintext]
eps2[label="●●●",shape=plaintext]
NULL[label="NULL",shape=plaintext]
head->D:f0
D:f1->B:f0
B:f1->line
line->A:f0
A:f1->eps2->NULL
}
```
(先抽到的先放入)
以上這個做法是傳統的 Fisher-Yate 的做法，現代大多使用 Richard Durstenfeld 改良過後的做法，也就是要對元素進行交換，具體實作如下:
```cpp=
void new_FYsfl(node_t **head){
srand(time(NULL));
node_t **tmp = head;
int len = 0;
while(*tmp){
tmp = &(*tmp)->next;
len++;
}
while(len>1){
int tar = (rand()%len);
tmp = head;
for(int i = 0; i < tar; i++)
tmp = &(*tmp)->next;
node_t **tmp2 = head;
for(int i = 0; i+1 < len; i++)
tmp2 = &(*tmp2)->next;
node_t *tmp3 = *tmp;
*tmp = *tmp2;
*tmp2 = tmp3;
tmp3 = (*tmp)->next;
(*tmp)->next = (*tmp2)->next;
(*tmp2)->next = tmp3;
len--;
}
}
```
> <s>待我學習Graphviz之後會嘗試畫出原理圖</s>
:::danger
沒做到的事情，不需要特別寫出來。
:notes: jserv
:::
>了解！
> [name=fennecJ]
## 參考資料
* [HackMD 語法](https://hackmd.io/c/tutorials-tw/%2Fs%2Ffeatures-tw)
* [Graphviz 語法](https://www.tonyballantyne.com/graphs.html)
* [C 規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
* [ZhuMon](https://hackmd.io/@ZhuMon/sysprog2020_quiz1)
* [RinHizakura](https://hackmd.io/@RinHizakura/BysgszHNw)
Sign in with Wallet
Connect another wallet