HackMD
2025q1 Homework2 (quiz1+2)
contributed by < TonyLinX >
2025q1 第 1 週測驗題
測驗 1
這段程式碼定義單向 linklist 的 node 以及串列整個 linklist 的 list_t :
#include <stddef.h>
typedef struct list_item {
int value;
struct list_item *next;
} list_item_t;
typedef struct {
struct list_item *head;
} list_t;
測試函式 list_insert_before
這個函式的功能是在指定的 before 節點前插入新的 node，並且會遍歷 linklist 來找到 before 節點的位置。
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
先來討論另個想法，實際上如果只是要遍歷整個 linklist 不需要 **p，只需要 *p，因為只要創建一個指向 list_item_t 的指標並讓它指向 l->head，並一路透過 next 即可往後遍歷。
void list_traverse(list_t *l) {
list_item_t *p = l->head;
while (p != NULL) {
printf("%d\n", p->value);
p = p->next;
}
}
那為什麼我們需要雙重指標 (**p)，因為我們要修改結構，如果說是單指標就會在 p = item 的地方出問題。因為 p 本身是局部變數，p = item 只是讓 p 去指向另個位址，但是整個 linklist 結構並不會改變，所以說我們需要 **p。
void list_insert_before(list_t *l, list_item_t *before, list_item_t *item) {
list_item_t *p;
for (p = l->head; p != before; p = p->next)
;
p = item;
item->next = before;
}
假設鏈結串列是：head -> A -> B -> C -> NULL，而 before 是 B，你想在 B 前插入 item，目標是讓鏈結串列變成：head -> A -> item -> B -> C -> NULL。
list_insert_before 的流程會先透過 for loop 尋找到 before 前面的節點，所以先初始化 p 為 l->head 的地址，然後比對 (*p) 是否為 before，如果不是 before 就往下一個節點移動， p = &(*p)->next 中的 *p 代表的是指向某一個 node 的指標，所以我們可以用他的成員 next 進行移動。 當遇到 before 時，p為 A->next 的地址，所以 *p 就是 A->next，那我們就可以透過 *p = item 插入 item，最後再讓 item 的 next 指向 before 就可完成這個 linklist。
void list_insert_before(list_t *l,
list_item_t *before,
list_item_t *item)
{
list_item_t **p;
for (p = &l->head; *p != before; p = &(*p)->next)
;
*p = item;
item->next = before;
}
詳細步驟
- 初始化:
p = l->head，所以p指向A（地址0x1000）。 - 迴圈執行：
- 第一次：
*p != before（0x1000 != 0x2000），p = &((*p)->next)：*p是A（0x1000），(*p)->next是A->next，也就是B（0x2000）。&((*p)->next)是A->next的地址（假設是0x1004，因為next是A結構中的成員）。- 所以
p更新為&A->next（0x1004）。
- 第二次：
*p == before（0x2000 == 0x2000），條件不成立，離開迴圈。 - 結果：迴圈結束時，
p指向A->next的地址（0x1004）。 *p = item：p是&A->next（0x1004），*p是A->next的值（原本是0x2000，指向B）。*p = item把A->next修改成item的地址（0x4000）。- 現在：
l->head -> A -> item，鏈結串列結構改變了！
item->next = before：item->next被設為B（0x2000）。- 結果：
l->head -> A -> item -> B -> C，插入成功！
- 第一次：
撰寫合併排序操作 : Commit 2b418c3
首先，設計 merge sort 的 test case，這邊的設計方式透過 list_insert_before 創建一個 999 -> 998 -> ... -> 0 的 linklist，期望再透過 merge sort 之後可以變成 0 -> 1 -> ... -> 999。而 merge sort 的方式採用 top-down 的方式實現，也就是遞迴的方式。
