Try   HackMD

2020q3 Homework1 (quiz1)

tags: sysprog2020 homework

contributed by <JKChun>

程式運作原理

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 ,並指派 headindirect






graphname



A

head_node



B

node_2



A->B





C

node_3



B->C





NULL1
NULL



C->NULL1





indirect
**indrect



head_pointer
head_pointer



indirect->head_pointer:n





head
**head



head->head_pointer:n





head_pointer->A





  • 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 ,並指派 headindirect
  • 第2到3行 此部分是要將 indirect 指向 entry node 前一個 node 的 next






%0



node_1

head

1

 



node_2

node_2

2

 



node_1:c->node_2:ptr






node_3

entry

3

 



node_2:c->node_3:ptr






node_4

node_4

4

 



node_3:c->node_4:ptr






NULL1
NULL



node_4:c->NULL1






head
**head



head_pointer
head_pointer



head->head_pointer:n





indirect
**indirect



indirect->node_2:ref





head_pointer->node_1:ptr





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






%0



node_1

head

1

 



node_2

node_2

2

 



node_1:c->node_2:ptr






node_4

node_4

4

 



node_2:c->node_4:ptr






node_3

entry

3

 



node_3:c->node_4:ptr






NULL1
NULL



node_4:c->NULL1






head
**head



head_pointer
head_pointer



head->head_pointer:n





indirect
**indirect



indirect->node_2:ref





head_pointer->node_1:ptr





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






%0



node_1

head

1

 



node_2

node_2

2

 



node_1:c->node_2:ptr






node_4

node_4

4

 



node_2:c->node_4:ptr






NULL1
NULL



node_4:c->NULL1






head
**head



head_pointer
head_pointer



head->head_pointer:n





indirect
**indirect



indirect->node_2:ref





head_pointer->node_1:ptr





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;






%0



node_1

head

1

 



node_2

node_2

2

 



node_1:c->node_2:ptr






node_3

node_3

3

 



node_2:c->node_3:ptr






NULL1
NULL



node_3:c->NULL1






head
*head



head->node_1:n





node_p
**node



node_p->head





temp
*temp



temp->node_1:n





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







%0



node_1

head

1

 



node_2

node_2

2

 



node_1:c->node_2:ptr






node_3

node_3

3

 



node_2:c->node_3:ptr






NULL1
NULL



node_3:c->NULL1






head
*head



head->node_2:ptr





node_p
**node



node_p->head





temp
*temp



temp->node_1:ptr





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







%0



node_1

head

1

 



node_3

node_3

3

 



node_1:c->node_3:ptr






node_2

node_2

2

 



node_2:c->node_3:ptr






NULL1
NULL



node_3:c->NULL1






head
*head



head->node_2:ptr





node_p
**node



node_p->head





temp
*temp



temp->node_1:n





(*node)->next = tmp;







%0



node_1

head

1

 



node_3

node_3

3

 



node_1:c->node_3:ptr






node_2

node_2

2

 



node_2:c->node_1:ptr






NULL1
NULL



node_3:c->NULL1






head
*head



head->node_2:ptr





node_p
**node



node_p->head





temp
*temp



temp->node_1:ptr





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







%0



node_1

head

1

 



node_3

node_3

3

 



node_1:c->node_3:ptr






node_2

node_2

2

 



node_2:c->node_1:ptr






NULL1
NULL



node_3:c->NULL1






head
*head



head->node_2:ptr





node_p
**node



node_p->node_1:ref





temp
*temp



temp->node_1:ptr





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






%0



node_1

head

1

 



node_2

node_2

2

 



node_1:c->node_2:ptr






node_3

node_3

3

 



node_2:c->node_3:ptr






NULL1
NULL



node_3:c->NULL1






head
*head



head->node_1:n





cursor
cursor



NULL2
NULL



cursor->NULL2





node_t *next = head->next;







%0



node_1

head

1

 



node_2

node_2

2

 



node_1:c->node_2:n






node_3

node_3

3

 



node_2:c->node_3:ptr






NULL1
NULL



node_3:c->NULL1






head
*head



head->node_1:ptr





cursor
cursor



NULL2
NULL



cursor->NULL2





next
*next



next->node_2:ptr





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







%0



node_1

head

1

 



NULL2
NULL



node_1:c->NULL2:n






node_2

node_2

2

 



node_3

node_3

3

 



node_2:c->node_3:ptr






NULL1
NULL



node_3:c->NULL1






head
*head



head->node_1:ptr





cursor
cursor



cursor->node_1:ptr





next
*next



next->node_2:ptr





head = next;







%0



node_1

head

1

 



NULL2
NULL



node_1:c->NULL2:n






node_2

node_2

2

 



node_3

node_3

3

 



node_2:c->node_3:ptr






NULL1
NULL



node_3:c->NULL1






head
*head



head->node_2:ptr





cursor
cursor



cursor->node_1:ptr





next
*next



next->node_2:ptr





  • 程式的思路是:
    • 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_pairreverse

函式 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 指標







%0



node_1

A

1

 



node_2

B

2

 



node_1:c->node_2:ptr






node_3

C

3

 



node_2:c->node_3:ptr






NULL1
NULL



node_3:c->NULL1






head
*head



head->node_1:ptr





oh1
*original_head_1



oh1->node_1:ptr





oh2
*original_head_2



oh2->node_2:ptr





oh3
*original_head_3( rev_ head )



oh3->node_3:ptr





實作 Fisher–Yates shuffle

針對 singly-linked list 的節點,實作 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;