2020q3 Homework1 (quiz1)

# 2020q3 Homework1 (quiz1) contributed by <`fdsa654hg`> ###### tags: `sysprog2020` ## 分析以下程式碼 ### 回答問題並用 Graphviz 解釋程式碼 #### 1.資料結構定義如下 ```graphviz digraph G{ rankdir=LR; node [shape=record]; a [label="{ <data> value | <ref> }"] b [label="{ <data> value | <ref> }"]; c [label="{ <data> value | <ref> }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` ```cpp= typedef struct __node { int value; struct __node *next; } node_t; ``` #### 2. Q1:AA1=? & Q2:AA2=? - `(a) assert(new_node)` - `(b) *indirect = new_node` ```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; //assert(new_node); while (*indirect) indirect = &(*indirect)->next; AA2 //*indirect = new_node; } ``` - AA1之前的程式碼為建立一個 `node_t` 的新實例`new_node`，將參數 `new_value` 賦值給它並讓 `new_value->next` 指向 `NULL` - 只看之前的程式碼仍無法判斷 AA1 為何，先考慮以下程式碼 ```cpp= while (*indirect) indirect = &(*indirect)->next; ``` - `add_entry` 會將新增的節點放在最後，`indirect` 剛開始為list之 `head` 經此迴圈迭代會指向最後一個 `node` 的 `Next` ，下一行程式碼只要將新增的節點 `new_node` 至於此記憶體位置即可，故AA2為 `*indirect = new_node` - 由以上推論AA1為 `assert(new_node)`，`assert()` 函式在此能起到判斷 `new_node` 是否成功建立的作用 #### 3. Q3:BB1=? & Q4:BB2=? ##### 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 ```cpp= node_t *swap_pair(node_t *head) { for (node_t **node = &head; *node && (*node)->next; BB1 /*node = &(*node)->next->next)*/) { node_t *tmp = *node; BB2 //*node = (*node)->next; tmp->next = (*node)->next; (*node)->next = tmp; } return head; } ``` - 此函式的目的是從list的 `head` 開始，每兩個node交換(換過的不再換) - 即 ```graphviz digraph G { rankdir=LR; node [shape=record]; a [label="{ <data> 1 | <ref> }"] b [label="{ <data> 2 | <ref> }"]; c [label="{ <data> 3 | <ref> }"]; d [label="{ <data> 4 | <ref> }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; a:data -> b:data [arrowhead=vee, arrowtail=vee, dir=both, tailport = n, headport=n, color=red]; c:data -> d:data [arrowhead=vee, arrowtail=vee, dir=both, tailport = n, headport=n, color=red]; } ``` - 變成 ```graphviz digraph G { rankdir=LR; node [shape=record]; a [label="{ <data> 2 | <ref> }"] b [label="{ <data> 1 | <ref> }"]; c [label="{ <data> 4 | <ref> }"]; d [label="{ <data> 3 | <ref> }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` - 故 `for loop` 應要每兩個 `node` 執行一次，而 `node` 為雙重指標，存取的資料應是 `node_t` 型別指標的址，所以 BB1 為 `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) ```cpp= node_t *tmp = *node; BB2; //*node = (*node)->next; tmp->next = (*node)->next; (*node)->next = tmp; ``` - 此段程式碼的目的是要交換兩個 `node` - 由於 `node` 為雙重指標，真正能操作Linked List的是其指向的指標，為了改變其結構要使用`*`號，並將 `*node` 指向的節點改為下一個節點，故答案為 `*node = (*node)->next` - 3、4行重新調整兩個節點的`next`所指的對象 #### 4.Q5: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 ```cpp= node_t *reverse(node_t *head) { node_t *cursor = NULL; while (head) { node_t *next = head->next; CCC //head->next = cursor; cursor = head; head = next; } return cursor; } ``` - 此函式目的是反轉原本的 list 順序，即 ```graphviz digraph G { rankdir=LR; node [shape=record]; a [label="{ <data> 1 | <ref> }"] b [label="{ <data> 2 | <ref> }"]; c [label="{ <data> 3 | <ref> }"]; d [label="{ <data> 4 | <ref> }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` - 變成 ```graphviz digraph G { rankdir=LR; node [shape=record]; a [label="{ <data> 4 | <ref> }"] b [label="{ <data> 3 | <ref> }"]; c [label="{ <data> 2 | <ref> }"]; d [label="{ <data> 1 | <ref> }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` ##### 此函式的執行邏輯為 - 用 `head` 作為媒介並使用 `while` 迴圈跑完整個 Linked List - 迴圈內先宣告一個空指標 `cursor` - `head` 為 list 的開頭，先宣告一個指標 `next` 指向 `head->next` 即第二個節點 - 為了反轉整個 list 的順序勢必得從開頭下手，因為 Singly Linked List 只能從開頭開始存取，且變數 `next` 已經存取 `head` 的下一個位置故下一行即可反轉，即 ```cpp= head->next = cursor ``` ```graphviz digraph G { rankdir=LR; node [shape=record]; a [label="{ <data> 1 | <ref> }"] b [label="{ <data> 2 | <ref> }"]; c [label="{ <data> 3 | <ref> }"]; d [label="{ <data> 4 | <ref> }"]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` - 下一步為 ```cpp= cursor = head ``` - 這樣下一個 `head` 能指向當前的 `head` - 全部選項僅(b)符合邏輯 - 最後的 `head ＝ next` 讓下次迭代有正確的 `head` - 照上述的邏輯運作，第二次迭代應為 ```graphviz digraph G { rankdir=LR; node [shape=record]; a [label="{ <data> 1 | <ref> }"] b [label="{ <data> 2 | <ref> }"]; c [label="{ <data> 3 | <ref> }"]; d [label="{ <data> 4 | <ref> }"]; b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` - 第三次迭代 ```graphviz digraph G { rankdir=LR; node [shape=record]; a [label="{ <data> 1 | <ref> }"] b [label="{ <data> 2 | <ref> }"]; c [label="{ <data> 3 | <ref> }"]; d [label="{ <data> 4 | <ref> }"]; b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` - 第四次迭代 ```graphviz digraph G { rankdir=LR; node [shape=record]; a [label="{ <data> 1 | <ref> }"] b [label="{ <data> 2 | <ref> }"]; c [label="{ <data> 3 | <ref> }"]; d [label="{ <data> 4 | <ref> }"]; b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; d:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` - 完成，結果正確 ### 修改程式碼以避免回傳指標 #### `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; } ``` - 為避免回傳指標，使用指標的指標來改寫原函式 ```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` 指標的原因是因為 `head` 指向的東西是會改變的，但若使用指標的指標當參數傳入，改變的東西是其儲存的值所指向的東西，本身並不會改變，所以不需要回傳新的 `head` - 如圖所示(`head` 為指標的指標，`head_value` 為`head` 所存的指標) ```graphviz digraph G { rankdir=LR; node [shape=record]; a [label="{ <data> 4 | <ref> }"] b [label="{ <data> 3 | <ref> }"]; c [label="{ <data> 2 | <ref> }"]; d [label="{ <data> 1 | <ref> }"]; b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; d:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; head[shape=plaintext,fontcolor=darkgreen]; head_value[shape=plaintext,fontcolor=darkgreen]; head -> head_value; head_value -> d:data } ``` - `swap_pair(head)` 作用後 ```graphviz digraph G { rankdir=LR; node [shape=record]; a [label="{ <data> 3 | <ref> }"] b [label="{ <data> 4 | <ref> }"]; c [label="{ <data> 1 | <ref> }"]; d [label="{ <data> 2 | <ref> }"]; b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; d:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; head[shape=plaintext,fontcolor=darkgreen]; head_value[shape=plaintext,fontcolor=darkgreen]; head -> head_value; head_value -> d:data } ``` - 可知 `head` 所指向的東西不會改變，會改變的只有 `head_value` #### `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; } ``` - 修改後 ```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; } ``` - 原理如 `swap_pair()` 那段所述，不過此段程式碼要將 `head` 以 `*head` 取代，並在最後加上 `*head = cursor` ，因為 `head` 後會指向 `NULL` ### 以遞迴呼叫 `reverse()` ```cpp= void reverse(node_t **head){ *head = rev_reverse(head); } node_t *rev_recursive(node_t **head){ if(*head!=NULL){ node_t cursor = NULL; (*head) -> next = cursor; cursor = rev_recursive((*head) -> next); cursor -> next = *head; return *head; } } ``` - 修改後 ```cpp= node_t *rev_recursive(node_t **head){ if((*head)->next){ node_t *next = rev_recursive(&(*head)->next); (*head)->next->next = *head; (*head)->next = NULL; return next; } else{ return *head; } } void reverse(node_t **head){ *head = rev_recursive(head); } ``` - 此資料結構為單向的 Linked List，且若要使用遞迴的方法反轉原始順序，必須先走到最後一個節點用 `if` 條件句判斷到達尾端並回傳 `head` (即原始list的末端) - 此處只會走到倒數第二個 `node` ```cpp= if((*head)->next) ``` ```graphviz digraph G { rankdir=LR; node [shape=record]; a [label="{ <data> 4 | <ref> }"] b [label="{ <data> 3 | <ref> }"]; c [label="{ <data> 2 | <ref> }"]; d [label="{ <data> 1 | <ref> }"]; b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; d:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; head[shape=plaintext,fontcolor=darkgreen]; head -> b:ref; } ``` ```cpp= (*head)->next->next = *head; (*head)->next = NULL; ``` - 此段程式碼的目的是將自己的 `next` 指向自己(即調轉方向)，並將自己的 `next` 清空 ```graphviz digraph G { rankdir=LR; node [shape=record]; a [label="{ <data> 4 | <ref> }"] b [label="{ <data> 3 | <ref> }"]; c [label="{ <data> 2 | <ref> }"]; d [label="{ <data> 1 | <ref> }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; d:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; head[shape=plaintext,fontcolor=darkgreen]; head -> b:ref; } ``` - 由於 `stack` 的特性，其執行順序會從倒數第二個節點開始執行上述兩行程式碼，下一個執行的是倒數第三個...，直到第一個節點也執行過了整個就完成了 - 由於除了在最後一個節點有回傳 `head` 之外其他的節點皆回傳上次回傳的結果，所以整個遞迴的過程回傳的值是最後一個節點的 `head` ，即新 list 的開頭 ### Fisher–Yates shuffle ```cpp= for(int i = n; i>=1; --i) { int j=rand(i);//生成1-i之間的隨機數 exchange(A[i],A[j]);//交換A[i]，A[j] } ``` - 這是 `Fisher–Yates shuffle` 的演算法(不額外新增空間儲存的版本)，不過這是用`array`實作的，我將把它改成 Linked List 的版本 - 演算法的實作其實蠻簡單的，不過由於 Linked List 沒有隨機存取性，所以交換兩個元素很可能必須 traverse 整個list，因此是最麻煩的部份，以下簡述程式碼運作原理 ```cpp= int list_length(node_t *head){ int count = 0; while(head){ ++count; head = head->next; } return count; } ``` - 此函式的作用為計算 list 的個數 ```cpp= void exchange_nodes(node_t **head, int first_node, int second_node){ int count = second_node - first_node; if(!count)return; node_t **indirection = head; node_t *first_cursor = NULL; node_t *second_cursor = NULL; while(first_node-1){ first_cursor = *indirection; indirection = &(*indirection)->next; --first_node; } node_t *first_node_des = *indirection; while(count){ second_cursor = *indirection; indirection = &(*indirection)->next; --count; } node_t *second_node_des = *indirection; if(first_cursor)first_cursor->next = second_node_des; second_cursor->next = first_node_des; node_t *tmp = second_node_des->next; second_node_des->next = first_node_des->next; first_node_des->next = tmp; if(!first_cursor)*head = second_node_des; } ``` - 第3行 -- 若隨機抽取的節點與未排序的節點為同一個就不用交換 - 第9～13行及17～21行 -- 取得隨機取得跟未排序的兩個節點的位置 - 第25～30行 -- 交換兩個節點並將其所指向的及被指向的節點調整好 - 第32行 -- 若交換到第1個節點更新新的 `head` ```cpp= void Fisher_Yates_shuffle(node_t **head){ for(int i = list_length(*head); i>=1; --i){ int j = rand() % i + 1; exchange_nodes(head,j,i); } } ``` - 這個函式為演算法的實例

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.