# 2020q3 Homework1 (quiz1)
contributed by < `chi-ming5566` >

---
## 程式運作
以 `add_entry()`, `find_entry()`, `remove_entry()`, `swap_pair()`, `reverse()`, `print_list()` 等函式所組成

---

### `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;

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

* 答案
* AA1為 `(a) assert(new_node)`
* AA2為 `(b) *indirect = new_node`

* 說明
* `*head`會指向 linked list 的尾端，在其插入一個 value 為 `new_value` 的 node。
* `**indirect` 是用來尋找 linked list (**head) 的尾端，而當 `*indirect` 找到尾端時， `*indirect == NULL`，就會將 `new_node` 插入linked list。
* 而 `assert` 是要確保 `new_node` 會正確分配記憶體，於是建立第一個 node，所以會直接跳到第 11 行，將 `indirect` 所存放的 value 當作 adrress，並且更改此 address 存放的 value，將該 value 改為 new_node 的 value。

---

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

* 說明
* 用 for 迴圈找到`*head` 後，傳回存放的值為 `value` 的 node，用於刪除某一個 node。

---

### `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);
}

* 說明
* 在 linked list 中找到 `**head`找到 node `*head` 然後刪除。
* 需要變更的 pointer 只有指向 `entry` 的 pointer，因此以 `**indirect` 存放此 pointer 的 address。
* 最後將此 `*indirect` 指向 `entry->next`，就不會有其他 pointer 指向該處。

* 以作業為例:

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

        node_t *entry = find_entry(head, 101);
        remove_entry(&head, entry);

        entry = find_entry(head, 111);
        remove_entry(&head, entry);

先執行到第10行，接著將 `head` 的 address與要刪除的 node 的 address 當作參數，一起傳入`remove_entry()`。

digraph a{
        node [shape=record];
        rankdir=LR
        entry [label="{<addr>(entry)|<ref>}"]
        head [label="{<addr>(main_head)|}"];
        
        a [label="{{<addr>|<next_addr>}|{72|<ref>}}"];
        b [label="{{<addr>|<next_addr>}|{101|<ref>}}"];
        c [label="{{<addr>|<next_addr>}|{108|<ref>}}"];
        d [label="{{<addr>|<next_addr>}|{109|<ref>}}"];
        e [label="{{<addr>|<next_addr>}|{110|<ref>}}"];
        f [label="{{<addr>|<next_addr>}|{111|<ref>}}"];
        head->a:addr;
        a:ref->b:addr;
        entry:ref->b:addr;
        b:ref->c:addr;
        c:ref->d:addr;
        d:ref->e:addr;
        e:ref->f:addr;
        
    }
    

---

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

`head` 的 value 是 `main` 的 `head` 的 address
`indirect` 存放 `head` 存放的 value

digraph a{
        node [shape=record];
        rankdir=LR
        
        
        a [label="{{<addr>|<next_addr>}|{72|<ref>}}"];
        b [label="{{<addr>|<next_addr>}|{101|<ref>}}"];
        c [label="{{<addr>|<next_addr>}|{108|<ref>}}"];
        d [label="{{<addr>|<next_addr>}|{109|<ref>}}"];
        e [label="{{<addr>|<next_addr>}|{110|<ref>}}"];
        f [label="{{<addr>|<next_addr>}|{111|<ref>}}"];
        a:ref->b:addr;
        b:ref->c:addr;
        c:ref->d:addr;
        d:ref->e:addr;
        e:ref->f:addr;
        
        now_head [label="{<addr>(head)|<data>}"]
        head [label="{<addr>(main_head)|<data>}"];
        
        now_head:data->head:addr;
        head:data->a:addr;
        indirect [label="{<addr>(indirect)|<data>}"];
        
        
        indirect:data->head:addr;
        entry [label="{<addr>(entry)|<data>}"];
        entry:data->b:addr;
    }
    

---

*indirect = entry->next;

讓 `*indirect` 所存放的值換為 `entry->next`，如此便可以達到刪除的目的

digraph a{
        node [shape=record];
        rankdir=LR
        
        
        a [label="{{<addr>|<next_addr>}|{72|<ref>}}"];
        b [label="{{<addr>|<next_addr>}|{101|<ref>}}"];
        c [label="{{<addr>|<next_addr>}|{108|<ref>}}"];
        d [label="{{<addr>|<next_addr>}|{109|<ref>}}"];
        e [label="{{<addr>|<next_addr>}|{110|<ref>}}"];
        f [label="{{<addr>|<next_addr>}|{111|<ref>}}"];
        a:ref->c:addr [color=red];
        b:ref->c:addr;
        c:ref->d:addr;
        d:ref->e:addr;
        e:ref->f:addr;
        main_head [label="{<addr>(main_head)|<data>}"];
        main_head->a:addr;
        head [label="{<addr>(head)|<data>}"];
        head:data->main_head:addr;
        indirect [label="{<addr>(indirect)|<data>}"];
        
        
        indirect:data->a:next_addr;
        entry [label="{<addr>(entry)|<data>}"];
        entry:data->b:addr;
    }

---

### `swap_pair()`

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

目的：交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 1->2->3->4，則該回傳 2->1->4->3

digraph swap{
    node [shape="record"]
    rankdir=LR;
    
    A [label="{{<addr>|<next_addr>}|{72|<ref>}}"];
    //B [label="{{<addr>|<next_addr>}|{101|<ref>}}"];
    C [label="{{<addr>|<next_addr>}|{108|<ref>}}"];
    D [label="{{<addr>|<next_addr>}|{109|<ref>}}"];
    E [label="{{<addr>|<next_addr>}|{110|<ref>}}"];
    //F [label="{{<addr>|<next_addr>}|{111|<ref>}}"];
    A:ref->C:addr;
    //B:ref->C:addr;
    C:ref->D:addr;
    D:ref->E:addr;
    //E:ref->F:addr;
    main_head [label="{<addr>(main_head)|<data>}"];
    main_head->A:addr;
    //head [label="{<addr>(head)|<data>}"];
    //head:data->main_head:addr;
    //indirect [label="{<addr>(indirect)|<data>}"];


    //indirect:data->A:next_addr;
    //entry [label="{<addr>(entry)|<data>}"];
}