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

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

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

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

AA1 目的是要確認 new_node 是否有成功宣告，所以選擇 (a) assert(new_node)

AA2 目的是在 while 找到最後一個節點的時插入 new_node，所以選擇 (b) *indirect = new_node

一開始

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        indir [
            shape = record 
            label = "**indirect(**head)"
        ]
        head [
            shape = record 
            label = "*head"
        ]
        node_t1 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        node_t2 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        new_node_t1 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        NULL [
            shape = record
            label = "NULL"
        ]
        new_node -> new_node_t1;
        indir -> head;
        head -> node_t1;
        node_t1:f1 -> node_t2;
        node_t2:f1 -> NULL;
    }
}

trace 到最後

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        indir [
            shape = record 
            label = "**indirect(**head)"
        ]
        indirect [
            shape = record
            label = "*indirect"
        ]
        head [
            shape = record 
            label = "*head"
        ]
        node_t1 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        node_t2 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        new_node_t1 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        NULL [
            shape = record
            label = "NULL"
        ]
        new_node -> new_node_t1;
        indir -> head;
        head -> node_t1;
        node_t1:f1 -> node_t2;
        node_t2:f1 -> NULL;
        indirect -> NULL
    }
}

把 new_node 接上去

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        indir [
            shape = record 
            label = "**indirect(**head)"
        ]
        head [
            shape = record 
            label = "*head"
        ]
        node_t1 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        node_t2 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        new_node_t1 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        NULL [
            shape = record
            label = "NULL"
        ]
        new_node -> new_node_t1;
        indir -> head;
        head -> node_t1;
        node_t1:f1 -> node_t2;
        node_t2:f1 -> new_node_t1;
        new_node_t1:f1 -> NULL;
    }
}

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

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = record 
            label = "head"
        ]
        current [
            shape = record 
            label = "current"
        ]
        node_t1 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        node_t2 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        NULL [
            shape = record
            label = "NULL"
        ]
        head -> node_t1
        current -> node_t1
        node_t1:f1 -> node_t2
        node_t2:f1 -> NULL
    }
}

當 current->value 不是想找的 value 時，把 current 移動到下一個 node

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = record 
            label = "head"
        ]
        current [
            shape = record 
            label = "current"
        ]
        node_t1 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        node_t2 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        NULL [
            shape = record
            label = "NULL"
        ]
        head -> node_t1
        current -> node_t2
        node_t1:f1 -> node_t2
        node_t2:f1 -> NULL
    }
}

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

流程跟 find_entry 類似，需要先找到要移除的 node，但是因為要移除 node 不能只使用 node_t *indirect 而是 node_t **indriect
一開始

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = record 
            label = "head"
        ]
        indirect [
            shape = record 
            label = "indirect"
        ]
        node_t1 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        node_t2 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        NULL [
            shape = record
            label = "NULL"
        ]
        target_node [
            shape = record
            label = "target_node"
        ]
        head -> node_t1
        indirect -> node_t1
        node_t1:f1 -> node_t2
        node_t2:f1 -> NULL
        target_node -> node_t2
    }
}

找到要移除的 node

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = record 
            label = "head"
        ]
        indirect [
            shape = record 
            label = "indirect"
        ]
        node_t1 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        node_t2 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        NULL [
            shape = record
            label = "NULL"
        ]
        target_node [
            shape = record
            label = "target_node"
        ]
        head -> node_t1
        indirect -> node_t2
        node_t1:f1 -> node_t2
        node_t2:f1 -> NULL
        target_node -> node_t2
    }
}

free(entry)

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = record 
            label = "head"
        ]
        node_t1 [
            shape = record 
            label = "<f0> value\l|<f1> *next\l"
        ]
        NULL [
            shape = record
            label = "NULL"
        ]
        head -> node_t1
        node_t1:f1 -> NULL
    }
}

### swap_pair

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

一開始

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = "recoed"
            label = "head"
        ]
        node_t1 [
            shape = record 
            label = "node"
        ]
        A [
            shape = record
            label = "A"
        ]
        B [
            shape = record
            label = "B"
        ]
        C [
            shape = record
            label = "C"
        ]
        head:s -> node_t1:n
        node_t1:s -> A:n
        A -> B -> C 
    }
}

node_t *tmp = *node;

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = "recoed"
            label = "head"
        ]
        node_t1 [
            shape = record 
            label = "node"
        ]
        temp [
            shape = record 
            label = "tmp"
        ]
        A [
            shape = record
            label = "A"
        ]
        B [
            shape = record
            label = "B"
        ]
        C [
            shape = record
            label = "C"
        ]
        head:s -> node_t1:n
        temp:e -> A:n
        node_t1:s -> A:n
        A -> B -> C 
    }
}

*node = &((*node)->next)

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = "recoed"
            label = "head"
        ]
        node_t1 [
            shape = record 
            label = "node"
        ]
        temp [
            shape = record 
            label = "tmp"
        ]
        A [
            shape = record
            label = "A"
        ]
        B [
            shape = record
            label = "B"
        ]
        C [
            shape = record
            label = "C"
        ]
        head:s -> node_t1:n
        temp:e -> A:n
        node_t1:s -> B:n
        A -> B -> C 
    }
}

tmp->next = (*node)->next

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = "recoed"
            label = "head"
        ]
        node_t1 [
            shape = record 
            label = "node"
        ]
        temp [
            shape = record 
            label = "tmp"
        ]
        A [
            shape = record
            label = "A"
        ]
        B [
            shape = record
            label = "B"
        ]
        C [
            shape = record
            label = "C"
        ]
        head:s -> node_t1:n
        temp:e -> A:n
        node_t1:s -> B:n
        A -> C 
        B -> C
    }
}

(*node)->next = tmp

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = "recoed"
            label = "head"
        ]
        node_t1 [
            shape = record 
            label = "node"
        ]
        temp [
            shape = record 
            label = "tmp"
        ]
        A [
            shape = record
            label = "A"
        ]
        B [
            shape = record
            label = "B"
        ]
        C [
            shape = record
            label = "C"
        ]
        head:s -> node_t1:n
        temp:e -> A:n
        node_t1:s -> B:n
        A -> C 
        B -> A
    }
}

&(*node)->next->next

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = "recoed"
            label = "head"
        ]
        node_t1 [
            shape = record 
            label = "node"
        ]
        temp [
            shape = record 
            label = "tmp"
        ]
        A [
            shape = record
            label = "A"
        ]
        B [
            shape = record
            label = "B"
        ]
        C [
            shape = record
            label = "C"
        ]
        head:s -> node_t1:n
        temp:e -> A:n
        node_t1:s -> C:n
        A -> C 
        B -> A 
    }
}

最後

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = "recoed"
            label = "head"
        ]
        A [
            shape = record
            label = "A"
        ]
        B [
            shape = record
            label = "B"
        ]
        C [
            shape = record
            label = "C"
        ]
        head:s -> B:n 
        B -> A -> C
    }
}

### reverse

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

透過 cursor 把整個 list 反轉
CCC 指向已經反轉的佇列的最前端 ， head 則指向下一個要反轉的 node

一開始

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = "recoed"
            label = "head"
        ]
        cursor [
            shape = "record"
            label = "cursor"
        ]
        A [
            shape = "record"
            label = "A"
        ]
        B [
            shape = "record"
            label = "B"
        ]
        C [
            shape = "record"
            label = "C"
        ]
        head -> A -> B -> C 
        cursor -> NULL
    }
}

node_t *next = head->next

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = "recoed"
            label = "head"
        ]
        cursor [
            shape = "record"
            label = "cursor"
        ]
        next [
            shape = "record"
            label = "next"
        ]
        A [
            shape = "record"
            label = "A"
        ]
        B [
            shape = "record"
            label = "B"
        ]
        C [
            shape = "record"
            label = "C"
        ]
        head -> A -> B -> C 
        next -> B
    }
}

head->next = cursor

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = "recoed"
            label = "head"
        ]
        cursor [
            shape = "record"
            label = "cursor"
        ]
        next [
            shape = "record"
            label = "next"
        ]
        A [
            shape = "record"
            label = "A"
        ]
        B [
            shape = "record"
            label = "B"
        ]
        C [
            shape = "record"
            label = "C"
        ]
        head -> A -> NULL
        next -> B -> C
        
    }
}

cursor = head

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = "recoed"
            label = "head"
        ]
        cursor [
            shape = "record"
            label = "cursor"
        ]
        next [
            shape = "record"
            label = "next"
        ]
        A [
            shape = "record"
            label = "A"
        ]
        B [
            shape = "record"
            label = "B"
        ]
        C [
            shape = "record"
            label = "C"
        ]
        head -> A -> NULL 
        next -> B -> C
        cursor -> A
        
    }
}

head = next

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = "recoed"
            label = "head"
        ]
        cursor [
            shape = "record"
            label = "cursor"
        ]
        next [
            shape = "record"
            label = "next"
        ]
        A [
            shape = "record"
            label = "A"
        ]
        B [
            shape = "record"
            label = "B"
        ]
        C [
            shape = "record"
            label = "C"
        ]
        head -> B 
        next -> B -> C
        cursor -> A -> NULL
        
    }
}

在經過一次迴圈

digraph add_entry {
    rankdir = "LR"
    subgraph A1 {
        head [
            shape = "recoed"
            label = "head"
        ]
        cursor [
            shape = "record"
            label = "cursor"
        ]
        next [
            shape = "record"
            label = "next"
        ]
        A [
            shape = "record"
            label = "A"
        ]
        B [
            shape = "record"
            label = "B"
        ]
        C [
            shape = "record"
            label = "C"
        ]
        head -> C 
        next -> C
        cursor -> B -> A -> NULL
        
    }
}

### print_list

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