2025q1 Homework2 (quiz1+2)

contributed by <mincch>

第一周測驗題

測驗 1

先閱讀教材 a pointer to a pointer 了解指標的指標是什麼?

#include <stdio.h>
int main() {
    int val = 10;
    int *pointer_1 = &val;
    int **pointer_2 = &pointer_1;

    printf("val 存的值: %d\n", val);
    printf("val 記憶體位址: %p\n", &val);

    printf("pointer_1 指向的位址儲存的值: %d\n", *pointer_1);
    printf("pointer_1 指向的位址: %p\n", pointer_1);
    printf("pointer_1 記憶體位址: %p\n", &pointer_1);
    
    printf("pointer_2 指向的位址所儲存的值(位址): %p\n", *pointer_2);
    printf("pointer_2 指向的位址所指向的位址儲存的值: %d\n", **pointer_2);
    printf("pointer_2 指向的位址: %p\n", pointer_2);
    printf("pointer_2 記憶體位址: %p\n", &pointer_2);

    return 0;
}

val 存的值: 10
val 所在的記憶體位址: 0x7fffffffd534

pointer_1 指向的位址儲存的值: 10
pointer_1 指向的位址: 0x7fffffffd534
pointer_1 所在的記憶體位址: 0x7fffffffd538

pointer_2 指向的位址所儲存的值(位址): 0x7fffffffd534
pointer_2 指向的位址所指向的位址儲存的值: 10
pointer_2 指向的位址: 0x7fffffffd538
pointer_2 所在的記憶體位址: 0x7fffffffd540

lsit_inster_before 函式的功能為: 負責在鏈結串列 (list_t) 中，在指定的節點 (before) 之前插入新節點 (item)。

AAAA : 是一個指向鏈結串列開頭的變數所以為 &l->head。p 就變成 指向 head 指標的指標 list_item_t **，因此 *p 就是 head 本身。

BBBB : 遍歷節點直到找到需要的點 before ， *p 代表當前節點，因此 *p != BBBB 代表還沒找到 before。

CCCC : 讓 p 指向下一個 next 指標的位置。

DDDD : *p 是 before 前一個節點的 next，讓 item 成為 before 前一個節點的 next。 最後讓 item->next 連接到 before，確保 item 插入後仍然連接到 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;
}

static char *test_list(void) 功能為: 測試在各個位置插入元素的情況

正確執行:

在現有的程式碼基礎上，撰寫合併排序操作

在將節點使用 list_move_tail 的方法改成使用 list_insert_before 替代 ，透過 pointer to pointer 操作 插入正確位置。

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *slow = head;
    struct list_head *fast = head->next;
    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    struct list_head first;
    list_cut_position(&first, head, slow);

    q_sort(&first);
    q_sort(head);
    q_merge_list(head, &first);
}

void q_merge_list(struct list_head *left_list, struct list_head *right_list)
{
    if (!left_list || !right_list)
        return;

    struct list_head temp;
    INIT_LIST_HEAD(&temp);

    while (!list_empty(left_list) && !list_empty(right_list)) {
        element_t *first_node = list_first_entry(left_list, element_t, list);
        element_t *second_node = list_first_entry(right_list, element_t, list);
        
        bool tag = strcmp(first_node->value, second_node->value) < 0;
        element_t *add_first = tag ? first_node : second_node;

        list_insert_before(&temp, temp.next, &add_first->list);
    }

    list_splice_tail_init(left_list, &temp);
    list_splice_tail_init(right_list, &temp);
    list_splice(&temp, left_list);
}

測驗 2

擁有兩個子節點的情況

• 找到 target 的 predecessor，就是左子樹中最大（最右邊）的節點：
  透過 while (EEEE) pred_ptr = FFFF; 來遍歷 target 左子樹中的最右點。
  在尋找 target->l 中最右的節點：
  EEEE 表示迴圈繼續的條件，還有右子樹 *pred_ptr->r。
  FFFF 表示更新指標，移動到右子樹 &(*pred_ptr)->r。
• 用這一點來取代 target：
  若 pred_ptr 直接是 target->l，直接把 target->r 連接到新節點。
  若 pred_ptr 不在 target->l，則將其從原來的位置移除，然後插入 target 的位置。

使用 find_free_tree(root, target) 找到 target 的位置。

block_t **find_free_tree(block_t **root, block_t *target) {
    while (*root && *root != target) {
        if (target->size < (*root)->size)
            root = &(*root)->l;
        else
            root = &(*root)->r;
    }
    return root;
}

使用 find_predecessor_free_tree(block_t **root, block_t *node) 找 predecessor

block_t *find_predecessor_free_tree(block_t **root, block_t *node) {
    block_t *pred = NULL;
    if (node->l) {
        pred = node->l;
        while (pred->r) pred = pred->r;
    }
    return pred;
}