# 2020q3 Homework1 (quiz1) contributed by < `OscarShiang` > ## 作業要求 * [x] 重新回答[第 1 周測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)，連同附帶的「延伸問題」。 * [x] 解釋程式運作原理時，應提供對應的 [Graphviz](https://graphviz.org/) 圖例，可參照 [Linked List 題目 1 + 分析](https://hackmd.io/@sysprog/linked-list-quiz) ## Quiz 1 ### AA1 因為 `AA1` 位於 `add_entry` 函式內，且在透過迴圈尋找最後一個節點之前，所以 `AA1` 是 `assert(new_node)` ，用以確認 `new_node` 有成功宣告與配置。 ### AA2 因為 `AA2` 在 `add_entry` 的最後，在迴圈迭代找到 linked list 最後一個節點的程式碼後，所以可以知道 `AA2` 是用以將新的節點連接到 list 上。因此答案是 `*indirect = new_node` ```graphviz digraph G { rankdir=LR node [shape=circle] A -> B -> C -> D D -> t[label="connect", color="red", penwidth=3] } ``` ### BB1 `BB1` 位在 `swap_pair` 中的 for 迴圈每次會更新的部分，所以可以得知其用來移動 node 所指向的位置。而且在該階段目標不是更動 list 中節點連接的方式，因此答案不會是 `*node` 的選項。再者因為 `node` 的資料型態是指標的指標，所以答案就會是 `node = &(*node)->next->next` 而每次更新時都會一次移動兩個節點的原因是因為要確認每次都是可以進行 `swap_pair` 的狀況 為了更清楚的說明，我以下圖進行示範 假設我們有一個 linked list 如下： ```graphviz digraph { rankdir=LR node [shape=circle] A -> B -> C -> D -> E } ``` 若以深色的節點表示 `*node` 所指下的位置的話則情況就會是 `node` 首先跳到 `A` 的位址 ```graphviz digraph { rankdir=LR node [shape=circle] A[style=filled] A -> B -> C -> D -> E } ``` 接著將 `*node` 轉換到 `(*node)->next` ```graphviz digraph { rankdir=LR node [shape=circle] B[style=filled] A -> B -> C -> D -> E } ``` 再來將 `A` 與 `B` 兩者的 `next` 值互換以完成交換 ```graphviz digraph { rankdir=LR node [shape=circle] B[style=filled] B -> A -> C -> D -> E } ``` 接著利用 for 迴圈更新的部分將 `*node` 切換到 `(*node)->next->next` ```graphviz digraph { rankdir=LR node [shape=circle] C[style=filled] B -> A -> C -> D -> E } ``` 因為 `A`, `B` 在上一次迴圈中已經交換過了，所以透過一次移動兩個節點的單位跳過已經交換完的節點 而當 `*node` 切換到 `E` 的時候 ```graphviz digraph { rankdir=LR node [shape=circle] E[style=filled] B -> A -> D -> C -> E } ``` 因為 `E` 的下一個節點不存在，即 `(*node)->next == NULL`，則程式會因為不滿足 for 迴圈執行的條件而跳出迴圈，完成 `swap_pair` ### BB2 承上題，因為是 swap 的函式，所以可以推論 `BB2` 的用途應該是將要交換的兩個節點的連結做更動，因為是要更動節點的連結，所以就不是針對 `node` 本身做操作，而是對 `*node` 做操作，因此答案就是 `*node = (*node)->next` ### CCC 因為 `CCC` 位在 `reverse` 函式中，所以我先以圖示來說明其運作的原理 假設我們現在有一個 list（`head` 的位置以深色表示） ```graphviz digraph { rankdir=LR node [shape=circle] A[style=filled] A -> B -> C -> D -> E } ``` 我們首先宣告一個新的指標 `cursor` 並賦值為 `NULL` 接著我們將 `head` 串到 `cursor` 的前面，則形成一個只有一個節點的新 list，並將 `head` 換到 `B`；`cursor` 則換到 `A` （`cursor` 所指向節點的以水藍色表示） ```graphviz digraph { rankdir=LR node [shape=circle] A[fillcolor="#A7FFFF", style=filled] B[style=filled] B -> C -> D -> E } ``` 我們重複這樣的動作 ```graphviz digraph { rankdir=LR node [shape=circle] B[fillcolor="#A7FFFF", style=filled] C[style=filled] B -> A C -> D -> E } ``` ```graphviz digraph { rankdir=LR node [shape=circle] C[fillcolor="#A7FFFF", style=filled] D[style=filled] C -> B -> A D -> E } ``` ```graphviz digraph { rankdir=LR node [shape=circle] D[fillcolor="#A7FFFF", style=filled] E[style=filled] D -> C -> B -> A E } ``` 可以看到在執行迴圈的過程中逐步將 `head` 各個節點連接到 `cursor` 所指向的新 list 上，直到 `head` 所指向的 list 全部連接到 `cursor` 所指向的 list 上時 ```graphviz digraph { rankdir=LR node [shape=circle] E[fillcolor="#A7FFFF", style=filled] E -> D -> C -> B -> A } ``` `cursor` 所指向的 list 就會是反轉過後的 list，而這時原本的 `head` 則已經被改到 `NULL` 值，因此我們將 `cursor` 作為新的 `head` return 回去讓其他程式可以將 `head` 的數值進行更新。 而因爲 `CCC` 在其中扮演的作用是將 `head` 原本的節點接在 `cursor` 之前，所以答案就會是 `head->next = cursor; cursor = head` ## 以指標的指標來改寫 `swap_pair` 與 `reverse` ### swap_pair 原本 `swap_pair` 的實作如下 ```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; } ``` 因為其在迴圈內的操作已經有使用到指標的指標，所以只需要將函式參數的型態做修改，就可以達到互換的同時更改 `head` 的位置 ```diff - node_t *swap_pair(node_t *head) + void swap_pair(node_t **head) { - for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next) { + 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; } ``` 因為我們操作的是指標的指標，所以在更改 `head` 變數的位址所指向的數值時就可以將 `head` 所保存的數值做修改，因而減少將新的 `head` 數值回傳給其他函數的動作。 ### reverse `reverse` 的實作如下 ```c void reverse(node_t **indirect) { node_t *cursor = NULL; while (*indirect) { node_t *next = (*indirect)->next; (*indirect)->next = cursor; cursor = *indirect; *indirect = next; } *indirect = cursor; } ``` 我們可以仿造 `swap_pair` 的方式，以指標的指標來記錄新的 list 第一個節點的位址，並搭配原本 list 的第一個節點 `head` 來進行操作 ```c void reverse(node_t **indirect) { node_t *curr = *indirect; *indirect = NULL; while (head) { node_t *next = curr->next; curr->next = *indirect; *indirect = head; head = next; } } ``` 透過不斷將 `*indirect` 的數值改為新 list 的第一個節點的值，我們就可以確保在不回傳新的 `head` 的狀態下完成整個 list 的反轉與更新 `head` 的數值了。 ### 實作程式碼 請參考 [linked_list.c - GitHub gist](https://gist.github.com/OscarShiang/a2885677184f5d049b50804f68e85ca4) ## 參考資料 1. [2020q3 第 1 週測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1) 2. [範例程式碼 (linked_list.c)](https://gist.github.com/OscarShiang/a2885677184f5d049b50804f68e85ca4) ###### tags: `sysprog2020`