2020q3 Homework1 (quiz1)

# 2020q3 Homework1 (quiz1) contributed by < `RainbowEye0486` > ## Outline [TOC] ## :penguin: 作業要求 * 重新回答[第 1 周測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)，連同附帶的「延伸問題」。 * 解釋程式運作原理時，應提供對應的 [Graphviz](https://graphviz.org/) 圖例，可參照 [Linked List 題目 1 + 分析](https://hackmd.io/@sysprog/linked-list-quiz) * 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb) 和 [Linked list 題目分析](https://hackmd.io/s/HyELy5bTz) 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及==進行相關實驗==。 ## Linked list 的認知 ### 原程式碼 ```clike= #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; } ``` ### add_entry `add_entry`: 新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy ```clike= 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; } ``` 首先了解什麼是 `assert` ，定義上來說，`assert` 可以是一個變量或任何C表達式。如果expression 計算結果為TRUE，`assert()`什麼都不做。如果表達式計算為false時，assert() 顯示stderr和中止執行程序上的錯誤信息。 `assert()` 經常被使用在 Debug 的版本，在 release 的版本中比較不會出現 assert() 。回到選項的部份： AA1 = ? - [x] `(a)` assert(new_node) - [ ] `(b)` indirect = new_node 首先用 `assert()` 去判斷 `malloc` 是否成功，如果失敗，程式便會中止於此，不會繼續運行下去。 AA2 = ? - [ ] `(a)` assert(new_node) - [x] `(b)` indirect = new_node 確定 `new node` 沒有問題了後，我們跑一個 `while` 迴圈，從`Linked list`的`head`開始，向下尋找下一個節點，直到 `*indirect` 回傳的值是 NULL 之後結束迴圈，這時候 `indirect` 的這個指標指向的節點本來是NULL ，現在將它接上 `new node` 當作最後一個節點。另外，之所以會需要用到pointer to pointer 的原因是，我們想要更改的其實是從`indirect`的真實值，而不是傳入值，用pointer to pointer的方式能夠指定地址的方式更改值。 ### swap_pair `swap_pair`: 交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 `1->2->3->4`，則該回傳 `2->1->4->3` ```clike= 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 - [x] `(e)` node = &(*node)->next->next - [ ] `(f)` *node = &(*node)->next->next 我們必須先知道 `for` 迴圈內的意思是甚麼 ```clike for (node_t **node = &head; *node && (*node)->next; BB1) ``` 括號內的敘述，我們知道起始條件是pointer to pointer的`head`，使用pointer to pointer 的原因一樣是我們想要取址而不是純粹取值，進入條件是當指標`*node`以及指標指向下一個節點的`(*node)->next`都存在，也就是說，如果不是剛好還剩下兩個或以上的節點，都會跳出迴圈。最後一個一次迴圈結束時執行的動作，也就是BB1，直覺來說會是向後遞移兩個節點，所以剩下的就是去找出哪個選項的type是符合的。幾個答案給的都十分相似，因此我的想法是找出等號左邊及右邊出現的變數會是甚麼。首先，我們要先知道真正的節點儲存在哪裏，由於一開始我們宣告的時候是`node_t **node = &head`，代表我們把`head`的地址當作pointer放在`node`中了，加上我們宣告的是pointer to pointer，所以我們需要dereference兩次才能抓到真正的`head`(也就是說，dereference一次得到的是指向節點的指標)。 ```graphviz digraph linked_list{ node [shape=record]; aa [label="{ <data> node | <ref> }"]; bb [label="{ <data> *node | <ref> }"]; aa:ref:c -> bb:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; bb:ref:c -> head:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; rankdir=LR; a [label="{ <data> a | <ref> }"]; b [label="{ <data> b | <ref> }"]; c [label="{ <data> c | <ref> }"]; d [label="{ <data> d | <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 -> a; } ``` - 我們的目的是想要讓指向節點的pointer能夠向後移動兩個節點。 - 我們知道: `node`裡面放的是一個能夠指向節點的地址，因此本身是"指標的指標" ```graphviz digraph linked_list{ rankdir=LR; node [shape=record]; a [label="{ <data> node | <ref> }"]; b [label="{ <data> linked list \npointer | <ref> }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` `*node`裡面放的是節點本身，本身是個指標 ```graphviz digraph linked_list{ rankdir=LR; node [shape=record]; a [label="{ <data> linked list \npointer | <ref> }"]; b [label="{ <data> 節點| <ref> }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` 因此，我們要做的事情很簡單，就是去改變 `node` 裡面的指標，所以等號左邊會是 `node` ，而不是 `*node` 。剩下有可能的答案剩下 (a) 和 (e) ，我們知道 `node` 裡面放的應該要是指標的地址，因此先將指標 `(*node)` 向後移了兩個單位後變成 `(*node)->next->next`，最後取地址放進 `node` 中，因此選 (e) BB2 = ? - [ ] `(a)` node = (*node)->next - [ ] `(b)` node = &(*node)->next - [x] `(c)` *node = (*node)->next - [ ] `(d)` *node = &(*node)->next - [ ] `(e)` *node = &((*node)->next) 為了交換節點，所以我們需要更改的是 `node pointer` 。因此 (a) (b) 選項不納入考慮，因為會使當前節點位移，造成迴圈指標亂跳。 `node_t *tmp = *node;` `BB2;` `tmp->next = (*node)->next;` ` (*node)->next = tmp;` 這四行代表宣告一個 `node pointer` ，然後進行swap的動作，根據上下文提示，我們可以輕易地猜到答案(因為是對稱的)，另一方面，根據上一題，我們知道只有 `node` 內需要做取址的動作，所以 (b) (d) (e) 都不需要考慮。剩下的答案選擇 `(c)`。 ### reverse `reverse`: 將給定的 linked list 其內節點予以反向，即 `1->2->3->4`，則該回傳 `4->3->2->1` ```clike= 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 - [x] `(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 透過分析程式碼內容，我們可以知道大致上透過 `cursor` 當作新的頭，並且持續移動它，有點像 `insert_head` 一樣，逐漸將原本的 `head` 元素 pop 出來，然後 push 進 `cursor` 指的地方。 ```graphviz digraph linked_list{ rankdir=LR; node [shape=record]; a [label="{ <data> a | <ref> }"]; b [label="{ <data> b | <ref> }"]; c [label="{ <data> c | <ref> }"]; d [label="{ <data> d | <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 -> a; } ``` ```graphviz digraph linked_list{ rankdir=LR; node [shape=record]; cursor } ``` 一開始的情況，將 `head` 指向的節點當作 `next` 取出，目的是不要遺失下一個節點的資訊，然後我們就可以放心的把原本的 `head->next` 轉移到 `cursor` 上了。 CCC 正是這個轉移的過程，轉移完的下一步是下個節點 `next ` 成為了新的 `head` ，所以中間的步驟應該是先把 pop 出來的節點接上 `cursor` ，接著 `cursor` 往前移動，也就是它該從原本的 `head->next` 變成是 `head` 本身，以節點的視角說，的確可以解釋是向前移動了。所以選擇最符合的答案 `(b)` ```graphviz digraph linked_list{ rankdir=LR; node [shape=record]; b [label="{ <data> b | <ref> }"]; c [label="{ <data> c | <ref> }"]; d [label="{ <data> d | <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]; head -> b; } ``` ```graphviz digraph linked_list{ rankdir=LR; node [shape=record]; b [label="{ <data> a\n(cursor) | <ref> }"]; } ``` 經過幾次遞迴 ```graphviz digraph linked_list{ node [shape=record]; head } ``` ```graphviz digraph linked_list{ rankdir=LR; node [shape=record]; a [label="{ <data> d\n(cursor) | <ref> }"]; b [label="{ <data> c | <ref> }"]; c [label="{ <data> b | <ref> }"]; d [label="{ <data> a | <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]; } ``` 最後回傳 `cursor` 當作新的 `head` ，原本的 `head` 變成是 NULL ## 參考資料 - [指標的指標 (pointer to pointer)](http://low-understated.blogspot.com/2009/04/pointer-to-pointer.html) - [What is the difference between NULL, '\0' and 0?](https://stackoverflow.com/questions/1296843/what-is-the-difference-between-null-0-and-0)

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.