# 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 。 結束後