2020q3 Homework1 (quiz1)

contributed by <hsiehong>

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

作業說明

---

add_entry

AA1 : assert(new_node);

AA2 : *indirect = new_node;

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
}

• line 5-7 : 新增一 node

• line 9 : assert(new_node) 在 C Library中，此 macro 會比較參數與0。相同的話錯誤訊息會被寫入 standard error device 且會呼叫abort
  目的是確保 new_node 能分配到空間
• line 12 : line 10 和 line 11，*indirect 會從 head 走訪 linked list 的所有節點，在迴圈結束時會停在最後一個節點，此時會將新的節點 new_node assign 給*indirect，即插入串列尾。

---

swap_pair

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

BB2 : *node = (*node)->next

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

• 將 linked list 中的node兩兩一組，並做交換
• line 3 : 走訪 linked list，且一次走訪兩個 node，此處是使用pointer to pointer，所以每次要跳兩個 node。
• 一開始沒注意到 -> 優先權大於 &，參考運算子優先順序
• line 4-7 : 交換兩個 node 的指向

dereference 與 reference 概念不清楚, pointer to pointer 概念混亂, 還需要去多找一些資料閱讀

---

reverse

CCC : head->next = cursor; cursor = head

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

• 將整個 linked list 反轉，並回傳反轉後的 head
• cursor 在每一個 iteration 中，初始都會在原 linked list 中 head 的前一個 node ，next 則永遠是 head 的下一項，並且將 head->next 指向 cursor (反轉的動作)，再將 cursor 指向 head

待補

• Graphviz 圖表優化，表達的不夠好，也畫的好醜…
• pointer to pointer 的相關應用