2025q1 Homework2 (quiz1+2)

contributed by wcc-gh

第一周

測驗一

解釋程式碼原理

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 所指的節點之前。

首先用指標的指標 p ，找到 before 的位置
一開始 p 指向 &l->head ，此時 *p 指向 a 的位址

每個迴圈會執行 p = &(*p)->next

當 *p == before 修改 *p 以插入 item

最後把 item->next 指向 before 所指的節點

加入合併排序

void list_merge_sort(list_t *list){
    
    if (list_size(list) < 2) return;
    list_item_t *s = list->head, *f = list->head->next;
    while (f && f->next){
        f = f->next->next;
        s = s->next;
    }
    list_t left, right;
    right.head = s->next;
    left.head = list->head;
    s->next = NULL;

    list_merge_sort(&left);
    list_merge_sort(&right);

    list_t dummy;
    dummy.head = NULL;
    list_item_t **cur = &dummy.head;
    while (left.head && right.head){
        if (left.head->value <= right.head->value){
            *cur = left.head;
            left.head = left.head->next;
        }
        else{
            *cur = right.head;
            right.head = right.head->next;
        }
        cur = &(*cur)->next;
    }
    if (left.head) 
        *cur = left.head;
    else
        *cur = right.head;
    
    list->head = dummy.head;
}

測驗二

解釋程式碼原理