# 2023q1 Homework1 (quiz1) contributed by < `kart81604` > :::danger 注意細節！ :notes: jserv ::: ## 測驗一 :::success AAA = `item` BBB = `list` CCC = `list_for_each_entry_safe` DDD = `list_move_tail` EEE = `list_move_tail` FFF = `list_splice_tail` ::: #### 程式碼運作原理 參數介紹 : `pivot` : queue 中第一個元素，拿來做比較。 `list_less` : 小於 pivot 的 `item` 會接上此 queue 。 `list_greater` : 大於等於 pivot 的 `item` 會接上此 queue 。 將 input 的 queue 的第一個 `item` 作為 pivot ，再將比 pivot 小的 `item` 組成新的 `list_less` queue ，其餘的為 `list_greater` queue 。 ```graphviz digraph init{ rankdir = "LR" head[label="head",shape=squre] pivot[label="6",color=red] head->pivot->7->5->9->2 } ``` ```graphviz digraph sort{ rankdir = "LR" greater[label="list_greater", shape=squre] less[label="list_less", shape=squre] less->5->2 greater->7->9 6[color=red] } ``` 再利用遞迴，對這兩個 queue 進行排序，這邊展示排序 `list_less` 。 :::info 這邊的 `list_less'` 跟 `list_greater'` ，與第一輪的不同。 ::: ```graphviz digraph sort{ rankdir="LR" greater[label="list_greater'",shape=squre] less[label="list_less'",shape=squre] pivot[label="5",color=red] less->2 } ``` ```graphviz digraph sort{ rankdir="LR" less[label="list_less",shape=squre] less->2->5 } ``` 排序完成後回到第一輪，再將兩者組合起來。 ```graphviz digraph sort{ rankdir = "LR" greater[label="list_greater", shape=squre] less[label="list_less", shape=squre] less->2->5 greater->7->9 6 } ``` ```graphviz digraph sort{ rankdir="LR" head[shape=squre] head->2->5->6->7->9 } ``` --- ## 測驗二 :::success GGGG = `list_for_each_entry_safe` HHHH = `list_add_tail` IIII = `stack[++top]` JJJJ = `stack[++top]` KKKK = `stack[top--]` ::: ### 程式碼運作原理 參數介紹 : `partition` : 用作對於 `stack` 最上面非空且非單的 queue ，進行分割。 `pivot` : queue中的第一個元素當作比較的依據。 `list_less` : 將 queue 中小於 `pivot` 的插入此 queue 的第一個。 `list_greater` : 將 queue 中大於等於 `pivot` 的插入此 queue 的第一個。 :::warning 下方的列舉 (即 `- ` 開頭的項目) 非必要，使用簡潔且清晰的描述。 :notes: jserv > 好的，已更改 ::: 在進到第一個 `while` 迴圈之前，建立了一個 `list_head` 陣列 `stack` ，再將 input 的 queue 接到 `stack[0]` 上面。(圖僅列舉有連結 queue 的部分，且 queue 是用doubly-linked list 連結，下圖應注意所連結的 queue 的狀態) ```graphviz digraph sta{ rankdir="LR" subgraph cluster_stack{ label="stack" a[label="0",shape=squre] } a->7->5->8->4->9 } ``` 進入 `while` 迴圈，初始化 `partition` ，然後將 `stack` 最上面的 queue 接到 `partition` 後面。 (紅色表示 pivot ) ```graphviz digraph partition{ rankdir="LR" part[label="partition",shape=squre] pivot[label="7",color=red] part->pivot->5->8->4->9 } ``` 如果 `partition` 不為空且不為單，則初始化 `list_less` 跟 `list_greater` ，將 `partition` 所接的 queue 的第一個獨立出來作為 `pivot` ，對 queue 中每個值做比較，比 `pivot` 小的接到 `list_less` ， 大於等於就接到 `list_greater` ，然後將剛剛獨立出來的 `pivot` 接到 `list_less` 的 tail ，接著將 `list_greater` 跟 `list_less` 接到 `stack` 上。 ```graphviz digraph sta{ rankdir="LR" subgraph cluster_stack{ label="stack" b[label="1",shape=squre] a[label="0",shape=squre] } pivot[label="7",color=red] a->9->8 b->4->5->pivot } ``` 如果 `partition` 為空或為單，則把 `stack` 最上面的queue，接到 `head` 的後面。 ```graphviz digraph sta{ rankdir="LR" subgraph cluster_stack{ label="stack" stack2[label="2",shape=squre,color=red] stack1[label="1",shape=squre] stack0[label="0",shape=squre] } stack0->9->8 stack1->7->5 stack2->4 } ``` ```graphviz digraph sta{ rankdir="LR" subgraph cluster_stack{ label="stack" stack2[label="2",shape=squre,color=red] stack1[label="1",shape=squre] stack0[label="0",shape=squre] } stack0->9->8 stack1->7->5 head[label="head",shape=squre] head->4 } ``` --- ## 測驗三 ::: success LLLL = `(uintptr_t)(a) ^ (uintptr_t)(b)` MMMM = `&list->tail` 或 `node` PPPP = `real_next->cmp` ::: ### 程式碼運作原理 藉由 `xorlist_for_each` 的程式碼，其中的參數 `rp` 代表目前所指的點， `node` 指的是 `rp` 的下一個點， `rn` 指的是 `node` 的下一個點，也就是 `rp` 的下下一個點， `rn `藉由 `address_of(rp, node->cmp)` 來得到`node` 下一個點的記憶體地址。