2024q1 Homework2 (quiz1+2)

contributed by <bclegend>

第一週測驗題

測驗一

程式碼

運作原理

實做 quick sort 演算法,並以以下 node_t 為 linked list 的基礎架構,排序 linked list 中數值的序列。

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

• 原始 linked list
  由下圖所示,在開始時將陣列的最左方的元素紀錄為 pivot

• 首先,移動指標 R 往 linked list 左方移動,若 R 指向的位置儲存的數值小於 pivot ,將指標 R指向位置的數值與指標 L 指向位置的數值交換

• 再來移動指標 L 的位置往右方移動,若 L 指向的位置儲存的數值大於 pivot ,將指標 L指向位置的數值與指標 R 指向位置的數值交換

• 重複以上動作直到 L 與 R 指向同一個位置

此時 linkedlist[0] 到 linkedlist[2] 為新的 linked list 1 ,linkedlist[3]為新的 linked list 2 , linkedlist[4] 到 linkedlist[7] 為新的 linked list 3
並將這三個新的 linked list 再繼續排列直到整個 linked list 排列完成

而在我們的實做中，我們利用 struct __node *left, *right; 進行堆疊,堆疊出左方的 linked list left 以及右方的 linked list right

這次的實做中，我們使用的是改變 node 中數值的方式

改進

1. 是否需要在配置 linked list node_t *begin[max_level], *end[max_level]; 時給 max_level 這麼多的空間？

使用 Linux 核心風格的 List API 改寫上述程式碼

測驗二

第二週測驗題

測驗一

Leetcode
在二元樹的構建過程中，我們可以利用不同的排序方式來唯一確定一顆樹的結構。其中，preorder 採用的是"中->左->右"的順序，inorder 採用的是"左->中->右"的順序。如果我們知道這兩種排序方式，就足以建構出唯一的二元樹。

程式的實作方式是利用 Linux 核心的 hash table。在這個實作中，我們首先以preorder的順序找到根節點的值，接著在inorder中找到對應的左子樹和右子樹元素。然後，我們將左右子樹當作新的根節點，再次進行相同的過程，直到找不到對應的元素為止。

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);
}

在 linux kernel 中 include/linux/types.h 定義 hlist_node 以及 hlist_head 結構如下

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};

• hlist_add_head
  在 hash table 中的 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 = AAAA;
+    n->next = h->first;
    n->pprev = &h->first;
    h->first = n;
}

• 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, BBBB) {
-        struct order_node *on = CCCC(p, struct order_node, node);
+    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;
}

• node_add
  在 hash table 中新增節點

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, DDDD);
+    hlist_add_head(&on->node, &heads[hash]);
}

測驗二

Leetcode

測驗三