2020q3 Homework1 (quiz1)

contributed by< JimmyLiu0530 >

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

• Linked list 測驗題目

測驗1: singly linked list

題目給定 linked list 結構定義為:

typedef struct __node {                   
    int value;
    struct __node *next;
} node_t;

且已知不存在 circular (環狀結構) 情況下，對單向 linked list 進行操作

圖例:

原始測驗題的思考及理解

• add_entry

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

程式碼如下:

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

核心觀念: 找到整串 linked list 的尾巴，將它指向新增的節點

運作原理如下:

1. 第3行 建立一個指向 head 的指標 indirect ( pointer to pointer )

2. 第5-7行 配置一個 node_t 的空間，並初始化
3. 第9行 應選 assert(new_node)，用來檢查new_node是否合法
4. 第10-11行 用來找到 linked list 的最後一個 node。下圖展示第一圈 while 後的結果，以此類推

5. 第12行 應選*indirect = new_node，把最後一個 node 的 next 指向 new_node，增加節點完成

Note

• -> 的執行順位大於 & ，所以要先進行 -> 運算再運算 &

• remove_entry

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

程式碼如下:

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. 第3行 建立一個指向 head 的指標 indirect ( pointer to pointer )

2. 第5-6行 找到欲刪除的節點 entry

3. 第8行 繞過 entry，也就是說把 entry 的上一個節點改指向 entry 的下一個節點

4. 第9行 釋放 entry 的記憶體資源

• swap_pair

交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 1->2->3->4，則該回傳 2->1->4->3

程式碼如下:

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

核心觀念: 倆倆一組，相關指標做改變

運作原理如下:

1. 第3行 for 條件 應選 node = &(*node)->next->next，因為此 function 為兩兩交換，因此下一輪 node pointer 應指向目前這對的尾，如下所示:

2. 第4行 建立一個 tmp 指向該對的頭，如下所示:

3. 第5行 應選 *node = (*node)->next，使 head 改指向該對的尾(e.g. node2)，如下所示:

4. 第6行 該對的頭 (e.g. node1) 的 next 改指向下一對的頭 (e.g. node3)，如下所示:

5. 第7行 該對的尾 (e.g. node2) 的 next 改指向頭 (e.g. node1)，如下所示:

6. 之後依此類推…直到交換結束，或是只剩沒成對的node。最後 return 交換後整個 linked list 的頭

• reverse

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

程式碼如下:

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

核心觀念: 將 cursor 視為指向 head 的前一個節點，next 視為指向 head 的後一個節點。不斷更新(往後挪)三個指標 cursor、head、next直到 linked list 的尾巴

運作原理如下:

1. 第5行 創建一個指標 next 指向目前 head 所指的節點的下一個節點。如圖 next 指向 node2

2. 第6行 應選 head->next = cursor; cursor = head ，如圖先將 head->next (i.e. node1) 指向 cursor 指的 NULL，再將 cursor 指向 head

3. 第7行 將 head 指標往後挪一個節點，如圖 head 從指向 node1 變成 node2

延伸問題

1.避免回傳指標的函式 swap_pair_revised & reverse_revised

說明: 利用指標的指標對 swap_pair 及 reverse 兩函式做改寫，來達到不需回傳整串 linked list 的 head

• swap_pair_revised

程式碼如下:

void swap_pair_revised(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;
    }
}

主程式呼叫:
swap_pair_revised(&head);

運作原理如下:

1. 與函式 swap_pair 只有傳入 parameter 的方式不同，差別在於 swap_pair 採 pass by value 的方法；而 swap_pair_revised 則是採 pass by reference 的方法。有關 pass by value 跟 reference 的詳細解說，可到 Pass by value vs Pass by reference 觀看

• reverse_revised

程式碼如下:

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

主程式呼叫:
reverse_revised(&head);

運作原理如下:

1. 與原函式概念一樣，只是改採用 pass by reference 的方法，因此一些相對應的變數(e.g. while 的條件從 head 改成 *indirect)也須做修改
2. 第10行 最後再把新的 linked list 頭的位置 assign 到 head (i.e. *indirect) 去

2. 以遞迴改寫 reverse 函式

首先，建立遞迴演算法有幾個重點: (a) 終止條件 (b) 將原問題變成與其相似且規模較小的問題

程式碼如下:

node_t *rev_recursive(node_t *p)
{
    if(p->next == NULL)
    {
        return p; 
    }
    node_t *head = rev_recursive(p->next);
    node_t *q = p->next;
    q->next = p;
    p->next = NULL;
    return head;
}

主程式呼叫:
head = rev_recursive(head);

運作原理如下:

1. 第3-6行 即為終止條件。if 條件若成立，代表 p 為此 linked list 的最後一個節點，也就是新的 head，因此回傳該位址
2. 第7行 遞迴呼叫 rev_recursive()，並將新的 head 記錄下來
3. 第8-10行 舉例來說，假設 p 指向 node2，則 q 指向 node3。經過這幾行的處理後，第一張圖會變成第二張圖，也就是 node3->next 指向 node2，且 node2->next 指向 NULL

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

什麼是 Fisher–Yates shuffle?

用來將一個有限集合生成一個隨機排列的方法，簡單來說，該算法可以洗牌序列。該算法產生無偏頗的排列，代表每種排列的可能性均等。

程式碼如下

// this swap function is under the premise that
// 1 <= p <= q <= total number of node in the linked list
// and is used to swap pth and qth node in the linked list

void swap(node_t **head, int p, int q)
{
    // nothing to do if p,q are the same
    if(p == q)
        return;
    
    // search for pth node in the linked list
    node_t *prevP = NULL, *currP = *head;
    for(int i = p-1; i>0; i--)
    {
        prevP = currP;
        currP = currP->next;
    }
    
    // search for qth node in the linked list
    node_t *prevQ = NULL, *currQ = *head;
    for(int i = q-1; i>0; i--)
    {
        prevQ = currQ;
        currQ = currQ->next;
    }
    // if pth node is head of linked list, i.e. p==1, make qth node a new head
    if (p==1)
        *head = currQ;
    else
        prevP->next = currQ;
    
    // if q is 1, p must be 1 either, the process will return due to line7
    prevQ->next = currP;
    
    // swap next pointers
    node_t *tmp = currQ->next;
    currQ->next = currP->next;
    currP->next = tmp;
}

void Fisher_Yates_shuffle(node_t **indirect)
{
    // count how many nodes are in linked list
    int totalNum = 0;
    node_t *tmp = *indirect;
    while(tmp)
    {
        totalNum += 1;
        tmp = tmp->next;
    }
    
    srand(time(NULL));
    
    // start from the first node and randomly choose a number q s.t. p<=q<=totalNum 
    for(int p = 1; p <= totalNum-1; p++)
    {
        int q = (rand() % (totalNum-p+1))+p;
        
        swap(indirect, p, q);
    }   
}

主程式呼叫:
Fisher_Yates_shuffle(&head);

運作原理如下:

1. 先說明 swap 函式，主要將第 p 跟第 q 個節點交換
   第11-24行 先找到第 p 跟第 q 個節點的位置，並記錄在 currP 及 currQ， prevP 跟 prevQ 則分別記錄 currP 及 currQ 的前一個節點

   第26-27行 需考慮 p==1 的情況，也就是第 p 個節點是 head

   第33行 之所以這裡不用 if-else 是因為在給定的前提中，1 <= p <= q。當 q=1 時，
   p 勢必也是 1 ，因此會在 line 8 retrun 掉了

   第36-38行 做一些 next pointer 的交換

2. 此 swap 函式因為是 linked list，所以不像 array 在給定第 p 跟第 q 個元素做交換下可在O(1)完成，需

   $O(n)$。

3. 接著看 Fisher_Yates_shuffle 函式，此函式精神在於在第 p 輪中，會隨機找一個介於 p 跟總節點數的數字 q，並將第 p 跟第 q 個交換
   第44-50行 計算 linked list 的總節點數
   第55-60行 從 linked list 的第一個節點開始，在之間隨機找一個節點做交換，再來換第二個節點…以此類推，一直重複做到倒數第二個節點

4. 此Fisher_Yates_shuffle 函式的時間複雜度為

   $O(n^2)$，但空間複雜度只需
   $O(1)$。