2024q1 Homework2 (quiz1+2)

contributed by < w96086123 >

第一週測驗

測驗一

了解資料結構

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

left 代表比 value 小的集合。
right 代表比 value 大的集合。
next 表示此 node 的下一個 node 。
value 表示此 node 的數值。

了解操作函數

list_add

將一個 node_t 加入至 list 的 head 。

list_tail

尋找此 node_t 中 left 的最後一個 node_t ，並且回傳該指標。
其中的 AAAA 為 (*left)->next。

list_length

尋找此 node_t 中 left 的長度。
其中的 BBBB 為 (*left)->next。

list_construct

建立一個 value 為 n 的 node_t ，並且將 node_t 加入至 list 的頭，且回傳該指標。

list_free

將 list 中的已配置記憶體的全部釋放。

list_is_ordered

檢查此 list 是否已完成排序。

shuffle

將 array 中的資料已亂數交換的方式打亂。

quick_sort

此方法利用堆疊取代原本的遞迴呼叫。

1. 將 DDDD 和 EEEE 完成，與了解 max_level 的數值定義

// Area 1
begin[i] = left;
end[i] = DDDD;
// Area 2
begin[i + 1] = pivot;
end[i + 1] = pivot;
// Area 3
begin[i + 2] = right;
end[i + 2] = EEEE;

此區主要作為切割並且儲存的區域，因此我將此區分成三個區域了解。

區域一：
    紀錄比 pivot 還要小的數值，因此範圍要為 left 至 list_tail(&left)。
    因此 `DDDD` 為 list_tail(&left) 。

區域二：
    紀錄 pivot 的位置，因此範圍要為 pivot 至 pivot 。 
    由於該位置已經進行分類確定好位置，因此 begin 和 end 為相同，在最後進行放置時，就可以判斷為可以放置的狀態了。

區域三：
    紀錄比 pivot 還要大的數值，因此範圍要為 right 至 list_tail(&right)。
    因此 `EEEE` 為 list_tail(&right) 。

藉由上面解析，可以知道每次的切割會新增兩個區塊，因此最大堆疊的空間需要 2 * n 。

2. 完成 CCCC

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

此區將 list 中進行分類。
逐一利用 list_add 進行分類，分類條件為 n->value > value ，若為真，則表示較大，將 n 分類為 right，否則，將 n 分類為 left 。
因此 CCCC 為 p->next 。

3. 將 1 與 2 一起觀看

原本的狀態

進行分類過後的狀態

4. 觀看整體
   由於先進行 right 的切割，因此第一次將 L 儲存為 result 的一定為最大值，第二次則為第二大值，依序下來，直到堆疊的索引小於 0 ，結果必為完成排序。

main

建立一個長度為 100000 的 array ，順序則為 1 至 100000，並且利用 shuffle 進行打亂，後建立打亂後順序的 list ，並進行 quick_sort 排序，排序後利用 list_is_ordered 進行排序結果的判斷，最後利用 list_free 將記憶體釋放，並且釋放該 array 。

延伸問題 1

因為每次的切割都需要使用兩次 list_tail ，但每次使用都需要 O(N) ，如果改成使用雙向鏈結串列的方式實做，時間複雜度將降低為 O(1) 。

修改資料結構

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

新增 prev 節點。

修改操作函數

list_add

if (*list != NULL)
    (*list)->prev = node_t;
node_t->next = *list;
node_t->prev = NULL;
*list = node_t;

list_tail

node_t *list_tail(node_t **left)
{
    if (*left){
        return (*left)->prev;
    }else{
        return *left;
    }
}

藉由新的結構，可以直接訪問最後的節點，無須逐步訪問，因此時間複雜度可變為 O(1) 。

list_construct

node_t *list_construct(node_t *list, int n)
{
    node_t *node = malloc(sizeof(node_t));
    node->next = list;
    node->prev = NULL;
    node->value = n;
    if (list != NULL)
        list->prev = node;
    return node;
}

由於修改為新的結構，因此在建立的過程中也需要做相對應的修改。

比較（10000 個節點）

	單向鏈結	雙向鏈結
處理時間 (s)	0.049148	0.036808

由上表可知，這樣得修改方式是有提昇處理時間。

延伸問題 2

若想要避免最壞狀況，可以使用 Median of Three 的方式取得 pivot ，這樣可以避免一直取得最大或是最小值。

測驗二

Timsort 步驟

1. 先尋找 run
   由左到右尋找非嚴格遞增或遞減的序列，每個 run 的長度盡量符合 minrun 跟 2 的冪。

2. 內部 run 進行插入排序法

3. 利用合併排序的方式進行合併

程式碼解讀

find_run

第二週測驗

測驗一

原版

利用深度優先搜尋的方式建立樹。

AAAA

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->pprev = &h->first;
    h->first = n;
}

此函數主要作用為將 n 插入至 h 的頭。
因此 AAAA 為 h->first 。

BBBB 和 CCCC

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);
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

此函數為尋找特定值。
BBBB 這裡要遍歷 hlist_node ，因此 BBBB 為 &heads 。
每次的遍歷都需要將當前指針轉換為 order_node，因此 CCCC 為 list_entry 。

DDDD

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

此函數主要將創立一個新的 order_node ，並且將此 node 放入置 hlist_head。
因此 DDDD 為 heads 。

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

利用深度優先搜尋法的方式建立 Tree。
先利用 find 尋找出 preoder[pre_low] 在 inorder 中的索引值，此索引值稱為 idx 。
切割方式：

​​​​左子樹：
​​​​    preorder ： pre_low + 1 至 pre_low + (idx - in_low) 。
​​​​                (idx - in_low) 表示有多少個節點。
​​​​    inorder : in_low 至 idx - 1 。
​​​​右子樹：
​​​​    preorder ： pre_high - (in_high - idx - 1) 至 pre_high 。
​​​​                (in_high - idx - 1) 表示有多少個節點。
​​​​    inorder : idx + 1 至 in_high 。

循環利用上面的方式，就可以將有 preorder 與 inorder 的序列，轉換為 Tree 了。

測驗二

了解資料架構

LRUCache

typedef struct {
    int capacity;
    int count;
    struct list_head dhead;
    struct hlist_head hhead[];
} LRUCache;

capacity 用於儲存 LRU 緩存的容量。
count 用於紀錄當前 LRU 緩存中儲存的數量。
dhead 用於紀錄 LRU 中節點的訪問順序，用於尋找替換順序。
hhead 用於紀錄 LRU 中節點的哈希表連結。

LRUNode

typedef struct {
    int key;
    int value;
    struct hlist_node node;
    struct list_head link;
} LRUNode;

key 節點的鍵值。
value 節點的值。
node 與其他節點的指標。
link 用於與 LRU 的連結。

測驗三