2025q1 Homework2 (quiz1+2)

contributed by < alexc-313 >

2025q1 第 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;

可以得知此程式的鏈結串列十分基本。
題目要求的 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;
}

題目希望我們使用雙重指標將 item 插入在 before 之前，關鍵在於 for 迴圈的寫法。

我們用 p = &l->head 會像以下圖示:

此時 *p 會是下一個節點的地址，因此我們用 *p != before 以及 p = &(*p)->next 來將 p 指向 before 的前一個節點的 next 。

用 *p = item 將 A->next 指向 item 。

再用 item->next = before 將 item 指向 before 。

這樣就可以完成題目所要的雙重指標操作。

撰寫合併排序操作

list_item_t *merge_list(list_item_t *l1, list_item_t *l2)
{
    list_item_t *head = NULL, **ptr = &head, **node;

    for (node = NULL; l1 && l2; *node = (*node)->next) {
        node = (l1->value < l2->value) ? &l1: &l2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (list_item_t *)((uintptr_t) l1 | (uintptr_t) l2);
    return head;
}

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

    list_item_t *slow = head, *fast = head->next, *mid;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    mid = slow->next;
    slow->next = NULL;

    list_item_t *front = merge_sort(head);
    list_item_t *back = merge_sort(mid);

    head = merge_list(front, back);
}

• merge_list
  參考〈你所不知道的 C 語言: linked list 和非連續記憶體〉中提到的 LeetCode 21. Merge Two Sorted Lists 案例探討，用間接指標避免配置暫時節點的空間，並用特殊的 bitwise 操作 *ptr = (list_item_t *)((uintptr_t) l1 | (uintptr_t) l2) 來將剩餘的節點接在合併完的鏈結串列後面。
• merge_sort
  使用基本的遞迴合併排序方法，並用快慢指標將鏈結串列剖半。

測驗 2

題目要求我們完成樹狀結構的記憶體區塊的程式碼，填上 remove_free_tree 中空缺的部分。
首先，先了解樹狀結構的節點架構

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

由這段程式碼可以做出以下示意圖:

再看到空格部分的程式碼

if ((*node_ptr)->l && (*node_ptr)->r) {
    /* Find the in-order predecessor:
     * This is the rightmost node in the left subtree.
     */
    block_t **pred_ptr = &(*node_ptr)->l;
    while (EEEE)
        pred_ptr = FFFF;

這段程式碼是在移除二元搜尋樹節點時，該節點左子樹與右子樹皆不空的狀況下，我們要找到該節點的 in-order predecessor 。
block_t **pred_ptr = &(*node_ptr)->l 先將 pred_ptr 指向 node_ptr 的左子樹，如下圖:

接下來我們只需要用 while 迴圈不斷將 pred_ptr 指向節點的右子樹，直到右子樹不存在就找到 in-order predecessor 了。

所以完成程式碼:

while ((*pred_ptr)->r)
    pred_ptr = &(*pred_ptr)->r;

嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼

此函式會走訪二元搜尋樹並嘗試尋找目標節點，若目標節點不存在則回傳 NULL 。

block_t **find_free_tree(block_t **root, block_t *target)
{
    block_t **current = root;

    while (*current) {
        if (*current == target) {
            return current;
        }

        if (target->size < (*current)->size) {
            current = &(*current)->l;
        } else {
            current = &(*current)->r;
        }
    }

    return NULL;
}

此函式會尋找並回傳目標節點的 in-order predecessor ，此函式在實際運行時並沒有特殊作用，其功能為測試及除錯用。

block_t *find_predecessor_free_tree(block_t **root, block_t *node)
{
    if (!node || !root || *root == NULL) return NULL;

    block_t *predecessor = NULL;
    block_t *current = *root;

    while (current) {
        if (node->size > current->size) {
            predecessor = current;
            current = current->r;
        } else if (node->size < current->size) {
            current = current->l;
        } else {
            if (current->l) {
                predecessor = current->l;
                while (predecessor->r) {
                    predecessor = predecessor->r;
                }
            }
            break;
        }
    }

    return predecessor;
}

我人工的創建二元搜尋樹，再用不同 assert 來測試各個函式是否正常運作。

int main()
{
    // Create nodes
    block_t node1 = {10, NULL, NULL};
    block_t node2 = {5, NULL, NULL};
    block_t node3 = {15, NULL, NULL};
    block_t node4 = {3, NULL, NULL};
    block_t node5 = {7, NULL, NULL};
    block_t node6 = {13, NULL, NULL};
    block_t node7 = {20, NULL, NULL};

    // Manually link nodes into a BST
    block_t *root = &node1;
    node1.l = &node2;
    node1.r = &node3;
    node2.l = &node4;
    node2.r = &node5;
    node3.l = &node6;
    node3.r = &node7;

    // Test find_free_tree()
    assert(find_free_tree(&root, &node5) == &node2.r);
    assert(find_free_tree(&root, &node7) == &node3.r);

    // Test find_predecessor_free_tree()
    assert(find_predecessor_free_tree(&root, &node3) == &node6);
    assert(find_predecessor_free_tree(&root, &node1) == &node5);

    print_tree(root, 0, 0);
    printf("\n");
    // Test remove_free_tree()
    remove_free_tree(&root, &node3);
    print_tree(root, 0, 0);
    printf("\n");
    assert(root->r == &node6);
    assert(root->r->r == &node7);
    assert(root->r->l == NULL);

    // Test removing a leaf node
    remove_free_tree(&root, &node7);
    print_tree(root, 0, 0);
    printf("\n");
    assert(root->r->r == NULL);

    // Test removing root node
    remove_free_tree(&root, &node1);
    print_tree(root, 0, 0);
    printf("\n");
    assert(root == &node5);

    printf("All tests passed!\n");
    return 0;
}

為了讓除錯及寫測試程式更方便，我用 ChatGPT 多寫了輔助函式 print_tree 來視覺化二元搜尋樹。

void print_tree(block_t *node, int depth, int is_right) {
    if (node == NULL) return;

    print_tree(node->r, depth + 1, 1);

    for (int i = 0; i < depth; i++) printf("    ");
    if (depth > 0) {
        printf("%s(%zu)\n", is_right ? "/---" : "\\---", node->size);
    } else {
        printf(" (%zu)\n", node->size);
    }

    print_tree(node->l, depth + 1, 0);
}

此函式的輸出如下:

        /---(20)
    /---(15)    
        \---(13)
 (10)
        /---(7) 
    \---(5)     
        \---(3)

其中 (10) 是 root ，/---代表右子樹，\---代表左子樹。

測驗 3

解釋程式碼運作原理

先觀察結構體的架構:

#include "list.h"

typedef struct __node {
    long value;
    struct list_head list;
} node_t;

從題目與程式碼可知此結構體運用 Linux 核心風格 List API 實作雙重環狀佇列，以及一個名為 value 的變數存放數值。

在快速看過其他用來測試或輔助用的程式碼後，我們看到第一個空格的程式碼:

static void rebuild_list_link(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node, *prev;
    prev = head;
    node = head->next;
    while (node) {
        node->prev = prev;
        prev = node;
        node = node->next;
    }
    prev->next = head;
    head->prev = prev;    /* GGGG */
}

這段程式碼再重建雙重環狀佇列， while 迴圈會把所有的節點串在一起，我們只需在迴圈結束後將最後一個節點正確接上就完成佇列的重組了。

prev->next = head;
head->prev = prev;

會把最後一個節點與第一個節點接上。

再看到 quick_sort 主體:

{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    struct list_head *begin[max_level];
    struct list_head *result = NULL, *left = NULL, *right = NULL;
    begin[0] = list->next;
    list->prev->next = NULL;
    while (i >= 0) {
        struct list_head *L = begin[i], *R = list_tail(begin[i]);
        if (L != R) {
            struct list_head *pivot = L;
            value = list_entry(pivot, node_t, list)->value    /* HHHH */
            struct list_head *p = pivot->next;
            pivot->next = NULL; /* break the list */

            while (p) {
                struct list_head *n = p;
                p = p->next;
                int n_value = list_entry(n, node_t, list)->value    /* IIII */;
                if (n_value > value) {
                    n->next = right;
                    right = n;
                } else {
                    n->next = left;
                    left = n;
                }
            }

            begin[i] = left;
            begin[i + 1] = pivot    /* JJJJ */;
            begin[i + 2] = right    /* KKKK */;
            left = right = NULL;
            i += 2;
        } else {
            if (L) {
                L->next = result;
                result = L;
            }
            i--;
        }
    }
    list->next = result;
    rebuild_list_link(list);
}

這段程式碼用最左邊的節點作為 pivot ，逐個比較節點與 pivot 的大小，將佇列中的節點拆分成比 pivot 小， pivot ，比 pivot 大三個佇列，分別存在 begin[i] 、 begin[i+1] 、 begin[i+2] 中。
接著從 i+2 開始，也就是比 pivot 大的佇列再做一次分割，直到佇列中只剩下小於或等於一個節點，再把該節點加進佇列 result 中，再遞減 i 這樣就可以逐步的實現非遞迴的快速排序法。

操作鏈結串列的示意圖:

以下程式碼用 list_entry 巨集來取得節點 ，再將該節點的 value 存入 value 及 n_value 中。

value = list_entry(pivot, node_t, list)->value    /* HHHH */
n_value = list_entry(n, node_t, list)->value    /* IIII */;

從此演算法的作法以及 begin[i] = left 可以推得:

begin[i + 1] = pivot    /* JJJJ */;
begin[i + 2] = right    /* KKKK */;

研讀〈A comparative study of linked list sorting algorithms〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作

該文比較了六種排序演算法: sediment sort, tree sort, bubble sort, selection sort, quick sort, merge sort ，其中 sediment sort, tree sort 是雙向鏈結串列的排序演算法，論文內的比較結果如下表:

Method	n <= 1000	n > 1000	Ratio
D-Bub	0.342743	0.649589	1.895
S-Bub	0.239701	0.546267	2.279
Select	0.160253	0.456876	2.851
Msort	0.032090	0.027577	0.859
Qsort	0.028548	0.024358	0.853
Tree	0.021951	0.019862	0.905

由上表可知 tree sort 是最有效率的雙向鏈結串列的排序演算法。

這個演算法是將雙向鏈結串列轉換成二元搜尋樹，利用二元搜尋樹有特殊排列的特性，再將其轉換成雙向鏈結串列。

以下是我的實作 tree sort 的方法:

先定義結構體:

#include "list.h"

typedef struct __list_node {
    int value;
    struct list_head list;
} node_t;

typedef struct __tree_node {
    int value;
    struct __tree_node *left, *right;
} t_node_t;

我們會需要一些輔助函式，下面這個函式會創建並插入新的節點到二元搜尋樹中。

t_node_t *insert(t_node_t* root, int value) {
    t_node_t* new = (t_node_t*)malloc(sizeof(t_node_t));
    new->value = value;
    new->left = new->right = NULL;

    if (root == NULL)
        return new;

    t_node_t *parent = NULL;
    t_node_t *cur = root;

    while (cur) {
        parent = cur;
        if (cur->value > value)
            cur = cur->left;
        else
            cur = cur->right;
    }
    
    if (parent->value > value)
        parent->left = new;
    else
        parent->right = new;

    return root;
}

這個函式會加入帶有 value 的新節點到雙向鏈結串列中。

void list_insert_tail(struct list_head *head, int value)
{
    node_t *new = malloc(sizeof(node_t));
    new->value = value;
    list_add_tail(&new->list, head);
}

這個函式用 inorder 的方式走訪二元搜尋樹中所有節點，並釋放二元搜尋樹中節點，同時呼叫 list_insert_tail 來加入節點。

void traverse(struct list_head *head, t_node_t *root)
{
    if (!root)
        return;
    
    traverse(head, root->left);
    list_insert_tail(head, root->value);
    free(root);
    traverse(head, root->right);
}

最後是 treesort

struct list_head *treesort(struct list_head *head)
{
    struct list_head *tree_head = malloc(sizeof(struct list_head));
    INIT_LIST_HEAD(tree_head);

    node_t *node, *safe;
    t_node_t *root = NULL;
    list_for_each_entry_safe(node, safe, head, list) {
        int value = node->value;
        list_del(&node->list);
        free(node);
        root = insert(root, value);
    }
    traverse(tree_head, root);
    return tree_head;
}

我簡單的寫了一個測試程式

int main()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    INIT_LIST_HEAD(head);

    list_insert_tail(head, 5);
    list_insert_tail(head, 3);
    list_insert_tail(head, 7);
    list_insert_tail(head, 2);
    list_insert_tail(head, 4);
    list_insert_tail(head, 6);
    list_insert_tail(head, 8);

    struct list_head *new = treesort(head);
    node_t *cur;
    list_for_each_entry(cur, new, list) {
        printf("%d ", cur->value);
    }
}

原本鏈結串列的排序是:
5 3 7 2 4 6 8
經過 treesort 後變成:
2 3 4 5 6 7 8

在這個程式中我使用 <list.h> 提供的 list_head 來實作環狀雙向鏈結串列，也試著避免使用遞迴的操作，不過在 traverse 中還是用到了遞迴，我目前沒有想到其他不使用遞迴的做法。另外，這個程式還有許多能改進的空間，像是對二元搜尋樹做平衡，缺乏檢查 malloc 是否成功，避免多建立 t_node_t 等等。這是我第一次聽到 tree sort ，所以花了許多時間，但經過這個實作後我對於雙向鏈結串列、二元搜尋樹，以及相關的演算法與操作都更了解。

2025q1 第 2 週測驗題

測驗 1

測驗 2

測驗 3