2025q1 Homework2 (quiz1+2)

contributed by <WenHsuanYu>

quiz 1

測驗 1

首先看到題目給定的 list_t 與節點 list_item_t 結構，便可得知是單向鏈結串列。

#include <stddef.h>
typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;

其中 head 會指向頭節點 （如果頭節點存在的話）。

題目指出其關鍵操作 list_insert_before 函式的語意如下：

由此可得知，傳入參數 l 為指向串列的指標，而函式會走訪串列以定位插入位置傳入參數 before 會指向插入節點 item 的下一個位置。

當 before 指向頭節點，item 會插入到最前面；before 指向 NULL，item 會插入到最尾端。當 before 不屬於 l 所指向的串列的節點時，會導致未定義的行為。

此 list_insert_before 函式定義如下：

list_item_t **p;
for (p = AAAA; *p != BBBB; p = CCCC)
    ;
*p = item;
DDDD = before;

依照該函式功能的註解，可推論一開始間接指標 p 指向偽節點位置(結構成員只有指標，而不具有值)，故 AAAA 為 &l->head，而迴圈會走訪每個節點(實際上 p 指向各個節點的 next 指標位置）直到註解所說定位到 before 之間的位置，由此可知 BBBB 為 before，而 CCCC 為 &(*p)->next，離開迴圈後，此時，間接指標 p 會指向 before 前節點的 next 指標，因此解參考（即 *p）很容易得到下一個節點，所以我們可以透過解參考的方式將該節點 next 指標指向插入節點 item，之後插入節點再跟原先的 before 連接起來，故 DDDD 為 item->next。

解釋 list_insert_before 函式，假設 ‵p‵ 已經走訪到 ‵before‵ 之前的節點，如下圖所示：

接著，我們想要插入 item 節點，其值為 2， 其。

紅線表示插入 item 節點，與其相對應的程式碼如下：

*p = item;

藍線表示插入節點指向 before 所指向的節點位置，與其相對應的程式碼如下:

item->next = before;

延伸問題:

1. 解釋運作原理

程式流程如下：

• main 函數會呼叫 test_suite 函式，該函式會進行鏈結串列的插入測試，並針對函式回傳結果進行處理，印出相關測試資訊，最後將函式回傳結果進行兩次 not 運算，反映出測試正常（以 0 結束)或者測試異常（以 1 不正常結束）。

int main(void)
{
    printf("---=[ List tests\n");
    char *result = test_suite();
    if (result)
        printf("ERROR: %s\n", result);
    else
        printf("ALL TESTS PASSED\n");
    printf("Tests run: %d\n", tests_run);
    return !!result;
}

• test_suite 函式透過巨集 my_run_test 來呼叫 test_list 測試函式，此巨集會接收傳入測試函式，並執行測試函式，檢查測試結果，若有錯誤訊息則將其回傳，否則在 test_suite 函式那一層會回傳 NULL，表示測試正常。

#define my_run_test(test)       \
    do {                        \
        char *message = test(); \
        tests_run++;            \
        if (message)            \
            return message;     \
    } while (0)
    
int tests_run = 0;

static char *test_suite(void)
{
    my_run_test(test_list);
    return NULL;
}
    

• test_list 測試函式主要用於驗證鏈結串列操作的正確性，其測試流程如下：

  • 初始化設定：
    首先，透過呼叫 list_reset 函式來初始化全域節點陣列和鏈結串列。這會將每個節點的值設定為其對應的索引值，並清除所有現有的鏈結關係，確保測試環境的乾淨。

  • 測試情境一：節點前端插入：
    在這個測試中，我們模擬將所有節點（目前設定為 1000 個）依序從鏈結串列的最前端插入。插入完成後，我們會利用 my_assert 巨集檢查鏈結串列的總長度是否正確，並確認節點數值是否呈現反向排列，以驗證前端插入的邏輯無誤。

  • 測試情境二：節點尾端插入：
    接著，我們將所有節點（同樣是 1000 個）依序從鏈結串列的尾端插入。插入完成後，一樣會透過 my_assert 巨集來檢查鏈結串列的長度，並驗證節點數值是否呈現順向排列，以確保尾端插入的功能正常。

  • 測試情境三：節點尾端插入
    這個情境是任意順序方式插入，當前同測試情境二。

#define my_assert(test, message) \
    do {                         \
        if (!(test))             \
            return message;      \
    } while (0)
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;
}

static char *test_list(void)
{
    /* Test inserting at the beginning */
    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;
    }

    /* Test inserting at the end */
    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;
    }

    /* Reset the list and insert elements in order (i.e. at the end) */
    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, "list size should be N");

    return NULL;
}

2. 撰寫合併排序操作

/**
 * Merges two singly-linked lists into a single sorted list.
 *
 * @param l Pointer to the head of the first sorted list.
 * @param r Pointer to the head of the second sorted list.
 * @return Pointer to the head of the merged sorted list.
 *
 * The function assumes that both input lists are sorted in ascending order.
 * It iteratively selects the smaller head node from the two lists and appends it to the result list.
 * The merged list reuses the nodes from the input lists; no new nodes are allocated.
 */
static list_item_t *merge_twolists(list_item_t *l, list_item_t *r)
{
	list_item_t dummy;
	list_item_t **indirect = &dummy->next;
	dummy.next = NULL;
	
	while(l && r) {
		list_item_t **item = (l->value <= r->value) ? &l : &r;
		*indirect = *item;
		indirect = &(*indirect)->next;
		*item = (*item)->next;
	}
	*item = a ? a : b;
	return dummy.next;
}
/**
 * @brief Sorts a singly linked list using the merge sort algorithm.
 *
 * This function implements the merge sort algorithm for singly linked lists.
 * It recursively splits the list into two halves, sorts each half, and then
 * merges the sorted halves back together.
 *
 * @param head Pointer to the head of the singly linked list to be sorted.
 * @return Pointer to the head of the sorted linked list.
 */
static list_item_t *list_merge_sort(list_item_t *head)
{
	if (!head || !head->next)
		return head;
	
	list_item_t *slow = head;
	list_item_t *fast = head->next;
	while (fast && fast->next) {
		slow = slow->next;
		fast = fast->next->next;
	}
	
	list_item_t *mid = slow->next;
	slow->next = NULL;
	
	list_item_t *left = merge_sort_list(head);
	list_item_t *right = merge_sort_list(mid);
	
	return merge_twolists(left, right);
	
}	

測驗 2

測驗 3

quiz 2

測驗 1

測驗 2

測驗 3