# 2024q1 Homework2 (quiz1+2)
contributed by < [Dainel-0224](https://github.com/Daniel-0224/lab0-c) >
## 第一周測驗題
### 測驗一
:::danger
不用列出參考題解，專注於程式碼和你的洞見。
:::
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
主要想法是先利用 `L` 與 `R` 決定出串列的頭尾，再以串列中的第一個節點作為 `pivot`，然後 `pivot->next` 逐一走訪串列，判斷節點和 pivot 之間的大小關係，以 `pivot` 為中心分成 `left` 串列及 `right` 串列，而 `begin` 與 `end` 這兩個陣列會新增紀錄三個子串列的開頭與結尾。
接下來以此串列為例：
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
node0[label=2]
node1[label=1]
node2[label=3]
node3[label=5]
NULL[label=NULL,shape=plaintext]
node0->node1->node2->node3->NULL
}
```
首先在 `while` 中將 `L` 及 `R` 指向最上層堆疊串列的頭和尾，並以串列起始當作 `pivot`。
```c
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
if (L != R) {
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
```
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
nodep[label=2]
node0[label=2]
node1[label=1]
node2[label=3]
node3[label=5]
NULL[label=NULL,shape=plaintext]
nodep->node0[color=white,arrowsize=0.00000000000000001]
node0->node1->node2->node3->NULL
{
rank="same";
pivot[label="pivot",shape=plaintext,fontcolor=blue]
pivot->nodep
}
{
rank="same";
L[label="L",shape=plaintext,fontcolor=red]
L->node0;
}
{
rank="same";
R[label="R",shape=plaintext,fontcolor=red]
R->node3;
}
{
rank="same";
n[label="n",shape=plaintext,fontcolor=red]
n->node1;
}
0[shape=plaintext,fontcolor=white]
n->0[color=red];
}
```
指標 `n` 會走訪每個節點判斷 `n->value` 及 `pivot->value` 之間的大小關係，將大於 `pivot->value` 的點放入 right 中，小於的放入 left。
```c
while (p) {
node_t *n = p;
p = p->next;
list_add(n->value > value ? &right : &left, n);
}
```
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
nodep[label=2]
node1[label=1]
node2[label=3]
node3[label=5]
NULL[label=NULL,shape=plaintext]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
nodep->NULL
node1->NULL1
node3->node2->NULL2
{
rank="same";
pivot[label="pivot",shape=plaintext,fontcolor=blue]
pivot->nodep
}
{
rank="same";
L[label="left",shape=plaintext,fontcolor=red]
L->node1;
}
{
rank="same";
R[label="right",shape=plaintext,fontcolor=red]
R->node3;
}
}
```
再用 `begin[]` 與 `end[]` 作為堆疊，用來紀錄子串列的比較範圍，子串列節點的值越小就會越早被放入堆疊。`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);
left = right = NULL;
i += 2;
```
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
node2[label=3]
node3[label=5]
NULL2[label=NULL,shape=plaintext]
node3->node2->NULL2
{
rank="same";
R[label="right",shape=plaintext,fontcolor=red]
R->node3;
}
}
```
最終将形成如下所示的堆叠
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
node0[label=2]
node1[label=1]
node2[label=3]
node3[label=5]
NULL[label=NULL,shape=plaintext]
node0->node1->node2->node3->NULL[color=white,arrowsize=0.00000000000000001]
begin0[label="begin[0]",shape=plaintext]
begin1[label="begin[1]",shape=plaintext]
begin2[label="begin[2]",shape=plaintext]
begin3[label="begin[3]",shape=plaintext]
begin4[label="begin[4]",shape=plaintext]
{rank="same"; begin0->node1}
{rank="same"; begin1->node0}
{rank="same"; begin3->node3}
{rank="same"; begin4->NULL}
{rank="same"; begin2->node2}
end0[label="end[0]",shape=plaintext]
end1[label="end[1]",shape=plaintext]
end2[label="end[2]",shape=plaintext]
end3[label="end[3]",shape=plaintext]
end4[label="end[4]",shape=plaintext]
{rank="same"; end0->begin0}
{rank="same"; end1->begin1}
{rank="same"; end3->begin3}
{rank="same"; end4->begin4}
{rank="same"; end2->begin2}
}
```
由於 `L=R`，將節點新增入 `Result` 串列中。
```c
else {
if (L)
list_add(&result, L);
i--;
}
```
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
node0[label=1]
node1[label=2]
node2[label=3]
node3[label=5]
NULL[label=NULL,shape=plaintext]
node0->node1->node2->node3->NULL
{
rank="same";
result[label="Result",shape=plaintext,fontcolor=Red]
result->node0
}
}
```
#### 可以改進的地方
我注意到可以改進的地方如下：
* `max_length` 的大小
* `pivot` 的挑選
### 測驗二
:::danger
不用列出參考題解，專注於程式碼和你的洞見。
:::
#### Timsort 原理
在現實世界中，許多資料往往是由一些已經部分排序的串列組合而成，於是 `Timsort` 的策略是首先識別出資料中已排序的子序列 (這些子序列稱為 `run`），然後透過不斷合併這些 `run` 來達成全資料範圍的排序。
首先要透過以下程式碼將 `doubly-linked list` 轉變成 `singly-linked list`。
```c
head->prev->next = NULL;
```
接下來這段程式碼將已排序的資料分成一個一個 `run`，而 `tp` 會指向最上層推疊的 `run`。
```c
do {
struct pair result = find_run(priv, list, cmp);
result.head->prev = tp;
tp = result.head;
list = result.next;
stk_size++;
tp = merge_collapse(priv, cmp, tp);
} while (list);
```
每個 `run` 的元素個數在 `find_run` 程式碼所示，存放在 `head->next->prev` 中。
```c
head->prev = NULL;
head->next->prev = (struct list_head *) len;
```
之後再呼叫 `merge_collapse` 檢查堆疊前三個 `run` 是否滿足:
1. A 的長度要大於 B 和 C 的長度總和。
2. B 的長度要大於 C 的長度。
並在以下情況進行合併
* `A <= B+C && A < C` 則 `AB` 合併
* `A <= B+C && A >= C` 則 `BC` 合併
* `B <= C` 則 `BC` 合併
直到所剩的堆疊小於三個，或是長度不滿足上述關係後，才進行統一合併。
最後透過 `build_prev_link` 恢復成雙向串列。
```c
static struct list_head *merge_collapse(void *priv,
list_cmp_func_t cmp,
struct list_head *tp)
{
int n;
while ((n = stk_size) >= 2) {
if ((n >= 3 &&
run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) ||
(n >= 4 && run_size(tp->prev->prev->prev) <=
run_size(tp->prev->prev) + run_size(tp->prev))) {
if (run_size(tp->prev->prev) < run_size(tp)) {
tp->prev = merge_at(priv, cmp, tp->prev);
} else {
tp = merge_at(priv, cmp, tp);
}
} else if (run_size(tp->prev) <= run_size(tp)) {
tp = merge_at(priv, cmp, tp);
} else {
break;
}
}
return tp;
}
```
#### 可以改進的地方
我注意到可以改進的地方如下：
* 在 `find_run` 中設計 `minrun` 使得串列分割成 2 的冪。
* Galloping mode 的實作，為了降低記憶體開銷及減少比較次數。
:::warning
期待你的程式碼。
:::
---
## 第二周測驗題
### 測驗一
一開始看到
```c
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
:::warning
你是文明人，不該「蠻」
:::
好奇為什麽這裡的 `node` 結構跟之前看到的雙向鏈結串列不同，在閱讀完〈[Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)〉後，了解這樣設計的好處是，當要刪除的節點是首個節點，即可藉由 `*pprev = next` 直接修改指標的指向，並且不用再將 `list_head` 傳遞給函式。
首先建立 `inorder hash table` ，然後呼叫 `dfs` 來建出 `binary tree`。
```c
static struct TreeNode *buildTree(int *preorder,
int preorderSize,
int *inorder,
int inorderSize)
{
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);
}
```
**DFS**
首先以前序的第一個節點當作樹根，再呼叫 `find` 找出他在 `hash table` 中的索引，然後在遞迴尋找左子樹和右子樹。
將左子樹的範圍設置為 (pre_low + 1, pre_low + (idx - in_low))，這是因為左子樹的大小是由中序走訪串列中該節點的索引位置決定的。
將右子樹的範圍設置為 (pre_high - (in_high - idx - 1), pre_high)，這是因為右子樹的大小也是由中序走訪串列中該節點的索引位置決定的。
```c
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;
}
```
### 測驗二
### 測驗三
Sign in with Wallet
Connect another wallet