# 2023q1 Homework1 (quiz1)
contributed by < [willow11235811](https://github.com/willow11235811) >
## 測驗題目
:::danger
不用抄題目，闡述你的認知。
:notes: jserv
>已修改
:::
上述快速排序法，會將以 ```pivot``` 分割出數值較小的 ```list_less``` 與數值較大的 ```list_greater``` 。
```CCC``` 作用為依序走訪整個所有節點，應使用 ```list_for_each_entry_safe``` 。
用以對節點內含值比較的函式 ```cmpint``` 會比較 ```itm``` 和 ```pivot``` 的值，若 ```itm``` 較小，會回傳負值。
```DDD``` 應將較 ```pivot``` 小的節點移出並加入 ```list_less``` 中； ```EEE``` 則是處理相等或較大的節點。
因此 ```DDD``` 與 ```EEE``` 應為 ```list_move_tail``` ，將移出的節點附加到對應佇列的尾部。
```c
list_add(&pivot->list, head);
list_splice(&list_less, head);
FFF(&list_greater, head);
```
合併佇列時， ```list_add``` 將 ```pivot``` 節點加入 ```head``` 佇列的頭部。
```list_splice``` 將 ```list_less``` 黏貼至 ```pivot``` 節點之前，
因此 ```FFF``` 應為 ```list_splice_tail```，要將 ```list_greater``` 黏貼至 ```pivot``` 節點之後。
:::spoiler 測驗1 完整程式碼
```c
static void list_sort(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head))
return;
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
struct item *pivot = list_first_entry(head, struct item, list);
list_del(&pivot->list);
struct item *itm = NULL, *is = NULL;
list_for_each_entry_safe (itm, is, head, list) {
if (cmpint(&itm->i, &pivot->i) < 0)
list_move_tail (&itm->list, &list_less);
else
list_move_tail (&itm->list, &list_greater);
}
list_sort(&list_less);
list_sort(&list_greater);
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
}
```
:::
---
## 測驗 2
```c
#define MAX_DEPTH 512
struct list_head stack[MAX_DEPTH];
```
利用 ```stack``` ，將程式改成迭代式的實作，但本實作能處理的節點數量顯然受限於 ```MAX_DEPTH``` 的大小。
```c
int top = -1;
list_splice_init(head, &stack[++top]);
```
首先，將欲處理的佇列經過 ```list_splice_init``` 接到 ```stack[0]``` 的頭部。
初始化 ```partition``` 作為處理待分割佇列的 ```list_head```。
```top``` 用以表示 ```stack``` 中還有多少佇列，也代表目前處理至 ```stack[top]``` 位置的佇列。
只要 ```top >= 0``` ，而且用以處理待分割佇列的 ```partition``` 中有兩個以上的節點，函式就要進行排序，直到 ```partition``` 中沒有或只剩一個節點。
```c
struct item *pivot =
list_first_entry(&partition, struct item, list);
list_del(&pivot->list);
INIT_LIST_HEAD(&pivot->list);
```
排序的方式是先把 ```partition``` 中的第一個節點 ```pivot``` 取出，作為排序比較的基準。
```c
GGGG (itm, is, &partition, list) {
list_del(&itm->list);
if (cmpint(&itm->i, &pivot->i) < 0)
list_move(&itm->list, &list_less);
else
list_move(&itm->list, &list_greater);
}
```
```GGGG``` 應為 ```list_for_each_entry_safe``` ，用以走訪整個 ```partition```。
將 ```pivot``` 以後的節點與 ```pivot``` 比較，較小者移動至 ```list_less``` 之頭部，較大者移動至 ```list_greater``` 的頭部。
```c
HHHH (&pivot->list, &list_less);
```
```pivot``` 也是需要處理的節點。
此處 ```HHHH``` 應為 ```list_add_tail``` ，將 ```pivot``` 加入 ```list_less``` 的尾部等待處理。
```c
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, IIII);
if (!list_empty(&list_less))
list_splice_tail(&list_less, JJJJ);
```
接下來要將 ```list_greater``` 和 ```list_less``` 佇列依序連接至 ```stack``` 上，模擬遞迴呼叫。
```IIII``` 應為 ```stack[++top]``` ， ```JJJJ``` 應為 ```stack[++top]```。
以第一次進入 ```while``` 迴圈為例，此時 ```top``` 值為 -1 ，利用 ```++top``` 將 ```top``` 值變為 0 ，即將 ```stack``` 佇列的第一個元素 ```stack[0]``` 作為插入 ```list_greater``` 的位置，並以同樣操作把 ```list_less``` 插入至 ```stack[1]``` 的位置。
此時 ```top``` 值為 1， 代表目前 ```stack``` 陣列中有 2 個排序後的佇列。
```c
list_splice_init(&stack[top--], &partition);
```
重新進入 ```while``` 迴圈，只要 ```top>=0``` ，就繼續對最尾部的 ```stack[top]``` 進行排序。
若這時 ```stack[top]``` 內只有一個元素，就會進入 ```else``` 的敘述。
```c
list_splice_tail(&partition, &stack[top]);
while (top >= 0 && list_is_singular(&stack[top])) {
struct item *tmp =
list_first_entry(&stack[top], struct item, list);
list_del(&tmp->list);
INIT_LIST_HEAD(KKKK);
list_add_tail(&tmp->list, head);
}
```
經過反覆的排序操作，排序後的佇列會由大至小的從 ```stack``` 的頭部向尾部分佈，此時 ```stack[top]``` 的元素為佇列中最小的元素。
將該元素以 ```list_del``` 自 ```stack[top]``` 佇列中刪除，並以 ```list_add_tail``` 加入 ```head``` 佇列中。
```KKKK``` 應為 ```stack[top--]``` ，將被取出元素的 ```stack[top]``` 初始化，並將 ```top``` 減一，更新目前 ```stack``` 陣列的元素數值。
反覆上述操作，最後 ```head``` 佇列為元素排序後的結果。
:::spoiler 測驗2 完整程式碼
```c
#define MAX_DEPTH 512
static void list_sort_nr(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head))
return;
struct list_head stack[MAX_DEPTH];
for (int i = 0; i < MAX_DEPTH; i++)
INIT_LIST_HEAD(&stack[i]);
int top = -1;
list_splice_init(head, &stack[++top]);
struct list_head partition;
INIT_LIST_HEAD(&partition);
while (top >= 0) {
INIT_LIST_HEAD(&partition);
list_splice_init(&stack[top--], &partition);
if (!list_empty(&partition) && !list_is_singular(&partition)) {
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
struct item *pivot =
list_first_entry(&partition, struct item, list);
list_del(&pivot->list);
INIT_LIST_HEAD(&pivot->list);
struct item *itm = NULL, *is = NULL;
list_for_each_entry_safe (itm, is, &partition, list) {
list_del(&itm->list);
if (cmpint(&itm->i, &pivot->i) < 0)
list_move(&itm->list, &list_less);
else
list_move(&itm->list, &list_greater);
}
list_add_tail (&pivot->list, &list_less);
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, stack[++top]);
if (!list_empty(&list_less))
list_splice_tail(&list_less, stack[++top]);
} else {
top++;
list_splice_tail(&partition, &stack[top]);
while (top >= 0 && list_is_singular(&stack[top])) {
struct item *tmp =
list_first_entry(&stack[top], struct item, list);
list_del(&tmp->list);
INIT_LIST_HEAD(stack[top--]);
list_add_tail(&tmp->list, head);
}
}
}
}
```
:::
---
## 測驗 3
Sign in with Wallet
Connect another wallet