2023q1 Homework (quiz1)

contributed by < LambertWSJ >

測驗連結 / GitHub

測驗 1

程式碼填空

• AAA
  $\to$ item
• BBB
  $\to$ list

list_first_entry 要傳入指標的型態還有成員，從而得知 AAA 跟 BBB 為 item 跟 list，目的是從 list 的偏移量(offset) 計算出 item 的地址。

• CCC
  $\to$ list_for_each_entry_safe
• DDD 與 EEE
  $\to$ list_move / list_move_tail

quicksort 的這個階要將 list 分成比 pivot 大以及比 pivot 小的串列。觀察傳入 CCC 的參數還有數量，可以得知 CCC 為 list_for_each_entry_safe。

本測驗的 quicksort 要將串列的內涵值按遞增順序排列，排序完後會得到如下的串列，因此串列的節點如果比 pivot 小的話要將節點移動到 list_less，反之則要將節點移動到 list_greater。

為什麼無論是用 list_move 或是 list_move_tail 都可以? 因為遞迴到最後只會剩下一個節點，亦即排序好的節點，在依據節點是 less 或是 greater 放在 pivot 的前面或是後面，list_move/_tail 的目的是為了分類。

• FFF
  $\to$ list_splice_tail
  最後的階段要將比 pivot 內涵值小的串列放在 pivot 前面，反之則要放在 pivot 後面，這樣串列的內涵值才會是遞增的，因此 list_greater 要透過 list_splice_tail 放在 pivot。

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

上面三行程式碼的圖解如下，其中 FFF 為 list_splice_tail

list_add(&pivot->list, head)

list_splice(&list_less, head)

list_splice_tail(&list_greater, head)

延伸問題

TODO

測驗 2

程式碼填空

以下將 list_less 跟 list_greater 分別稱為大串列跟小串列。

GGGG

$\to$ list_for_each_safe_entry
跟測驗1一樣的原理，透過 list_for_each_safe_entry 將原串列依據 pivot 的內涵值分成大串列跟小串列。

HHHH

$\to$ list_move_tail
IIII

$\to$ &stack[++top]
JJJJ

$\to$ &stack[++top]

將 pivot 合併到小串列，因為排序完要得到內涵值遞增的串列，而 pivot 的內涵值比小串列還大，因此要用 list_move_tail。

另外，stack 具有 LIFO 的特性，所以先推入大串列，再推入小串列，這樣再推出後要合併的時候才會是內涵值遞增的串列。

if (!list_empty(&list_greater))
    list_splice_tail(&list_greater, &stack[++top]);
if (!list_empty(&list_less))
    list_splice_tail(&list_less, &stack[++top]);

當大小串列分割完後，要將其推入到 stack，stack 用來模擬遞迴的過程，保存的是每次遞回分割的大小串列。

KKKK

$\to$ &stack[top--]

如果下一輪迴圈從 stack 推出的串列單一節點，表示串列是排序好的節點，這時候就可以將節點添加到 head，

延伸問題

TODO

測驗 3

程式碼填空