Try   HackMD

2025q1 Homework2 (quiz1+2)

contributed by <eric895888>

作業書寫規範:

  • 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
  • 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
  • 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
  • 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
  • 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
  • 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
  • HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
  • 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
  • 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
  • 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
  • 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
  • 避免使用不必要的 emoji 字元

開發環境

$ gcc --version 
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ ldd --version
ldd (Ubuntu GLIBC 2.35-0ubuntu3.9) 2.35
Copyright (C) 2024 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Written by Roland McGrath and Ulrich Drepper.

$ lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          39 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   8
  On-line CPU(s) list:    0-7
Vendor ID:                GenuineIntel
  Model name:             11th Gen Intel(R) Core(TM) i5-11300H @ 3.10GHz
    CPU family:           6
    Model:                140
    Thread(s) per core:   2
    Core(s) per socket:   4
    Socket(s):            1
    Stepping:             1
    CPU max MHz:          4400.0000
    CPU min MHz:          400.0000
    BogoMIPS:             6220.80

第一週測驗題

測驗 1

測驗1實作鏈結串列的插入與基本操作，list_insert_before() 用於在指定節點前插入新節點，並透過指標操作維持鏈結串列的結構，test_list() 測試不同插入情境，包括在串列開頭與結尾插入節點，並使用 my_assert() 確保串列的長度與順序正確，list_reset() 重新初始化測試資料，test_suite() 執行所有測試，而 main() 呼叫 test_suite() 並輸出測試結果。
而 list_insert_before() 目的是插入 item 節點於 before 之前，若 before == NULL，則插入到鏈結串列的末端，使用 list_item_t **p 來遍歷鏈結串列，使用指標的指標方式確保能直接修改指向的位置，如果 before 是 head，則 head 直接更新為 item。

AAAA 填入&l->head是遍歷的起點。
BBBB 填入before是搜尋的目標。
CCCC 填入&(*p)->next是遍歷方式。
DDDD 填入item->next讓 item 的 next 指向 before。

static void list_insert_before(list_t *l,list_item_t *before, list_item_t *item)
{
    if (!l || !before || !item) 
        return;  

    list_item_t **p;

    for (p = &l->head; *p != before; p = &(*p)->next)
        ;

    *p = item;
    item->next = before;
}

合併排序

這段程式碼使用合併排序（Merge Sort）來對單向鏈結串列進行排序，首先，findMid() 使用快慢指標找到鏈結串列的中點，將其拆分為兩半，接著，mergeSort() 採用遞迴方式對兩個子串列分別進行排序，直到每個子串列只剩下一個節點；然後根據 你所不知道的 C 語言: linked list 和非連續記憶體 做出mergeTwoLists() 合併兩個已排序的子串列，確保結果仍然是排序好的，最後，mergeSortList() 負責處理 list_t 結構，呼叫 mergeSort() 排序並更新 head，從而完成整個鏈結串列的排序。

list_item_t *mergeTwoLists(list_item_t *left, list_item_t *right) {
    list_item_t *head;
    list_item_t **ptr = &head;
    while (left && right) {
        if (left->value < right->value) {
            *ptr = left;
            left = left->next;
        } else {
            *ptr = right;
            right = right->next;
        }
        ptr = &(*ptr)->next;
    }
    *ptr = left ? left : right;
    return head;
}

//Fast-Slow Pointer
void findMid(list_item_t *head, list_item_t **left, list_item_t **right) {
    if (!head || !head->next) {
        *left = head;
        *right = NULL;
        return;
    }

    list_item_t *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    *left = head;
    *right = slow->next;
    slow->next = NULL;
}

list_item_t *mergeSort(list_item_t *head)
{
    if(!head || !head->next)
        return head;
    list_item_t *left, *right;

    findMid(&head,left,right);

    left = mergeSort();
    right = mergeSort();
    return sortedMerge(left,right);
    
}

測驗 2

測驗2的程式碼實作了一個二元搜尋樹（BST）的節點刪除函式 remove_free_tree()，用來從 block_t 型態的 BST 中刪除指定的 target 節點。首先，find_free_tree(root, target) 找到指向該節點的指標 node_ptr，接著根據 target 節點的子節點情況進行刪除操作，如果 target 有 兩個子節點，則使用中序（in-order predecessor）的走訪方式，也就是左子樹中最大（最右）節點 pred_ptr，然後以 pred_ptr 替換 target，並將 target 的右子樹連接到 pred_ptr。如果 pred_ptr 不是 target 的直接左子節點，則從原來位置刪除 pred_ptr，並將其作為新節點插入。如果 target 只有一個子節點，則直接讓 target 的父節點指向 target 唯一的子節點，繼續維持 BST 結構。如果 target 沒有子節點，則將其設為 NULL，從樹中刪除。最後，target->l 和 target->r 被設為 NULL。

remove_free_tree() 中如果要被刪除的節點有兩個子樹，使用中序的走訪方式找到左子樹中最右邊的節點。
EEEE 填入 (*pred_ptr)->r 。
FFFF 填入 &(*pred_ptr)->r 則是用來往右走訪的操作。

block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
    pred_ptr = &(*pred_ptr)->r;

測驗 2 測試程式碼

/* 在 BST 中尋找節點的指標 */
block_t **find_free_tree(block_t **root, block_t *target) {
    while (*root) {
        if ((*root)->size == target->size)
            return root;
        else if (target->size < (*root)->size)
            root = &((*root)->l);
        else
            root = &((*root)->r);
    }
    return NULL;
}

/* 找到左子樹的最大值 */
block_t *find_predecessor_free_tree(block_t **root, block_t *node) {
    if (!node || !node->l) return NULL;
    block_t *pred = node->l;
    while (pred->r) {
        pred = pred->r;
    }
    return pred;
}

/* 插入節點到 BST */
void insert_free_tree(block_t **root, size_t size) {
    block_t *new_node = (block_t *)malloc(sizeof(block_t));
    new_node->size = size;
    new_node->l = new_node->r = NULL;

    if (!*root) {
        *root = new_node;
        return;
    }

    block_t *parent = NULL, *current = *root;
    while (current) {
        parent = current;
        if (size < current->size)
            current = current->l;
        else
            current = current->r;
    }

    if (size < parent->size)
        parent->l = new_node;
    else
        parent->r = new_node;
}

/* 印出 BST（中序） */
void print_tree(block_t *root) {
    if (!root) 
        return;
    print_tree(root->l);
    printf("%zu ", root->size);
    print_tree(root->r);
}
int main() {
    block_t *root = NULL;

    insert_free_tree(&root, 50);
    insert_free_tree(&root, 30);
    insert_free_tree(&root, 70);
    insert_free_tree(&root, 20);
    insert_free_tree(&root, 40);
    insert_free_tree(&root, 60);
    insert_free_tree(&root, 80);

    printf("BST 初始化中序走訪: ");
    print_tree(root);
    printf("\n");

    block_t target;
    
    target.size = 50;
    printf("刪除節點: %zu\n", target.size);
    remove_free_tree(&root, &target);
    print_tree(root);
    printf("\n");

    target.size = 30;
    printf("刪除節點: %zu\n", target.size);
    remove_free_tree(&root, &target);
    print_tree(root);
    printf("\n");

    target.size = 70;
    printf("刪除節點: %zu\n", target.size);
    remove_free_tree(&root, &target);
    print_tree(root);
    printf("\n");

    return 0;
}

測驗 3

測驗3的程式碼實作了一個基於單向鏈結串列的快速排序法，不過並不是常見的遞迴方式而是改使用迭代的方式去實作，先建立一個list，並插入隨機順序的 100000 個數字，然後對鏈結串列進行 quick_sort，最後驗證排序結果 (assert(list_is_ordered(list)))，並列印排序後的數據。
quick_sort 使用 begin 陣列來管理子鏈表的拆分，並在每層迭代選擇第一個節點作為 pivot，將其後的元素依據數值大小分成 left (小於等於 pivot) 和 right (大於 pivot)處理兩部分，最終將結果合併。

GGGG 填入head->prev = prev;指向最後一個節點。
HHHH 填入list_entry(pivot,node_t,list)->value。
IIII 填入list_entry(n,node_t,list)->value。
JJJJ 填入pivot。
KKKK 填入right。

第二週測驗題

測驗 1

程式碼使用 struct listitem 定義雙向鏈結串列節點，並透過 testlist 初始化鏈結串列。首先，程式產生隨機數，getnum()透過三個變數計算亂數，get_unsigned16() 產生 16-bit 無號整數，而 random_shuffle_array() 對 values 陣列進行洗牌，接著，程式遍歷 values 陣列，將其數值存入動態配置的 struct listitem，並插入 testlist 串列中，排序部分使用 list_quicksort() 進行快速排序，選擇 pivot 節點後，將較小與較大的節點分別移動到 list_less 和 list_greater，遞迴處理後重新組合串列，排序完成後，程式先使用 qsort() 排序 values 陣列作為正確結果，然後檢查 testlist 內的節點是否與 values 內容一致，確保排序正確。最後，程式逐一釋放記憶體，並確認 testlist 已清空 (list_empty(&testlist)) 以確保資源管理正確。

AAAA 填入 list_first_entry() 它的作用是獲取鏈結串列的第一個元素。
BBBB 填入 list_del()這是 quicksort 分割（partition）過程的步驟，因為 pivot 不能留在 head 裡，要另外存放，方便後續排序。
CCCC 填入list_move_tail因為需要將大於 pivot 的元素移到 list_greater。
DDDD 填入 list_add()，因為需要把 pivot 放回原本的鏈結串列。
EEEE 填入 list_splice()，因為需要把 pivot 左邊較小的元素併回 head。
FFFF 填入list_splice_tail()，因為需要把 pivot 右邊較大的元素併回 head。

測驗 2

clz2()若 upper 等於 0，則下一次遞迴呼叫應檢查 lower 部分，並記錄目前已累計的 leading zero，若 upper 不等於 0，則下一次遞迴呼叫應繼續檢查 upper 部分，如果 x == 0 且 c == 0，則回傳 32，表示 32-bit 數字完全沒有 1，全都是 0。

static const int mask[] = {0, 8, 12, GGGG};
static const int magic[] = {HHHH, 1, 0, IIII};

unsigned clz2(uint32_t x, int c)
{
    if (!x && !c)
        return 32;

    uint32_t upper = (x >> (16 >> c));
    uint32_t lower = (x & (0xFFFF >> mask[c]));
    if (c == JJJJ)
        return upper ? magic[upper] : KKKK + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);
}

GGGG 填入14，因為要lower要保留的位數是2。
HHHH 填入2
IIII 填入0
JJJJ 填入3
KKKK 填入2
LLLL 填入1
MMMM 填入~1
NNNN 填入1
PPPP 填入2

測驗 3

這段程式碼實作 twoSum 演算法，用來尋找陣列 nums 中兩個數字相加等於 target 的索引，其中 map_add 用來插入鍵值對，而 map_get 用來查找特定鍵的值，在 twoSum 函式中，程式遍歷 nums 陣列，對於每個數字 nums[i]，計算 target - nums[i] 是否已存在於 hash table 中，若找到則回傳兩個索引，否則將 nums[i] 及其索引存入 hash table 。
AAAA 填入 map->bits
BBBB 填入 map->bits
CCCC 填入 first->pprev
DDDD 填入 n->pprev
EEEE 填入 n->pprev

Last changed by 
 
ShanXD
0
37

Read more

2025q1 Homework1 (lab0)

2025q1 Homework1 (lab0)

Mar 29, 2025
linux2025-ideas

Mar 8, 2025
Read more from ShanXD
Published on HackMD