# 2024q1 Homework2 (quiz1+2)
contributed by < [gawei1206](https://github.com/gawei1206) >
## 第一周測驗題
### 測驗一
#### `list_tail()` / `list_length()`
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(*left)->next; //AAAA
return *left;
}
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(*left)->next; //BBBB
}
return n;
}
```
`list_tail` 和 `list_length` 都需要從頭逐一走訪所有節點，`*left` 指向 `list` 的第一個節點，透過`left = &(*left)->next` 更改 `left` 持續走訪下一個節點
#### `q_sort()`
以非遞迴的方式來實作快速排序法，透過 `begin` 與 `end` 作為堆疊，紀錄串列的範圍，過程中判斷 `begin[i]` 與 `end[i]` 是否相等，如果相等就用 `list_add` 將 `pivot` 加入到 `result` 的開頭
```c
if (L)
list_add(&result, L);
```
若不相等，透過`begin[i]` 取出一段串列，並把第一個節點設為 `pivot` ，走訪串列時將節點的 `value` 與 `pivot` 比較，小於等於 `pivot` 的節點加入 `left` 串列中，大於 `pivot` 的節點加入 `right` 串列中
```c
while (p) {
node_t *n = p;
p = p->next; //CCCC
list_add(n->value > value ? &right : &left, n);
}
```
將一段串列分成 `left` 與 `right` 後，更新到 `begin` 與 `end` 中
```c
begin[i] = left;
end[i] = list_tail(&left); //DDDD
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right); //EEEE
```
#### 以圖形化觀察變化
第一輪：
以測驗一的例子來看，第一個點作為 `pivot` ，以 `p` 開始走訪每一個節點，將各個節點分配至 `left` 與 `right` 之中
分配完成後，以 `begin[i]` 、 `end[i]` 指向 `left` 開始與結束的位址， `begin[i+2]` 、 `end[i+2]` 指向 `right` 開始與結束的位址， `begin[i + 1]` 、 `end[i + 1]` 則指向 `pivot`
第二輪：
這時 `i = 2`，取出 `begin[2]` 紀錄的串列，並重複第一輪的操作
 
第三輪開始：
這時 `i = 4` ， `begin[4]` 指向 `NULL` ， `i--`
接下來 `i = 3` 、 `i = 2` 、 `i = 1` 時 `begin[i] == end[i]` ，將節點加入到 `result` 中，完成右半部的排序
最後剩下 `begin[0]` 、 `end[0]` 中有元素，重複上面的動作
再將這些節點加入 `result` 中，完成左半部的排序
#### 改善程式碼
- 使用第一周作業用到的 `element_t` 結構，透過雙向鏈結串列可以更快的存取最後一個節點，避免像函式 `list_tail` 一樣需要從頭走訪一次
- 在快速排序中 `pivot` 的選擇會影響執行的效率，選擇當前最大或最小的 `value` 作為 `pivot` 是最差的情況，可以透過 median of three 或 median of median 來改善這種情況
### 測驗二
## 第二周測驗題
### 測驗一
以DFS的方法重建一棵樹，首先以 `node_add` 這個函式將節點加入雜湊表中
```c
for (int i = 0; i < inorderSize; i++)
node_add(inorder[i], i, inorderSize, in_heads);
```
#### `node_add`
找出此節點應該存放的開頭位址，並以 `hlist_add_head` 將他加入鏈結串列的開頭
```c
int hash = (val < 0 ? -val : val) % size;
hlist_add_head(&on->node, &heads[hash]); //DDDD
```
#### `hlist_add_head`
從[Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)可以看到 `hlist_node` 的結構與使用方式
Linux 核心的 hash table 實作中，用以處理 hash 數值碰撞的 `hlist_node` 的結構:
```c
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
再來可以知道知到 `next` 指向相鄰的節點本身，而 `pprev` 指向指著自身節點的指標
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
list_head[label = "<m>list_head | <n>first"]
node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", group = list];
node_3[label = "<m>hlist_node_3 | {<p>pprev | <n>next}", group = list];
NULL[shape = plaintext, label = "NULL", group = list]
{rank = "min" list_head}
list_head -> node_1 -> node_2 -> node_3[
weight = 10, style = invis
]
list_head:n -> node_1:m;
node_1:p -> list_head:n;
node_1:n -> node_2:m;
node_2:p -> node_1:n;
node_2:n -> node_3:m;
node_3:p -> node_2:n;
node_3:n -> NULL;
}
```
```c
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
if (h->first)
h->first->pprev = &n->next;
n->next = h->first; //AAAA
n->pprev = &h->first;
h->first = n;
}
```
所以在 `hlist_add_head` 中要插入一個節點時，會先判斷 `hlist_head` 是否已經有儲存節點，若存在節點，先將第一個節點 `h->first` 的 `pprev` 指向 `&n->next`，再來將 `n->next` 指向第一個節點 `h->first`
#### `find`
```c
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, &heads[hash]) { //BBBB
struct order_node *on = list_entry(p, struct order_node, node); //CCCC
if (num == on->val)
return on->idx;
}
return -1;
}
```
再算出雜湊值後，找出對應的雜湊表開頭，走訪並找到符合條件的節點，回傳數值在 `inorder` 中的索引值
#### `dfs`
```c
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);
```
最後以dfs重建整棵樹時從 `preorder[0]` 開始，前序排列中第一個點為 root ，找出他在 `inorder` 中的索引，計算出 `preorder` 與 `inorder` 中左右子樹的索引範圍，透過遞迴重建整棵樹
#### 左子樹
```graphviz
digraph a {
node [shape= "none"]
pre[shape = record, label = " <l0> 3 | <l1> 9 | <l2> 20 | <l3> 15 | <l4> 7 ",height=0.2, width=2];
p_left_h [label="pre_low + 1", fontcolor="red" ]
p_left_t [label="pre_low + (idx - in_low)", fontcolor="red" ]
p_left_h->pre:l1
p_left_t->pre:l1
preorder->pre:l0
//
in[shape = record, label = " <l0> 9 | <l1> 3 | <l2> 15 | <l3> 20 | <l4> 7 ",height=0.2, width=2];
i_left_h [label="in_low", fontcolor="red" ]
i_left_t [label="idx - 1", fontcolor="red" ]
in:l0 -> i_left_h [dir=back]
in:l0 -> i_left_t [dir=back]
inorder->in:l0
}
```
#### 右子樹
```graphviz
digraph a {
node [shape= "none"]
pre[shape = record, label = " <l0> 3 | <l1> 9 | <l2> 20 | <l3> 15 | <l4> 7 ",height=0.2, width=2];
p_right_h [label="pre_high-(in_high-idx-1)", fontcolor="blue"]
p_right_t [label="pre_high", fontcolor="blue"]
p_right_h -> pre:l2
p_right_t -> pre:l4
preorder->pre:l0
//
inorder
in[shape = record, label = " <l0> 9 | <l1> 3 | <l2> 15 | <l3> 20 | <l4> 7 ",height=0.2, width=2];
i_right_h [label="idx + 1", fontcolor="blue"]
i_right_t [label="in_high", fontcolor="blue"]
i_right_h -> in:l2
i_right_t -> in:l4
inorder->in:l0
}
```
#### 延伸問題
### 測驗二
#### 程式碼解說
在 [Leetcode 146. LRU Cache](https://leetcode.com/problems/lru-cache/) 中我們得知三個函式的功能:
- `lRUCacheCreate` : 創建大小為 `size` 的快取
- `lRUCacheGet` : 如果 `key` 存在快取回傳 `value`，否則回傳 -1
- `lRUCachePut` : 如果 `key` 存在，更新快取中的 `key,value` ，否則新增 `key,value` 至快取中，如果超過快取大小，移除最久沒使用的 `key`
為了完成程式碼，需了解以下結構:
```c
typedef struct {
int capacity;
int count;
struct list_head dhead;
struct hlist_head hhead[];
} LRUCache;
typedef struct {
int key;
int value;
struct hlist_node node;
struct list_head link;
} LRUNode;
```
`LRUCache` 中的 `dhead` 使用雙向環狀串列來紀錄快取的使用情形，近期有使用過的節點會越靠近 `dhead`，`hhead[]` 則是像測驗一中一樣，用雜湊表來紀錄節點，提高存取節點的速度
`LRUNode` 中的 `node` 會根據雜湊值被紀錄在對應的 `hhead[]` 裡，`link` 則會加入 `dhead` 的串列中，根據使用情形改變在串列的位置
#### lRUCacheGet
```c
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, node); //HHHH
if (cache->key == key) {
list_move(&cache->link, &obj->dhead); //IIII
return cache->value;
}
}
return -1;
}
```
先以 `value` 計算出雜湊值，再至對應的串列逐一走訪，找出 `key` 值相符的 `cache` ，如果資料存在，將找到的節點更新至 `dhead` 的開頭
#### lRUCachePut
```c
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, node); //JJJJ
if (c->key == key) {
list_move(&cache->link, &obj->dhead); //KKKK
cache = c;
}
}
if (!cache) {
if (obj->count == obj->capacity) {
cache = list_last_entry(&obj->dhead, LRUNode, link);
list_move(&cache->link, &obj->dhead);
hlist_del(&cache->node);
hlist_add_head(&cache->node, &obj->hhead[hash]);
} else {
cache = malloc(sizeof(LRUNode));
hlist_add_head(&cache->node, &obj->hhead[hash]);
list_add(&cache->link, &obj->dhead);
obj->count++;
}
cache->key = key;
}
cache->value = value;
}
```
主要在做三件事，
1. 第一段與 `lRUCacheGet` 相似，目的是查看欲加入的節點是否存在快取中，如果存在更新他在 `dhead` 中的位置
2. 再來是如果想加入節點但空間不足的情況，會將最久沒使用的節點刪除，並加入新節點在 `dhead` 開頭
3. 最後可以加入節點，配置節點需要的空間，插入新節點到雜湊表，也加入到 `dhead` 開頭
### 測驗三
Sign in with Wallet
Connect another wallet