2020q3 Homework1 (quiz1)

contributed by < erickuo5124 >

tags: 2020進階電腦系統理論與實作

---

重新回答 quiz1

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
}

此段程式碼會新增節點在 linked list 的最後面，並且利用指標的指標來直接改變裡面的值。

在 malloc 時，應注意是否成功取得記憶體，因此 AA1 需使用 assert(new_node)

而在跳出 while 迴圈時， indirect 應在整個 linked list 的最後面，此時需將新增的節點接上，因此 AA2 的答案為 *indirect = new_node

---

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

此程式碼會交換相鄰的節點。若為奇數個節點，則最後一個不會交換

for 迴圈走訪整個 linked list， BB1 需要在每次迴圈移動兩個位置。因為必須改 node 的值，因此等號左方為 *node 的不考慮。又因為 node 為指標的指標， *(node)->next->next 的值需要再取址，因此選 node = &(*node)->next->next

BB2 選擇使用 *node = (*node)->next 來對原 linked list 中的值作改變

---

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

此程式碼會將整個 linked list 倒轉

先將 head->next 的值存起來，把現在指到的節點接上新 linked list 之後，又以 cursor 為新 linked list 的頭，最後再移動到下一個節點，因此 CCC 選 head->next = cursor; cursor = head

step1

step2

step3

改寫 swap_pair 與 reverse 函式

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

模仿 add_entry 的寫法，用了 indirect 接了傳進來的位址，並同時模仿了 loop

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

改寫原理同上