2020q3 Homework1 (quiz1)

contributed by < guyleaf >

題目

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

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

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

• add_entry: 新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy
• remove_entry: 移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)
• swap_pair: 交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 1->2->3->4，則該回傳 2->1->4->3
• reverse: 將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1

詳細請參考: 2020q3 第 1 週測驗題

解答

• AA1: assert(new_node)
• AA2: *indirect = new_node
• BB1: node = &(*node)->next->next
• BB2: *node = (*node)->next
• CCC: head->next = cursor; cursor = head

程式運作原理

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

建立一個 node 並加到 linked list 的尾端:

• 此寫法使用 pointer to pointer 的方法，double pointer 的 indirect 指向 head pointer 的位址，表示 indirect 可以控制被指向的 pointer 所指的 node ，也就是可以間接控制 head 所指的方向

• 建立一個 new_node 後， indirect 利用迴圈指向最尾端 node 的 next pointer ，再利用 double pointer 的特性， 間接控制 next pointer 指向 new_node

• 接著再來說說 assert 的放置問題，我認為需放在 malloc 之後才有作用，因為 malloc 分配記憶體失敗時，會回傳 NULL ，這時候就要判斷是否分配成功，否則將會造成 Segmentation fault
• 根據 C 語言規格書的說明: assert 是用於診斷測試程式，當參數條件不成立時，跳出 failed 例外並呼叫 abort 函式，異常中止程式

The assert macro puts diagnostic tests into programs; it expands to a void expression. When it is executed, 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 (including the text of the argument, the name of the source file, the source line number,and the name of the enclosing function — the latter are respectively the values of the preprocessing macros __FILE__ and __LINE__ and of the identifier __func__)on the standard error stream in an implementation-defined format. It then calls the abort function.

• 所以我想做一些實驗來證明我的推論…TODO

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

• 尋找與參數 value 相符的 node ，並回傳該 node 位址，若無則回傳 NULL (也就是沒找到， 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);
}

• TODO

Swap_pair

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

• TODO

Reverse

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

• TODO

Print_list

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

• TODO

改寫 swap_pair 和 reverse - pointer to pointer

• TODO

遞迴版本的 reverse

• TODO

實現 Fisher–Yates shuffle

• TODO