# 2020q3 Homework1 (quiz1)
contributed by < guyleaf >

## 題目
考慮一個單向 linked list，其結構定義為:

typedef struct __node {                   
    int value;
    struct __node *next;
} node_t;

已知不存在 circular (環狀結構)，接下來將對該單向 linked list 進行下列操作:
* `add_entry`: 新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy
* `remove_entry`: 移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)
* `swap_pair`: 交換一對相鄰的節點，取自 [LeetCode: Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)，給定 1->2->3->4，則該回傳 2->1->4->3
* `reverse`: 將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1

詳細請參考: [2020q3 第 1 週測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)

## 解答
* AA1: `assert(new_node)`
* AA2: `*indirect = new_node`
* BB1: `node = &(*node)->next->next`
* BB2: `*node = (*node)->next`
* CCC: `head->next = cursor; cursor = head`

## 程式運作原理
### Add_entry

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);
    while (*indirect)
        indirect = &(*indirect)->next;
    *indirect = new_node;
}

建立一個 node 並加到 linked list 的尾端:
* 此寫法使用 pointer to pointer 的方法，double pointer 的 `indirect` 指向 `head pointer` 的位址，表示 `indirect` 可以控制被指向的 pointer 所指的 node ，也就是可以間接控制 `head` 所指的方向

digraph add_entry {
        node [shape=record];
        rankdir=LR;
        {
            node1 [label="{ <data> node1 | <ref>  }"];
            node2 [label="{ <data> node2 | <ref>  }"];
            NULL1 [label="NULL", shape=plaintext];
            NULL2 [label="NULL", shape=plaintext];
            new_node [label="{ <data> new_node | <ref>  }"];
        }
        
        node [shape=box];
        rank="same";
        {
            indirect [label="indirect", fontcolor=red];
            head [label="head", fontcolor=blue];
            indirect -> head [arrowsize=0.8];
        }
        
        
        head -> node1:data [arrowsize=0.8];
        node1:ref:c -> node2:data [arrowtail=dot, dir=both, tailclip=false, arrowsize=0.8];
        node2:ref:c -> NULL1 [arrowtail=dot, dir=both, tailclip=false, arrowsize=0.8];
        
        new_node:ref:c -> NULL2 [arrowtail=dot, dir=both, tailclip=false, arrowsize=0.8];
}

* 建立一個 `new_node` 後， `indirect` 利用迴圈指向最尾端 node 的 next pointer ，再利用 double pointer 的特性， 間接控制 next pointer 指向 `new_node`

digraph add_entry {
        node [shape=box];
        head [label="head", fontcolor=blue];
        
        
        node [shape=record];
        rankdir=LR;
        {
            node1 [label="{ <data> node1 | <ref>  }"];
            node2 [label="{ <data> node2 | <ref>  }"];
            NULL1 [label="NULL", shape=plaintext];
            new_node [label="{ <data> new_node | <ref>  }"];
        }
        
        node [shape=box];
        indirect [label="indirect", fontcolor=red];
        
        head -> node1:data [arrowsize=0.8];
        node1:ref:c -> node2:data [arrowtail=dot, dir=both, tailclip=false, arrowsize=0.8];
        indirect -> node2:ref [arrowsize=0.8];
        node2:ref:c -> new_node:data [arrowtail=dot, dir=both, tailclip=false, arrowsize=0.8];
        new_node:ref:c -> NULL1 [arrowtail=dot, dir=both, tailclip=false, arrowsize=0.8];
}

* 接著再來說說 `assert` 的放置問題，我認為需放在 `malloc` 之後才有作用，因為 `malloc` 分配記憶體失敗時，會回傳 `NULL` ，這時候就要判斷是否分配成功，否則將會造成 Segmentation fault
* 根據 C 語言規格書的說明: `assert` 是用於診斷測試程式，當參數條件不成立時，跳出 failed 例外並呼叫 `abort` 函式，異常中止程式
> The `assert` macro puts diagnostic tests into programs; it expands to a void expression. When it is executed, if expression(which shall have a scalar type) is false (that is,compares equal to 0), the assert macro writes information about the particular call that failed (including the text of the argument, the name of the source file, the source line number,and the name of the enclosing function — the latter are respectively the values of the preprocessing macros `__FILE__` and `__LINE__` and of the identifier `__func__`)on the standard error stream in an implementation-defined format. It then calls the abort function.

* 所以我想做一些實驗來證明我的推論....TODO

### Find_entry

node_t *find_entry(node_t *head, int value)
{
    node_t *current = head;
    for (; current && current->value != value; current = current->next)
        /* interate */;
    return current;
}

* 尋找與參數 `value` 相符的 node ，並回傳該 node 位址，若無則回傳 `NULL` (也就是沒找到， `current` 移動到最尾端)

### Remove_entry

void remove_entry(node_t **head, node_t *entry)
{
    node_t **indirect = head;

    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    *indirect = entry->next;
    free(entry);
}

* TODO

### Swap_pair

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

* TODO

### Reverse

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

* TODO

### Print_list

void print_list(node_t *head)
{
    for (node_t *current = head; current; current = current->next)
        printf("%d ", current->value);
    printf("\n");
}

* TODO

## 改寫 swap_pair 和 reverse - pointer to pointer
* TODO

## 遞迴版本的 reverse
* TODO

## 實現 Fisher–Yates shuffle
* TODO