2023q1 Homework1 (quiz1)

contributed by < peter91015 >

題目

測驗一

解釋原理
這個程式碼在實作 quick sort ，並且是以遞迴的方式來進行 divide and conquer。當輸入進來的 list 的節點(不含 head )一個以下的時候就可以直接回傳；而在節點個數兩個以上的時候，必須要對 list 的節點去做分割：其方法是找一個基準的節點 pivot ，這個程式碼取的是 head 的下一個節點(因此對照 list.h，AAA 和 BBB 的答案為 item 和 list )，根據和 pivot 比較的結果放進 list_greater 和 list_less 。所以必須走訪每個 list 上面的節點並且會移除走過得節點(因此 CCC 的答案為 list_for_each_safe)，接著就可以對 list_greater 和 list_less 分別做遞迴呼叫。最後再把 list_greater 和 list_less 的結果分別插入 head 裡面，就會得到排序好的 list (由於是遞增的順序， list_greater 要置入於 head 的後面，故 FFF 的答案是 list_splice_tail)。

解釋原理
這個程式碼一樣是在實作 quick sort，不過這次不用遞迴而是使用迴圈並且搭配自行宣告陣列的方式來模擬原本的遞迴呼叫。
整個程式碼的原理如下：堆疊所儲存的資料為分割過的 list ，並且起始值為整個 linked list 放進 stack[0] 之中。只要在堆疊的還有資料的情況下(即
$t o p \geq 0$ )每次取出一個堆疊上的 list，如果 list 的節點數是兩個以上便在繼續分割為兩個 list 並且放置於堆疊之中(所以對應 III 和 JJJ 的答案皆為 stack[++top])，順序是先放較大的分割；如果 list只有一個以下的節點便不再需要分割，而是要把節點放回 head ，同時因為堆疊取出來的資料會是先從小的開始取出，放回 head 的必須插入在 head的前面，此時該層堆疊已經沒有資料了，要將該層的 list 做 INIT_LIST_HEAD 並且返回上一層，對應到 KKK 必須要是 stack[top–]