# 2025q1 Homework2 (quiz1+2)
contributed by <eric895888>

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境

$ 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()` 重新初始化測試資料，t`est_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 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists) 做出`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