2024q1 Homework2 (quiz1+2)

contributed by < hugo0406 >

第一周測驗題

測驗一

測驗二

---

第二周測驗題

測驗一

注意以下:

1. 避免過早逐行程式碼講解，否則很容易淪落為「舉燭」。
2. 程式碼背後的動機、考量因素，還有手法比程式碼本身，更值得在開發紀錄探討。
3. 為何給定 preorder 和 inorder，即可重建二元樹？你該探討。

給定由二個由整數構成陣列的前序 (preorder) 和中序 (inorder) 形式，分別是對同一棵二元樹的前序及中序走訪結果，藉此重建此二元樹。以下是運用 Linux 核心的 hash table 實作程式碼

不用抄寫題目，專注探討程式原理、闡述你的洞見，還有你預期做哪些改進。

hlist 用於 hash table 的實作，詳細內容請參考Linux 核心的 hash table 實作。
hlist_head 和 hlist_node 用於 hash table 中 bucket 的實作，具有相同 hash value 的節點 (即

$hash(i)=hash(j),i\ne j$ ) 會放在同一條鏈結串列上。

值得我們注意的是 hlist_node 裡的 **pprev 是指標的指標，它指向的是前一個節點的 next 指標。 這樣的目的是即使要刪除的節點是 最前面的節點 時，也可以透過 *pprev = next 去直接修改指標的指向。

struct order_node {
    struct hlist_node node;
    int val;
    int idx;
};

order_node 結構如下圖所示:

struct TreeNode {
    int val;
    struct TreeNode *left, *right;
};

TreeNode結構如下圖所示:

static inline void INIT_HLIST_HEAD(struct hlist_head *h)
{
    h->first = NULL;
}

INIT_HLIST_HEAD 對鏈結串列的頭初始化為 NULL ，對應的圖如下:

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    if (h->first)
        h->first->pprev = &n->next;
    n->next = AAAA;
    n->pprev = &h->first;
    h->first = n;
}

從函式名稱 hlist_add_head 不難看出要在鏈結串列的開頭加入節點 ( LIFO 準則)

首先可以看到一開始的 if 為判斷 h->first 是否為 NULL，若不為 NULL 則代表鏈結串列上有節點。

• 鏈結串列非空

 #4 h->first->pprev = &n->next;

#5 n->next = h->first; //AAAA

#6 n->pprev = &h->first;

#7 h->first = n;

• 鏈結串列為空

#5 n->next = h->first; //AAAA

#6 n->pprev = &h->first;

#7 h->first = n;

static int find(int num, int size, const struct hlist_head *heads)
{
    struct hlist_node *p;
    int hash = (num < 0 ? -num : num) % size;
    hlist_for_each (p, BBBB) {
        struct order_node *on = CCCC(p, struct order_node, node);
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

從函式名稱 find 及回傳值型態可以推測出此函示去尋找值為 num 的節點 ，並返回該節點的 idx。

首先觀察第 4 行，這邊的雜湊函數是採用 Division method ，共有 size 個 bucket，hash 的值為 num 所屬的第幾個 bucket ， 接下來第五行去該 bucket 所指向的鏈結串列去走訪每個節點尋找，可以看出 BBBB = &heads[hash] 。因為要把 num 與每個節點的 val 進行比較是否相等，需要知道 order_node 這個結構體起始地址，可以透過 container_of 這個巨集來得到 ，

因此 CCCC=container_of 或 CCCC=list_entry。

不用列出參考題解，專注在程式碼的探討。

static inline void node_add(int val,
                            int idx,
                            int size,
                            struct hlist_head *heads)
{
    struct order_node *on = malloc(sizeof(*on));
    on->val = val;
    on->idx = idx;
    int hash = (val < 0 ? -val : val) % size;
    hlist_add_head(&on->node, DDDD);
}

函式 node_add() 依節點的雜湊值將節點插入所屬 bucket 鏈結串列的開頭，因此 DDDD = &heads[hash]

static struct TreeNode *buildTree(int *preorder,
                                  int preorderSize,
                                  int *inorder,
                                  int inorderSize)
{
    struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads));
    for (int i = 0; i < inorderSize; i++)
        INIT_HLIST_HEAD(&in_heads[i]);
    for (int i = 0; i < inorderSize; i++)
        node_add(inorder[i], i, inorderSize, in_heads);

    return dfs(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1,
               in_heads, inorderSize);
}

函示 build_tree() 依中序和前序建一顆二元樹，為了方便說明，假設 Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 。

首先上段程式碼會先建立一個雜湊表 ， bucket 的數量等於 inorderSize ，按照上面的假設，共有 5 個 buckets ，接下來對每個鍊節串列的頭進行初始化。

示意圖如下：

接下來依序將 inorder 裡的元素經過雜湊函數，插入其所屬的鏈結串列

示意圖如下：

最後程式遞迴呼叫 dfs()

static struct TreeNode *dfs(int *preorder,
                            int pre_low,
                            int pre_high,
                            int *inorder,
                            int in_low,
                            int in_high,
                            struct hlist_head *in_heads,
                            int size)
{
    if (in_low > in_high || pre_low > pre_high)
        return NULL;

    struct TreeNode *tn = malloc(sizeof(*tn));
    tn->val = preorder[pre_low];
    int idx = find(preorder[pre_low], size, in_heads);
    tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
                   in_low, idx - 1, in_heads, size);
    tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
                    idx + 1, in_high, in_heads, size);
    return tn;
}

測驗二

測驗三

不用抄寫題目，專注探討程式原理、闡述你的洞見，還有你預期做哪些改進。

#define __const_hweight8(w)                                              \
    ((unsigned int) ((!!((w) & (1ULL << 0))) + (!!((w) & (1ULL << 1))) + \
                     (!!((w) & (1ULL << 2))) + (!!((w) & (1ULL << 3))) + \
                     (!!((w) & (1ULL << 4))) + (!!((w) & (1ULL << 5))) + \
                     (!!((w) & (1ULL << 6))) + (!!((w) & (1ULL << 7)))))

首先觀察這個巨集，拆分成多個小項進行分析。先來看 (!!((w) & (1ULL << 0))， w 與常數 1 進行 bitwise AND 再經過二次 NOT，根據 C 語言的 bit-field 裡所提及的，經過兩次 NOT，能確保結果一定是 0 或 1 ，若 w 的 least significant bit 為 1，則運算結果為 1 。可以歸納出 (!!((w) & (1ULL << n)) ，若 w 的第 n 位(從低位開始) bit 為 1 ，則運算結果為 1。總結來說，這個巨集就是對 w 的 least significant byte 進行 population count , __const_hweight16(w) 就是對最低位的兩個 BYTE 進行 popcount ，其餘以此類推。