2025q1 Homework2 (quiz1+2)

contributed by <DrXiao>

第一週測驗題 - 測驗 1

從原題目的程式碼中，可見程式碼並非使用動態配置記憶體，而是採用全域變數的定義方式，配置了 1000 個節點，並在 test_list() 函式中欲使用 list_insert_before() 將這些節點的的指標依序指向適當的節點，讓鏈結串列得以被建立起來。

從原題目的圖片訊息可以得知，list_insert_before() 的函式型態如下：

static inline void list_insert_before(list_t *l,
                                      list_item_t *before,
                                      list_item_t *item);

閱讀註解後可得知，這個函式的用意就是想將 item 這個節點插入至鏈結串列 l 當中，並且是插入在 before 節點前面，其中須考慮以下情況：

• 如果 before 相當於 l 中的第一個節點，仍把 item 插入在 before 前面，
  ，並把 item 視作是 l 的第一個節點。
• before 是 NULL 的話，就相當於把 item 插入在 l 的尾端。
• 如果 before 不是 NULL，但實際上不在鏈結串列 l 內的話，其行為是未定義的。
  • 但實際上以題目給定的程式碼來說，不會有這樣的使用案例，故實作上可以省去這點的考量。

綜合以上的前情提要，了解 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 = &l->head; *p != before; p = &(*p)->next)
        ;   
    *p = item;
    item->next = before;
}

對應原題目的填空，AAAA ~ DDDD 的答案如下：

AAAA: &l->head
BBBB: before
CCCC: &(*p)->next
DDDD: item->next

在原先給定的程式片段中，便提示了可以使用間接指標的技巧，透過宣告 list_item_t ** 的物件，去找到 before 節點，並在最後將 item 節點安插在 before 之前。

接著舉例說明程式碼的運作方式，考慮一個 3 個節點的鏈結串列（資料內容依序是 40 -> 25 -> 30），若想在第 3 個節點之前插入新的節點（資料為 15），在呼叫 list_insert_before() 之前，可以先將鏈結串列及該函式的變數，繪製成以下的樣貌：

首先在上圖中可見：

• 左上角一個 item 的文字，指向帶有整數 25 的節點，即是對應函式參數 item
• 圖中的 before，即是對應參數的 before
• 圖中的 p 即是對應區域變數 list_item **p
• 最下方及有一排節點，即是鏈結串列本體（如舉例所述，但有 3 個節點）
  • 而左下角的 head ，就是對應 l->head。（就是用第一個參數 l 取得的串列開頭指標）

接下來為避免撰寫上的混亂，之後仍會用 item 、 before … ，來代稱圖中的各個部份

呼叫 list_insert_before() 後，在執行該函式本體的一開始，可以得知各個變數會變成下圖的關係：

• before 是呼叫者自行指定的節點指標，以本例來說，它會指向了第 3 個節點（含有整數 30 的節點），這樣可以透過 before 指標，將 item 適當地安插在 before 之前
• 因為有了 p = &l->head 這行進行指派，在上圖中可見 p 指向了 head

第一週測驗題 - 測驗 2

EEEE 為 (*pred)->right != NULL
FFFF 為 &(*pred)->right

第一週測驗題 - 測驗 3

第二週測驗題 - 測驗 1

第二週測驗題 - 測驗 2

第二週測驗題 - 測驗 3