HackMD
2025q1 Homework2 (quiz1+2)
contributed by: <Beethovenjoker> (章元豪) Github
2025q1 第 1 週測驗題
指標的指標
指標的指標（pointer to pointer），目的是讓插入新節點時的程式碼變得簡潔且不必特別處理串列頭或尾的特殊情況。
void list_insert_before(list_t *list, 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;
}
首先讓 p 指向鏈結串列的開頭（head 指標）。這樣的目的是，不論要插入的位置是串列的何處，都可以用同一套邏輯來處理，不需要額外寫多餘的判斷式。從 head 開始往後找，找到要插入節點的目標位置（before）。每一次迴圈，p 都會向後移動到下一個節點的 next 指標，直到找到我們想插入的位置。最後插入新節點，把新節點 item 放進我們找到的位置。然後讓新節點的next指向before。
管理樹狀結構的記憶體空間
這段程式的功能是從一個二元搜尋樹（Binary Search Tree, BST）中移除一個指定的節點，並且維持原本樹的結構不被破壞。
- 在移除節點時，樹的結構必須保持 BST 的特性:
- 每個節點左子樹的元素都小於該節點。
- 每個節點右子樹的元素都大於該節點。
- 移除節點時的三種情況:
- 沒有子節點 → 直接移除。
- 只有一個子節點 → 以該子節點取代該節點。
- 有兩個子節點 → 用它的前驅（左子樹中最大的節點）取代它。
if ((*node_ptr)->l && (*node_ptr)->r) {
當移除節點有兩個子節點時，用前驅節點來取代被移除的節點。
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
pred_ptr = pred_ptr=pred_ptr->r;
先從左子節點開始，往右一直走訪，直到右子節點為 NULL，此時找到的節點就是前驅節點。
target->l = NULL;
target->r = NULL;
移除節點後，最後要清空移除節點的左右指標，防止dangling references。
非遞迴快速排序法
傳統的遞迴快速排序法透過選擇 pivot 並執行分割，將陣列切成左右兩部分，然後遞迴排序。但在非遞迴版本中，這些遞迴呼叫用堆疊模擬，以達到相同效果。
- 演算法步驟
- 選擇 pivot（選擇鏈結串列最左側的值)。
- 走訪串列，將小於 pivot 的值存入 left的串列，大於 pivot 的值存入 right串列。
- 分割成三組：left、pivot、right。
- 優先排序 right，存入 result。
- 接著處理 left，最終完成排序。
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;
head->prev = prev;
}
在 Linux list.h 的 struct list_head 是循環鏈結串列，這表示最後一個節點的 next 會回到 head。prev->next = head 讓最後一個節點的 next 回到 head，但還需要將 head->prev 指向最後一個節點，讓 prev 能正確反向連結。
struct list_head *pivot = L;
value = list_entry(pivot, node_t, list)->value;
pivot 是 struct list_head *，但我們需要 pivot 對應的 node_t 結構體的value。因此，我們利用 Linux 核心提供的巨集list_entry(ptr, type, member)，從 list_head 結構中取得對應的container structure，最後從 node_t 的結構體存取value。
int n_value = list_entry(n, node_t, list)->value;
if (n_value > value) {
n->next = right;
right = n;
} else {
n->next = left;
left = n;
}
與前面類似，我們需要從 list_head 結構取得 node_t 的value，因此同樣使用 list_entry()。這樣 n_value 就是目前節點的值，能夠與 pivot 比較來決定該節點應該放入 left 或 right。
begin[i] = left;
begin[i + 1] = pivot;
begin[i + 2] = right;
left = right = NULL;
i += 2;
begin[i+1] 用來存放當前的 pivot 節點，因為 pivot 是分割的中間值，所以它自己就是一個獨立的部分。begin[i] 和 begin[i+2] 分別存放left和right。快速排序法會優先處理 right，確保先排序右邊。
