# 2024q1 Homework2 (quiz1+2)
## 測驗一
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
由下圖可知,雖然題目中定義的結構有點複雜,但其實就是鏈結串列的變形,多了一個 `next` 指標指向下個節點。
注意到因 Linux 的鏈結串列式環狀的,因此最後一個節點的
```graphviz
digraph structs {
node[shape=record]
init [label="<left> left|<data> null|<right> right"]
struct1 [label="<left> left|<data> data|<right> right|<next> next"]
struct2 [label="<left> left|<data> data|<right> right|<next> next"]
struct3 [label="<left> left|<data> data|<right> right|<next> next"];
struct2:right -> struct3[arrowhead=vee, tailclip=true, arrowsize=1];
struct1:right -> struct2[arrowhead=vee, tailclip=true, arrowsize=1];
struct3:left -> struct2[arrowhead=vee, tailclip=true, arrowsize=1];
struct2:left -> struct1[arrowhead=vee, tailclip=true, arrowsize=1];
struct3:right -> struct1[arrowhead=vee, tailclip=true, arrowsize=1];
struct1:left -> init[arrowhead=vee, tailclip=true, arrowsize=1];
struct1:next -> struct2[arrowhead=vee, tailclip=true, arrowsize=1];
struct2:next -> struct3[arrowhead=vee, tailclip=true, arrowsize=1];
struct3:next -> init[arrowhead=vee, tailclip=true, arrowsize=1];
init:next -> struct1[arrowhead=vee, tailclip=true, arrowsize=1];
}
```
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB);
}
return n;
}
```
在 Linux 中,鏈結串列預設皆為環狀的。因此,若要取得最後一個節點,可以逐一檢查 `right` 指標是否指向串列的 `init` 位置。反過來說,其實亦可以先檢查該節點是否剛好是 `init` 位置,若成立,則 `tail` 位於該節點的 `left` 指標。實作中,while 迴圈裡的條件即為綜合上述兩個條件。
在計算鏈結串列亦可用類似的手法,持續走訪直到 `left` 為 `init` 指標,並記錄共計移動了幾次。
在此次快速排序的應用中, `left` 指標儲存彼此節點 `value` 大的單向鏈結串列,而 `right` 則儲存比節點 `value` 小的單向鏈結串列。因此,其實上述定義的結構,是一個單向的鏈結串列。
注意到此段程式碼的目的在於計算有多少個節點比現在這個節點大。因此 `list_length`
的輸入不是要此鏈結串列的開頭,而是子鏈結串列的開頭,而 `tail` 則不用檢查此節點是否為 `init` 的狀況。
### Quick sort
快速排列的概念就是選擇一個 pivot (軸) 元素,然後將所有比 pivot 小的元素放在 pivot 的左邊,所有比 pivot 大的元素放在 pivot 的右邊,這樣 pivot 就位於最終排序的位置上。然後,對 pivot 左邊的子陣列和右邊的子陣列分別重複進行相同的操作,直到整個陣列排序完成。
## 測驗一
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
```graphviz
digraph "__node"
{
node [shape="record"];
rankdir = "LR"
subgraph cluster_a
{
label = "node_t";
node1 [label="<head>value|next|{<left> left |<right> right}"];
}
}
```
由下圖可知,雖然題目中定義的結構有點複雜,但其實就是鏈結串列的變形,多了一個 `next` 指標指向下個節點。
注意到因 Linux 的鏈結串列式環狀的,因此最後一個節點的
```graphviz
digraph structs {
node[shape=record]
init [label="<left> left|<data> null|<right> right"]
struct1 [label="<left> left|<data> data|<right> right|<next> next"]
struct2 [label="<left> left|<data> data|<right> right|<next> next"]
struct3 [label="<left> left|<data> data|<right> right|<next> next"];
struct2:right -> struct3[arrowhead=vee, tailclip=true, arrowsize=1];
struct1:right -> struct2[arrowhead=vee, tailclip=true, arrowsize=1];
struct3:left -> struct2[arrowhead=vee, tailclip=true, arrowsize=1];
struct2:left -> struct1[arrowhead=vee, tailclip=true, arrowsize=1];
struct3:right -> struct1[arrowhead=vee, tailclip=true, arrowsize=1];
struct1:left -> init[arrowhead=vee, tailclip=true, arrowsize=1];
struct1:next -> struct2[arrowhead=vee, tailclip=true, arrowsize=1];
struct2:next -> struct3[arrowhead=vee, tailclip=true, arrowsize=1];
struct3:next -> init[arrowhead=vee, tailclip=true, arrowsize=1];
init:next -> struct1[arrowhead=vee, tailclip=true, arrowsize=1];
}
```
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB);
}
return n;
}
```
在 Linux 中,鏈結串列預設皆為環狀的。因此,若要取得最後一個節點,可以逐一檢查 `right` 指標是否指向串列的 `init` 位置。反過來說,其實亦可以先檢查該節點是否剛好是 `init` 位置,若成立,則 `tail` 位於該節點的 `left` 指標。實作中,while 迴圈裡的條件即為綜合上述兩個條件。
在計算鏈結串列亦可用類似的手法,持續走訪直到 `left` 為 `init` 指標,並記錄共計移動了幾次。
在此次快速排序的應用中, `left` 指標儲存彼此節點 `value` 大的單向鏈結串列,而 `right` 則儲存比節點 `value` 小的單向鏈結串列。因此,其實上述定義的結構,是一個單向的鏈結串列。
注意到此段程式碼的目的在於計算有多少個節點比現在這個節點大。因此 `list_length`
的輸入不是要此鏈結串列的開頭,而是子鏈結串列的開頭,而 `tail` 則不用檢查此節點是否為 `init` 的狀況。
### Quick sort
快速排列的概念就是選擇一個 pivot (軸) 元素,然後將所有比 pivot 小的元素放在 pivot 的左邊,所有比 pivot 大的元素放在 pivot 的右邊,這樣 pivot 就位於最終排序的位置上。然後,對 pivot 左邊的子陣列和右邊的子陣列分別重複進行相同的操作,直到整個陣列排序完成。
而實作中,將節點放在 `pivot` 的左右邊則是改變鏈結串列元素的 `next` 與 `prev` 節點的位置。另外,此動作亦可以 `list_add()` 的 API 實作。
```c
/**
* list_add() - Add a list node to the beginning of the list
* @node: pointer to the new node
* @head: pointer to the head of the list
*/
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
```
一般的快速排序:
非遞迴的快速排序:
如果節點的值比 pivot 大,則繼續走訪
若走訪的節點的值比 pivot 小,則進行交換 swap 。
結束後