# 2020q3 Homework1 (quiz1)
contributed by < `erickuo5124` >
###### tags: `2020進階電腦系統理論與實作`

----

## 重新回答 quiz1

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;

    assert(new_node); // AA1
    while (*indirect)
        indirect = &(*indirect)->next;
    *indirect = new_node; // AA2
}

此段程式碼會新增節點在 linked list 的最後面，並且利用指標的指標來直接改變裡面的值。

在 malloc 時，應注意是否成功取得記憶體，因此 `AA1` 需使用 `assert(new_node)`

而在跳出 while 迴圈時， `indirect` 應在整個 linked list 的最後面，此時需將新增的節點接上，因此 `AA2` 的答案為 `*indirect = new_node`

digraph G {
	1 -> 2 -> 3 -> tail->NULL;
    indirect -> NULL;
    {rank=same; 1; 2; 3; tail;NULL;}
    NULL[shape=none]
    indirect[shape=box]
}

----

node_t *swap_pair(node_t *head)
{
    for (node_t **node = &head; *node && (*node)->next
    ; node = &(*node)->next->next) { // BB1
        node_t *tmp = *node;
        *node = (*node)->next; // BB2
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
    return head;
}

此程式碼會交換相鄰的節點。若為奇數個節點，則最後一個不會交換

for 迴圈走訪整個 linked list， `BB1` 需要在每次迴圈移動兩個位置。因為必須改 `node` 的值，因此等號左方為 `*node` 的不考慮。又因為 `node` 為指標的指標， `*(node)->next->next` 的值需要再取址，因此選 `node = &(*node)->next->next`

`BB2` 選擇使用 `*node = (*node)->next` 來對原 linked list 中的值作改變

---

node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    while (head) {
        node_t *next = head->next;
        head->next = cursor; cursor = head; // CCC
        head = next;
    }
    return cursor;
}

此程式碼會將整個 linked list 倒轉

先將 `head->next` 的值存起來，把現在指到的節點接上新 linked list 之後，又以 `cursor` 為新 linked list 的頭，最後再移動到下一個節點，因此 `CCC` 選 `head->next = cursor; cursor = head`

**step1**

digraph original {
    head -> next -> 2 -> 3;
    {rank=same; head; next; 2;3;}
}

digraph reverse {
    cursor -> 0 -> NULL;
    {rank=same; cursor; 0;NULL}
}

**step2**

digraph original {
    next -> 2 -> 3;
    {rank=same; next; 2;3;}
}

digraph reverse {
    head->cursor -> 0 -> NULL;
    {rank=same; cursor; 0;NULL}
    NULL[shape=none]
}

**step3**

digraph original {
    head -> next -> 3;
    {rank=same;head; next; 3;}
}

digraph reverse {
    cursor -> 1 -> 0 -> NULL;
    {rank=same; cursor; 1;0;NULL}
    NULL[shape=none]
}

## 改寫 swap_pair 與 reverse 函式

void reverse(node_t **head)
{
    node_t **indirect = head;
    node_t *cursor = NULL;
    while (*indirect) {
        node_t *next = (*indirect)->next;
        (*indirect)->next = cursor; 
        cursor = *indirect;
        *indirect = next;
    }
    *head = cursor;
}

模仿 add_entry 的寫法，用了 indirect 接了傳進來的位址，並同時模仿了 loop

void swap_pair(node_t **head)
{
    node_t **indirect = head;
    for (node_t **node = indirect; *node && (*node)->next; node = &(*node)->next->next) {
        node_t *tmp = *node;
        *node = (*node)->next;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
}

改寫原理同上