2024q1 Homework2 (quiz1+2)

測驗一

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

由下圖可知，雖然題目中定義的結構有點複雜，但其實就是鏈結串列的變形，多了一個 next 指標指向下個節點。

注意到因 Linux 的鏈結串列式環狀的，因此最後一個節點的

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 左邊的子陣列和右邊的子陣列分別重複進行相同的操作，直到整個陣列排序完成。

測驗一

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

由下圖可知，雖然題目中定義的結構有點複雜，但其實就是鏈結串列的變形，多了一個 next 指標指向下個節點。

注意到因 Linux 的鏈結串列式環狀的，因此最後一個節點的

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 實作。

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