# 2025q1 Homework2 (quiz1+2)
contributed by < timsong1 >
## Review [第一周測驗題](https://hackmd.io/@sysprog/linux2025-quiz1)
### 測驗 1
本題的 **單向鏈結串列**資料結構:
```cpp
typedef struct list_item {
int value;
struct list_item *next;
} list_item_t;
typedef struct {
struct list_item *head;
} list_t;
```
在這種資料結構中，會有一個 `head` 指標當作 [dummy node (或叫 sentinel node)](https://en.wikipedia.org/wiki/Sentinel_node)
這在鏈結串列是很常使用到的實作方式，主要原因：
1. 統一處理邊界條件，在沒有 dummy node 的情況下，對於頭節點的插入、刪除等操作常常需要額外判斷
2. 有了 dummy node，程式碼在走訪與修改串列時，就不需要再寫額外的 if 判斷來檢查當前節點是否為頭節點
這也是 Linus Torvalds 在[演講](https://www.youtube.com/watch?v=o8NPllzkFhE&t=850s)中提到的在程式設計中所謂 "good taste"
要實作的 `list_insert_before()` 如下:
```cpp
static inline void list_insert_before(list_t *l,
list_item_t *before,
list_item_t *item);
{
list_item_t **p;
for (p = AAAA; *p != BBBB; p = CCCC)
;
*p = item;
DDDD = before;
}
```
已知要使用[間接指標](https://stackoverflow.com/questions/72910521/what-difference-between-direct-pointer-and-indirect-pointer)，因此要使一個間接指標( 如 `list_item_t **p`) 直接指向某一個指標，透過直接修改`p`來達成"**間接**"修改被指向的指標所指向的位址
在程式碼中可看到 for 迴圈，因此可以知道`AAAA`為串列`l`的`head`指標位址
`AAAA = &l->head`
而`BBBB`為迴圈的中止條件，根據題意可知要停在`before`
`BBBB = before`
而`CCCC`則是要用來更新間接指標，指向下一個節點的`next`指標
`CCCC = &(*p)->next`
最後間接指標指到`before`時，透過改變`p`來"間接"改變原本的串列
再讓`item`節點接上`before`
`DDDD = item->next`
---
### 額外補充：assert marco
### 測驗 2
本題的二元樹資料結構：
```cpp
typedef struct block {
size_t size;
struct block *l, *r;
} block_t;
```
以下是要實作的程式碼片段:
```cpp
/* Locate the pointer to the target node in the tree. */
block_t **node_ptr = find_free_tree(root, target);
.
.
.
/* Find the in-order predecessor:
* This is the rightmost node in the left subtree.
*/
block_t **pred_ptr = &(*node_ptr)->l;
while (EEEE)
pred_ptr = FFFF;
```
透過註解可得知要透過這迴圈找到 in-order [predecessor](https://www.geeksforgeeks.org/inorder-predecessor-successor-given-key-bst/) (所以可以預設該樹為 BST)，
就是`node_ptr`指向的節點的 predecessor，也就是小於該節點的所有節點中，最大的節點：
`the rightmost node in the left subtree`
因為`pred_ptr`在進入迴圈前已經指向`node_ptr`的左子樹，在迴圈內則是要一直往右子樹走訪，最後會`pred_ptr`指向某個節點，其`r`指向`NULL`
`EEEE = (*pred_ptr)->r`
`FFFF = &(*pred_ptr)->r`
---
### 測驗 3
```cpp
static void rebuild_list_link(struct list_head *head)
{
if (!head)
return;
struct list_head *node, *prev;
prev = head;
node = head->next;
while (node) {
node->prev = prev;
prev = node;
node = node->next;
}
prev->next = head;
/* GGGG */;
}
```
單從這函式看可以知道是在把雙向鏈結串列中的每個`prev`指標重新接上
while 迴圈結束後只剩下`prev`跟`head`互相鏈接
`GGGG = head->prev=prev`
資料結構:
```cpp
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
quick sort 主體：
```cpp=
{
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);
}
```
這個 quick sort 是使用非遞迴方法，可以參考[詳細解說](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-3)
其實這題單看程式碼，如果理解 quick sort ，應該便能知道答案
13行得知算出`pivot`
14行可知要算出`pivot`的`value`，再搭配使用 list.h 的 marco
`HHHH = list_entry(pivot,node_t,list)->value`
`IIII = list_entry(n,node_t,list)->value`
`JJJJ = pivot`
`KKKK = right`
---
## Review [第二周測驗題](https://hackmd.io/@sysprog/linux2025-quiz2)
Sign in with Wallet
Connect another wallet