2025q1 Homework2 (quiz1+2)

contributed by < timsong1 >

Review 第一周測驗題

測驗 1

本題的 單向鏈結串列資料結構:

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)
這在鏈結串列是很常使用到的實作方式，主要原因：

1. 統一處理邊界條件，在沒有 dummy node 的情況下，對於頭節點的插入、刪除等操作常常需要額外判斷
2. 有了 dummy node，程式碼在走訪與修改串列時，就不需要再寫額外的 if 判斷來檢查當前節點是否為頭節點

這也是 Linus Torvalds 在演講中提到的在程式設計中所謂 "good taste"

要實作的 list_insert_before() 如下:

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;
}

已知要使用間接指標，因此要使一個間接指標( 如 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

本題的二元樹資料結構：

typedef struct block {
    size_t size;
    struct block *l, *r;
} block_t;

以下是要實作的程式碼片段:

/* 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 (所以可以預設該樹為 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

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

資料結構:

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

quick sort 主體：

{
    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 是使用非遞迴方法，可以參考詳細解說
其實這題單看程式碼，如果理解 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 第二周測驗題