owned this note
owned this note
Published
Linked with GitHub
# 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` 下一個點的記憶體地址。
Google Drive
Gist
Clipboard
Sign in with Wallet
