# 2020q3 Homework1 (quiz1) contributed by < `sammer1107` > ###### tags: `進階電腦系統理論與實作` [TOC] ## AA1 & AA2 ```cpp=9 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; } ``` ### 程式理解 1. 13~15 行的地方我們已經要了新的記憶體，並在上面放入了新的值 2. 18~19 行的目的是要找到最後一個節點(當 next 為 NULL) ### AA1 根據上面的理解，**AA1** 不應該是 ```*indirect = new_node```，否則迴圈執行的結果永遠都是得到 NULL 後結束。因此 **AA1** 應是 assert(new_node)，檢查是否正確取得記憶體。 ### AA2 找到最後一個節點後，需要將最後的 `next` 指標指向 `new_node`。迴圈結束時，`*indirect`相當於最後一個節點的 `next` ，故答案為 `*indirect = new_node`。 ## BB1 & BB2 ```c=42 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 1. `swap_pair` 的功能為兩兩掉換，故 **BB1** 的功能是要連跳兩個 node。 3. 而且這裡我們是要改變 node 指向的位置而不是要修改 List 連接，故等號左邊要是 `node` 而不是 `*node`。 4. (a) 不對因為 `next` 的 type 為 `node_t*` ，故要再取址才是我們要的。 答案為 `(e) node = &(*node)->next->next` ### BB2 1. 在迴圈內我們要完成交換 Node 的工作，經過第 4 行後 ```c=45 node_t *tmp = *node; ``` 指標們長這樣，node1 與 node2 為目前要 swap 的節點。... 則代表前後延伸的節點 ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] nodepp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">node</TD></TR> </TABLE>>]; tmpp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">tmp</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> ... </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node1</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node2</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> ... </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; a:next:c -> b:val; b:next:c -> c:val; c:next:c -> d:val; { rank=same; nodepp:p:s -> a:next:c; } { rank=same; tmpp:p:s -> b:val; } } ``` :::warning 這樣表示 `node` 為指向前一節點的 `next` 的指標，`tmp` 則為指向第1節點的指標。 ::: 2. 要把 node2 往前移的第一個動作就是把前一個節點的 `next` 牽往 node2。==做完後==長這樣 ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] nodepp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">node</TD></TR> </TABLE>>]; tmpp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">tmp</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> ... </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node1</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node2</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> ... </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; a:next:c -> b:val [style=invis] a:next:c -> c:val; b:next:c -> c:val; c:next:c -> d:val; { rank=same; nodepp:p:s -> a:next:c; } { rank=same; tmpp:p:s -> b:val; } } ``` 這裡我們要修改的是前一個 node 的 `next` 讓他指向 node2 ，故等號左邊應是 `*node`，而 node2 的位置為 `(*node)->next` (等於 node1 的 `next` )。故答案選 **(e)** 3. 下一行將後面的節點交手從 node2 交手給 node1。 ```c=47 tmp->next = (*node)->next; ``` 做完後長這樣 ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] nodepp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">node</TD></TR> </TABLE>>]; tmpp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">tmp</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> ... </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node1</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node2</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> ... </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; c -> b [style=invis]; a -> b [style=invis]; a:next:c -> c:val; b:next:c -> d:val; c:next:c -> d:val; { rank=same; nodepp:p:s -> a:next:c; } { rank=same; tmpp:p:s -> b:val; } } ``` 4. 最後將 node1 接在 node2 後面就完成了 ```c=48 (*node)->next = tmp; ``` 完成圖 ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] nodepp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">node</TD></TR> </TABLE>>]; tmpp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">tmp</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> ... </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node1</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node2</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> ... </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; a:next:c -> c:val; b:next:c -> d:val; c:next:c -> b:val; { rank=same; nodepp:p:s -> a:next:c; } { rank=same; tmpp:p:s -> b:val; } } ``` ## CCC ```c=53 node_t *reverse(node_t *head) { node_t *cursor = NULL; while (head) { node_t *next = head->next; CCC; head = next; } return cursor; } ``` 要 reverse linked list 我們需要兩個指標一前一後走到底，而 `cursor` 在這裡就是跟在 `head` 之後的指標。故選項要選 **(b)**`head->next = cursor; cursor = head` ，把 `head` 的 `next` 改為指向前一個節點，然後 `cursor` 和 `head` 各往前走一步。 ### 第1次進迴圈的情況(57行) ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] head [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">head</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> node1 </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; cursor [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">cursor</TD></TR> </TABLE>>]; null [label=< <TABLE BORDER="0" CELLBORDER="0" cellspacing="0"> <TR><TD PORT="p">NULL</TD></TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node2</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node3</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> node4 </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; next [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">next</TD></TR> </TABLE>>]; a:next:c -> b:val; b:next:c -> c:val; c:next:c -> d:val; { rank=same; cursor:p:s -> null:n; } { rank=same; head:p:s -> a:val; } { rank=same; next:p:s -> b:val; } null -> a [style=invis] } ``` 做完 `head->next = cursor` 後 ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] head [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">head</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="next"> </TD> <TD PORT="val"> node1 </TD> </TR> </TABLE>>]; cursor [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">cursor</TD></TR> </TABLE>>]; null [label=< <TABLE BORDER="0" CELLBORDER="0" cellspacing="0"> <TR><TD PORT="p">NULL</TD></TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node2</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node3</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> node4 </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; next [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">next</TD></TR> </TABLE>>]; null:p:e -> a:next:c [dir=back]; a:next:c -> b:val [style=invis]; b:next:c -> c:val; c:next:c -> d:val; { rank=same; cursor:p:s -> null:n; } { rank=same; head:p:s -> a:val; } { rank=same; next:p:s -> b:val; } } ``` `cursor = head` 後 `head=next`出回圈的樣子 ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] head [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">head</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="next"> </TD> <TD PORT="val"> node1 </TD> </TR> </TABLE>>]; cursor [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">cursor</TD></TR> </TABLE>>]; null [label=< <TABLE BORDER="0" CELLBORDER="0" cellspacing="0"> <TR><TD PORT="p">NULL</TD></TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node2</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node3</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> node4 </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; a:next:c -> b:val [style=invis]; b:next:c -> c:val; c:next:c -> d:val; { rank=same; cursor:p:s -> a:val:n; } { rank=same; head:p:s -> b:val; } null:p:e -> a:next:c [dir=back] } ``` ### 第2次進迴圈的情況(57行) ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] head [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">head</TD></TR> </TABLE>>]; next [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">next</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="next"> </TD> <TD PORT="val"> node1 </TD> </TR> </TABLE>>]; cursor [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">cursor</TD></TR> </TABLE>>]; null [label=< <TABLE BORDER="0" CELLBORDER="0" cellspacing="0"> <TR><TD PORT="p">NULL</TD></TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node2</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node3</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> node4 </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; a:next:c -> b:val [style=invis]; b:next:c -> c:val; c:next:c -> d:val; { rank=same; cursor:p:s -> a:val:n; } { rank=same; head:p:s -> b:val; } { rank=same; next:p:s -> c:val; } null:p:e -> a:next:c [dir=back] } ``` 做完 `head->next = cursor` 後 ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] head [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">head</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="next"> </TD> <TD PORT="val"> node1 </TD> </TR> </TABLE>>]; next [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">next</TD></TR> </TABLE>>]; cursor [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">cursor</TD></TR> </TABLE>>]; null [label=< <TABLE BORDER="0" CELLBORDER="0" cellspacing="0"> <TR><TD PORT="p">NULL</TD></TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="next"> </TD> <TD PORT="val">node2</TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node3</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> node4 </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; a:val -> b:next:c [dir=back]; b:next:c -> c:val [style=invis]; c:next:c -> d:val; { rank=same; cursor:p:s -> a:val:n; } { rank=same; head:p:s -> b:val; } { rank=same; next:p:s -> c:val; } null:p:e -> a:next:c [dir=back] } ``` 然後移動指標 ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] head [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">head</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="next"> </TD> <TD PORT="val"> node1 </TD> </TR> </TABLE>>]; cursor [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">cursor</TD></TR> </TABLE>>]; null [label=< <TABLE BORDER="0" CELLBORDER="0" cellspacing="0"> <TR><TD PORT="p">NULL</TD></TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="next"> </TD> <TD PORT="val">node2</TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node3</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> ... </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; null2 [label=< <TABLE BORDER="0" CELLBORDER="0" cellspacing="0"> <TR><TD PORT="p">NULL</TD></TR> </TABLE>>]; a:val -> b:next:c [dir=back]; b:next:c -> c:val [style=invis]; c:next:c -> d:val; d:next:c -> null2:p:w { rank=same; cursor:p:s -> b:val:n; } { rank=same; head:p:s -> c:val; } null:p:e -> a:next:c [dir=back] } ``` 之後依此類推 ### 結束時 結束時 `head` 到達最尾端的 `NULL`，cursor 則指向最後的節點，也就是新的頭，所以回傳 cursor。 ## 延伸問題 2 ### swap_pair 的 pointer to pointer 版本 ```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; } } ``` 程式碼原理一致，再開頭時新的運作方式變成: :::warning 括號 head 代表在 main 中的 head。 ::: 1. 第5行 ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] nodepp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">node</TD></TR> </TABLE>>]; tmpp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">tmp</TD></TR> </TABLE>>]; headp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">(head)</TD></TR> </TABLE>>]; headpp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">head</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> node1 </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node2</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node3</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> ... </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; a:next:c -> b:val; b:next:c -> c:val; c:next:c -> d:val; nodepp:p:s -> headp:p:w; { rank=same; tmpp:p:s -> a:val; } { rank=same; headpp:p:s -> headp:p:n; } headp:p:e -> a:val } ``` 2. 第 6 行 ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] nodepp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">node</TD></TR> </TABLE>>]; tmpp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">tmp</TD></TR> </TABLE>>]; headp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">(head)</TD></TR> </TABLE>>]; headpp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">head</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> node1 </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node2</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node3</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> ... </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; a:next:c -> b:val; b:next:c -> c:val; c:next:c -> d:val; nodepp:p:s -> headp:p:w; { rank=same; tmpp:p:s -> a:val; } { rank=same; headpp:p:s -> headp:p:n; } headp:p:e -> b:val headp:p:e -> a:val [style=invis] } ``` 3. 第 7 行 ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] nodepp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">node</TD></TR> </TABLE>>]; tmpp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">tmp</TD></TR> </TABLE>>]; headp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">(head)</TD></TR> </TABLE>>]; headpp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">head</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> node1 </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node2</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node3</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> ... </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; a:next:c -> c:val; b:next:c -> c:val; c:next:c -> d:val; nodepp:p:s -> headp:p:w; { rank=same; tmpp:p:s -> a:val; } { rank=same; headpp:p:s -> headp:p:n; } headp:p:e -> b:val b:p:e -> a:val [style=invis] } ``` 4. 第8行 ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] nodepp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">node</TD></TR> </TABLE>>]; tmpp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">tmp</TD></TR> </TABLE>>]; headp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">(head)</TD></TR> </TABLE>>]; headpp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">head</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> node1 </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node2</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node3</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val"> ... </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; a:next:c -> c:val; c:next:c -> d:val; nodepp:p:s -> headp:p:w; { rank=same; tmpp:p:s -> a:val; } { rank=same; headpp:p:s -> headp:p:n; } headp:p:e -> b:val b:next:e -> a:val } ``` `head` 在這裡很自然的指向了新的頭，所以完全不需要新增程式碼來處理這部份。 ### reverse 的 pointer to pointer 版本 ```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; } ``` 這個版本沒做什麼修改，只要將 `head` 都換成 `*head` 即可，回傳的動作則改成直接設定 `*head`。 ## 延伸問題 3 - recursive reverse ```c= node_t *reverse_recursive(node_t *head) { if(!head || !head->next){ return head; } node_t *rev_head = reverse_recursive(head->next); head->next->next = head; head->next = NULL; return rev_head; } void reverse(node_t **head) { *head = reverse_recursive(*head); } ``` ### 程式解說 #### reverse 此函式是為了包裝 reverse 的呼叫成指標的型式，並會完成最後修改頭的動作。 #### reverse_recursive 1. 此函式把 linked list 拆成第一個節點以及後面整串，然後遞迴呼叫翻轉後面整串。 ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] headp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">head</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node1</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey"> <TR> <TD PORT="val">node2</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey"> <TR> <TD PORT="val"> ... </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey"> <TR> <TD PORT="val"> last node </TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; null [label=< <TABLE BORDER="0" CELLBORDER="0" cellspacing="0"> <TR> <TD PORT="p"> NULL </TD> </TR> </TABLE>>]; a:next:c -> b:val; b:next:c -> c:val; c:next:c -> d:val; d:next:c -> null:p:w; { rank=same; headp:p:s -> a:val; } } ``` 2. 後面翻轉完後回傳的是後面那串新的頭。 ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] headp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">head</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="val">node1</TD> <TD PORT="next"> </TD> </TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey"> <TR> <TD PORT="next"> </TD> <TD PORT="val">node2</TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey"> <TR> <TD PORT="next"> </TD> <TD PORT="val"> ... </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey"> <TR> <TD PORT="next"> </TD> <TD PORT="val"> last node </TD> </TR> </TABLE>>]; null [label=< <TABLE BORDER="0" CELLBORDER="0" cellspacing="0"> <TR> <TD PORT="p"> NULL </TD> </TR> </TABLE>>]; rev_head [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="p"> rev_head </TD> </TR> </TABLE>>]; a:next:c -> b:val; a->null [style=invis] b:val -> c:next:c [dir=back]; c:val -> d:next:c [dir=back]; null:p:e -> b:next:c [dir=back] { rank=same; headp:p:s -> a:val; } { rank=same; rev_head:p:s -> d:val} } ``` 3. 再來 ``` head->next->next = head; ``` 目的是要教第一個節點接回到尾巴。 最後再把尾巴的 `next` 設為 `NULL`: ``` head->next = NULL; ``` 做完就變 ```graphviz digraph { rankdir=LR; node [shape=none]; edge [arrowhead=vee,headclip=false, tailclip=false] headp [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR><TD PORT="p">head</TD></TR> </TABLE>>]; a [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="next"> </TD> <TD PORT="val">node1</TD> </TR> </TABLE>>]; b [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey"> <TR> <TD PORT="next"> </TD> <TD PORT="val">node2</TD> </TR> </TABLE>>]; c [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey"> <TR> <TD PORT="next"> </TD> <TD PORT="val"> ... </TD> </TR> </TABLE>>]; d [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0" BGCOLOR="lightgrey"> <TR> <TD PORT="next"> </TD> <TD PORT="val"> last node </TD> </TR> </TABLE>>]; null [label=< <TABLE BORDER="0" CELLBORDER="0" cellspacing="0"> <TR> <TD PORT="p"> NULL </TD> </TR> </TABLE>>]; rev_head [label=< <TABLE BORDER="0" CELLBORDER="1" cellspacing="0"> <TR> <TD PORT="p"> rev_head </TD> </TR> </TABLE>>]; null:p:e -> a:next:c [dir=back]; b:val -> c:next:c [dir=back]; c:val -> d:next:c [dir=back]; a:val:e -> b:next:c [dir=back] { rank=same; headp:p:s -> a:val; } { rank=same; rev_head:p:s -> d:val} } ``` 回傳 `rev_head` 就完成了翻轉的動作。 ## 延伸問題 4 - Fisher-Yates Shuffle ```c= void shuffle(node_t **head){ node_t *old_head, *cursor, **indirect; int range = 0; old_head = cursor = *head; // get list length while(cursor){ range += 1; cursor = cursor->next; } // starts Fisher-Yates *head = NULL; for(;range > 0; --range){ indirect = &old_head; // move to selected node for(int i = rand() % range; i > 0; --i){ indirect = &(*indirect)->next; } // move selected node to new list node_t *tmp = *indirect; // holds the node to move *indirect = (*indirect)->next; // skip the node to move tmp->next = *head; // move the node to the head of new list *head = tmp; } } ``` ### 程式解說 + 6~8: 得到 list 長度，後面 Fisher-Yates 要用 + 11: `*head` 作為新的 list 的頭 + 12: Fisher-Yates Shuffle 的迴圈，出迴圈後就完成搬運所有節點了。head也將變成新的 list。 + 15~17: 取得隨機數然後找到第 i 個節點 + 20~23: 將這個節點從舊 list 移到新 list 的頭
Last changed by  
 
Yu Jen Lin
391

Read more

2020q3 Homework3 (quiz3)

contributed by < sammer1107 > 測驗題 測驗 1 int asr_i(signed int m, unsigned int n) { const int logical = (((int) -1) OP1) > 0; unsigned int fixu = -(logical & (OP2)); int fix = *(int *) &fixu;

11/18/2020
2020q3 Homework6 (kcalc)

contributed by < sammer1107 > 作業說明 完善測試機制 原本的 test case 跑完也不確定結果到底正不正確，所以我決定先從改善 test 機制開始。 NAN="NAN_INT" INF="INF_INT"

11/11/2020
2020q3 Homework5 (quiz5)

contributed by < sammer1107 > ==測驗題目== 測驗 1 #include <stdio.h> #include <stdlib.h> double divop(double orig, int slots) { if (slots == 1 || orig == 0)

11/10/2020
2020q3 Homework5 (render)

contributed by < sammer1107 > 程式原理 Class Renderer 這個 class 負責根據一個 Game 物件的狀態來算繪遊戲場景。Renderer 內固定有一個 RayCaster，讓 Renderer 可以使用他來計算場景。 GetARGB 方法 inline static uint32_t GetARGB(uint8_t brightness) { return (brightness << 16) + (brightness << 8) + brightness;

10/26/2020
Read more from Yu Jen Lin
Published on HackMD