2020q3 Homework1 (quiz1)

contributed by < sammer1107 >

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

• 2020q3 Homework1 (quiz1)
  • AA1 & AA2
    • 程式理解
    • AA1
    • AA2
  • BB1 & BB2
    • BB1
    • BB2
  • CCC
    • 第1次進迴圈的情況(57行)
    • 第2次進迴圈的情況(57行)
    • 結束時
  • 延伸問題 2
    • swap_pair 的 pointer to pointer 版本
    • reverse 的 pointer to pointer 版本
  • 延伸問題 3 - recursive reverse
    • 程式解說
  • 延伸問題 4 - Fisher-Yates Shuffle
    • 程式解說

AA1 & AA2

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;

    AA1;
    while (*indirect)
        indirect = &(*indirect)->next;
    AA2;
}

程式理解

1. 13~15 行的地方我們已經要了新的記憶體，並在上面放入了新的值
2. 18~19 行的目的是要找到最後一個節點(當 next 為 NULL)

AA1

根據上面的理解，AA1 不應該是 *indirect = new_node，否則迴圈執行的結果永遠都是得到 NULL 後結束。因此 AA1 應是 assert(new_node)，檢查是否正確取得記憶體。

AA2

找到最後一個節點後，需要將最後的 next 指標指向 new_node。迴圈結束時，*indirect相當於最後一個節點的 next ，故答案為 *indirect = new_node。

BB1 & BB2

node_t *swap_pair(node_t *head)
{
    for (node_t **node = &head; *node && (*node)->next; BB1) {
        node_t *tmp = *node;
        BB2;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
    return head;
}

BB1

1. swap_pair 的功能為兩兩掉換，故 BB1 的功能是要連跳兩個 node。
2. 而且這裡我們是要改變 node 指向的位置而不是要修改 List 連接，故等號左邊要是 node 而不是 *node。
3. (a) 不對因為 next 的 type 為 node_t* ，故要再取址才是我們要的。

答案為 (e) node = &(*node)->next->next

BB2

1. 在迴圈內我們要完成交換 Node 的工作，經過第 4 行後
   ​​​​    node_t *tmp = *node;
   

   指標們長這樣，node1 與 node2 為目前要 swap 的節點。… 則代表前後延伸的節點

   這樣表示 node 為指向前一節點的 next 的指標，tmp 則為指向第1節點的指標。

2. 要把 node2 往前移的第一個動作就是把前一個節點的 next 牽往 node2。做完後長這樣
   這裡我們要修改的是前一個 node 的 next 讓他指向 node2 ，故等號左邊應是 *node，而 node2 的位置為 (*node)->next (等於 node1 的 next )。故答案選 (e)
3. 下一行將後面的節點交手從 node2 交手給 node1。
   ​​​​tmp->next = (*node)->next;
   

   做完後長這樣
4. 最後將 node1 接在 node2 後面就完成了
   ​​​​(*node)->next = tmp;
   

   完成圖

CCC

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

要 reverse linked list 我們需要兩個指標一前一後走到底，而 cursor 在這裡就是跟在 head 之後的指標。故選項要選 (b)head->next = cursor; cursor = head
，把 head 的 next 改為指向前一個節點，然後 cursor 和 head 各往前走一步。

第1次進迴圈的情況(57行)

做完 head->next = cursor 後

cursor = head 後 head=next出回圈的樣子

第2次進迴圈的情況(57行)

做完 head->next = cursor 後

然後移動指標

之後依此類推

結束時

結束時 head 到達最尾端的 NULL，cursor 則指向最後的節點，也就是新的頭，所以回傳 cursor。

延伸問題 2

swap_pair 的 pointer to pointer 版本

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

程式碼原理一致，再開頭時新的運作方式變成:

括號 head 代表在 main 中的 head。

1. 第5行
2. 第 6 行
3. 第 7 行
4. 第8行

head 在這裡很自然的指向了新的頭，所以完全不需要新增程式碼來處理這部份。

reverse 的 pointer to pointer 版本

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

這個版本沒做什麼修改，只要將 head 都換成 *head 即可，回傳的動作則改成直接設定 *head。

延伸問題 3 - recursive reverse

node_t *reverse_recursive(node_t *head)
{   
    if(!head || !head->next){
        return head;
    }
    node_t *rev_head = reverse_recursive(head->next);
    head->next->next = head;
    head->next = NULL;
    return rev_head;
}

void reverse(node_t **head)
{
    *head = reverse_recursive(*head);
}

程式解說

reverse

此函式是為了包裝 reverse 的呼叫成指標的型式，並會完成最後修改頭的動作。

reverse_recursive

1. 此函式把 linked list 拆成第一個節點以及後面整串，然後遞迴呼叫翻轉後面整串。

2. 後面翻轉完後回傳的是後面那串新的頭。

3. 再來

   ​​​​    head->next->next = head;
   

   目的是要教第一個節點接回到尾巴。

   最後再把尾巴的 next 設為 NULL:

   ​​​​    head->next = NULL;
   

   做完就變

   回傳 rev_head 就完成了翻轉的動作。

延伸問題 4 - Fisher-Yates Shuffle

void shuffle(node_t **head){
    node_t *old_head, *cursor, **indirect;
    int range = 0;
    old_head = cursor = *head;
    // get list length
    while(cursor){
        range += 1;
        cursor = cursor->next;
    }
    // starts Fisher-Yates
    *head = NULL;
    for(;range > 0; --range){
        indirect = &old_head;
        // move to selected node
        for(int i = rand() % range;
            i > 0; --i){
            indirect = &(*indirect)->next;
        }
        // move selected node to new list
        node_t *tmp = *indirect; // holds the node to move
        *indirect = (*indirect)->next; // skip the node to move
        tmp->next = *head; // move the node to the head of new list
        *head = tmp;
    }
}

程式解說

• 6~8: 得到 list 長度，後面 Fisher-Yates 要用
• 11: *head 作為新的 list 的頭
• 12: Fisher-Yates Shuffle 的迴圈，出迴圈後就完成搬運所有節點了。head也將變成新的 list。
• 15~17: 取得隨機數然後找到第 i 個節點
• 20~23: 將這個節點從舊 list 移到新 list 的頭