2020q3 Homework1 (quiz1)

tags: sysprog2020 homework

contributed by <JKChun>

• Linked List 2020q3 第一周測驗題連結
• 繳交作業區

程式運作原理

Function 1 : add_entry

• Function 的功能為：

新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy

• Source Code：

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

• Function 的 input 為指向 node 的指標的指標 head 和一個整數型別的變數new_value
• 第1行 建立一個指向 node 的指標的指標 indirect ，並指派 head 給indirect

• 2到4行 用 malloc 分配記憶體空間給 new_node，並指派 new value 以及指向 NULL
• AA1 assert(new_node) 確定 new_node 有成功建立
• 6到7行 讓indriect指向 linked_list 最後一個節點的 next
• AA2 *indirect = new_node 最後將 new_node 指派給 next ，讓 new_node 變成 linked_list 的最後一個 node

Function 2 : remove_entry

• Function 的功能為：

移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)

• Source Code：

void remove_entry(node_t **head, node_t *entry)
{
    node_t **indirect = head;

    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    *indirect = entry->next;
    free(entry);
}

• 第1行 建立一個指向 node 的指標的指標 indirect ，並指派 head 給 indirect
• 第2到3行 此部分是要將 indirect 指向 entry node 前一個 node 的 next

• 第4行 利用 indirect 更改 entry node 前一個 node 的 next ，讓它直接指向 entry node 的下一個 node

• 第5行 用 free 釋放 entry 占用的記憶體

Function 3 : swap_pair

• Function 的功能為：

交換一對相鄰的節點，給定 1->2->3->4，則該回傳 2->1->4->3

• Source Code：

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

• 此 function 的功能就是把 linked list 裡的 node 按照順序兩兩一組，把順序反過來，所以　for 迴圈 的判斷條件很簡單，就是沒有成對的 node 就跳出迴圈
• 也因為是一次操作兩個 node ，所以 BB1 一次跳過兩個 node
• 和一般的 swap function 思維一樣，在 for 迴圈 裡先額外建一個 temp 指標
• 流程如下：　
  node_t *tmp = *node;

*node = (*node)->next; (#BB2)

tmp->next = (*node)->next;

(*node)->next = tmp;

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

• 讓**node 指向第一個 node 的 next　，這樣做的話，假如有第四個 node ，就可以像上面操作 *head 一樣，讓 head node 的 next 可以指向第四個 node
• 最後跳出 for 迴圈 並回傳 head

Function 4 : reverse

• Function 的功能為：

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

• Source Code：

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

• 流程如下：　
  node_t *cursor = NULL;

node_t *next = head->next;

head->next = cursor; cursor = head; (#CCC)

head = next;

• 程式的思路是：
  • 讓 cursor 指向 *head 指向的 node 在反轉後要指向的地方，拿上面舉例，head->node_2->node_3 ，在反轉後 head node 應該要指向 NULL ，所以一開始 cursor 為指向 NULL 的 pointer ，接著讓 head->next = cursor ，再讓 cursor 指向 head node ，因為 head node 是下一個 node node_2 要指向的 node
  • 讓 *head 指向 自己原本指向的 node 再下一個順位的 node 也就是 node_2
  • 一直重複循環到 *head 指向 NULL ，然後回傳 cursor 結束

改寫 swap_pair 和 reverse

函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = … 的更新，請用指標的指標來改寫，並避免回傳指標;

改寫 swap_pair

• 原本的 code：

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

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

• 原本的 code 本來就會將原本指向 head node 的指標指向第二個 node (前面解釋 swap_pair 時有畫出圖)， 所以改成 pass by reference 的方式就不必回傳 head pointer 了

改寫 reverse

• 原本的 code：

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

• pointer to pointer 版：

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

reverse recursive 版

• reverse function

void reverse(node_t **head)
{
    *head = rev_recursive( *head )
}

• recursive function

node_t *rev_recursive( node_t *original_head )
{
    if( original_head == NULL )
        return NULL;
    if( original_head->next == NULL )
        return original_head;
    
    node_t *rev_head = rev_recursive( original_head->next );
    original_head->next->next = original_head;
    original_head->next = NULL;
    return rev_head;
}

recursive function 裡的：

if( original_head == NULL )
    return NULL;
if( original_head->next == NULL )
    return original_head;
node_t *rev_head = rev_recursive( original_head- >next );
return rev_head;

是用來找到指向 linked list 最後一個 node 的指標並不停的回傳，到最後的 reverse function 更新 head 指標
假設有3個 node ，程式會呼叫3次 recursive function

1. 第3次的 recursive function 回傳 C node 的指標( rev_head )
2. 第2次的 recursive function 運用 original_head_2 讓 C 指向 B，B 指向 NULL　，回傳 C node 的指標
3. 第1次的 recursive function 運用 original_head_1 讓 B 指向 A，A 指向 NULL　，回傳 C node 的指標

最後的 reverse function 更新 head 指標

實作 Fisher–Yates shuffle

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

• 演算法：(節自維基百科 Fisher–Yates shuffle)

To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

void Shuffle( node_t **head ){
    
    // count the number of node in the list
    int num_of_node = 0;
    node_t *indirect = *head;
    while (indirect){
        num_of_node++;
        indirect = indirect -> next;
    }
    
    srand ( time(NULL) );
    
    node_t *cursor = *head;
    node_t *prev_cursor = NULL;
    node_t *prev_indirect = NULL;
    indirect = *head;
    // Fisher–Yates shuffle
    for(;num_of_node > 1; --num_of_node){
    
        prev_cursor = NULL;
        cursor = head;
        prev_indirect = NULL;
        indirect = head;
        
        // move cursor and indirect pointers to the node to be changed
        // move prev_cursor and prev_indirect pointers to the previous node of 
        // node to be changed
        for(int i = rand() % num_of_node; i > 1; --i){  
            prev_cursor = cursor;
            cursor = cursor -> next; 
        }
        
        for(int i = num_of_node; i > 1; --i){
            prev_indirect = indirect;
            indirect = indirect -> next;  
        }
        
        // down below is swapping two node
        if (prev_cursor != NULL)  
            prev_cursor->next = indirect;  
        else   
            *head = indirect;  
    
        prev_indirect->next = cursor;  
  
        // Swap next pointers  
        Node *temp = indirect->next;  
        indirect->next = cursor->next;  
        cursor->next = temp;  
    }
}

• 用了5個 pointer
• 處理是 head node 要交換的情況

    // down below is swapping two node
    if (prev_cursor != NULL)  
        prev_cursor->next = indirect;  
    else   
        *head = indirect;