2025q1 Homework2 (quiz1+2)

contributed by < NeedToDebugMyLife >

Quiz 1

Q1

資料結構

1. list_item_t

   ​​​​typedef struct list_item {
   ​​​​    int value;
   ​​​​    struct list_item *next;
   ​​​​} list_item_t;
   

2. list_t

   ​​​​typedef struct {
   ​​​​    struct list_item *head;
   ​​​​} list_t;
   

題目

static inline void list_insert_brfore(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;
}

答案

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

說明

此段程式用於插入一個新節點到目標節點的前方

• for 迴圈用於走訪佇列來找出要插入的位置
• 找到後將節點插入到該位置 (*p = item)
• 將新節點的 next 指標指向 before 節點
  
  

Case1 - 考慮將節點 3 (item) 插入到佇列 (l) 的節點 4 (before) 前:

初始狀態

• l 是指向 "list_t 結構" 的指標
• p 是指向 "list_t 結構內的 list_item 指標" 的間接指標
• *p 是指向 "list_t 結構內的 list_item 指標" 所指向的 "list_item 結構"(AAAA)
• before 是指向 list_item_t 結構的指標，用於表示插入位置節點(4)
• item 是指向 list_item_t 結構的指標，用於要插入的節點(3)

指標 p 用於走訪節點，每次檢查節點完成後都會往後移動一節點(CCCC)，當 *p 指向 before 節點時(BBBB)，結束走訪

走訪輪數1

走訪輪數2

*p 指向 before, 結束走訪。此時 p 指向節點 2。

插入節點

將 item 插入到 p 後方 (即 *p指向的位置)

將 item 節點的 next 指標指向 before 節點 (DDDD)

完成插入

Case2 - 考慮將節點 1 (item) 插入到佇列 (l) 的節點 2 (before) 前:

初始狀態

因為 *p 指向 before, 所以不需要走訪。此時 p 指向 head 節點 (&l->head)。

插入節點

將 item 插入到 p 後方 (即 *p指向的位置)

將 item 節點的 next 指標指向 before 節點 (DDDD)

完成插入

可以發現使用間接指標插入節點的方式，無論在哪一種情況下，l 指標都是不需要更動的。

Q2

資料結構

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

題目

void remove_free_tree(block_t **root, block_t *target)
{
    /* Locate the pointer to the target node in the tree. */
    block_t **node_ptr = find_free_tree(root, target);

    /* 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 (EEEE)
            pred_ptr = FFFF;

        /* Verify the found predecessor using a helper function (for debugging).
         */
        block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
        assert(expected_pred == *pred_ptr);

        /* If the predecessor is the immediate left child. */
        if (*pred_ptr == (*node_ptr)->l) {
            block_t *old_right = (*node_ptr)->r;
            *node_ptr = *pred_ptr; /* Replace target with its left child. */
            (*node_ptr)->r = old_right; /* Attach the original right subtree. */
            assert(*node_ptr != (*node_ptr)->l);
            assert(*node_ptr != (*node_ptr)->r);
        } else {
            /* The predecessor is deeper in the left subtree. */
            block_t *old_left = (*node_ptr)->l;
            block_t *old_right = (*node_ptr)->r;
            block_t *pred_node = *pred_ptr;
            /* Remove the predecessor from its original location. */
            remove_free_tree(&old_left, *pred_ptr);
            /* Replace the target node with the predecessor. */
            *node_ptr = pred_node;
            (*node_ptr)->l = old_left;
            (*node_ptr)->r = old_right;
            assert(*node_ptr != (*node_ptr)->l);
            assert(*node_ptr != (*node_ptr)->r);
        }
    }
    /* If the target node has one child (or none), simply splice it out. */
    else if ((*node_ptr)->l || (*node_ptr)->r) {
        block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
        *node_ptr = child;
    } else {
        /* No children: remove the node. */
        *node_ptr = NULL;
    }

    /* Clear the removed node's child pointers to avoid dangling references. */
    target->l = NULL;
    target->r = NULL;
}

答案

• EEEE = (*pred_ptr)->r
• FFFF = &(*pred_ptr)->r

說明

此段程式用於管理可使用的記憶體區塊

Case1 - 考慮釋出一可用空間 r