# 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 的認知
### 原程式碼

#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

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`

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` 迴圈內的意思是甚麼

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一次得到的是指向節點的指標)。

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`裡面放的是一個能夠指向節點的地址，因此本身是"指標的指標"

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`裡面放的是節點本身，本身是個指標

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`

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` 指的地方。

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;
}

digraph linked_list{
    rankdir=LR;
    node [shape=record];
    cursor
}

一開始的情況，將 `head` 指向的節點當作 `next` 取出，目的是不要遺失下一個節點的資訊，然後我們就可以放心的把原本的 `head->next` 轉移到 `cursor` 上了。

CCC 正是這個轉移的過程，轉移完的下一步是下個節點 `next ` 成為了新的 `head` ，所以中間的步驟應該是先把 pop 出來的節點接上 `cursor` ，接著 `cursor` 往前移動，也就是它該從原本的 `head->next` 變成是 `head` 本身，以節點的視角說，的確可以解釋是向前移動了。
所以選擇最符合的答案 `(b)`

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;
}

digraph linked_list{
    rankdir=LR;
    node [shape=record];
    b [label="{ <data> a\n(cursor) | <ref>  }"];
}

經過幾次遞迴

digraph linked_list{
   
    node [shape=record];
     
    head
}

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)