2024q1 Homework2 (quiz1+2)

contributed by < steven523 >

第一週測驗題

測驗一

此題參考〈Optimized QuickSort — C Implementation (Non-Recursive)〉，透過 quicksort() 實作非遞迴的快速排序法，並運用 stack 來模擬遞迴函式呼叫

以下是鏈結串列的結構體，有一個 long 儲存的資料及一個 next 指標，可判斷其為單向的鏈結串列，還有兩個指標為 left 和 right

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

首先程式一開始為 test_arr 這個整數型態的陣列配置記憶體空間，接著指派 0~99999 給它，並呼叫 shuffle 函式將陣列中的元素打亂

list_construct 函式用於建立一個新節點，並將其插入到鏈結串列 list 的頭部，然後返回鏈結串列的首節點
所以下列程式整體上來說是透過 while 將 test_arr[count] 的值逐一插入 list 頭部，最終形成的鏈結串列會與 test_arr[count] 順序相反

node_t *list_construct(node_t *list, int n)
{
    node_t *node = malloc(sizeof(node_t));
    node->next = list;
    node->value = n;
    return node;
}
int main(int argc, char **argv)
{
    node_t *list = NULL;
    ...
    while (count--)
        list = list_construct(list, test_arr[count]);
    ...
}

list_add 與 list_construct 用途相似，都是將節點插入鏈結串列的頭部，只差在 list_construct 傳入值的型態是 int，所以要為其先用 malloc 配置一個記憶體位置

qiuck_sort 函式在每一輪迴圈都會經過以下步驟

首先宣告L 及 R 分別指向鍵結串列的第一個節點與最後一個節點，並指派第一個節點為 pivot，p 為下一個節點，最後將 pivot 與原鏈結串列分開

利用以下程式碼走訪整個串列，並判斷目前的節點是否大於 pivot->value，是的話加入 right，否則加入 left

while (p) {
    node_t *n = p;
    p = p->next;
    list_add(n->value > value ? &right : &left, n);
}

此為原鏈結串列初始化過後的樣子，left 和 right 在每次回全結束前都會重設為空的鏈結串列

因為 p 指向的值 2 小於 pivot 的 3，所以將 p 指向的節點透過 list_add 函式加入 left 頭部， 接著 p 指向下一個節點

持續同樣操作直到整個鏈結串列走訪完的結果會像下圖

begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right)

最後透過上述程式碼將 left 頭尾放入 beg[i], end[i] 中來取代原本的整個佇列的位置，right 頭尾則放入 beg[i+2], end[i+2]，並將 i+2 後重新下輪迴圈進行排序

如果 L != R 成立，即 beg[i] 等於 end[i]，代表此佇列只有一個節點，此時就將該節點加入 result 。接著 i– 後會將上圖 pivot 節點再加入 result ，最後對上圖 left 進行排序直到整個鏈結串列排序完成。

整體插入 result 順序為 right -> pivot -> left，因為 list_add 是從頭部插入所以能知道結果是由小到大排序好的鏈結串列

不用列出參考題解，你專注在程式碼的原理即可。

測驗二

Tim sort 為 Tim Peter 提出，結合了合併排序和插入排序的特點

首先識別出資料中已排序的子序列 (這些子序列稱為 run），然後透過不斷合併這些 run 來達成全資料範圍的排序

Timsort 採用一組堆疊 (stack) 來暫存 run，此舉是為了避免在一開始就掃描整個資料範圍來產生 run，從而降低記憶體開銷。過程中，Timsort 運用 merge_collapse 函式來確保堆疊上的 run 長度保持平衡。該函式主要檢查堆疊頂端的 3 個 run 是否滿足以下原則：

1. A 的長度要大於 B 和 C 的長度總和。
2. B 的長度要大於 C 的長度。

不用列出參考題解，你專注在程式碼的原理即可。

第二週測驗題

測驗一

透過 preoreder 和 inorder 的二元樹排序，重建原本的二元樹。

參考 Linux 核心的 hash table 實作
hlist_node 間接指標

• 僅有末端指標內容是 NULL。
• next 指向相鄰的節點本身，而 pprev 指向指著自身節點的指標

void hlist_delete_node(struct hlist_node *n)
{
    struct hlist_node *next = n->next;
    struct hlist_node **pprev = n->pprev;
	
    // Since there is always a pointer which points to node n,
    // no special case is needed to deal with.
    *pprev = next;
    if (next)
        next->pprev = pprev;
}

• *pprev 是指上個節點的 next 指標
• **pprev 就是上一個節點本身，所以通過執行 *pprev = next; 就代表將 n 的上一個節點的 next 指向 n 的下一個節點，實現將 n 從鏈結串列中移除的操作

hlist_add_head

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    if (h->first)
        h->first->pprev = &n->next;
    n->next = h->first;
    n->pprev = &h->first;
    h->first = n;
}

這個函式執行 hash table 中，將 n 插入雙向鏈結串列。將 hlist_node n 插入於 hlist_head h 的前端。

find

static int find(int num, int size, const struct hlist_head *heads)
{
    struct hlist_node *p;
    int hash = (num < 0 ? -num : num) % size;
    hlist_for_each (p, &heads[hash]) {
        struct order_node *on = list_entry(p, struct order_node, node);
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

將傳入的 num 尋找雜湊表中的位置索引。宣告 hash 得知該節點放於雜湊表中的哪個槽，並以 hlist_for_each 走訪每個節點，尋找節點並回傳索引。

dfs

static struct TreeNode *dfs(int *preorder,
                            int pre_low,
                            int pre_high,
                            int *inorder,
                            int in_low,
                            int in_high,
                            struct hlist_head *in_heads,
                            int size)
{
    if (in_low > in_high || pre_low > pre_high)
        return NULL;

    struct TreeNode *tn = malloc(sizeof(*tn));
    tn->val = preorder[pre_low];
    int idx = find(preorder[pre_low], size, in_heads);
    tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
                   in_low, idx - 1, in_heads, size);
    tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
                    idx + 1, in_high, in_heads, size);
    return tn;
}

Preorder 中第一筆資料為根，而 Inorder 中左子樹及右子樹之資料分別在根的左右，所以利用 find() 得到根的 index 後，即可切割出左子樹及右子樹，且因為 Preorder 中左子樹之資料必定在右子樹之資料前面，所以先對左子樹遞迴做 dfs()``，接著對右子樹遞迴做 dfs()` 便可得到整棵樹

node_add

static inline void node_add(int val,
                            int idx,
                            int size,
                            struct hlist_head *heads)
{
    struct order_node *on = malloc(sizeof(*on));
    on->val = val;
    on->idx = idx;
    int hash = (val < 0 ? -val : val) % size;
    hlist_add_head(&on->node, &head[hash]);
}

這裡執行的是建立一個 node 並將其存放至 hash table。建立一個新節點，宣告 hash 決定該節點要存放於 hash table 的哪個槽裡，最後使用 hlist_add_head 將該節點加入 hash table

buildTree

static struct TreeNode *buildTree(int *preorder,
                                  int preorderSize,
                                  int *inorder,
                                  int inorderSize)
{
    struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads));
    for (int i = 0; i < inorderSize; i++)
        INIT_HLIST_HEAD(&in_heads[i]);
    for (int i = 0; i < inorderSize; i++)
        node_add(inorder[i], i, inorderSize, in_heads);

    return dfs(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1,
               in_heads, inorderSize);
}

透過前序和中序來完成