2022q1 Homework1 (quiz1)

contributed by < 2020leon >

作業要求

• 重新回答第 1 周測驗題^{從測驗一到測驗四}，附帶的「延伸問題」也需要完成
  • 解釋程式運作原理時，應提供對應的 Graphviz 圖例，可參照 Linked List 題目 1 + 分析
• 比照 課前測驗參考解答: Q1, Linked list 題目分析 和 參考題解 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及進行相關實驗。
• 將你的共筆加到 2022q1 Homework1 (作業區)

測驗題目

測驗 1

測驗 1 資料結構

從題目中萃取資料結構。

struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };
typedef struct { int bits; struct hlist_head *ht; } map_t;
struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};

• map_t 為一雜湊表的實做，其最主要的成員為 ht ，即一指向 struct hlist_head 的指標。而 bits 則為定義其大小。然 bits 並非直接定義 map_t 的大小，其值表示以二為底的指數。更明確來說， map_t 的大小為二的 bits 次方。此可由以下巨集得知及函式實做得知
  ​​​​#define MAP_HASH_SIZE(bits) (1 << bits)
  

  ​​​​map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
  

• struct hlist_head 僅為 struct hlist_node 的包裝
• struct hlist_node 內含 next 指向下一個節點，及 pprev 指向前一個節點的 next 成員
• struct hash_key 可理解為繼承 struct hlist_node 的結構，用於儲存資料本身

測驗 1 填空

本題主要針對下方函式填空。

void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;

    struct hlist_head *h = &map->ht[hash(key, map->bits)];
    struct hlist_node *n = &kn->node, *first = h->first;
    AAA;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    BBB;
}

該函式主要目的為新增一筆資料至 hash table 中。藉 first->pprev = &n->next 可知該函式會將欲插入的資料放置至 list 的頭位置，因此 AAA 或 BBB 要分別針對 n 的 pprev 和 next 賦值。其中 n->next = first 、 n->pprev = &h->first （ h 為指向該 list 的頭結構 struct hlist_head 的指標），最後根據選項將上述二賦值式分別填入其中。

陳述式	答案
AAA	n->next = first
BBB	n->pprev = &h->first

測驗 2

測驗 2 資料結構

從題目中萃取資料結構。

struct ListNode {
    int val;
    struct ListNode *next;
};

• struct ListNode 為一簡單的單向 linked list

測驗 2 填空

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    if (COND1) {
        /* Remove all duplicate numbers */
        while (COND2)
            head = head->next;
        return deleteDuplicates(head->next);
    }

    head->next = deleteDuplicates(head->next);
    return head;
}

本題需針對上述程式碼中的 COND1 及 COND2 進行填空。藉由觀察上述程式碼可發現其為一遞迴函式：藉遞迴的方式將重複的數字移除。

填空時可由內而外解題。由於本函式的目的為將重複的數字移除，故先推論 COND2 為 head->val == head->next->val ，又因在比較時須確保 head->next 不為 NULL ，因此其應為 head->next && head->val == head->next->val 。再看 COND1 ，由於只有含重複數字的 list 才需進入該區塊，因此條件同 COND2 。

陳述式	答案
COND1	head->next && head->val == head->next->val
COND2	head->next && head->val == head->next->val

避免遞迴版本

struct ListNode *_deleteDuplicates(struct ListNode *head)
{
    struct ListNode *_head = NULL, **pptr = &_head;
    while (head) {
        while (head && head->next && head->val == head->next->val) {
            /* Remove all duplicate numbers */
            while (head->next && head->val == head->next->val)
                head = head->next;
            head = head->next;
        }
        *pptr = head;
        if (head) {
            pptr = &head->next;
            head = head->next;
        }
    }
    return _head;
}

Circular Doubly-linked List 版本

參見：linux2022-lab0#q_delete_dup

測驗 3

測驗 3 資料結構

typedef struct {
    int capacity, count;             
    struct list_head dhead, hheads[];
} LRUCache;
    
typedef struct {
    int key, value;
    struct list_head hlink, dlink;
} LRUNode;

• LRUCache 內含四個成員： capacity 為定義快取的大小、 count 為紀錄目前有效內容的變數、 dhead 為快取的所在、 hheads 為 flexible array member ，內容為所有的資料
• LRUNode 為用於儲存資料的結構，內含四個成員： key 為搜尋時的唯一值， value 為所儲存的資料、 hlink 為在 LRUCache::hheads[] 中的 struct list_head 結構、 dlink 則為在 LRUCache::dhead 中的 struct list_head 結構

測驗 3 填空

本題需針對下方各區塊程式碼的 MMM1 、 MMM2 、 MMM3 及 MMM4 進行填空，其均為 Linux 核心風格的 list 巨集，以 list_ 開頭。

首先是 MMM1 。

void lRUCacheFree(LRUCache *obj)
{       
    LRUNode *lru, *n;
    MMM1 (lru, n, &obj->dhead, dlink) {
        list_del(&lru->dlink);
        free(lru);
    }
    free(obj); 
}

其答案應為 list_for_each_entry_safe 。藉由函式名稱得知此函式應會刪除所有的節點，因此在所有 list_for_each_ 開頭及 _safe 結尾的巨集均為候選，再來根據資料型態可知應填 list_for_each_entry_save 。

再來是 MMM2 。

int lRUCacheGet(LRUCache *obj, int key)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM2 (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            return lru->value;
        }
    }
    return -1;
}

該函式功能為遍歷 obj->hheads[hash] 以尋找對應的值，並將找到的值放入 obj->dhead 中。根據功能及資料型態，答案應為 list_for_each_entry 。

最後是 MMM3 及 MMM4 。

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM3 (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            lru->value = value;
            return;
        }
    }

    if (obj->count == obj->capacity) {
        lru = MMM4(&obj->dhead, LRUNode, dlink);
        list_del(&lru->dlink);
        list_del(&lru->hlink);
    } else {
        lru = malloc(sizeof(LRUNode));
        obj->count++;
    }
    lru->key = key;
    list_add(&lru->dlink, &obj->dhead);
    list_add(&lru->hlink, &obj->hheads[hash]);
    lru->value = value;
}

MMM3 的功能同 MMM2 ，因此填 list_for_each_entry 。

MMM4 是要在快取已滿的情況下從相關的 list 移除節點。觀察 lRUCacheGet 與 lRUCachePut 可知最新的節點會在 list 的頭部，為符合 LRU ，須將位在最尾端的節點移除，因此答案應為 list_last_entry 。

陳述式	答案
MMM1	list_for_each_entry_save
MMM2	list_for_each_entry
MMM3	list_for_each_entry
MMM4	list_last_entry

測驗 4

測驗 4 資料結構

struct seq_node {
    int num;
    struct list_head link;
};

• struct seq_node 內含兩個成員： num 用於儲存數字、而 link 則是用於串接其他 struct list_head 物件用的

測驗 4 填空

本題需要填空的空格為 LLL 及 RRR 。

int longestConsecutive(int *nums, int n_size)
{
    int hash, length = 0;
    struct seq_node *node;
    struct list_head *heads = malloc(n_size * sizeof(*heads));

    for (int i = 0; i < n_size; i++)
        INIT_LIST_HEAD(&heads[i]);

    for (int i = 0; i < n_size; i++) {
        if (!find(nums[i], n_size, heads)) {
            hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size;
            node = malloc(sizeof(*node));
            node->num = nums[i];
            list_add(&node->link, &heads[hash]);
        }
    }

    for (int i = 0; i < n_size; i++) {
        int len = 0;
        int num;
        node = find(nums[i], n_size, heads);
        while (node) {
            len++;
            num = node->num;
            list_del(&node->link);

            int left = num, right = num;
            while ((node = find(LLL, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            while ((node = find(RRR, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            length = len > length ? len : length;
        }
    }

    return length;
}

此函式輸入一個整數陣列，輸出 Longest Consecutive Sequence 的長度。函式 longestConsecutive 上半部將整數陣列轉換成 struct list_head 。觀察 LLL 及 RRR 的位置，可知其嘗試在 list 中尋找是否有鄰近的數字。觀察變數 left 和 right 的宣告，可得其初始值均為 num ，也就是 node->num 。因此在尋找鄰近數字時，應尋找已經加一或減一的數值。綜觀選項， LLL 應填入 --left ，而 RRR 應填入 ++right 。

陳述式	答案
LLL	--left
RRR	++right