# 2025q1 Homework1 (ideas)
contributed by < `HenryChaing` >
### 第一週測驗
### 測驗 1
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
h [label="{ head | <ref2> }"];
a [label="{ <data> b | <ref2> }"];
b [label="{<data> c | <ref2> }"];
c [label="{ <data> d | <ref2> }"];
item [label="{ <data> e | <ref2> }"];
next[label="indirect pointer",shape=plaintext,fontcolor=red]
null[label="NULL",shape=plaintext,fontcolor=blue]
a:ref2:c -> b:data:n
h:ref2:c -> a:data:n
b:ref2:c -> c:data:n
c:ref2:e -> null
next->h:ref2:s
}
```
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
h [label="{ head | <ref2> }"];
a [label="{ <data> b | <ref2> }"];
b [label="{<data> c | <ref2> }"];
c [label="{ <data> d | <ref2> }"];
item [label="{ <data> e | <ref2> }"];
next[label="indirect pointer",shape=plaintext,fontcolor=red]
null[label="NULL",shape=plaintext,fontcolor=blue]
a:ref2:c -> b:data:n
h:ref2:c -> a:data:n
b:ref2:c -> c:data:n
c:ref2:e -> null
next->c:ref2:s
}
```
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
h [label="{ head | <ref2> }"];
a [label="{ <data> b | <ref2> }"];
b [label="{<data> c | <ref2> }"];
c [label="{ <data> d | <ref2> }"];
item [label="{ <data> e | <ref2> }"];
next[label="indirect pointer",shape=plaintext,fontcolor=red]
null[label="NULL",shape=plaintext,fontcolor=blue]
a:ref2:c -> b:data:n
h:ref2:c -> a:data:n
b:ref2:c -> c:data:n
c:ref2:e -> item:data:w
item:ref2:e -> null
next->c:ref2:s
}
```
```c
static inline void list_insert_before (list_t *l, list_item_t *before,
list_item_t *item) {
list_item_t **p;
for (p = &l->head; *p != before; p = &(*p)->next)
;
*p = item;
item->next = before;
}
```
這個函式在實作插入單一節點到特定位置，它的特點在於使用指標的指標來改變原本鏈結串列的 link ，指標的指標會先查看它所指向的指標所指向的節點是否為 `before` ，若成立則把指向的指標變向指到要插入的節點，插入的節點再指向 `before` 。
### 測驗 2
這個測驗是實作顯式配置器當中，關於從 Free list 取得配置空間的發法實作，從程式碼可以發現 Free list 的結構為 BST ，而不是直覺上的一維鏈結串列。
這個範例中只實作了 `remove_free_tree` ，也就是將欲移除的節點從 BST 中取出，後續我也補上了 `find_free_tree` 函式，不過先解釋 `remove_free_tree` 的運作原理：
首先函式會分析移除的節點是否有左子樹以及右子樹，若兩者都有則會尋找要替換原先移除節點位置的替代節點，與資料結構課本相同替代節點為中序走訪中移除節點的前一個節點，也就是左子樹中值最大的節點。
接著談到我實作的 `find_free_tree` 函式，我是採取遞迴的方式實作，靈感來自於二元樹的前序走訪。前兩個條件判別都是遞迴的中止條件，最後則是遞迴的處理，它會依序走訪左子樹以及右子樹，若有符合條件（值相同）的節點就會回傳該節點的間接指標。
```c
block_t **find_free_tree(block_t **root, block_t *target) {
if (root == NULL) return NULL;
else if ((*root)->size == target->size) {
printf("root [%d], ", (*root)->size);
return root;
}
else {
printf("else\n ");
block_t **root_1 = find_free_tree (&(*root)->l, target);
if (root_1 != NULL) {
printf("root1 [%d], ", (*root_1)->size);
return root_1;
}
block_t **root_2 = find_free_tree (&(*root)->r, target);
if (root_2 != NULL) {
printf("root2 [%d], ", (*root_2)->size);
return root_2;
}
return NULL;
}
}
```
至於我的測試程式碼，我會預先建立一個二元樹，節點的值是按照節點編號給予，因此它僅是一顆二元樹而非二元搜尋樹。接著再對建立的二元樹呼叫 `find_free_tree` , 如果有找到對應值相同的節點，再呼叫 `remove_free_tree` 函式將節點移除。並且再移除前後都會使用中序走訪將節點值印出，確定移除奏效。
### 測驗 3
```c
quick_sort(struct list_head *list) {
int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n;
struct list_head *begin[max_level];
struct list_head *result = NULL, *left = NULL, *right = NULL;
begin[0] = list->next;
list->prev->next = NULL;
while (i >= 0) {
struct list_head *L = begin[i], *R = list_tail(begin[i]);
if (L != R) {
struct list_head *pivot = L;
value = /* HHHH */
struct list_head *p = pivot->next;
pivot->next = NULL; /* break the list */
while (p) {
struct list_head *n = p;
p = p->next;
int n_value = /* IIII */;
if (n_value > value) {
n->next = right;
right = n;
} else {
n->next = left;
left = n;
}
}
begin[i] = left;
begin[i + 1] = /* JJJJ */;
begin[i + 2] = /* KKKK */;
left = right = NULL;
i += 2;
} else {
if (L) {
L->next = result;
result = L;
}
i--;
}
}
list->next = result;
rebuild_list_link(list);
}
```
```graphviz
digraph g2 {
node[shape=plaintext];
"left" [fontcolor="purple"];
"right" [fontcolor="purple"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
p [fontcolor="black"];
l0 [label ="NULL", fontcolor="black"];
l1 [label ="NULL", fontcolor="black"];
l2 [label ="NULL", fontcolor="black"];
l3 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
n1 -> n0 -> n2 -> n4 -> l0
}
pivot -> n3 -> l1;
left -> l2;
right -> l3;
L -> n3;
R -> n4;
p -> n1;
}
```
這個是非遞迴式的快速排序實作，僅以上圖作說明，每次 partirion 會針對 `begin[i]` 子串列進行，將 `L` , `R` 指標指向子串列的頭尾節點。接著會從頭至尾走訪這個串列，將小於 `pivot` 的值加入 `left` 指向的串列，反之則加入 `right` 指向的串列。最後則依序將 `left` 指向的串列賦予給 `begin[i]` , `pivot` 賦予給 `begin[i+1]` , `right` 賦予給 `begin[i+2]` 。
### 第二週測驗
### 測驗 `1`
這個是標準的遞迴實作快速排序，先回答為什麼 `list_move_tail` 才會是 stable sorting ，答案是這與函式實作有關，這裡的 partition 與上題測驗 `3` 相同，都是將大於或小於 pivot 的值加入對應的子串列，因此加入子串列的動作也會影響這個排序是否為 stable sorting 。
以這個串列為例 [6, 7, 80, 5, 5*, 9] 在第一次 partition 當中 `6` 是 pivot 值，因此 [5, 5*] 都會被加入 left 子串列中，若是加入函式以 `list_move_tail` 實作，less 將會是 [5, 5*, NULL] ，但是若今天是以 `list_move` 實作，則會因為加入順序的關係得到 [5*, 5, NULL] 這個 unstable 的結果，注意這裡的焦點是 5 以及 5* 的前後順序對調了。
接著是第二部份使用 perf 觀察快速排序以及 list_sort 之間的差異，這個在第一次已經有補充說明，詳閱 [使用 perf 對 `q_merge` 以及 `lib/list_sort` 實行效能分析](https://hackmd.io/9Gqp61PUSRyjVh8A0rN_4A?both#%E4%BD%BF%E7%94%A8-perf-%E5%B0%8D-q_merge-%E4%BB%A5%E5%8F%8A-liblist_sort-%E5%AF%A6%E8%A1%8C%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90)
### 測驗 `3`
這題的主旨是要使用 Linux 核心提供的 `hlist_head` 來實作雜湊表，要解決的問題是 `two_sum()` ，首先要來介紹 `hlist_head` , `hlist_node` 如何構成雜湊表。
`hlist_node` 結構包含了兩個成員, 分別指向下一個 `hlist_node` 以及上一個 `hlist_node` 的 `next` 指標。至於 `hlist_head` 則包含了一個成員指向 `hlist_node` 。
這樣實作的好處在於雜湊表中 `hlist_head` 僅須包含一個成員，相比 `list_head` 省去了一半的空間。至於使用間接指標則是方便加入以及刪除節點。
接著分析到 `two_sum` 的實例，有了雜湊表的實作，可以從原先的雙重迴圈轉為單一的迴圈，至於每次迭代則是先尋找雜湊表當中是否有可以湊齊目標值的節點存在，若不存在則將迭代到的陣列值加入雜湊表當中。由於雜湊演算法是單純的乘法以及位元操作，因此不論是雜湊新增亦或是檢索時間成本皆為 $O(1)$ （不考慮過度 conflict 的狀況）。
以下是簡短的測試程式碼， `two_sum` 函式會先檢索雜湊表看是否可以組成目標值，再將陣列數值加入雜湊表。
Sign in with Wallet
Connect another wallet