2020q3 Homework1 (quiz1)

contributed by < Veternal1226 >

tags: sysprog2020

---

延伸問題:

• 1. 解釋上述程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現;
• 2. 函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = … 的更新，請用指標的指標來改寫，並避免回傳指標;
• 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;

---

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 的指標
以下圖為例:

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

第19&20行用來將 indirect 指向 list 最尾端，因此判斷此 function 是實作將新 node 插入 list 尾端。
因此18行應為檢查新節點有沒有 malloc 成功，21行應為把新節點加入 list 中。

故AA1 = (a)assert(new_node)
AA2 = (b)*indirect = new_node

圖解插入新 node 前的狀態:

---

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

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

BB2 在流程中比較好解釋

流程:
初始狀態:

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

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

(*node)->next = tmp;

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

因此 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;

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

流程:

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

head->next = cursor; //CCC

cursor = head; //CCC

head = next;

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

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

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