# 2020q3 Homework1 (quiz1)
contributed by <[`hsiehong`](https://github.com/hsiehong/ACSTI)>
###### tags: `進階電腦系統理論與實作`

[作業說明](https://hackmd.io/@sysprog/sysprog2020-quiz1)

----

### `add_entry`
#### `AA1 : assert(new_node);`
#### `AA2 : *indirect = new_node;`

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
}

* line 5-7 : 新增一 node

digraph newNode{
    
    node[shape=box,color=red]
        rankdir=LR
        {
            newNode[label=new_node]
            NULL[label=NULL,shape=plaintext]
        }
        newNode->NULL
        
}

* line 9 : `assert(new_node)` 在 [C Library](http://www.cplusplus.com/reference/cassert/assert/?kw=assert)中，此 macro 會比較參數與0。相同的話錯誤訊息會被寫入 standard error device 且會呼叫[abort](http://www.cplusplus.com/reference/cstdlib/abort/)
目的是確保 `new_node` 能分配到空間
* line 12 : line 10 和 line 11，`*indirect` 會從 head 走訪 linked list 的所有節點，在迴圈結束時會停在最後一個節點，此時會將新的節點 `new_node` assign 給`*indirect`，即插入串列尾。

digraph link{
    node[shape=box,color=red]
    rankdir=LR
    {
        it[label=indirect, shape=plaintext]
        A[]
        B[]
        C[]
        N[label=null, shape=plaintext]
        A->B->C->N
        nn[label=new_node]
    }
    {
        rank=same
        it->N
    }
}

digraph link2{
    node[shape=box,color=red]
    rankdir=LR
    {
        //head[label=head, shape=plaintext]
        it2[label=indirect, shape=plaintext]
        A[]
        B[]
        C[]
        NN[label=new_node]
        Null[label=NULL, shape=plaintext]
        A->B->C->NN->Null
    }
    {
        rank=same
        it2->NN
    }
}

----

### `swap_pair`
#### `BB1 : node = &(*node)->next->next`
#### `BB2 : *node = (*node)->next`

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

* 將 linked list 中的node兩兩一組，並做交換
* line 3 : 走訪 linked list，且一次走訪兩個 node，此處是使用==pointer to pointer==，所以每次要跳兩個 node。
* 一開始沒注意到 **->** 優先權大於 **&**，參考[運算子優先順序](https://magicjackting.pixnet.net/blog/post/70902861)
* line 4-7 : 交換兩個 node 的**指向**
:::warning
dereference 與 reference 概念不清楚, pointer to pointer 概念混亂, 還需要去多找一些資料閱讀
:::

digraph swapGraph{
    node[shape=box,color=red]
    rankdir=LR
    {
        head[label=head, shape=plaintext]
        A[]
        B[]
        C[]
        D[]
        E[]
        Null[label=NULL,shape=none]
        N[shape=none]
        head->A->B->C->D->E->Null
        N->A,B
    }
}

digraph struct{
    node[shape=box, color=red]
    rankdir=LR
    {
        head[label=head, shape=plaintext]
        A2[label=A]
        B2[label=B]
        C2[label=C]
        D2[label=D]
        E2[label=E]
        Null2[label=NULL,shape=none]
        head->B2->A2->C2 [color=green]
        C2->D2->E2->Null2
        N2[label="node", shape=none]
    }
    {
        rank=same
        N2->C2
    }
}

digraph swapGraph{
    node[shape=box,color=red]
    rankdir=LR
    {
        head[label=head, shape=plaintext]
        A[]
        B[]
        C[]
        D[]
        E[]
        Null[label=NULL,shape=none]
        N[shape=none, label="node"]
        head->B->A->C
        C->D->E[color=green]
        E->Null
    }
    {
        rank=same
        N->E
    }
}

----

### `reverse`
#### `CCC : head->next = cursor; cursor = head`

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

* 將整個 linked list 反轉，並回傳反轉後的 head
* `cursor` 在每一個 iteration 中，初始都會在原 linked list 中 `head` 的前一個 node ，`next` 則永遠是 `head` 的下一項，並且將 head->next 指向 cursor (反轉的動作)，再將 cursor 指向 head

### 待補
* Graphviz 圖表優化，表達的不夠好，也畫的好醜...
* pointer to pointer 的相關應用