2024q1 Homework2

contributed by < patri27826 >

第 1 週測驗題

測驗一

#### AAAA ```diff node_t *list_tail(node_t **left) { while ((*left) && (*left)->next) - left = &(AAAA); + left = &(*left->next) return *left; } ```

第一個AAAA是要填充list_tail，那具體做法就是我在每一個迴圈中，都先去確認說下一次是不是null，是的話就轉到下一個，因此答案為(*left->next)

不用列出參考題解，你只要專注在程式碼和你的洞見。

#### BBBB ```diff int list_length(node_t **left) { int n = 0; while (*left) { ++n; - left = &(BBBB); + left = &((*left)->next); } return n; } ``` 同上一題，也是去找長度，因次這邊也是去`left`的下一個`node`

CCCC

while (p) {
    node_t *n = p;
-   p = CCCC;
+   p = p->next;
    list_add(n->value > value ? &right : &left, n);
}

不用列出參考題解，你只要專注在程式碼和你的洞見。

這邊的while，目的是要把整個列表依照pivot值分到left right，因此CCCC就是p->next以 遍歷整個列表

linked list 為「鏈結串列」，可簡稱為 list (串列)，但不可稱「链表」，該資料結構不具備任何「表」的寓意，參見中華民國教育部重編國語辭典「表」，指「分格或分項以列記事物的文件」，而 linked list 作為資料結構，全然沒有「分格」和「分項」的意涵。

$\to$ 資訊科技詞彙翻譯

DDDD EEEE

     begin[i] = left;
-    end[i] = DDDD;
+.   end[i] = list_tail(&left);
     begin[i + 1] = pivot;
     end[i + 1] = pivot;
     begin[i + 2] = right;
-    end[i + 2] = EEEE;
+    end[i + 2] = list_tail(&right);

這裡主要就是要把begin[i] end[i]分別存left的頭尾，而begin[i+2] end[i+2]存right的頭尾，讓我們再下一次迴圈中去分別比較，有點divide and conquer的感覺，

工程人員說話要精準，避免說「感覺」

是使用到divide and conquer的概念來實作，把大問題拆成小問題來個別解決

程式碼解釋

這個快速排序法是使用非遞迴方式，並在 linked list 上實作，主要做法如下，

1. 首先假設初始佇列如下

2. 我們會先初始化兩個 begin end 陣列， size 為 2 * n ， n 是佇列的長度
   另外初始化兩個 left right 的指標，以及一個 i ，記錄目前 begin end 內元素的長度
3. 我們挑選最左邊的元素作為 pivot ，並遍歷 逐一走訪每個節點，把所有小於 pivot 的都放到 left ，其他放到 right ，結果如下圖

注意用語。

$\to$ 資訊科技詞彙翻譯

4. 將left 的頭尾分別存到 begin[i] end[i]
   將 right 的頭尾分別存到 begin[i+2] end[i+2]
   最後把 pivot 存到begin[i+1] end[i+1]

5. pivit 會逐漸右移，並且每次都先去處理 pivot 右邊部分的佇列，等到右邊部分的到達終止條件，終止條件就是 begin[i] = end[i] ，也就是只剩下一個元素，這時則將 right 的部分加入 result ，如下圖。

6. 隨著 i-- ， 會將所有 begin[i] = end[i] 的點加入 result ，其餘的長度 >1 的佇列，則要再進行一次 Divide and Conquer ，直到所有人都變成單一節點，再依次加入 result

討論及改進

這份程式碼有幾個特點，

1. 會優先處理右邊的子集
2. pivot 選擇第一個元素
3. 用 begin end 陣列來模擬遞迴的情況

改進的方向有如下

1. 在選擇 pivot 上，如果只透過挑選最左邊的 pivot ，如果遇到已排序的陣列，反而是更消耗運算時間，所以如何有效率地挑選 pivot 可以是一個優化方向
   1. 參考避免 Quick Sort 的 Worst Case 發生，可以透過先亂數選取三個點，再取他們之間的中間值作為 pivot 值，可以避免選取到最小或是最大值的可能性。
2. 在小規模佇列去使用到 quick sort 可能反而會對排序需要花費更多的時間，或許可以設一個 threshold ，大於他可以使用 quick sort ，小於他就去呼叫較為簡單的排序法，例如 bubble sort insertion sort

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

測驗二

在 merge 函式，目的是要把 a b 合併，接著利用迴圈比較 a , b 的第一個節點,將較小者加入新鏈結串列的尾部, 加入後要將 tail 指標向後移,下次加入節點時才能繼續加入鏈結串列尾端, 因此 BBBB 為 &a->next，CCCC 則為 &b->next。

在 build_prev_link 中，目的是要把 prev 連接起來，通過一個迴圈，逐一走訪每個節點，並在最後把 head tail 之間的鏈結接起來，因此 DDDD 是 tail->next ， EEEE 是 head->prev

討論及改進

在我看完程式碼後，直覺上會覺得 merge_final 跟 merge 這兩個函式太像了，只有頭跟尾巴的操作以及參數有差異，我會認為這兩個函式是可以合併的，但就會需要考慮到兩邊的 input 跟額外操作等等，但會是一個可以改進的方向

Galloping Mode

---

第 2 週測驗題

測驗一

#### AAAA `hlist_add_head` 是要將節點添加到鏈表的頭部，因此 `AAAA` 要填入 `h->first` ，讓 `n->next` 指向 `h->first` ，把 `n` 接到 `h` 的頭上面 #### BBBB ```diff static int find(int num, int size, const struct hlist_head *heads) { struct hlist_node *p; int hash = (num < 0 ? -num : num) % size; - hlist_for_each (p, BBBB) { + hlist_for_each (p, &heads[hash]) { - struct order_node *on = CCCC(p, struct order_node, node); + struct order_node *on = list_entry(p, struct order_node, node); if (num == on->val) return on->idx; } return -1; } ```

不用列出參考題解，你只要專注在程式碼和你的洞見。

這個 find 函數的目的是在指定的 hash table 中查找特定值 num 對應的索引。

測驗二

測驗三