Try   HackMD

2020q3 Homework1 (quiz1)

contributed by < OscarShiang >

作業要求

Quiz 1

AA1

因為 AA1 位於 add_entry 函式內,且在透過迴圈尋找最後一個節點之前,所以 AA1assert(new_node) ,用以確認 new_node 有成功宣告與配置。

AA2

因為 AA2add_entry 的最後,在迴圈迭代找到 linked list 最後一個節點的程式碼後,所以可以知道 AA2 是用以將新的節點連接到 list 上。因此答案是 *indirect = new_node







G



A

A



B

B



A->B





C

C



B->C





D

D



C->D





t

t



D->t


connect



BB1

BB1 位在 swap_pair 中的 for 迴圈每次會更新的部分,所以可以得知其用來移動 node 所指向的位置。而且在該階段目標不是更動 list 中節點連接的方式,因此答案不會是 *node 的選項。再者因為 node 的資料型態是指標的指標,所以答案就會是 node = &(*node)->next->next

而每次更新時都會一次移動兩個節點的原因是因為要確認每次都是可以進行 swap_pair 的狀況

為了更清楚的說明,我以下圖進行示範

假設我們有一個 linked list 如下:







%0



A

A



B

B



A->B





C

C



B->C





D

D



C->D





E

E



D->E





若以深色的節點表示 *node 所指下的位置的話則情況就會是

node 首先跳到 A 的位址







%0



A

A



B

B



A->B





C

C



B->C





D

D



C->D





E

E



D->E





接著將 *node 轉換到 (*node)->next







%0



B

B



C

C



B->C





A

A



A->B





D

D



C->D





E

E



D->E





再來將 AB 兩者的 next 值互換以完成交換







%0



B

B



A

A



B->A





C

C



A->C





D

D



C->D





E

E



D->E





接著利用 for 迴圈更新的部分將 *node 切換到 (*node)->next->next







%0



C

C



D

D



C->D





B

B



A

A



B->A





A->C





E

E



D->E





因為 A, B 在上一次迴圈中已經交換過了,所以透過一次移動兩個節點的單位跳過已經交換完的節點

而當 *node 切換到 E 的時候







%0



E

E



B

B



A

A



B->A





D

D



A->D





C

C



D->C





C->E





因為 E 的下一個節點不存在,即 (*node)->next == NULL,則程式會因為不滿足 for 迴圈執行的條件而跳出迴圈,完成 swap_pair

BB2

承上題,因為是 swap 的函式,所以可以推論 BB2 的用途應該是將要交換的兩個節點的連結做更動,因為是要更動節點的連結,所以就不是針對 node 本身做操作,而是對 *node 做操作,因此答案就是 *node = (*node)->next

CCC

因為 CCC 位在 reverse 函式中,所以我先以圖示來說明其運作的原理

假設我們現在有一個 list(head 的位置以深色表示)







%0



A

A



B

B



A->B





C

C



B->C





D

D



C->D





E

E



D->E





我們首先宣告一個新的指標 cursor 並賦值為 NULL

接著我們將 head 串到 cursor 的前面,則形成一個只有一個節點的新 list,並將 head 換到 Bcursor 則換到 Acursor 所指向節點的以水藍色表示)







%0



A

A



B

B



C

C



B->C





D

D



C->D





E

E



D->E





我們重複這樣的動作







%0



B

B



A

A



B->A





C

C



D

D



C->D





E

E



D->E











%0



C

C



B

B



C->B





D

D



E

E



D->E





A

A



B->A











%0



D

D



C

C



D->C





E

E



B

B



C->B





A

A



B->A





可以看到在執行迴圈的過程中逐步將 head 各個節點連接到 cursor 所指向的新 list 上,直到 head 所指向的 list 全部連接到 cursor 所指向的 list 上時







%0



E

E



D

D



E->D





C

C



D->C





B

B



C->B





A

A



B->A





cursor 所指向的 list 就會是反轉過後的 list,而這時原本的 head 則已經被改到 NULL 值,因此我們將 cursor 作為新的 head return 回去讓其他程式可以將 head 的數值進行更新。

而因爲 CCC 在其中扮演的作用是將 head 原本的節點接在 cursor 之前,所以答案就會是 head->next = cursor; cursor = head

以指標的指標來改寫 swap_pairreverse

swap_pair

原本 swap_pair 的實作如下

node_t *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;
    }
    return head;
}

因為其在迴圈內的操作已經有使用到指標的指標,所以只需要將函式參數的型態做修改,就可以達到互換的同時更改 head 的位置

- node_t *swap_pair(node_t *head)
+ void swap_pair(node_t **head)
 {
-    for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next) {
+    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;
     }
-    return head;
 }

因為我們操作的是指標的指標,所以在更改 head 變數的位址所指向的數值時就可以將 head 所保存的數值做修改,因而減少將新的 head 數值回傳給其他函數的動作。

reverse

reverse 的實作如下

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

我們可以仿造 swap_pair 的方式,以指標的指標來記錄新的 list 第一個節點的位址,並搭配原本 list 的第一個節點 head 來進行操作

void reverse(node_t **indirect)
{
    node_t *curr = *indirect;
    *indirect = NULL;
    while (head) {
        node_t *next = curr->next;
        curr->next = *indirect;
        *indirect = head;
        head = next;
    }
}

透過不斷將 *indirect 的數值改為新 list 的第一個節點的值,我們就可以確保在不回傳新的 head 的狀態下完成整個 list 的反轉與更新 head 的數值了。

實作程式碼

請參考 linked_list.c - GitHub gist

參考資料

  1. 2020q3 第 1 週測驗題
  2. 範例程式碼 (linked_list.c)
tags: sysprog2020