2020q3 Homework1 (quiz1)

contributed by < shauming1020 >

tags: homework

Q1. 解釋程式運作原理

解釋上述程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現;

---

add_entry

新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy

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 檢查是否成功 malloc 空間給 new_node 指向

ISO/IEC 9899:TC3 規格書 p.169 提到 assert

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 on the standard error stream in an implementation-defined format.165).
It then calls the abort function.

• AA2 當 *indirect 取值為 NULL 時，表 indirect 正指向尾端節點的 next，因此要讓尾端節點指向 新節點的位址，故選　*indirect = new_node;

• 示意流程

#10 condition: while (*indirect)

• 從 indirect 所存位址取值不為 NULL 時，表尚未走訪到尾端節點

#11 indirect = &(*indirect)->next

• 取的值為 NULL 時，表走訪到尾端節點的 next

#12 *indirect = new_node

• 讓他的 next 指向 new_node (即 &node3)

---

find_entry

搜尋節點，成功則回傳找到的目標節點，否則回傳 NULL

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

#4 condition: current && current->value != value

• 若 current 未指向 NULL 且 current 的 value 不為目標值，則往 next 繼續走訪
• 當找到目標值，表 current 指向目標節點位址，回傳 current，否則回傳 NULL

---

remove_entry

移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)

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

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

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

• 示意流程

#5 condition: while ((*indirect) != entry)

• 當 *indirect 與 entry 指向不同的節點位址時

#6 indirect = &(*indirect)->next

• 則往下繼續遍歷，直到 *indirect 恰指向目標節點的位址

#8 *indirect = entry->next

• 讓 *indirect 指向 entry 的 next

#9 free(entry)

• 釋放 entry 所指向 heap 的空間

---

swap_pair

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

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

• BB1 解讀成 node = &(((*node)->next)->next)，完成一對的交換後，將 *node 往下走訪兩節點
• BB2 *node 為新一對當中的開頭者，因此要先讓 *node 往下一個節點去抓新的開頭
• 示意流程

#3 condition: if *node && (*node)->next

• 判斷當前與下一個指向是否為空，若非空則可以進行成對的交換

#4 node_t *tmp = *node

• 讓一個 tmp 指標指向與 *node 相同的位址

#5 *node = (*node)->next

• (*node)->next 為 &node2 指派給 *node，即讓 *node，也就是 head 往下走訪一個節點
• 往下個節點抓新對的開頭

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

• 這時 (*node)->next 為 &node3，指派到 tmp->next，也就讓 (*node) 的下一個節點成為 tmp 的下一個節點

#7 (*node)->next = tmp

• 將 tmp 的值指派到 (*node)->next，也就是 (*node)->next 的值改為 tmp 所存的節點位址

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

• &(*node)->next->next 解讀成 &(((*node)->next)->next)
• 因此先得到 (*node)->next) 的值 &node1
• 再將 node1->next 的位址指派給 node

• 執行直到跳出迴圈 ，最後回傳 head

---

reverse

將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1

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

• 從最後 return cursor 得知，cursor 是新 list 的 head，因此 head->next = cursor 是讓舊的 head 去指向新的 head (i.e. cursor)，再透過 cursor = head 讓 cursor 移動到新接上來的節點上，達到反向的效果
• 示意流程

#5 node_t *next = head->next;

• head->next 取值 &node2，指派到 next

#6 head->next = cursor

• 將 cursor 值 NULL，指派到 head->next

#6 cursor = head

• 將 head 值 &node1，指派給 cursor

#7 head = next

• 將 next 值 &node2，指派給 head

• 直到 head 值為 NULL，跳出迴圈並回傳 cursor，即成為新的 head

---

Q2. 請用指標的指標來改寫，並避免回傳指標

函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = … 的更新，請用指標的指標來改寫，並避免回傳指標;

1. 改寫 swap_pair

void swap_pair_v2(node_t **node)
{
    for (; *node && (*node)->next; node = &(*node)->next->next) {
        node_t *tmp = *node;
        *node = (*node)->next;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
}
...
    swap_pair_v2(&head);

• 原來的程式碼輸入 node_t *head 後再調用 node_t **node = &head 去進行操作，最後回傳 head 指標
• 因為 call-by-value，執行函式呼叫後會宣告一個 node_t *head 與輸入的指標指向相同的節點，函式內是對該 head 進行操作，因此實際上並沒有更動到原先輸入的指標，故最後還要回傳完成操作後的 head
• 參考 你所不知道的C語言:指標篇
• 而一開始若把 &head 當作引數輸入給 node_t **node，則會直接對原 head 操作

2. 改寫 reverse

void reverse_v2(node_t **node)
{
    node_t *cursor = NULL;
    while (*node) {
        node_t *next = (*node)->next;
        (*node)->next = cursor; cursor = *node;
        *node = next;
    }
    *node = cursor;
}

...
    reverse_v2(&head);

• 原理與上述相同，而最後操作完 head 會指向 NULL，因此要讓 head 重新指向新的 head (i.e. cursor)
• 示意流程

#5 node_t *next = (*node)->next

#6 (*node)->next = cursor; cursor = *node;

#7 *node = next

• 下個迴圈
  #5 node_t *next = (*node)->next

#6 (*node)->next = cursor

#6 cursor = *node

#7 *node = next

• 依序做下去直到跳出迴圈

#9 *node = cursor

• 最後要將 cursor 值指派給 *node

---

Q3. 以遞迴改寫上述的 reverse

以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_resersive，隨後在 reverse 函式中呼叫 rev_resersive;

node_t *rev_resersive(node_t **node, node_t **cursor) {
    if (*node) {
        node_t *next = (*node)->next;
        (*node)->next = *cursor; *cursor = *node;
        *node = next;
        *cursor = rev_resersive(node, cursor);
    }
    return *cursor;
}

void reverse_v3(node_t **node)
{
    node_t *cursor = NULL;
    *node = rev_resersive(node, &cursor);
}
...
    reverse_v3(&head);

• 將 while 迴圈內會重複執行的程式部份改用遞迴方式呼叫執行，最後在回傳 cursor 即可

---

Q4. Fisher–Yates shuffle

針對 singly-linked list 的節點，實作 Fisher–Yates shuffle，你應該儘量降低記憶體的使用量;

The modern algorithm

-- To shuffle an array a of n elements (indices 0..n-1):
** for i from n−1 downto 1 do **
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

假設rand()時間複雜度為O(1)
採用array實作時間複雜度為O(n)，但需要一額外與數組大小相同的空間，用來存放隨機取出的值，因此空間複雜度為O(2n)

---

Range	Roll	Scratch	Result
		1 2 3 4 5 6 7 8
1–8	6	1 2 3 4 5 8 7	6
1–7	2	1 7 3 4 5 8	2 6
1-6	6	1 7 3 4 5	8 2 6
…

實作

create_list

生成 n 個值為 {1, …, n} 升冪排列的 list node

void create_list(node_t **node, int n)
{
    for (int i = 1; !(*node) && i <= n; node = &(*node)->next, i++) {
        node_t *new_node = malloc(sizeof(node_t));
        new_node->value = i;
        new_node->next = NULL;

        *node = new_node;
    }
}

• n = 4

swap_value

交換兩 node_t 的值

void swap_value(node_t **a, node_t **b) {
    int tmp = (*a)->value;
    (*a)->value = (*b)->value;
    (*b)->value = tmp;
}

FYshuffle

• 參考 Shuffle a given array using Fisher–Yates shuffle Algorithm 矩陣版本修改

void FYshuffle (node_t **head, int n)
{
    srand(time(NULL));
    reverse(head);

    node_t **start = head;
    node_t **pick = head;

    for (int i = n-1; i > 0; i--) {
        // select a random index from 0 to i
        int j = rand() % (i+1);

        // shift pick to this index
        for (;j && (*pick); j--, pick = &(*pick)->next);

        // swap the pick value with start value.
        swap_value(start, pick);

        // update the start and pick
        start = &(*start)->next; pick = start;
    }
}

Range	Roll	Scratch
		1 2 3 4 5 6 7 8
reverse	-	8 7 6 5 4 3 2 1
1–8	3	[6] 7 8 5 4 3 2 1
1–7	6	[6 2] 8 5 4 3 7 1
1-6	6	[6 2 1] 5 4 3 7 8
1-5	0	[6 2 1 5] 4 3 7 8
…

#4 reverse(head)

• 演算法會從數組尾端往前取值，但作業要求是單向的list，因此需先對 list 反向

#5 condition: for (int i = n-1; i > 0; i--)

#11 int j = rand() % (i+1)

• 從 [0, i] 隨機取出一個值，i + 1 為當前可取的 list 長度，且會逐漸縮短

#14 for (;j && (*pick); j--, pick = &(*pick)->next);

• 移動 pick 使其指向目標 node
• 假設 j = 3，則將 pick 往 next 移動 3 次
• 若 j = 0，則不需要移動 pick

#17 swap_value(start, pick)

#20 start = &(*start)->next

#20 pick = start

• 假設每回都取到自己，即 j = 0
• 執行完 n - 1 個 iteration，此例 n = 4，故 start 會移動 3 次

分析

• 假設 rand() 為
  $O(1)$ 和 reverse() 為
  $O(n)$
• 時間複雜度
  • Worst Case : 每次取到最遠的值做交換，每回移動 pick
    $O(n)$，共 n 回，
    $O(n^2)$
  • Best Case : 每次取到最近的值交換，每回移動 pick
    $O(1)$，共 n 回，
    $O(n)$
  • Average Case :
    $O$((
    $n^2$ +
    $n$) / 2) =
    $O(n^2)$
• 空間複雜度
  • 只使用 n 個 node 和 3 個 pointer to pointer 變數，故
    $O(n)$

完整測試程式碼如下

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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

void create_list(node_t **node, int n)
{
    for (int i = 1; !(*node) && i <= n; node = &(*node)->next, i++) {
        node_t *new_node = malloc(sizeof(node_t));
        new_node->value = i;
        new_node->next = NULL;

        *node = new_node;
    }
}

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

void swap_value(node_t **a, node_t **b) {
    int tmp = (*a)->value;
    (*a)->value = (*b)->value;
    (*b)->value = tmp;
}

void FYshuffle (node_t **head, int n)
{
    srand(time(NULL));
    reverse(head); printf("reverse as initial ... "); print_list(*head);

    node_t **start = head;
    node_t **pick = head;

    for (int i = n-1; i > 0; i--) {
        // select a random index from 0 to i
        int j = rand() % (i+1);

        // shift pick to this index
        for (;j && (*pick); j--, pick = &(*pick)->next);
        printf("[iter %d] start at %d ,and swap with %d ... ", n-i, (*start)->value, (*pick)->value);

        // swap the pick value with start value.
        swap_value(start, pick); print_list(*head);

        // update the start and pick
        start = &(*start)->next; pick = start;
    }
    printf("[final] start at %d \n", (*start)->value);
}

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

int main() {
    int len = 8;
    node_t *head = NULL;
    create_list(&head, len);

    printf("before shuffle "); print_list(head);

    FYshuffle(&head, len);
    printf("after shuffle "); print_list(head);
}

before shuffle 1 2 3 4 5 6 7 8 
reverse as initial ... 8 7 6 5 4 3 2 1 
[iter 1] start at 8 ,and swap with 8 ... 8 7 6 5 4 3 2 1 
[iter 2] start at 7 ,and swap with 4 ... 8 4 6 5 7 3 2 1 
[iter 3] start at 6 ,and swap with 3 ... 8 4 3 5 7 6 2 1 
[iter 4] start at 5 ,and swap with 6 ... 8 4 3 6 7 5 2 1 
[iter 5] start at 7 ,and swap with 5 ... 8 4 3 6 5 7 2 1 
[iter 6] start at 7 ,and swap with 7 ... 8 4 3 6 5 7 2 1 
[iter 7] start at 2 ,and swap with 1 ... 8 4 3 6 5 7 1 2 
[final] start at 2 
after shuffle 8 4 3 6 5 7 1 2

---