2020q3 Homework1 (quiz1)

contributed by < Holychung >

2020q3 第 1 週測驗題

Outline

• 2020q3 Homework1 (quiz1)
  • Outline
  • 題目
  • 程式運作原理
    • add_entry
    • remove_entry
    • swap_pair
    • reverse
  • 延伸問題
    • swap_pair
    • reverse
    • 遞迴版 reverse
    • Fisher–Yates shuffle
  • 延伸閱讀

題目

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

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

已知不存在 circular (環狀結構)，接下來將對該單向 linked list 進行下列操作:

• add_entry
• remove_entry
• swap_pair
• reverse

程式運作原理

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

head 是指標的指標，指向 linked list 起點的指標位置。
首先建立了一個指標的指標 indirect，指向 head 所指向的位置。

接著 malloc 新增一個節點 new_node 的記憶體空間，這個節點 next 指向 NULL。

經過 while 迴圈走訪 linked list，indirect 會指向最尾端 NULL，此時將最尾端指向 new_node，完成新增節點。

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

swap_pair

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

透過指標的指標 node 指向 linked list 開頭的位址，每一次交換相鄰的兩個節點，完成之後 node 指向下下一個節點的位置，直到 最尾端或是只剩一個節點的時候停止，並且把參數 head 指標傳回去更新新的起點位置。

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

一開始用指標的指標 node 指向起始的位址。

然後用指標 tmp 指向 *node 的位址。

*node 移動指向下一個節點。

把第一個節點的 next 指向第二個節點 next，也就是把 tmp 指向的節點的 next 改成 node 節點指向的 next。

再把第二個節點的 next 指向第一個節點，也就是把 node 指向的節點的 next 改成 tmp 指向的位址，完成一對節點的交換。

原本 node 是指向 head 這個指標，在做完一次 swap 後，head 會更新指到新的起點位置，因此要再把這個指標回傳回去更新開頭位置。
然後 node 就繼續指向下下一個節點，直接把 node 指向下一個節點的指標 next，一直做到最後結束。

reverse

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

用指標 cursor 紀錄下上一個節點的位置，初始值為 null，用一開始傳進來的起點位置 head 開始對 linked list 每一個節點做反轉，每一次 loop 都把當前的節點 next 指向前一個節點位址，直到最後，再回傳最後一個節點位址，也就是反轉後的開頭位址。

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

先用指標 next 紀錄下一個節點的位置，也就是當前 head->next 指向的位置。

然後 head 指向的節點的 next 就可以指向上一個節點，達到反轉。

上一個節點 cursor 就可以更新程現在這個節點 head，再把 head 指向剛剛 next 保存下來的下一個節點位置，完成一個節點的反轉。

延伸問題

用指標的指標來改寫 swap_pair reverse，避免回傳指標。
並且以遞迴改寫上述的 reverse。

swap_pair

原本的寫法是傳入指標，所以在函式結束的時候並不會更新到原本的指標 head，所以需要回傳開頭的位置。修改成指標的指標進行操作，就會更新到原本的 head，就不用回傳指標。

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

reverse

修改成指標的指標進行操作，就不用回傳指標，只是要注意最後要把 head 指向前一個的 cursor，才是開頭的位置。

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

遞迴版 reverse

把 reverse 整個 linked list 的工作拆成一次只 reverse 當前的節點，然後把剩下的 linked list 丟下去遞迴。
所以遞迴函式rev_recurive 需要吃兩個參數，第一個 head 是指向剩下的 linked list 起點位置，第二個 cursor 則是指向上一個節點的位置。然後每次遞迴都更新並傳遞這兩個參數，直到最後指向尾端 NULL，再把 head 指向 cursor 才是開頭的位置。

void rev_recurive(node_t **head, node_t *cursor)
{
    if (*head == NULL) {
        *head = cursor;
        return;
    }

    node_t *next = (*head)->next;
    (*head)->next = cursor; cursor = *head;
    *head = next;
    rev_recurive(head, cursor);
}

void reverse(node_t **head)
{
    rev_recurive(head, NULL);
}

並且有實現老師上課講解的尾端遞迴 (Tail Recursion)。

Tail recursion 是遞迴的一種特殊形式，副程式只有在最後一個動作才呼叫自己。以演算法的角度來說，recursion tree 全部是一脈單傳，所以間複雜度是線性個該副程式的時間。不過遞迴是需要系統使用 stack 來儲存某些資料，於是還是會有 stack overflow 的問題。但是從編譯器的角度來說，因為最後一個動作才呼叫遞迴，所以很多 stack 資料是沒用的，所以他是可以被優化的。基本上，優化以後就不會有時間與空間效率的問題。

Fisher–Yates shuffle

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

參考 Fisher–Yates shuffle 的方法和 dalaoqi 的做法，先計算出 singly-linked list 的長度，然後開始進入迴圈實作。每次挑選一個隨機的節點 target，然後把 target 前後的節點接起來，再把 target 接到新的 list 開頭的位置，直到迴圈結束。最後再把新的 list 的開頭位址 new_head 更新到原本開頭的 head。

void shuffle(node_t **head)
{
    if (*head == NULL)
        return;

    srand(time(NULL));
    int len = 0;
    node_t **indirect = head;
    
    while (*indirect) {
        len++;
        indirect = &(*indirect)->next;
    }
    
    node_t *new_head = NULL;
    for (int i = len; i > 0; i--) {
        int random = rand() % i;
        indirect = head;
        while (random--)
            indirect = &(*indirect)->next;
        node_t *target = *indirect;
        *indirect = (*indirect)->next;
        target->next = NULL;
        if (new_head) {
            target->next = new_head;
            new_head = target;
        } else {
            new_head = target;
        }
    }
    *head = new_head;
}

首先，indirect 先指向開頭 head，並且透過迴圈計算出 list 長度。

接下來進入 for 迴圈，每一次都隨機選取出一個節點，並且用 indirect 去找到該節點，並且用一個指標 target 指向該節點。

透過 indirect 把 target 前一個節點接到後一個節點上。

然後把 target 接到新的 list 的開頭。

直到迴圈結束，把指標的指標 head 指向新的開頭 new_head 就結束了。

延伸閱讀

• graphviz tutorial
• graphviz documentation
• 你所不知道的C語言：遞迴呼叫篇
• 尾端遞迴 (Tail Recursion)
• Fisher–Yates shuffle