# 2024q1 Homework2 (quiz1+2)
contributed by < [steven523](https://github.com/steven523) >
## 第一週測驗題
### 測驗一
此題參考〈[Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)〉，透過 quicksort() 實作非遞迴的快速排序法，並運用 stack 來模擬遞迴函式呼叫
以下是鏈結串列的結構體，有一個 long 儲存的資料及一個 `next` 指標，可判斷其為單向的鏈結串列，還有兩個指標為 `left` 和 `right`
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t
```
```graphviz
digraph "__node" {
rankdir=LR;
node[shape=record, style=bold];
subgraph cluster_0 {
node [shape=record];
value [label="value"];
ptr [label="{<node> left |<node> right}|next"];
style=bold;
label=node_t
}
}
```
首先程式一開始為 `test_arr` 這個整數型態的陣列配置記憶體空間，接著指派 0~99999 給它，並呼叫 `shuffle` 函式將陣列中的元素打亂
`list_construct` 函式用於建立一個新節點，並將其插入到鏈結串列 `list` 的頭部，然後返回鏈結串列的首節點
所以下列程式整體上來說是透過 while 將 `test_arr[count]` 的值逐一插入 `list` 頭部，最終形成的鏈結串列會與 `test_arr[count]` 順序相反
```c
node_t *list_construct(node_t *list, int n)
{
node_t *node = malloc(sizeof(node_t));
node->next = list;
node->value = n;
return node;
}
int main(int argc, char **argv)
{
node_t *list = NULL;
...
while (count--)
list = list_construct(list, test_arr[count]);
...
}
```
```graphviz
digraph list_construct {
node[shape=record];
rankdir=LR;
n1[label="{<data> node1|<next>}", color=red];
edge[tailclip=false,arrowtail=dot,dir=both];
n1:next:c -> NULL;
}
```
```graphviz
digraph list_construct {
node[shape=record];
rankdir=LR;
n1[label="{<data> node1|<next>}"];
n2[label="{<data> node2|<next>}", color=red];
edge[tailclip=false,arrowtail=dot,dir=both];
n2:next:c -> n1;
n1:next:c -> NULL;
}
```
:::info
`list_add` 與 `list_construct` 用途相似，都是將節點插入鏈結串列的頭部，只差在 `list_construct` 傳入值的型態是 `int`，所以要為其先用 `malloc` 配置一個記憶體位置
:::
`qiuck_sort` 函式在每一輪迴圈都會經過以下步驟
首先宣告`L` 及 `R` 分別指向鍵結串列的第一個節點與最後一個節點，並指派第一個節點為 pivot，`p` 為下一個節點，最後將 `pivot` 與原鏈結串列分開
利用以下程式碼走訪整個串列，並判斷目前的節點是否大於 `pivot->value`，是的話加入 `right`，否則加入 `left`
```c
while (p) {
node_t *n = p;
p = p->next;
list_add(n->value > value ? &right : &left, n);
}
```
此為原鏈結串列初始化過後的樣子，`left` 和 `right` 在每次回全結束前都會重設為空的鏈結串列
```graphviz
digraph G {
node[shape=plaintext];
pivot;
L
R
p [fontcolor="red"];
left;
right;
node[shape=box];
n0 [label= "3"];
n1 [label= "2"];
n2 [label= "1"];
n3 [label= "4"];
n4 [label= "5"];
{
rank="same";
n0 -> NULL
n1 -> n2
n2 -> n3
n3 -> n4
}
pivot -> n0;
L -> n0;
R -> n4;
p -> n1;
}
```
因為 `p` 指向的值 2 小於 `pivot` 的 3，所以將 `p` 指向的節點透過 `list_add` 函式加入 `left` 頭部， 接著 `p` 指向下一個節點
```graphviz
digraph G {
node[shape=plaintext];
pivot;
L
R
p [fontcolor="red"];
left;
right;
node[shape=box];
n0 [label= "3"];
n1 [label= "2"];
n2 [label= "1"];
n3 [label= "4"];
n4 [label= "5"];
{
rank="same";
n0 -> NULL
n2 -> n3
n3 -> n4
}
pivot -> n0;
L -> n0;
R -> n4;
p -> n2;
left -> n1;
}
```
持續同樣操作直到整個鏈結串列走訪完的結果會像下圖
```graphviz
digraph G {
node[shape=plaintext];
pivot;
left;
right;
node[shape=box];
n0 [label= "3"];
n1 [label= "2"];
n2 [label= "1"];
n3 [label= "4"];
n4 [label= "5"];
{
rank="same"
}
pivot -> n0;
left -> n2 -> n1;
right -> n4 -> n3;
}
```
```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` 頭尾放入 beg[i], end[i] 中來取代原本的整個佇列的位置，right 頭尾則放入 beg[i+2], end[i+2]，並將 i+2 後重新下輪迴圈進行排序
如果 `L != R` 成立，即 `beg[i]` 等於 `end[i]`，代表此佇列只有一個節點，此時就將該節點加入 `result` 。接著 i-- 後會將上圖 `pivot` 節點再加入 `result` ，最後對上圖 left 進行排序直到整個鏈結串列排序完成。
整體插入 `result` 順序為 `right` -> `pivot` -> `left`，因為 `list_add` 是從頭部插入所以能知道結果是由小到大排序好的鏈結串列
:::danger
不用列出參考題解，你專注在程式碼的原理即可。
:::
### 測驗二
Tim sort 為 Tim Peter 提出，結合了合併排序和插入排序的特點
首先識別出資料中已排序的子序列 (這些子序列稱為 run），然後透過不斷合併這些 run 來達成全資料範圍的排序
Timsort 採用一組堆疊 (stack) 來暫存 run，此舉是為了避免在一開始就掃描整個資料範圍來產生 run，從而降低記憶體開銷。過程中，Timsort 運用 merge_collapse 函式來確保堆疊上的 run 長度保持平衡。該函式主要檢查堆疊頂端的 3 個 run 是否滿足以下原則：
1. A 的長度要大於 B 和 C 的長度總和。
2. B 的長度要大於 C 的長度。
:::danger
不用列出參考題解，你專注在程式碼的原理即可。
:::
## 第二週測驗題
### 測驗一
透過 preoreder 和 inorder 的二元樹排序，重建原本的二元樹。
參考 [Linux 核心的 hash table 實作](https://hackmd.io/rpIi8FeqQ9eBJ-UTFgb--A)
hlist_node 間接指標
* 僅有末端指標內容是 NULL。
* `next` 指向相鄰的**節點本身**，而 `pprev` 指向**指著自身節點的指標**
```c
void hlist_delete_node(struct hlist_node *n)
{
struct hlist_node *next = n->next;
struct hlist_node **pprev = n->pprev;
// Since there is always a pointer which points to node n,
// no special case is needed to deal with.
*pprev = next;
if (next)
next->pprev = pprev;
}
```
* `*pprev` 是指上個節點的 `next` 指標
* `**pprev` 就是上一個節點本身，所以通過執行 `*pprev = next;` 就代表將 n 的上一個節點的 `next` 指向 n 的下一個節點，實現將 n 從鏈結串列中移除的操作
`hlist_add_head`
```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;
n->pprev = &h->first;
h->first = n;
}
```
這個函式執行 hash table 中，將 `n` 插入雙向鏈結串列。將 `hlist_node n` 插入於 `hlist_head h` 的前端。
`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]) {
struct order_node *on = list_entry(p, struct order_node, node);
if (num == on->val)
return on->idx;
}
return -1;
}
```
將傳入的 `num` 尋找雜湊表中的位置索引。宣告 `hash` 得知該節點放於雜湊表中的哪個槽，並以 `hlist_for_each` 走訪每個節點，尋找節點並回傳索引。
`dfs`
```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;
}
```
Preorder 中第一筆資料為根，而 Inorder 中左子樹及右子樹之資料分別在根的左右，所以利用 `find()` 得到根的 index 後，即可切割出左子樹及右子樹，且因為 Preorder 中左子樹之資料必定在右子樹之資料前面，所以先對左子樹遞迴做 `dfs()``，接著對右子樹遞迴做 `dfs()` 便可得到整棵樹
`node_add`
```c
static inline void node_add(int val,
int idx,
int size,
struct hlist_head *heads)
{
struct order_node *on = malloc(sizeof(*on));
on->val = val;
on->idx = idx;
int hash = (val < 0 ? -val : val) % size;
hlist_add_head(&on->node, &head[hash]);
}
```
這裡執行的是建立一個 node 並將其存放至 hash table。建立一個新節點，宣告 `hash` 決定該節點要存放於 hash table 的哪個槽裡，最後使用 `hlist_add_head` 將該節點加入 hash table
`buildTree`
```c
static struct TreeNode *buildTree(int *preorder,
int preorderSize,
int *inorder,
int inorderSize)
{
struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads));
for (int i = 0; i < inorderSize; i++)
INIT_HLIST_HEAD(&in_heads[i]);
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);
}
```
透過前序和中序來完成
Sign in with Wallet
Connect another wallet