2025q1 Homework2 (quiz1+2)

contributed by < Huadesuwa >

第 1 周測驗題

測驗 1

延伸問題 1

首先看到 struct list_item 為節點的結構，其中有一個整數型別 value 用於儲存資料，以及一個 a pointer named next to a strcut list_item ，因此可以得知這是一個單向的鏈結串列， 而 head 則會指向整個鏈結串列

typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;
typedef struct {
    struct list_item *head;
} list_t;

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

其關鍵操作 list_insert_before 函式的語意如下：
函式會逐步走訪整個鏈結串列，定位到 before 之前指向的節點，並將 item 插入該位置

• 時間複雜度為
  $O(n)$ ，n 是指需要幾步才能找到要插入的位置
• 若 before 指向鏈結串列的頭 ，意謂著會插入在鏈結串列最前面的位置

• 反之，指向 NULL ，則會插入在尾巴

• 除了之外的事件都被視為 Undefined

其測試程式 test_list 將會對 list_insert_before 進行測試，驗證函式功能是否正確:

• 將 before 設置為鏈結串列的頭( l.head )，測試插入 item 到前面的功能
• 將 before 設置為 NULL ，測試插入 item 到後面的功能
  • 判斷是否有 Unexpected Value 的情況
• 測試完畢後，重置鏈結串列(將值由小到大重新插入)

延伸問題 2

參照，使用間接指標 **ptr 指向鏈結串列的頭，避免配置暫時指標的記憶體空間，而迴圈的中止條件為其中一串鏈結串列被走訪完畢 ( NULL ) ，剩餘的則透過 bitops 操作串上。

因為是單向鏈結串列(傳入的鏈結串列皆為排序過的)，所以當走訪過程中指向 NULL ，則代表其中一項串列被合併完了。

list_item_t **ptr = &head->head, **node;
for (node = NULL; L1 && L2; *node = (*node)->next) {
    node = (L1->head->value < L2->head->value) ? &L1->head : &L2->head;
    *ptr = *node;
    ptr = &(*ptr)->next;
}
*ptr = (list_item_t *) ((uintptr_t) L1->head | (uintptr_t) L2->head);

測驗 2

延伸問題 1

首先，解釋程式碼各個函式的用義
block_t : 實現二元搜尋樹 (BST) 的結構體，每個節點都代表一個記憶體區塊。
find_free_tree : 是個搜尋函式，會回傳指向 target 的指標 node_ptr 。
find_predecessor_free_tree : 用來尋找某個節點的in-order predecessor ，也就是在 BST 中小於某個節點的最大節點。
remove_free_tree：負責從 BST 中移除指定的節點，並確保樹的結構仍然維持 BST 的特性，也是這段程式碼的重點。

移除指定的節點時，分為三種 Case

1. 刪除的節點有兩個子節點
   • 透過 find_free_tree 找到目標的位置，**node_ptr 指向目標位置，**pred_ptr 指向左子樹的根節點。接下來，需要找出 in-order predecessor ，也就是左子樹中最大的節點。
2. 刪除的節點沒有子節點 → 直接刪除*node_ptr = NULL;。
3. 刪除的節點只有一個子節點 → 讓它的子節點取代它的位置。

/* If the target node has two children, we need to find a replacement. */
if ((*node_ptr)->l && (*node_ptr)->r) {
    ...
}
/* If the target node has one child (or none), simply splice it out. */
else if ((*node_ptr)->l || (*node_ptr)->r) {
    ...
} else {
    /* No children: remove the node. */
    ...
}

• Still Case3
  1. while 迴圈持續向右逐步走訪左子樹，直到找到最右側的節點。
  2. 因此 EEEE 為 (*pred_ptr)->r 才能在已經找不到右子節點時跳出迴圈；
  3. 而 FFFF 則是 pred_ptr 所指向節點的右子節點的地址 &(*pred_ptr)->r ，如此才能使迴圈不斷向右走訪。
     • 之後透過 find_predecessor_free_tree 再次搜尋
     • 並使用 assert 檢查找到的 in-order predecessor 是否相同，若不相同則終止程式
  4. 最後，把 target 替換為 pred_ptr，有兩種情況：
     • pred_ptr 剛好是 target 的左子節點，此時用 pred_ptr 替換 target ；保留 target 的右子樹 。
     • pred_ptr 在 target 左子樹的更深處，先遞迴刪除 pred_ptr ，因為需要從 predecessor 的左子樹尋找它的 predecessor 。

測試

效能評比

測驗 3

延伸問題 1

〈Optimized QuickSort — C Implementation (Non-Recursive)〉提出非遞迴 (non-recursive; iterative) 的快速排序法。此處提到的方法是以 swap 為主體，利用 L 與 R 去紀錄需交換的數量，再用 begin[] 與 end[] 作為堆疊，用來紀錄比較的範圍。
在此使用了 Linux 風格的 List API 來建立鍊結串列，並使用 value 來紀錄數值。

typedef struct __node
{
    long value;
    struct list_head list;
} node_t;

以下為測試與輔助函式:
list_construct : 在 list 中建立新的節點。
list_free : 釋放整個鏈結串列 list 已分配的記憶體空間。
list_is_ordered : 驗證鏈結串列 list 是否為有序排列。
shuffle : 打亂陣列的排列， 運作條件為 n < RAND_MAX
list_tail : 找到鏈結串列 list 的尾巴
list_length : 計算鏈結串列 list 大小(內含多少節點)
rebuild_list_link : 將單向鏈結串列轉換為雙向環狀鏈結串列

• 迴圈內會將單向連接轉變為雙向連接，直到走訪至鏈結串列的尾巴 ( NULL )
• 因此， GGGG 為 head->prev=prev ，如此才能做到首尾相連

while (node) {
    node->prev = prev;
    prev = node;
    node = node->next;
}
prev->next = head;
head->prev=prev

接著便開始進行排序的動作，

排序的過程中，先將 L 及 R 兩指標指向鏈結串列的頭及尾。

若 L 及 R 兩者不同，則將 piviot 指向 L 所指的節點，並將 piviot 的數值存於 value。

value = list_entry(pivot, node_t, list) -> value

使用 p 指向 piviot 的下一個節點，並斷開 piviot (指向 NULL )。

使用 p 逐步走訪整個節點，將小於 value 的置於 left 中，大於 value 則置於 right 中。

int n_value = list_entry(n, node_t, list)->value;

if (n_value > value) {
    n->next = right;
    right = n;
} else {
    n->next = left;
    left = n;
}

接著將 begin[] 指向對應的位置。

begin[i]= begin[0] = left;
begin[i + 1]= begin[1] = pivot; /* JJJJ */
begin[i + 2]= begin[2] = right; /* KKKK */
left = right = NULL;

在下一輪，同樣將 L 指向 begin[i] 即 begin[2] (從較大子序列開始), 而 R 則指向 begin[2] 尾端。

此時按照先前的步驟將 piviot 設置在 L 並將 p 指向 piviot 下一個節點

同樣逐步走訪節點，將小於 value 的置於 left 中，大於 value 則置於 right 中，並將 begin[] 指向對應的位置。

begin[i]= begin[2] = left;
begin[i + 1]= begin[3] = pivot;
begin[i + 2]= begin[4] = right;
left = right = NULL;

此時 L 將指向 begin[4] , R 指向 begin[4] 的尾端，兩者皆指向 NULL ，且 L 為 NULL 因此 i= i-1 = 3 。又 3 也同樣為單一一個節點，因此 i 會不斷扣一並在過程中逐步將元素加到 result 中。

此時依照先前的方法同樣為 2 及 1 兩個節點設置 begin[] 。

最後使用 result 收回

接著再使用 rebuild_list_link 設置回原本的雙向環狀鍊結串列。

研讀 A comparative study of linked list sorting algorithms

第 2 周測驗題

測驗 1

延伸問題 1

在此使用 Linux 核心風格 List API 來開發快速排序程式碼。使用 list_head 來建立鍊結串列，並使用變數型別 uint16_t 來紀錄要被排序的數值。

struct listitem {
    uint16_t i;
    struct list_head list;
};

以下為測試與輔助函式:
cmpint : 實作 quicksort 的比較，因為傳入的參數是 void * 不能做 bitops ，因此要先做強制型別轉換 (const uint16_t *)
random_shuffle_array : 打亂 operations 裡的排列順序，於迴圈中 get_unsigned16 將決定每階段互相交換的位置
getnum :

• s1、s2、s3 以 static 宣告，因此只會初始化一次
• 使得每獲取一次亂數就更新一次，下次獲取的亂數就不會與現在一致，作到亂數的效果。

s1=(s1*171)%30269
s2=(s2*172)%30307
s3=(s3*170)%30323

get_unsigned16 : 呼叫上述 getnum 函式兩次製造16位元的亂數
main :
對含有 256 個數字的陣列 value 進行隨機排序，並建立一個鏈結串列加入這些數字。接著對鏈結串列執行 list_quicksort 快速排序，最後比較陣列 value 和鏈結串列的值 i ，若不同會因為巨集 assert 而終止程式。

主要函式:
list_quicksort

1. 首先，要選擇鏈結串列第一個元素作為 pivot ，由於 head 會指向整個鏈結串列，因此使用 list_first_entry ，找到指向的鏈結串列第一個元素。
2. 之後，要從鏈結串列裡移除 pivot ，好讓 quicksort 對鏈結串列剩餘的元素進行快速排列。
3. 以 list_for_each_entry_safe 逐步走訪整個鏈結串列， 將值小於 pivot 的用 list_move_tail 移入 list_less ，反之，大於的值移入 list_greater

pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);
list_for_each_entry_safe (item, is, head, list) {
    if (cmpint(&item->i, &pivot->i) < 0)
        list_move_tail(&item->list, &list_less);
    else
        list_move_tail(&item->list, &list_greater);
}

4. 透過遞迴對 pivot 左右兩邊的鏈結串列進行排序，當鏈結串列排到不能在排時就返回(只有單一元素)。
5. 最後，當整個鏈結串列都排序完畢時，就要將 pivot 、 list_less 、 list_greater 合併。

list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);

延伸問題 2

測驗 2

// ```c
// static const int mask[] = {0, 8, 12, 14};
// static const int magic[] = {2, 1, 0, 0};

// 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 == 3)
// return upper ? magic[upper] : 2 + magic[lower];
// return upper ? clz2(upper, c + 1) : (16 >> ©) + clz2(lower, c + 1);
// }
// //c
// uint64_t sqrti(uint64_t x)
// {
// uint64_t m, y = 0;
// if (x <= 1)
// return x;

// int total_bits = 64;

// /* clz64(x) returns the count of leading zeros in x.
// * (total_bits - 1 - clz64(x)) gives the index of the highest set bit.
// * Rounding that index down to an even number ensures our starting m is a
// * power of 4.
// */
// int shift = (total_bits - 1 - clz64(x)) & ~1;
// m = 1ULL << shift;

// while (m) {
// uint64_t b = y + m;
// y >>= 1;
// if (x >= b) {
// x -= b;
// y += m;
// }
// m >>= 2;
// }
// return y;
// }
// ```

延伸問題 1

延伸問題 2

延伸問題 3

測驗 3

延伸問題 1