HackMD
2025q1 Homework2 (quiz1+2)
contributed by < qianzsh >
Q1
- 首先看到 struct list_item 為節點的結構，有一個 int 儲存資料，及一個 next pointer，因此可以推測其為一個單向的 linked list，接著 list_t 結構中只有一個成員 head，它用來儲存鏈結串列中第一個節點的位址。
#include <stddef.h>
typedef struct list_item {
int value;
struct list_item *next;
} list_item_t;
typedef struct {
struct list_item *head;
} list_t;
- 利用指標的指標對記憶體位置上的值做更改以實現插入節點的功能，若是僅使用指標 p ，修改 p 的值只是改變了這個變數的內容，不會影響到鏈結串列中實際存放的指標。
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;
}
Q2
- 首先考慮目標節點有左右兩個子節點的情況，這時被刪除節點的位置可以從左邊子樹中遞補也可以從右邊子樹中遞補，這次題目選擇從左邊子樹中遞補，以下程式碼在左邊子樹中尋找最右邊的節點。
/* If the target node has two children, we need to find a replacement. */
if ((*node_ptr)->l && (*node_ptr)->r) {
/* Find the in-order predecessor:
* This is the rightmost node in the left subtree.
*/
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
pred_ptr = &(*pred_ptr)->r;
Q3
while (p) {
node_t *n = p;
p = p->next;
list_add(n->value > value ? &right : &left, n);
}
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;
