2024q1 Homework2 (quiz1+2)

contributed by <padaray>

第一週測驗題

題目連結

測驗 1

參考資料是 Optimized QuickSort ，此方法實作非遞迴的快速排序法

鏈結串列結構

快速排序法使用的函式

1. list_add
   此函式將節點 node_t 插入串列 list ，使節點 node_t 成為 list 串列的第一個節點，傳入的參數為 **list 原因是使用 *list 會複製一個 list 串列副本，因此要使用指標的指標來避免此問題

2. list_tail
   此函式會逐一走訪每個節點，走訪到最後一個節點時，回傳該節點的記憶體位置，傳入的參數為 **left 原因是避免使用到條件判斷式，以此精簡程式碼
   完整程式碼，已填空遮蔽部分 AAAA

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &(*left)->next;
    return *left;
}

3. list_length
   初始化變數 n 為 0，逐一走訪每個節點，每走訪一個節點變數 n + 1，最後回傳變數 n
   完整程式碼，已填空遮蔽部分 BBBB

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &(*left)->next;
    }
    return n;
}

快速排序法程式碼

quick_sort
先呼叫函式 list_length 計算串列長度 n，以此得知堆疊所需要的配置的空間大小， begin[] 和 end[] 分別儲存串列的頭和尾，result 儲存排序後的串列， left 儲存小於 pivot 的節點， right 儲存大於 pivot 的節點

int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n;
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;

begin[0] = *list;
end[0] = list_tail(list);

初始化變數 L 和 R 為 begin[] 和 end[] ， L 和 R 指向不同節點時，代表該串列節點數大於一，節點數不足二時，直接將該節點加入 result 串列

 if (L != R) {
     ...
 } else {
    if (L)
        list_add(&result, L);
    i--;
}

    node_t *pivot = L;
    value = pivot->value;
    node_t *p = pivot->next;
    pivot->next = NULL;

從第二個節點開始逐一走訪，當此節點 value 小於 pivot->value 加入 left 串列，反之加入 right 串列，下圖為範例：

while (p) {
    node_t *n = p;
    p = p->next;
    list_add(n->value > value ? &right : &left, n);
}

將 left 串列也就是比 pivot 小的節點儲存在堆疊下方，比 pivot 大的節點儲存在堆疊下方，並且把 left 和 right 串列清空，之後重複執行前面的步驟，下圖為範例：

    begin[i] = left;
    end[i] = list_tail(&left);
    begin[i + 1] = pivot;
    end[i + 1] = pivot;
    begin[i + 2] = right;
    end[i + 2] = list_tail(&right);

    left = right = NULL;
    i += 2;

測驗 2

第二週測驗題

題目連結

測驗 1

題目為給定一個二元樹的前序(preorder)和中序(inorder)，以此重建二元樹

hash key 結構

hash table 結構

使用的函式：
hlist_add_head
此函式是為了將一個 hash_key 插入 h->first。

• 若列表不為空，將 first->pprev 也就是本來節點一的 pprev 指向 n->next ， n->next 指向 h->first ， n->pprev 指向 &h->first ，最後 h->first 指向 n，即完成將新的節點，加入 first 第一個指向的地點。
• 實際方式如下方圖示：

node_add
此函式目的為加入一個新的節點進入 hash table。

• 初始化 order_node 的記憶體空間，傳入 idx 和 val，使用 hash 函式將存入的位置打亂，hash 函式是將 val 絕對值後除餘 size 值
• 最後用 hlist_add_head 函式插入 hash table
• 下方以 hash table size 為 5 ，val 為 4 為例：

dfs
此函式為深度優先演算法，主要目的是建構二元樹。

• 先使用 find 函式查找 tn 在 inorder 內的位置 idx
• 接著利用 idx 就可以知道左子樹是in_low 到 idx-1，右子樹是 idx+1 到 in_hight 。
• 最後將左子樹和右子樹放進 dfs 函式，回傳 tn

主程式：
buildTree
此函式目的為根據給定的前序和中序，建構一個二元樹，也就是題目要求。

• 使用 hash table 的原因是為了將搜尋的時間複雜度下降，因此一開始會將所有的值加入到 hash table 中
• 遞迴呼叫 dfs 函式建構左右子樹

測驗 2

實作 LRU Cache

測驗二的 hash table 程式碼與測驗一相同，因此不多贅述。

LRUNode 結構：LRU Cache 中 Node 的結構，其中包含 key-value 對、list 結構和 hlist 結構

LRUCache 結構：整個 LRU Cache，包括容量、當前儲存的數量…等

LRU Cache 使用的函式：

lRUCacheCreate
此函式用於創建一個空的 LRUCache。

• 輸入參數為 capacity 也就是 cache 的容量( hlist_head 串列的長度 )，初始化所有的變數，回傳一個完整 LRU Cache

lRUCacheFree
此函式用於刪除整個 LRU Cache。

• 使用 list_for_each_safe 函式走訪每個節點，同時斷開目前節點與串列的連結，並且釋放此節點空間

lRUCacheGet
此函式用於取得 key 在 LRUCache 中所對應的 value。

• 先將輸入的 key 值除餘 LRUCache->capacity 得到變數 hash
• 使用 hlist_for_each 函式走訪 LRUCache->hhead[hash] 的每個節點
• 若有和輸入變數 key 值相同的節點，則將此節點使用 list_move 函式移動到 hhead[hash] 串列的第一個節點

lRUCachePut
此函式用於在 LRUCache 中放入 key-value。

• 前半部操作與 lRUCacheGet 相似，若此 key 已經存在，則將此節點移動到串列的第一個。
• 當節點不存在時，判斷 LRUCache 是否已滿 ( count == capacity )，若已滿則使用 list_move 函式將最後節點移至第一個節點，使用 hlist_del 函式刪除此節點，最後用 hlist_add_head 函式加入新的節點。
• LRUCache 沒滿則直接插入新節點即可

測驗 3

const_hweightn: n = 8, 16, 32, 64
這四個巨集用來計算在一段二進制數列中，共有幾個位元為 1

FIND_NTH_BIT
這個巨集用來查看第 N 個 bit 為 0 或 1。

• 先計算 word 中被設置的位元數目，比較查找第 num 個被設置的位元。若找到則回傳該位元的索引值；否則，繼續往下個位元找。

__ffs
此函式全名為 find first bit，目的為找到第一個位元數為 1 的位置。

• num 變數用來計算第一個位元 1 的位置。先檢查第一個位元是否在後 32 個 bits，如果是 num + 32
• 檢查第一個位元 1 的位置是否在後 16 個 bits，如果是 num + 16，依此類推，持續執行檢查到最後一位。

fns
此函式全名為 find N'th set bit，目的為找到第 N 個位元數為 1 的位置。

• 先呼叫 __ffs 函式找到第一個位元數 1
• 呼叫 __clear_bit 函式清除該位元並且將 N - 1，持續上述動作直到 N 為 0

主程式：
find_nth_bit
此函式目的為在一段二進制數列中，找到第 N 個位元為 1 的位置。

• 先檢查要查找的第 n 位是否超過傳入的參數 size 的範圍
• 使用 small_const_nbits 確認要搜索的範圍是否不超過一個 word，是的話使用 fnc 函式找到 bit 為 1 的位置
• 要搜索的範圍超過一個 word 時，使用 FIND_NTH_BIT 函式確認第一個 bit 為 1 的位置