# 2020q3 Homework1 (quiz1)
contributed by < `Veternal1226` >

###### tags: `sysprog2020`

---

:::info
延伸問題:

- [x] 1. 解釋上述程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現;
- [x] 2. 函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = ... 的更新，請用指標的指標來改寫，並避免回傳指標;
- [x] 3. 以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_recursive，隨後在 reverse 函式中呼叫 rev_recursive;
- [ ] 4. 針對 singly-linked list 的節點，實作 Fisher–Yates shuffle，你應該儘量降低記憶體的使用量;
:::

## node_t架構:

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

  digraph structs {
  		rankdir=LR;
        node[shape=record]
        struct0 [label="{<value> value|<next> next }"];
		struct1 [label="{<value> ...|<next> ... }"];
		
        struct0:next:struct1 -> struct1[  tailclip=true]
        
}

---
### add_entry
將新節點加至 list 尾端

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

indirect 這邊使用了 pointer to pointer ，代表指向 \*head 的指標
以下圖為例:

  digraph structs {
    node[shape=record]
    pointer0 [label="{<pointer> indirect}"];
	pointer1 [label="{<pointer> head}"];
	node0 [shape=box,label=0];
    node1 [shape=box,label=1];
    node2 [shape=box,label=2];
	NULL [shape=box,label=NULL]

    node0->node1->node2->NULL
		
    pointer0 -> pointer1 [tailclip=true];
    pointer1 -> node0 [tailclip=true];
	{rank=same;node0;node1;node2;NULL};
}

\*\*indirect 表 list node 0
\*indirect 表 head
indirect 表 &head

第19&20行用來將 indirect 指向 list 最尾端，因此判斷此 function 是實作將新 node 插入 list 尾端。
因此18行應為檢查新節點有沒有 malloc 成功，21行應為把新節點加入 list 中。
:::success
故AA1 = `(a)assert(new_node)`
AA2 = `(b)*indirect = new_node`
:::

圖解插入新 node 前的狀態:

  digraph structs {
    node[shape=record]
    pointer0 [label="{<pointer> indirect}"];
	pointer1 [label="{<pointer> ...}"];
	pointer2 [label="{<pointer> head}"];
	node0 [shape=box,label=0];
    node1 [shape=box,label=1];
    node2 [shape=box,label=2];
	NULL [shape=box,label=NULL]

    node0->node1->node2->NULL
		
    pointer0 -> pointer1 [tailclip=true];
    pointer1 -> NULL [tailclip=true];
	pointer2 -> node0 [tailclip=true];
	{rank=same;node0;node1;node2;NULL};
}

---
### find_entry
回傳指定值(value) 位在 list 中的哪個 node_t

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

實作方式為遍歷 list 直到 current->value == 指定值，
回傳 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);
    return;
}

實作方式為遍歷 list 直到 \*indirect == entry
透過將 \*indirect 指標指向 entry->next 來跳過 entry

---
### swap_pair

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

for 迴圈的第三個分區用來放做完一次內容後要執行的程式碼，經驗來說通常會放 index 移動或指標移動。
swap_pair 的作用是兩兩相鄰的交換，因此每次移動要移兩次 next ，因此 BB1 要填的內容我一開始的想法是填入`*node = (*node)->next->next`。
但實驗後發現 head 會跑掉，因為改動 \*node會改到 head 的值，因此應該要改的是再上一層的位址，也就是 `node = &(*node)->next->next`

:::success
因此 BB1 = `(e) node = &(*node)->next->next`
:::

BB2 在流程中比較好解釋

流程:
初始狀態:

  digraph structs {
    node[shape=record]
	pointer0 [label="{<pointer> tmp}"];
    pointer1 [label="{<pointer> node}"];
	node0 [shape=box,label=0];
    node1 [shape=box,label=1];
    node2 [shape=box,label=2];
	NULL [shape=box,label="..."]

    node0->node1
	node1->node2
	node2->NULL
		
    pointer1 -> node0 [tailclip=true];
    pointer0 -> node0 [tailclip=true];
	{rank=same;node0;node1;node2;NULL};
}

\*node = (\*node)->next; //BB2
因為這邊第一次就是要改 head 值，所以直接用 \*node 沒問題，把 \*node 改指到 \*node->next

  digraph structs {
    node[shape=record];
	pointer0 [label="{<pointer> tmp}"];
    pointer1 [label="{<pointer> node}"];
	node0 [shape=box,label=0];
    node1 [shape=box,label=1];
    node2 [shape=box,label=2];
	NULL [shape=box,label="..."]

    node0->node1
	node1->node2
	node2->NULL
    pointer1 -> node1 [tailclip=true];
    pointer0 -> node0 [tailclip=true];
	{rank=same;node0;node1;node2;NULL};
}

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

  digraph structs {
    node[shape=record];
	pointer0 [label="{<pointer> tmp}"];
    pointer1 [label="{<pointer> node}"];
	node0 [shape=box,label=0];
    node1 [shape=box,label=1];
    node2 [shape=box,label=2];
	NULL [shape=box,label="..."]

	node0->node2
	node1->node2
	node2->NULL
		
	pointer0 -> node0 [tailclip=true];
    pointer1 -> node1 [tailclip=true];
	{rank=same;node0;node1;node2;NULL};
}

(*node)->next = tmp;

  digraph structs {
    node[shape=record]
	pointer0 [label="{<pointer> tmp}"];
    pointer1 [label="{<pointer> node}"];
	node0 [shape=box,label=0];
    node1 [shape=box,label=1];
    node2 [shape=box,label=2];
	NULL [shape=box,label="..."]
	
	node0->node2
	node1->node0
	node2->NULL
	
	pointer0 -> node0 [tailclip=true];
    pointer1 -> node1 [tailclip=true];
	{rank=same;node0;node1;node2;NULL};
}

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

  digraph structs {
    node[shape=record]
    pointer1 [label="{<pointer> node}"];
	node0 [shape=box,label=0];
    node1 [shape=box,label=1];
    node2 [shape=box,label=2];
	NULL [shape=box,label="..."]
	
	node0->node2
	node1->node0
	node2->NULL
	
    pointer1 -> node2 [tailclip=true];
	{rank=same;node0;node1;node2;NULL};
}

:::success
因此 BB2 = `(c)*node = (*node)->next`
:::

---
### reverse

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

cursor 用來表示新 list 的開頭
每次迴圈將 next 記錄下來
把head所指節點的 next 轉向 cursor 所指位置
> head->next = cursor;

再把 cursor 指到此節點
> cursor = head;

:::success
因此 CCC = `(b)head->next = cursor; cursor = head`
:::

流程:

  digraph structs {
    node[shape=record];
	pointer0 [label="{<pointer> cursor}"];
    pointer1 [label="{<pointer> head}"];
	NULL0 [shape=box,label="NULL"]
	node0 [shape=box,label=0];
    node1 [shape=box,label=1];
    node2 [shape=box,label=2];
	NULL1 [shape=box,label="NULL"]
    node0->node1
	node1->node2
	node2->NULL1
	pointer0 -> NULL0 [tailclip=true];
    pointer1 -> node0[tailclip=true];
{rank=same;NULL0;node0;node1;node2;NULL1};
}

while (head) {
node_t *next = head->next;

  digraph structs {
    node[shape=record];
	pointer0 [label="{<pointer> cursor}"];
    pointer1 [label="{<pointer> head}"];
	pointer2 [label="{<pointer> next}"];
	NULL0 [shape=box,label="NULL"]
	node0 [shape=box,label=0];
    node1 [shape=box,label=1];
    node2 [shape=box,label=2];
	NULL1 [shape=box,label="NULL"]

    node0->node1
	node1->node2
	node2->NULL1
    pointer0 -> NULL0 [tailclip=true];
    pointer1 -> node0[tailclip=true];
	pointer2 -> node1 [tailclip=true];
	{rank=same;NULL0;node0;node1;node2;NULL1};
}

head->next = cursor; //CCC

  digraph structs {
    node[shape=record];
	pointer0 [label="{<pointer> cursor}"];
    pointer1 [label="{<pointer> head}"];
	pointer2 [label="{<pointer> next}"];
	NULL0 [shape=box,label="NULL"]
	node0 [shape=box,label=0];
    node1 [shape=box,label=1];
    node2 [shape=box,label=2];
	NULL1 [shape=box,label="NULL"]

    node0->NULL0
	node1->node2
	node2->NULL1
	pointer0 -> NULL0 [tailclip=true];
    pointer1 -> node0[tailclip=true];
	pointer2 -> node1 [tailclip=true];
{rank=same;NULL0;node0;node1;node2;NULL1};
}

cursor = head; //CCC

  digraph structs {
    node[shape=record];
	pointer0 [label="{<pointer> cursor}"];
    pointer1 [label="{<pointer> head}"];
	pointer2 [label="{<pointer> next}"];
	NULL0 [shape=box,label="NULL"]
	node0 [shape=box,label=0];
    node1 [shape=box,label=1];
    node2 [shape=box,label=2];
	NULL1 [shape=box,label="NULL"]

    node0->NULL0
	node1->node2
	node2->NULL1
	pointer0 -> node0 [tailclip=true];
    pointer1 -> node0[tailclip=true];
	pointer2 -> node1 [tailclip=true];
{rank=same;NULL0;node0;node1;node2;NULL1};
}

head = next;

  digraph structs {
    node[shape=record];
	pointer0 [label="{<pointer> cursor}"];
    pointer1 [label="{<pointer> head}"];
	pointer2 [label="{<pointer> next}"];
	NULL0 [shape=box,label="NULL"]
	node0 [shape=box,label=0];
    node1 [shape=box,label=1];
    node2 [shape=box,label=2];
	NULL1 [shape=box,label="NULL"]

    node0->NULL0
	node1->node2
	node2->NULL1
	pointer0 -> node0 [tailclip=true];
    pointer1 -> node1[tailclip=true];
	pointer2 -> node1 [tailclip=true];
{rank=same;NULL0;node0;node1;node2;NULL1};
}

中間步驟省略，迴圈結束後應該會長這樣

  digraph structs {
    node[shape=record];
	pointer0 [label="{<pointer> cursor}"];
    pointer1 [label="{<pointer> head}"];

	NULL0 [shape=box,label="NULL"]
	node0 [shape=box,label=0];
    node1 [shape=box,label=1];
    node2 [shape=box,label=2];
	NULL1 [shape=box,label="NULL"]

    node0->NULL0
	node1->node0
	node2->node1
	pointer0 -> node2 [tailclip=true];
    pointer1 -> NULL1[tailclip=true];
{rank=same;NULL0;node0;node1;node2;NULL1};
}

cursor 指向 reverse 完後的 list ，這邊直接回傳 cursor。
( 在後面改寫成 pointer to pointer 時，要加一步 \*head=cursor )

---

## swap_pair 和 reverse 改寫
### swap_pair

void 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 改寫成 \*(&head) 跟 head 都能動

### reverse

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

把所有 head 改寫成 \*head ，並加上前面說到的 \*head=cursor 後就能動

---

### recursive reverse
參考自[chwchao](https://hackmd.io/@6R35tGUKTmC5_lms3b3V3g/SyGYIBDVw)

node_t *rev_recursive(node_t *head)
{
    if (!head || !(head)->next) {
        return head;
    }
    node_t *new_head = rev_recursive(head->next);
    if (head->next) {
        head->next->next = head;  // change head->next's next to previous layer's head
    }
    head->next = NULL;  // always set new tail to NULL
    return new_head;
    
}

先走到 list 尾端，將尾端指標作為回傳值回傳，每往上一層，將下方一層的 next (head->next->next) 轉向此層的head，所以程式碼為 `head->next->next = head;`
要確保 reverse 完的 list 最後指向 NULL: `head->next = NULL`

原本的reverse改寫成:

void reverse(node_t **head)
{
    *head = rev_recursive(*head);
    return;
}