2025q1 Homework2 (quiz1+2)

contributed by <allen741>

第 1 週測驗題

測驗1

程式脈絡

直接觀察 main 函式，一開始呼叫函式test_suite，而後呼叫test_list函式便開始進行函式list_insert_before的測試，第一次測試插入1000個元素在鏈結串列最前面

for (size_t i = 0; i < N; i++)
        list_insert_before(&l, l.head, &items[i]);

然後利用巨集my_assert檢查鏈結串列的值是否正確

while (cur) {
    my_assert(cur->value == k, "Unexpected list item value");
    k--;
    cur = cur->next;
}

第二次測試是1000個list_item全插入在鏈結串列最後面，一樣利用assert巨集檢查插入的元素的成員value是否和預期相同，若不同則會列印 error 訊息。

解題

從題目可以看到是要實作鏈結串列的插入，且需要插入到 before 這個指標指向的元素前面，而需要回答的地方為 for 迴圈處如何遍歷鏈結串列找到 before 指標指向的元素，因此需回去重新觀察鏈結串列的資料結構才有辦法回答

#include <stddef.h>
typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;

上面 list_item_t 的宣告讓 list_item_t 成為 struct list_item 的別名，因此之後初始化 list_item items[N]不需寫成 struct list_item items[N]，只需寫 list_item_t items[N]，這樣可以簡化程式碼。從上方圖形可以知道鏈結串列的結構名稱為 list_t，它含有一個 list_item 的指標 head 指向鏈結串列的第一個元素 list_item，而 list_item 包含變數 value 用來儲存整數資料和指標 next 用來指向下一個元素。

觀察函式 list_insert_before 內有一個指標的指標 p 作為 for 迴圈的索引，可以知道它是用來指向 list_item * ，因此只能用來指向 head 或是 next，因為題目說如果輸入參數list_item_t *before為head則插入元素到最前面，且迴圈內將 p 所指向的指標指向輸入參數item，可以得知 AAAA 的答案一定是 head 的地址，因此答案為&l->head。

因為item要插入到before的前面，因此迴圈必須在搜尋到before時跳出，因此BBBB的答案應為before，而CCCC應為 p 所指到的list_item的指標next的地址，因此為&(*p)->next，如此可以使原本指到before的指標在迴圈內改為指到item。

插入完item後需要將item的next指標指向before使鏈結串列完整連接，因此DDDD應為item->next或是(*p)->next，讓item能連接到before。

測驗2

程式脈絡 & 解題

題目所在的函式是要在記憶體中尋找一個free block，程式碼透過二元搜尋樹記錄不同大小的free block，透過函式find_free_tree找到適合的free block後，需要找到替代它的block，因此需要從它的子樹尋找predecessor來替代它以維持二元搜尋樹的結構。

題目是在左右子樹都存在元素的情況下尋找predecessor，從註解/* Find the in-order predecessor: * This is the rightmost node in the left subtree. */可以知道要尋找左子樹的最右邊的元素，一開始進入while迴圈前已將pred_ptr設為左子樹的根節點，因此只需在while迴圈持續尋找最右邊的節點，所以EEEE為(*pred_ptr)->r才能在遇到NULL時跳出迴圈，而FFFF則為pred_ptr所指向的節點的右子節點的地址，因此為&(*pred_ptr)->r。

之後透過函式find_predecessor_free_tree再次搜尋predecessor，並使用assert巨集檢查是否找到的兩個predecessor相同，若不相同則終止程式。

最後，根據找到的predecessor是否是原來要移除的節點的左子節點來決定如何調整子樹，若不是的話則需要透過遞迴呼叫移除predecessor，因為需要從predecessor的左子樹尋找它的predecessor

另外，如果要移除的target只有左子樹或右子樹只需要直接將左子節點或右子節點替代原來的節點即可，最後將要移除的target所指向左右子節點的指標設為NULL即結束函式。

測驗3

程式脈絡

函式rebuild_list_link

題目是要在雙向鏈結串列實作非遞迴的quicksort，函式rebuild_list_link是在quicksort排序完後對每個節點的prev指標要進行重建，因為quicksort是以節點的next指標排序而不管節點的prev指標。透過while迴圈將全部的節點的prev指標重建後，需要再將鏈結串列的最後一個元素的next指標指向head並將head的prev指標指向最後一個元素才能完成雙向鏈結串列。

函式quicksort

quicksort函式一開始宣告begin[max_level]做為儲存left、pivot、right未排序鏈結串列的指標陣列，max_level的值設為鏈結串列的2倍大小以確保當所有元素都被分在left或right時有足夠的空間進行排序。

在while迴圈中會以指標L儲存begin[i]指向的鏈結串列的第一個元素，以指標R儲存begin[i]最後一個元素，比較它們是否相同。

1.L和R不相同

begin[i]指向的鏈結串列的元素至少有兩個，需要將所有元素和pivot(第一個元素)比大小後加入left或right這兩個指標所指向的鏈結串列中，最後將left傳給 begin[i]，pivot 傳給begin[i+1]，right傳給begin[i+2]後，繼續對begin[i+2]也就是right指向的鏈結串列做排序直到排序出整個鏈結串列中最大值的元素為止，這時，L才會第一次等於R。

2.L和R相同

begin[i]指向的鏈結串列的元素只有一個，因此將它的next指標指向已經排序好的鏈結串列之中的最小元素result，再將result設為它自己後，繼續對begin[i-1]指向的鏈結串列做排序，若begin[i-1]指向的鏈結串列不只一個元素則會進入第一種狀況繼續分割成三個鏈結串列。

解題

因為value會持續和鏈結串列的元素比大小，因此HHHH應該為pivot所指向的元素的值，因此答案為list_entry(pivot,node_t,list)->value，n_value會經由IIII不斷更新後再和value做比較，因此答案為用來遍歷鏈結串列的指標n所指向的元素的值，為list_entry(n,node_t,list)->value，最後JJJJ和KKKK即為pivot或right才能將結果存在begin陣列中，因為題目有說明會先對right指向的鏈結串列做排序且之後變數i繼續加2，因此JJJJ為pivot而KKKK為right。

第 2 週測驗題

測驗1

cmpint

實作quicksort的數字比較，因為傳入的參數是void *無法存取，因此需要強制轉型為uint16_t *後才能比較數字大小，這裡可以知道數字為無號16位元整數，因此範圍為0~65535

getnum

用來產生亂數，首先宣告3個16位元無號整數s1、s2、s3，並初始化為2、1、1，因為前面為 static 的宣告因此只會初始化一次，之後便做以下計算

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

函式回傳的值為 s1 ^ s2 ^ s3，而且只有8位元，代表三個16位元的數經過 xor 運算後只回傳最右邊的8位元，可以知道這個函式用來產生0~255之間的亂數

get_unsigned16

呼叫上述getnum函式兩次製造16位元的亂數

main

對含有256個數字的陣列value進行隨機排序後，建立一個鏈結串列加入這些數字，再對value執行qsort快速排序，對鏈結串列執行list_quicksort快速排序，最後比較陣列value和鏈結串列的值是否相同，若不同會因為巨集assert終止程式

list_quicksort

對雙向鏈結串列進行快速排序，選擇鏈結串列第一個元素作為pivot，透過遞迴呼叫排序比pivot大和小的元素

延伸問題

改進 random_shuffle_array

 for (uint16_t i = len - 1; i > 0; i--) {
        uint16_t j = get_unsigned16() % (i + 1); // 在 [0, i] 範圍內選擇
        uint16_t temp = operations[i];
        operations[i] = operations[j];
        operations[j] = temp;
     }

將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting

因為list_move是將元素插入到鏈結串列的第一個位置，而list_move_tail是插入到鏈結串列的最尾端，list_for_each_entry_safe會從鏈結串列的開頭開始和 pivot 比大小，因此若使用list_move會讓較後面的元素排在前面，造成有相同數值的元素經過排序後順序顛倒，無法滿足 stable sorting

測驗2

clz2

用來計算32位元無號整數從最左邊的位元往右遇到1之前有幾個0，c的範圍為0~3，用來控制x要提取的位元數的範圍

c = 0  upper = 第 16 ~ 31 bit , lower = 第 0 ~ 15 bit
c = 1  upper = 第  8 ~ 15 bit , lower = 第 0 ~  7 bit
c = 2  upper = 第  4 ~  7 bit , lower = 第 0 ~  3 bit
c = 3  upper = 第  2 ~  3 bit , lower = 第 0 ~  1 bit

函式會在c不等於3時繼續遞迴呼叫，直到最後等於3時會利用magic陣列計算最後第0~3位元有幾個0，如此即完成計算32位元的無號整數中從最左邊的位元往右遇到1之前有幾個0

sqrti

計算64位元無號整數的平方根的整數值，函式一開始先從左邊開始找出第一個數值為1的位元的索引值，若為奇數則會因為和~1做邏輯and運算而減1得到變數shift，之後設定64位元無號整數m第shift位的位元為1，利用二進制開平方法從最高位開始逐步逼近平方根

x = 63 = 16 + 47 = 36 + 27 = 49 + 13 
x = 1000 = 256 + 744 = 576 + 424 = 784 + 216 = 900 + 100 = 961 + 39

在 x = 63 時，shift = 4，因此m為16，因為m< 63，因此會繼續測試是否

$6^2$=

$(4+2{)}^2$ 會大於63，再測試

$7^2$ =

$(4+2+1{)}^2$ =49 < 63後，可以知道63的平方根的整數值為7

在 x = 1000 時，shift = 8，因此會測試

$2^8$ =

${16}^2$ = 256 ，

${24}^2$=

$(16+8{)}^2$ = 576，

${28}^2$=

$(16+8+4{)}^2$ = 784，

${30}^2$=

$(16+8+4+2{)}^2$ = 900，

${31}^2$=

$(16+8+4+2+1{)}^2$ = 961，在m為 1 時961仍然小於1000，因此得到結果為31

在迴圈中，會將m加到y，因為最後的答案應為每次加到y的m的開根號，因此每次迴圈均會將y除以2，總共會執行

$\frac{shift}{2}$次，讓y透過位元右移對其中不同的m值開根號，以 x = 1000 為例
y = 0
y = 256
y =

$\frac{256}{2}$ = 128
y =

$\frac{256}{2}$ + 64 = 192
y =

$\frac{256}{4}$ +

$\frac{64}{2}$ = 96
y =

$\frac{256}{4}$ +

$\frac{64}{2}$ + 16 = 112
y =

$\frac{256}{8}$ +

$\frac{64}{4}$ +

$\frac{16}{2}$ = 56
y =

$\frac{256}{8}$ +

$\frac{64}{4}$ +

$\frac{16}{2}$ + 4 = 60
y =

$\frac{256}{16}$ +

$\frac{64}{8}$ +

$\frac{16}{4}$ +

$\frac{4}{2}$ = 30
y =

$\frac{256}{16}$ +

$\frac{64}{8}$ +

$\frac{16}{4}$ +

$\frac{4}{2}$ + 1 = 31

這也可以驗證為何一開始要找偶數位元且每次m要右移2位(

$m÷4$)而不是1位，因為奇數位所表達的數值無法開根號為整數且

$\sqrt{2}$不是整數

延伸問題

在 while 迴圈之後加入以下判斷式即可對

$\sqrt{x}$向上取整數

if(x > 0){
  y++;
}

測驗3

hash

將輸入值value乘上 0x61C88647後右移22個位元得到在 hash table 的索引值，其中，0x61C88647轉成有號整數為 2654435769，剛好是

$2^{32}$ *

$\frac{2}{1+\sqrt{5}}$，即

$2^{32}$除以黃金比例

map_add

將新的資料加入 hash table，不管是否有相同索引值的元素已在 hash table中，新的資料均會加入到鏈結串列的開頭而非結尾，因為此為單向鏈結串列

map_deinit

函式會釋放 hash table 中所有的鏈結串列，每次刪除鏈結串列的元素時，會先將元素從鏈結串列移除再釋放記憶體，也就是會把鏈結串列的頭指標改成指向下一個元素，並把下一個元素的pprev(指標的指標)改成指向頭指標，讓欲刪除的元素無法透過鏈結串列搜尋後才釋放記憶體，這裡不了解的地方是為何需要如此大費周章的在鏈結串列更改指標移除元素，因為函式到最後仍然會將所有的元素包括 hash table 全部刪除，為何不直接釋放記憶體就好還需要特別先從鏈結串列移除後才釋放記憶體?
可能原因: 可能是為了整個 linux kernel 的穩定性，避免指標在刪除元素後有短暫的時間指向未定義的記憶體空間

twoSum

一開始宣告一個 hash table，透過 for 迴圈尋找 target-nums[i] 是否在 hash table 中，若沒有則將nums[i]加入 hash table 中，如果有則代表已找到兩個數相加為 target，因此將結果存入陣列ret並回傳，倘若最後迴圈結束仍然沒有找到兩個數相加為 target，就會回傳空陣列。