2025q1 Homework2 (quiz1+2)

        # 2025q1 Homework2 (quiz1+2)

contributed by <As7r1d>

2025q1 第 1 週測驗題

測驗1

AAAA：&list->head
BBBB：before
CCCC：&(*p)->next
DDDD：item->next

解釋程式碼運作原理

測試程式簡述

目的
- 執行針對 1000 個節點的插入測試
巨集
- 定義了一個大小為 1000 的節點陣列 items

主要有 2 個測試

測試將節點插入串列尾端且順序正確

    list_reset();
    my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
    for (size_t i = 0; i < N; i++)
        list_insert_before(&l, l.head, &items[i]);
    my_assert(list_size(&l) == N, "Final list size should be N");
    size_t k = N - 1;
    list_item_t *cur = l.head;
    while (cur) {
        my_assert(cur->value == k, "Unexpected list item value");
        k--;
        cur = cur->next;
    }

測試將節點插入串列最前端且順序正確

    list_reset();
    my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
    for (size_t i = 0; i < N; i++)
        list_insert_before(&l, NULL, &items[i]);
    my_assert(list_size(&l) == N, "Final list size should be N");
    k = 0;
    cur = l.head;
    while (cur) {
        my_assert(cur->value == k, "Unexpected list item value");
        k++;
        cur = cur->next;
    }

在了解測試程式目的後，接下來了解串列架構：

#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 函式

static inline 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; 
}

list_insert_before 目的：在這個函式中有一個單向鏈結串列 l ，將 item 插入 before 節點之前。
list_item_t **p：p 是個變數指向 list_item_t * 指標的指標，一開始會指向 head。在 for loop 中，要找到要插入位置 before 節點，如果找到就離開迴圈，沒有找到就繼續尋找。這種指標的指標方法不需要透過特例判斷也可以正確處理插入在鏈結串列頭部或中間的情況。

接下來用圖解方式一步步解釋，使用指標的指標方式，設定情境是我要在 C 節點前插入節點 X：

初始單向鏈結串列

p = &l->head 一開始是 p 指向 head 這個指標變數本身的位址，對 p 取值是 A 節點。

於是 p = &(*p)->next。接著對 p 取值是 B 節點。

於是又 p = &(*p)->next。對 p 取值是 C 節點。找到before = C。

跳出迴圈，*p = item; 將 p 指向的值改成 &X。

item->next = before;，把 X->next 指向 before（即C）

接下來思考 edge case，如果l是空的，即 l->head == NULL 情況。

初始狀態

因為 *p == NULL，如果呼叫 list_insert_before(l, NULL, nodeA)，那麼 before == NULL，所以 *p == before跳出 for 迴圈，執行 *p = item;，p 指向的值改為 &nodeA

item->next = before;，把 nodeA 之 next 改成 NULL。

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

static list_item_t* find_middle(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;
    }
    return slow; 
}


static list_item_t* merge_sorted_lists(list_item_t *l1, list_item_t *l2) {
    list_item_t dummy;
    list_item_t *tail = &dummy;
    dummy.next = NULL;

    while (l1 && l2) {
        if (l1->value < l2->value) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

static list_item_t* merge_sort_list(list_item_t *head) {
    if (!head || !head->next)
        return head; 

    list_item_t *mid = find_middle(head);
    list_item_t *right = mid->next;
    mid->next = NULL; 

    list_item_t *left_sorted = merge_sort_list(head);
    list_item_t *right_sorted = merge_sort_list(right);

    return merge_sorted_lists(left_sorted, right_sorted);
}

void list_merge_sort(list_t *l) {
    if (!l)
        return;
    l->head = merge_sort_list(l->head);
}

測驗2

EEEE：(*pred_ptr)->r
FFFF：&(*pred_ptr)->r

解釋程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼

這題程式碼主要是二元搜尋樹（BST）中刪除節點的功能。

二元搜尋樹特性如下：

left child node 的值小於 parent node。
right child node 的值大於 parent node。
舉例如下圖：

節點架構如下：

typedef struct block {
    size_t size;
    struct block *l, *r;
} block_t;

remove_free_tree()：該函式目的是從樹中移除一個特定的記憶體區塊 block_t *target。刪除節點同時保持這棵樹的性質，主要有三種情況：
- 目標節點沒有 child node 時，直接移除。
- 目標節點只有一個 child node，將 child node 連接到 parent node。
- 目標節點有兩個 child node，從目前節點的左子樹開始，然後一直往右走，直到沒有右小孩了，就找出其左子樹中最右邊的節點來替代目標節點。
而我們需要完成 find_free_tree() 該函式

block_t **find_free_tree(block_t **root, block_t *target) {
    while (*root) { // 只要目前節點不是 NULL
        if (*root == target) {
            return root; // 找到 回傳指向它的指標
        }
        if (target->size < (*root)->size) {
            root = &(*root)->l; // 小的往左找
        } else {
            root = &(*root)->r; // 大的往右找
        }
    }
    return NULL; // 找不到
}

void remove_free_tree

2025q1 第 1 週測驗題

測驗1

解釋程式碼運作原理

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

測驗2

解釋程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼

參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現

測驗3

2025q1 第 2 週測驗題

2025q1 第 1 週測驗題

測驗1

解釋程式碼運作原理

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

測驗2

解釋程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼

參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現

測驗3

2025q1 第 2 週測驗題

Read more

2025q1 Homework3 (kxo)

2025q1 Homework4 (quiz3+4)

linux2025-ideas

linux2025-homework1