2025q1 Homework2 (quiz1+2)

contributed by < PigeonSir >

w1 測驗 1

運用 "a pointer to a pointer" 技巧操作單向的鏈結串列，其中基本的結構體如下

insert before

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

利用 p 做為指標的指標，指向當前節點的 next 的地址，對 p 執行 deference 可得到下一個節點的地址
與沒有使用指標的指標技巧的作法比較 :

static inline void list_insert_before(list_t *h, list_item_t *before, list_item_t *item)
{
    lsit_item_t *cur, *prev;
    for (cur = h->head; cur != before; prev = cur, cur = cur->next)
        ;
    prev->next = item;
    item->next = cur;
}

使用 "a pointer to a pointer" 技巧後就不需要使用額外的指標紀錄拜訪過的節點 (prev)

測試程式

my_assert

#define my_assert(test, message) \
    do {                         \
        if (!(test))             \
            return message;      \
    } while (0)

定義 my_assert 宏用於觀察執行時遭遇的錯誤，這裡有一個疑問是為何要使用到 do while ，

圖例

要插入 node2 於 node3 以前

走訪鏈結串列直到 *p == before 時跳出迴圈，此時 p 紀錄的為 node1 中 next 的地址

更新 *p (即 node1 的 next) 為 node2 ，最後再將 node3 接上於 node2 後便完成

W1 測驗 2