contributed by < OscarShiang
>
因為 AA1
位於 add_entry
函式內,且在透過迴圈尋找最後一個節點之前,所以 AA1
是 assert(new_node)
,用以確認 new_node
有成功宣告與配置。
因為 AA2
在 add_entry
的最後,在迴圈迭代找到 linked list 最後一個節點的程式碼後,所以可以知道 AA2
是用以將新的節點連接到 list 上。因此答案是 *indirect = new_node
BB1
位在 swap_pair
中的 for 迴圈每次會更新的部分,所以可以得知其用來移動 node 所指向的位置。而且在該階段目標不是更動 list 中節點連接的方式,因此答案不會是 *node
的選項。再者因為 node
的資料型態是指標的指標,所以答案就會是 node = &(*node)->next->next
而每次更新時都會一次移動兩個節點的原因是因為要確認每次都是可以進行 swap_pair
的狀況
為了更清楚的說明,我以下圖進行示範
假設我們有一個 linked list 如下:
若以深色的節點表示 *node
所指下的位置的話則情況就會是
node
首先跳到 A
的位址
接著將 *node
轉換到 (*node)->next
再來將 A
與 B
兩者的 next
值互換以完成交換
接著利用 for 迴圈更新的部分將 *node
切換到 (*node)->next->next
因為 A
, B
在上一次迴圈中已經交換過了,所以透過一次移動兩個節點的單位跳過已經交換完的節點
而當 *node
切換到 E
的時候
因為 E
的下一個節點不存在,即 (*node)->next == NULL
,則程式會因為不滿足 for 迴圈執行的條件而跳出迴圈,完成 swap_pair
承上題,因為是 swap 的函式,所以可以推論 BB2
的用途應該是將要交換的兩個節點的連結做更動,因為是要更動節點的連結,所以就不是針對 node
本身做操作,而是對 *node
做操作,因此答案就是 *node = (*node)->next
因為 CCC
位在 reverse
函式中,所以我先以圖示來說明其運作的原理
假設我們現在有一個 list(head
的位置以深色表示)
我們首先宣告一個新的指標 cursor
並賦值為 NULL
接著我們將 head
串到 cursor
的前面,則形成一個只有一個節點的新 list,並將 head
換到 B
;cursor
則換到 A
(cursor
所指向節點的以水藍色表示)
我們重複這樣的動作
可以看到在執行迴圈的過程中逐步將 head
各個節點連接到 cursor
所指向的新 list 上,直到 head
所指向的 list 全部連接到 cursor
所指向的 list 上時
cursor
所指向的 list 就會是反轉過後的 list,而這時原本的 head
則已經被改到 NULL
值,因此我們將 cursor
作為新的 head
return 回去讓其他程式可以將 head
的數值進行更新。
而因爲 CCC
在其中扮演的作用是將 head
原本的節點接在 cursor
之前,所以答案就會是 head->next = cursor; cursor = head
swap_pair
與 reverse
原本 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
的實作如下
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
sysprog2020