HackMD
2025q1 Homework2(quiz1+2)
contribute by dingsen-Greenhorn
Week1_Quiz
測驗1-1
首先定義要用到的程式
#include <stddef.h>
typedef struct list_item {
int value;
struct list_item *next;
} list_item_t;
typedef struct {
struct list_item *head;
} list_t;
參考示意圖如下：
- 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
此處實做 list_insert_before
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;
}
list_insert_before在單向鏈結串鏈中，在指定節點的前面插入新節點
而迴圈中，讓 p 持續向右移動，當 *p == before 時，代表此時 **p 是指向前一個節點的 *next 也就是停止處。再讓 item->next 指向 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
假設我們有一個鏈結串列，如下所示：
head -> 0 -> 1 -> 2 -> 3 -> NULL
我們要在節點 2 之前插入一個新節點 99。
初始化指標 p：p 開始指向 head。
遍歷鏈結串列：p 依次指向節點 0, 1, 2，直到找到要插入的位（2）。
插入節點 99：當 p 指向節點 2 時，我們將 99 插入到它之前，將 p 指向 99，並將 99->next 指向原來的節點 2。
結果會變成：
head -> 0 -> 1 -> 99 -> 2 -> 3 -> NULL
這樣，99 節點就被成功插入到 2 節點之前了。
在現有的程式碼基礎上，撰寫合併排序操作
測驗1-2
現在我們刪除 30：
[50]
/ \
[30]* [70]
/ \ / \
[20] [40] [60] [80]
步驟 1：找到 30
使用 find_free_tree(&root, 30)：
block_t **find_free_tree(block_t **root, block_t *target) {
block_t **current = root;
while (*current) {
if (*current == target) {
return current; // 找到目標，返回指標
} else if (target->size < (*current)->size) {
current = &((*current)->l); // 向左子樹搜尋
} else {
current = &((*current)->r); // 向右子樹搜尋
}
}
return NULL; // 沒找到
}
延續以上的例子說明：
target = 30
current = &root（指向 50）
30 < 50，往左走 → current = &(50->l)（指向 30）
找到 30，返回 &(50->l)
步驟 2：刪除 30
if ((*node_ptr)->l && (*node_ptr)->r)
若 target 節點同時有左、右子樹，則：
找到「中序前驅 (in-order predecessor)」，即左子樹中最大的節點。用這個前驅節點來取代 target。
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r != NULL)
pred_ptr = pred_ptr = &(*pred_ptr)->r;
30 有兩個子節點 (20 和 40)，所以需要找到 前驅節點（左子樹的最大值）。20 是 30 的左子樹，20 沒有右子節點，因此 20 就是 30 的前驅。
步驟 3：用 20 取代 30
20 取代 30
40（原本 30 的右子節點）保持不變
刪除原本的 20 節點
[50]
/ \
[20] [70]
\ / \
[40] [60] [80]
30 成功被刪除，BST 結構仍然有效！
target 的前驅更深（在左子樹更深處）
當 target 左子樹更深時，我們需要找到左子樹最右側的節點：
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);
/* 用前驅來替換 target */
*node_ptr = pred_node;
(*node_ptr)->l = old_left;
(*node_ptr)->r = old_right;
}
範例 （前驅節點更深）：
[50]
/ \
[30] [70]
/ \
[10] [40]
\
[20]
刪除 30：
target = 30
前驅 = 20（30 左子樹的最大值）
遞迴刪除 20
用 20 取代 30
