2025q1 Homework2 (quiz1+2)

Q1 測驗

list_insert_before

先考量鏈結串列：

#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 以及 list_t，而 list_insert_before 這個函式如下：

static inline void list_insert_before(list *l, list_item_t *before, \
list_item_t *item)
{
    list_item **p;
    for (p = &(l->head); *p != before; p = &(*p)->next)
        ;
    *p = item;
    item->next = before;
}

他需要帶入一個 list 以及指向 before 與指向 item 的結構體 list_item_t，而函式的功能是將 item 插入 before 之前，考量以下三種情境：

1. before 指向鏈結的頭部，則 item 插入到頭部之前
2. before 為 NULL，則 item 加到鏈結的尾端
3. before 不存在在鏈結當中，則視為未定義行為

首先，會先建立 N 個 list_item_t 的結構體 items ，以及 list_t 的結構體 l，並且對鏈結串列初始化，每當 items 初始化的數量增加，後面 items 的 value 就會比前面再多加 1。

#define N 1000

static list_item_t items[N];
static list_t l;

static list_t *list_reset(void)
{
    for (size_t i = 0; i < N; i++) {
        items[i].value = i;
        items[i].next = NULL;
    }
    l.head = NULL;
    return &l;
}

當我們執行 test_list 時，會進行 list_insert_before 命令，並且分別對插入到頭部和插入到尾端進行測試：
插入到頭部：

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

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

插入到尾端：

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

k = 0;
cur = l.head;
while (cur) {
    my_assert(cur->value == k, "Unexpected list item value");
    k++;
    cur = cur->next;
}

在現有的程式碼進行合併排序

list_item_t *find_middle(list_item_t *head) {
    if (!head || !head->next)
        return NULL;
    list_item_t *slow = head;
    list_item_t *fast = head->next;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

list_item_t *mergeTwo(list_item_t *left, list_item_t *right) {
    list_item_t *head;
    list_item_t **ptr = &head;
    while (left && right) {
        if (left->value < right->value) {
            *ptr = left;
            left = left->next;
        } else {
            *ptr = right;
            right = right->next;
        }
        ptr = &(*ptr)->next;
    }
    *ptr = left ? left : right;
    return head;
}

list_item_t *mergeSort(list_item_t *head) {
    if (!head || !head->next)
        return head;
    list_item_t *mid = find_middle(head);
    list_item_t *left = head;
    list_item_t *right = mid->next;
    mid->next = NULL;
    
    list_item_t *left_sorted = mergeSort(left);
    list_item_t *right_sorted = mergeSort(right);
    list_item_t *merged = mergeTwo(left_sorted, right_sorted);

    
    
    return merged;
}

Q2 測驗