2025q1 Homework2 (quiz1+2)

contributed by <As7r1d>

2025q1 第 1 週測驗題

quiz1 題目

測驗1

解釋程式碼運作原理

• 測試程式簡述
  • 巨集
    • 定義了一個大小為 1000 的節點陣列 items

主要有兩個測試：

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

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

串列架構如下：

#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_item_t 表示串列的節點。其中 value 表示節點儲存的數值
  ，next 則表示指向下一個 list_item_t 節點的指標（若為 NULL，表示是最後一個節點）。

• list_t 中 head 表示指向串列的第一個節點。如果 head 是 NULL，表示鏈結串列為空。

• list_insert_before
  在這個函式中目的是將 item 插入 before 節點之前。

  ​​​​void list_insert_before(list_t *list, list_item_t *before, list_item_t *item) {
  ​​​​    list_item_t **p;
  ​​​​    for (p = &list->head; *p != before; p = &(*p)->next)
  ​​​​        ;
  ​​​​    *p = item;
  ​​​​    item->next = *p; 
  ​​​​}
  

  • 定義 list_item_t **p，p 是個變數指向 list_item_t * 指標的指標。
    在 for 迴圈中，要找到要插入位置 before 節點，如果找到就離開迴圈，沒有找到就繼續尋找。
  • p = &list->head 表示一開始 p 指向 head 節點指標的指標。
  • *p != before 檢查目前 p 指向的節點是否是目標節點（before）。
  • p = &(*p)->next 如果不是，就移動到下一個節點的指標。如果找到，*p = item 指向 before 的指標改指向 item。
  • item->next = before 將 item 的 next 指向 before，完成插入。

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

測驗2

解釋程式碼運作原理

• 這題程式碼主要是二元搜尋樹（BST）中刪除節點的功能。刪除節點主要有三種情況：
  • 目標節點沒有 child node 時，直接移除。
  • 目標節點只有一個 child node，將 child node 連接到 parent node。
  • 目標節點有兩個 child node，找出中序前置節點（左子樹中最大的節點）來替代目標節點
• 二元搜尋樹特性如下：
  • left child node 的值小於 parent node。
  • right child node 的值大於 parent node。
  • 舉例如下圖：
• 節點架構如下：
  ​​​​typedef struct block {
  ​​​​    size_t size;
  ​​​​    struct block *l, *r;
  ​​​​} block_t;
  
• void remove_free_tree 函式
  ​​​​block_t **find_free_tree(block_t **root, block_t *target);
  ​​​​block_t *find_predecessor_free_tree(block_t **root, block_t *node);
  
  ​​​​void remove_free_tree
  ​​​​