2025q1 Homework2 (quiz1+2)

contributed by < JUSTUSVMOS >

Week 1 Quiz - Linked List

Week1 Quiz

Quiz 1 - Head Linked List `list_insert_before`

解釋程式碼

1. 線性尋找插入位置

迴圈條件 *p != before：只要目前節點不是欲插入點，就把 p 移到下一個「指標的位址」──亦即 p = &(*p)->next。
若 before 為 NULL，迴圈會跑到最後一個節點的 next 欄位位址，使 p 最終指向「尾端指標」(即目前為 NULL 的那格)。

2. 重寫指標，完成插入（兩步）

*p = item;

把原本指向 before 的指標改成指向新節點 item。

若 p 是 &l->head，這行相當於更新 head。
item->next = before;

將新節點的 next 接回 before。

如果 before == NULL，就讓 item 成為新的尾節點 (next == NULL)。

test_list() 共有三段情境

插入到開頭 (before l.head)

for (i = 0; i < N; i++)
    list_insert_before(&l, l.head, &items[i]);

第一次 l.head == NULL ⇒ 行為相當於 push-front；插入後 head 指向 items[0].
第二次之後，before == l.head ⇒ 新節點不斷插到現行 head 前面，故串列最終逆序 (N-1 … 2 1 0).

插入到結尾 (before NULL)

list_insert_before(&l, NULL, &items[i]);

把 before == NULL 解讀為「附加在尾端」。

由於每次都選擇尾端，最終串列保持順序 (0 1 2 … N-1).

再次驗證尾端插入
與 2 相同，確保重複 reset → re-insert 仍正確、沒有記憶體殘留影響。

在現有的程式碼基礎上，撰寫合併排序操作

// 合併 a 與 b，回傳排序後的 head
static list_item_t* merge_two(list_item_t *a, list_item_t *b) {
    list_item_t *head = NULL;
    list_item_t **ptr = &head;   // ptr 永遠指向「下一條要填入節點的那個指標」

    while (a && b) {
        if (a->value <= b->value) {
            *ptr = a;           // 接上 a
            a = a->next;        // a 前進
        } else {
            *ptr = b;           // 接上 b
            b = b->next;        // b 前進
        }
        ptr = &((*ptr)->next); // ptr 跟著移動到剛接上節點的 next 欄位
    }

    // 其中一邊耗盡，直接把剩下的整串接上
    *ptr = a ? a : b;
    return head;
}

// 其餘遞迴拆半、排序邏輯不變
static list_item_t* merge_sort_rec(list_item_t *head) {
    if (!head || !head->next)
        return head;

    list_item_t *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    list_item_t *mid = slow->next;
    slow->next = NULL;

    return merge_two(merge_sort_rec(head),
                     merge_sort_rec(mid));
}

void list_merge_sort(list_t *l) {
    l->head = merge_sort_rec(l->head);
}

Week 1 Quiz 2 - Binary Search Tree

解釋程式碼

在二元搜尋樹（Binary Search Tree，BST）中，某個節點 x 的 predecessor（前驅）指的是「在中序（左→根→右）遍歷中，緊接在 x 之前的那個節點」。換句話說，它是所有小於 x->key 節點中，鍵值最大的那一個。

如何找前驅

假設我們要找節點 x 的前驅，主要有兩種情況：

左子樹非空
- 前驅就是 x 左子樹中的最大節點。
- 作法：從 x->left 開始，一直往右走到不能再右→即為前驅。
左子樹為空
- 這時候前驅必定在 x 的祖先節點中。
- 作法：沿著父指標（或用遞迴／棧模擬）往上走，直到某個節點 p 滿足：
  - 你剛從 p->right 走進 p（也就是 x 在 p 的右子樹裡）。
  - 那麼 p 就是前驅。
- 若一路走到根都沒找到，代表 x 是整棵樹中最小的節點，沒有前驅。

範例

      20
     /  \
   10    30
   / \     \
  5  15     40
       \
        17

前驅(20)
- 左子樹非空 → 在子樹 10–15–17 中找最大 → 17
前驅(10)
- 左子樹非空 → 在子樹 5 中最大 → 5
前驅(5)
- 左子樹空，向上看：5 是 10 的左子節點 → 繼續往上，到 20…都不是從右子樹來 → 無前驅
前驅(30)
- 左子樹空，向上看：30 是 20 的右子 → 前驅就是 20

remove_free_tree 的運作步驟

定位到要刪除的節點指標
```
block_t **node_ptr = find_free_tree(root, target);
```
node_ptr 指向「指向目標節點的那個指標」（pointer-to-pointer），方便後面直接改寫它。
如果有兩個子節點
- 必須找一個「替身」來頂替自己，常用中序前驅 (in-order predecessor)。
- 前驅定義：左子樹裡最大的那個 → 往左一次，再一路往右跑到底。
- 有了 pred_ptr 指向前驅節點的指標之後，分兩種情況：

前驅就是左子節點

```c
if (*pred_ptr == (*node_ptr)->l) {
    block_t *old_right = (*node_ptr)->r;
    *node_ptr = *pred_ptr;        // 左子節點取代自己
    (*node_ptr)->r = old_right;   // 接回原本的右子樹
}
```

前驅在更深處

```c
else {
    block_t *old_left  = (*node_ptr)->l;
    block_t *old_right = (*node_ptr)->r;
    block_t *pred_node = *pred_ptr;

    remove_free_tree(&old_left, *pred_ptr);
    *node_ptr = pred_node;        // 用前驅頂替自己
    (*node_ptr)->l = old_left;    // 接回拆掉的左子樹
    (*node_ptr)->r = old_right;   // 接回原本的右子樹
}
```

只有一邊子節點或沒有子節點

else if ((*node_ptr)->l || (*node_ptr)->r) {
    *node_ptr = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
} else {
    *node_ptr = NULL;
}

－若只有一個子節點，就讓它直接頂上來；若都沒有，直接把指標設 NULL。

清理原目標節點指標
```
target->l = target->r = NULL;
```
避免外面還留著懸空指標。

為什麼要找左子樹最右邊？

前驅要比 target->size 小（必在左子樹），又要是所有小於它之中「最大的」。
在 BST 上，左子樹的每個節點都小於根，而最右邊的那個正是最大值，所以往右跑到底就對了。

整段程式利用 pointer-to-pointer 技巧，將各種指標重連都改寫在 *node_ptr 或 *pred_ptr 上，免去處處判頭尾、記前驅父節點等繁瑣分支。

嘗試補完程式碼，使其可獨立執行

find_free_tree 在二元搜尋樹中找到大於或等於 target 值的最小節點，並返回指向該節點的指標。

block_t **find_free_tree(block_t **root, block_t *target)
{
    if (!(*root))
        return root;

    if ((*root)->size >= target->size) {
        block_t **left = find_free_tree(&(*root)->l, target);
        return (*left) ? left : root;
    }

    return find_free_tree(&(*root)->r, target);
}

print_tree採用中序遍歷 (in-order traversal) 來印出整棵二元搜尋樹（BST），順序為：

先走左子樹 -> 印出當前節點 -> 再走右子樹

void print_tree(block_t *root) {
    if (!root)
        return;
    print_tree(root->l);
    printf("%zu ", root->size);
    print_tree(root->r);
}

測試主程式 main ：建樹、刪除並列印每次結果

int main() {
    block_t *root = NULL;

    // 插入順序：產生值為 (i * 3) % 10 的節點，確保亂中有序且不重複
    for (int i = 0; i < 10; i++) {
        insert_tree(&root, (i * 3) % 10);
    }

    print_tree(root);
    puts("");  // 印出初始樹狀結構

    // 刪除順序：依序以 (i * 4) % 10 模擬實際記憶體釋放情境
    block_t dummy;
    for (int i = 0; i < 10; i++) {
        dummy.size = (i * 4) % 10;
        remove_free_tree(&root, &dummy);
        print_tree(root);
        puts("");  // 每次刪除後印出目前 BST 結構
    }

    return 0;
}

2025q1 Homework2 (quiz1+2)

Week 1 Quiz - Linked List

Quiz 1 - Head Linked List list_insert_before

解釋程式碼

在現有的程式碼基礎上，撰寫合併排序操作

Week 1 Quiz 2 - Binary Search Tree

解釋程式碼

嘗試補完程式碼，使其可獨立執行

Read more

2025q1 Homework1 (lab0)

2025q1 Homework5 (assessment)

2025q1 Homework1 (ideas)

2025q1 Homework1 (ideas)

Quiz 1 - Head Linked List `list_insert_before`