# 2024q1 Homework2 (quiz1+2)
contributed by < [`Lccgth`](https://github.com/Lccgth) >
## 第一週測驗題
### 測驗 `1`
#### `list_add()`
將一個新的節點添加到鏈結串列的開頭處。
`node_t` 為要加入到鏈結串列的節點，而 `*list` 為指向鏈結串列的開頭的指標。
```c
node_t->next = *list;
*list = node_t;
```
```graphviz
digraph list_add {
rankdir=LR;
node [shape=box, fontname = "Helvetica"];
label="Before Adding New Node";
"*list" -> node1;
subgraph cluster {
label = "";
node1 -> node2 -> null;
}
}
```
```graphviz
digraph list_add {
rankdir=LR;
node [shape=box, fontname = "Helvetica"];
label = "After Adding New Node";
"*list" -> node_t;
subgraph cluster {
label = "";
node_t -> node1 -> node2 -> null;
}
}
```
#### `list_tail()`
返回鏈結串列尾部的節點。
從 `*left` 開始逐一走訪鏈結串列中的節點，直到找到尾部節點就將其回傳。
```c
while ((*left) && (*left)->next)
left = &((*left)->next);
```
#### `list_length()`
返回鏈結串列的長度。
從 `*left` 開始逐一走訪鏈結串列中的節點，並同時計算長度，走訪完後回傳，此函式的 `**left` 需要指向鏈結串列的開頭，否則長度會計算錯誤。
```c
while (*left) {
++n;
left = &((*left)->next);
}
```
#### `list_construct()`
創建一個節點，並將其加到鏈結串列的開頭處。
使用 `malloc()` 分配記憶體空間，再將新節點的 `next` 指向鏈結串列的開頭，最後將新節點的 `value` 設成 `n`。
```c
node_t *node = malloc(sizeof(node_t));
node->next = list;
node->value = n;
```
#### `list_free()`
逐一釋放鏈結串列的節點所使用到的記憶體空間。
逐一走訪鏈結串列，並同時釋放目前走訪到的節點使用到的記憶體空間。
進行小幅改寫移除迴圈中的 `if` 判斷式，使程式碼更加簡潔。
```diff
- node_t *node = (*list)->next;
+ node_t *node;
while (*list) {
- free(*list);
- *list = node;
- if (node)
- node = node->next;
+ node = *list;
+ list = (*list)->next;
+ free(node);
}
```
#### `list_is_ordered()`
檢查鏈結串列是否已經排序完成。
逐一走訪鏈結串列中的節點，並和目前為止觀察到的最大值 (`value`) 比較，若當前節點小於 `value`，回傳 `false`，若當前節點大於 `value`，則更新 `value` 成目前節點的值。
我將一開始的 `value` 就設定為開頭節點的 `value`，在迴圈內就不用判斷是否為第一次進入迴圈，但需要先判斷一次 `list` 是否為 `NULL`。
```diff
- bool first = true;
- int value;
+ if (!list)
+ return true;
+ int value = list->value;
+ list = list->next;
while (list) {
- if (first) {
- value = list->value;
- first = false;
- } else {
- if (list->value < value)
- return false;
- value = list->value;
- }
+ if (list->value < value)
+ return false;
+ value = list->value;
list = list->next;
}
```
#### `shuffle()`
打亂鏈結串列中的節點順序。
逐一走訪鏈結串列的節點，並隨機選一個後續節點和目前節點交換。
此方法只在 `n < RAND_MAX` 時有效，因為 `rand()` 會返回一個 0 到 RAND_MAX 的隨機數，若 `n >= RAND_MAX` 時會導致無法產生足夠均勻的隨機數。
```c
for (size_t i = 0; i < n - 1; i++) {
size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
int t = array[j];
array[j] = array[i];
array[i] = t;
}
```
#### `quick_sort()`
使用非遞迴的方式實作快速排序。
每一組 `begin[i]` 和 `end[i]` 表示第 i 個鏈結串列，利用 `i` 選擇目前要處理的串列是哪一個。
迴圈會先判斷目前的 `begin[i]` 是否和 `end[i]` 相等，如果相等就直接將此串列加入 `result` 的開頭。
```c
if (L != R){
// ...
} else {
if (L)
list_add(&result, L);
}
```
接著將目前串列的開頭設為 `pivot`，並從下一個節點開始逐一走訪，如果走訪到的節點小於 `pivot`，就將其加入 `left`，反之則加入 `right`。
```c
while (p) {
node_t *n = p;
p = p->next;
list_add(n->value > value ? &right : &left, n);
}
```
然後更新 `begin` 和 `end`，將 `begin[i]` 設為 `left`，`begin[i + 1]` 設為 `pivot`，而 `begin[i + 2]` 設為 `right`。
```c
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);
```
最後 `begin` 中的每條串列都會只有一個節點，並會依序被加入到 `result` 中，完成排序。
#### 快速排序法圖解
例題
```graphviz
digraph list_add {
rankdir=LR;
pivot [label="pivot" shape=plaintext];
NULL [shape=none];
4 -> 1 -> 3 -> 5 -> 2 -> 7 -> NULL;
{ rank=same; pivot -> 4; }
}
```
Step 1:
將 `4` 設為 `pivot`，逐一走訪串列，將比 `pivot` 小的節點放到 `begin[0]`，比 `pivot` 大的放到 `begin[2]`，`pivot` 放在 `begin[1]`。
```graphviz
digraph list_add {
rankdir=LR;
begin0 [label="begin[0]", shape=none];
begin1 [label="begin[1]", shape=none];
begin2 [label="begin[2]", shape=none];
begin0 -> 2 -> 3 -> 1;
begin1 -> 4;
begin2 -> 7 -> 5;
}
```
Step 2:
將 `7` 設為 `pivot`，逐一走訪 `begin[2]`，將比 `pivot` 小的節點放到 `begin[2]`，`pivot` 放在 `begin[3]`。
```graphviz
digraph list_add {
rankdir=LR;
begin0 [label="begin[0]", shape=none];
begin1 [label="begin[1]", shape=none];
begin2 [label="begin[2]", shape=none];
begin3 [label="begin[3]", shape=none];
begin0 -> 2 -> 3 -> 1;
begin1 -> 4;
begin2 -> 5;
begin3 -> 7;
}
```
Step 3:
因為 `begin[3]`、`begin[2]`、`begin[1]` 都只有一個節點，所以依序加入到 `result` 中。
```graphviz
digraph list_add {
rankdir=LR;
result [label="result", shape=none];
begin0 [label="begin[0]", shape=none];
result -> 4 -> 5 -> 7;
begin0 -> 2 -> 3 -> 1;
}
```
Step 4:
將 `2` 設為 `pivot`，逐一走訪 `begin[0]`，將比 `pivot` 小的節點放到 `begin[0]`，比 `pivot` 大的放到 `begin[2]`，`pivot` 放在 `begin[1]`。
```graphviz
digraph list_add {
rankdir=LR;
result [label="result", shape=none];
begin0 [label="begin[0]", shape=none];
begin1 [label="begin[1]", shape=none];
begin2 [label="begin[2]", shape=none];
result -> 4 -> 5 -> 7;
begin0 -> 1;
begin1 -> 2;
begin2 -> 3;
}
```
Step 4
因為 `begin[3]`、`begin[2]`、`begin[1]` 都只有一個節點，所以依序加入到 `result` 中。
```graphviz
digraph list_add {
rankdir=LR;
result [label="result", shape=none];
result -> 1 -> 2 -> 3 -> 4 -> 5 -> 7;
}
```
### 測驗 `2`
#### Timsort
結合了 Merge sort 和 Insertion sort 的優點，適用於部分已經排序完成的串列，且為一種穩定 (stable) 的排序法。
#### `run_size()`
計算並返回一段以排序好的元素 (run) 大小，此大小被儲存在 `head->next->prev` 中
#### `merge()`
合併兩段已排序好的鏈結串列，會依序將目前兩個串列開頭處較小的節點加入到 `head` 後。
可使用 `while` 替換 `for`，並在其中一個串列已走訪完後跳出迴圈，將剩下的串列直接串接在尾部。
新增參數 `*last` 表示合併完的串列要插入的位置，將 `merge_final()` 中的功能進行整合，只要將 `*last` 設定為 `NULL` 就是原本 `merge()` 的功能，其他情況則會是 `merge_final()` 的功能。
```diff
struct list_head *head;
struct list_head **tail = &head;
- for (;;) {
+ while (a && b)
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
- if (!a) {
- *tail = b;
- break;
- }
} else {
*tail = b;
tail = &b->next;
b = b->next;
- if (!b) {
- *tail = a;
- break;
- }
}
}
+ *tail = a ? a : b;
+ if (last)
+ build_prev_link(last, last->prev, head);
```
#### `build_prev_link()`
將 `tail` 和 `list` 拼接起來，並設定其中節點的 `prev`，使其成為環狀雙向鏈結串列。
```c
tail->next = list;
do {
list->prev = tail;
tail = list;
list = list->next;
} while (list);
tail->next = head;
head->prev = tail;
```
#### `merge_final()`
將最後兩段 run 進行合併，並使用 `build_prev_link()` 調整串列，使其成為環狀雙向鏈結串列。
此函式和 `merge()` 的重複性太高，可以進行重構使程式碼更精簡。
#### `find_run()`
找到一段排序好的串列，若為降序排列則反轉其為升序。
#### `merge_at()`
在特定位置 `at` 合併兩個串列，並同時更新 `stk_size` (run 的數量)。
#### `merge_force_collapse()` 和 `merge_collapse()`
當 run 的數量達到一定條件時就選擇合併一些 run，以提升後續合併時的效率。
#### `timsort()`
將一鏈結串列依照 `find_run()` 分成多段 run，並依照 `merge_force_collapse()` 和 `merge_collapse()` 的規則進行適當的合併，最後再使用 `build_prev_link()` 進行串列的調整以完成排序。
## 第二週測驗題
### 測驗 `1`
#### `INIT_HLIST_HEAD()`
藉由將 `h->list` 設為 `NULL` 來初始化 `hlist`。
#### `hlist_add_head()`
將一個的新的節點插入到 `hlist` 的開頭處。
如果 `hlist` 不為空，就將開頭處節點的 `pprev` 指向 `n->next` 的位址，接著依序更新新節點的 `next` 和 `pprev`，最後將開頭節點設為 `n`。
```c
if (h->first)
h->first->pprev = &n->next;
n->next = h->first;
n->pprev = &h->first;
h->first = n;
```
#### `find()`
在一組 `hlist` 中尋找 `num` 的 `idx`。
先通過計算 `hash` 得知此數在 `heads` 中的哪一個串列中，接著逐一走訪此串列的節點來和 `num` 做比對。
```c
int hash = (num < 0 ? -num : num) % size;
hlist_for_each (p, &heads[hash]) {
struct order_node *on = list_entry(p, struct order_node, node);
if (num == on->val)
return on->idx;
}
```
#### `dfs()`
深度優先搜尋，根據前序和中序建立出二元樹。
因前序中首節點為樹的根節點，再依據中序得知每個節點是在根節點的左子樹還是右子樹中，依序建立出獨一無二的二元樹。
#### `node_add()`
將新節點根據雜湊函式加入到 `heads` 中，這裡的雜湊函式會返回一個 0 到 size - 1 間的整數。
```c
on->val = val;
on->idx = idx;
int hash = (val < 0 ? -val : val) % size;
hlist_add_head(&on->node, &heads[hash]);
```
#### `buildTree()`
先根據中序節點數初始化對應數量的 `hlist`，接著將這些節點根據雜湊函式加入到對應的 `hlist` 中，最後使用 `dfs()` 來建立出二元樹。
### 測驗 `2`
#### `hlist_del()`
將 `hlist` 中的節點 `n` 刪除。
```c
struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
```
#### `list_add()`
將新的節點插入到串列的開頭處。
#### `list_del()`
將特定的節點從串列中刪除。
#### `list_move()`
利用 `list_del()` 和 `list_add()` 將特定節點移到串列的開頭處。
#### `lRUCacheCreate()`
創立一個指定大小的快取，並初始化其 `dhead` 和 `hhead`。
#### `lRUCacheFree()`
逐一走訪串列中的節點，並依序釋放占用的記憶體空間。
```c
list_for_each_safe (pos, n, &obj->dhead) {
LRUNode *cache = list_entry(pos, LRUNode, link);
list_del(&cache->link);
free(cache);
}
free(obj);
```
#### `lRUCacheGet()`
從 LRU 快取中獲取 `key` 對應的值。
先透過取餘數的方法計算 `hash`，再逐一走訪對應的串列，當找到對應的值時，將其移到串列的開頭處，表示最近被訪問過。
```c
int hash = key % obj->capacity;
hlist_for_each (pos, &obj->hhead[hash]) {
LRUNode *cache = list_entry(pos, LRUNode, link);
if (cache->key == key) {
list_move(&cache->link, &obj->dhead);
return cache->value;
}
}
```
#### `lRUCachePut()`
在 LRU 快取中新增或更新 key-value。
此函式和 `lRUCacheGet()` 有高度相似的程式碼，可將其獨立成一個函式使程式碼更精簡。
```diff
+ LRUNode* findLRUNode(LRUCache *obj, int key)
+ {
+ int hash = key % obj->capacity;
+ struct hlist_node *pos;
+ hlist_for_each(pos, &obj->hhead[hash]) {
+ LRUNode *node = list_entry(pos, LRUNode, node);
+ if (node->key == key)
+ return node;
+ }
+ return NULL;
+ }
int lRUCacheGet(LRUCache *obj, int key)
{
- int hash = key % obj->capacity;
- struct hlist_node *pos;
- hlist_for_each (pos, &obj->hhead[hash]) {
- LRUNode *cache = list_entry(pos, LRUNode, link);
- if (cache->key == key) {
- list_move(&cache->link, &obj->dhead);
- return cache->value;
- }
- }
+ LRUNode *cache = findLRUNode(obj, key);
+ if (cache) {
+ list_move(&cache->link, &obj->dhead);
+ return cache->value;
+ }
return -1;
}
void lRUCachePut(LRUCache *obj, int key, int value)
{
- LRUNode *cache = NULL;
- int hash = key % obj->capacity;
- struct hlist_node *pos;
- hlist_for_each (pos, &obj->hhead[hash]) {
- LRUNode *c = list_entry(pos, LRUNode, link);
- if (c->key == key) {
- list_move(&cache->link, &obj->dhead);
- cache = c;
- }
- }
+ LRUNode *cache = findLRUNode(obj, key);
+ if (cache) {
+ list_move(&cache->link, &obj->dhead);
+ cache->value = value;
+ }
// ...
}
```
### 測驗 `3`
#### `__ffs()`
利用二分搜尋法的方式依序找到 `word` 第一個值為 1 的位元。
```c
if ((word & 0xffffffff) == 0) {
num += 32;
word >>= 32;
}
```
#### `__clear_bit()`
將特定位元的值設為 0。
`BITMASK(n)` 會返回一個只有第 n 個位元為 1 的數，將其作反轉就能得到只有第 n 個位元為 0 的數。
```c
unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);
*p &= ~mask;
```
#### `fns()`
在 `word` 裡找到第 n 個值為 1 的位元。
#### `find_nth_bit()`
在一個記憶體區域中找到第 n 個值為 1 的位元。
#### `FIND_NTH_BIT()`
逐一走訪記憶體區域的 unsigned long，使用 `hweight_long()` 計算每單位中位元值為 1 的數量，從而找到第 n 個值為 1 的位元位置
```c
if (sz & BITS_PER_LONG)
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);
```
Sign in with Wallet
Connect another wallet