2025q1 Homework2 (quiz1+2)

contributed by < willy-liu >

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，就要先遍歷鏈結串列，找到before。最簡單的做法其實只需要*p就好，實作如下

{
    list_item_t *p;

    if (l->head == before) {
        item->next = l->head;
        l->head = item;
        return;
    }

    for (p = l->head; p && p->next != before; p = p->next);
    if (p) {
        item->next = p->next;
        p->next = item;
    }
}

首先找到要插入的位置，然後將item->next設定為p->next，最後讓p->next等於item就好。
然而，這樣的實作方式在邊界條件就會有例外，before如果在head就需要將l->head取代成item。這樣的例外就是一個不好的code smell，特別是在雙向鏈結串列，或是其他結構，如果邊界情況有好幾個時，不但會影響程式碼的閱讀，還會影響效能。

使用了**p就可以完美解決這樣的邊界情況，將遍歷的對象從節點本身，改為在next指標的位址上做移動，head的型態也與next相同，所以對p取址一次*p就可以變更l->head或是list_item->next，邊界情況要做的事與一般情況的邏輯就會一致。

{
    list_item_t **p;
    for (p = &l->head; *p != before; p = &(*p)->next);
    item->next = *p;
    *p = item;
}

延伸-撰寫合併排序操作

要實作合併排序，需要

測驗 2

測驗 3

2025q2 第 2 週測驗題

測驗 1

測驗 2

測驗 3

AAAA：map->bits
BBBB：map->bits
CCCC：first->next
DDDD：n->pprev
EEEE：n->pprev

Linux kernel風格的hash table架構如下

這邊注意到pprev是「指標的指標」，才可以避免發生移除節點時的例外，因為開頭的行為會與其他節點有不一致的行為

結構體解釋

typedef struct {
    int bits;
    struct hlist_head *ht;
} map_t;

struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};