2024q1 Homework2 (quiz1+2)

contributed by < jychen0611 >

第 1 週測驗題

quiz 1

<程式運作原理>

結構體

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

以下分別為取得串列尾節點和取得串列長度之函式。
因為 left 為節點指標的指標，(*left)表指向該節點的指標，依據判斷可知 AAAA 應填入(*left)->next ，而 left = &((*left)->next) 表left 指向隔壁節點指標的位址。
其函式回傳為指向串列尾端節點的指標。
同理，BBBB 應填入(*left)->next ，表left 指向隔壁節點指標的位址。

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

<圖解說明>

以下是運用 Optimized QuickSort — C Implementation (Non-Recursive) 所實作非遞迴 (non-recursive; iterative) 的快速排序法程式碼。

• begin[i], end[i] 分別用來存放單一排序分割的起始點和終點，i 為分割編號
• left 用來存放小於等於 pivot 的節點
• right 用來存放大於 pivot 的節點
• result 用來存放排序完的分割

其流程為

• 以 L R 指向串列分割 i 之兩端，當 L R 尚未交會則進行內部排序
• 最左邊的數設為 pivot，p 則指向 pivot 隔壁的節點，pivot 的 next 指向 NULL
• 指標 p 會一直往右走，將大於 pivot 的節點存入 right ， 小於的存入 left
• 由上述可知 CCCC 應填入 p -> next
• 接著可得到三組分割 left pivot right，其對應的分割編號分別為 i i+1 i+2
• 由上述可知 DDDD 應填入 list_tail(left) ， EEEE 應填入 list_tail(right)
• 下一回合將進行 串列分割 i+2 之內部排序（也就是先排右邊）
• 直到右邊都排序完成後，才會將排序完的分割存入 result，並開始進行左邊分割的排序。

void quick_sort(node_t **list)
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];
    node_t *result = NULL, *left = NULL, *right = NULL;
    
    begin[0] = *list;
    end[0] = list_tail(list);
            
    while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        if (L != R) {
            node_t *pivot = L;
            value = pivot->value;
            node_t *p = pivot->next;
            pivot->next = NULL;
    
            while (p) {
                node_t *n = p;
                p = CCCC;
                list_add(n->value > value ? &right : &left, n);
            }

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

            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

<圖解說明>

quiz 2

<程式運作原理>

以下為 Timsort merge 過程。
由於 tail 為指標的指標，AAAA 應填入 &head ，表指標 head 的位址。
同理， BBBB 應該填入 &a->next ， CCCC 應該填入 &b->next 表指向下個節點指標的位址（更新 tail）。

static struct list_head *merge(void *priv,
                               list_cmp_func_t cmp,
                               struct list_head *a,
                               struct list_head *b)
{
    struct list_head *head;
    struct list_head **tail = AAAA;

    for (;;) {
        /* if equal, take 'a' -- important for sort stability */
        if (cmp(priv, a, b) <= 0) {
            *tail = a;
            tail = BBBB;
            a = a->next;
            if (!a) {
                *tail = b;
                break;
            }
        } else {
            *tail = b;
            tail = CCCC;
            b = b->next;
            if (!b) {
                *tail = a;
                break;
            }
        }
    }
    return head;
}

以下為補上雙向鏈結串列中的 prev 之函式，過程如下：

• 先將 tail 的 next 指向 head
• 以 list 逐步走訪整個串列，將 link 所指節點的 prev 指向 tail 。
• 最後再補上 tail 的 next 指向 head ， head 的 prev 指向 tail 之動作

由上述可知 DDDD 為 tail->next ，EEEE 為 head->prev

static void build_prev_link(struct list_head *head,
                            struct list_head *tail,
                            struct list_head *list)
{
    tail->next = list;
    do {
        list->prev = tail;
        tail = list;
        list = list->next;
    } while (list);

    /* The final links to make a circular doubly-linked list */
    DDDD = head;
    EEEE = tail;
}

下面是 timsort 程式碼。其過程如下 ：

void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
    stk_size = 0;

    struct list_head *list = head->next, *tp = NULL;
    if (head == head->prev)
        return;

    /* Convert to a null-terminated singly-linked list. */
    head->prev->next = NULL;

    do {
        /* Find next run */
        struct pair result = find_run(priv, list, cmp);
        result.head->prev = tp;
        tp = result.head;
        list = result.next;
        stk_size++;
        tp = merge_collapse(priv, cmp, tp);
    } while (list);

    /* End of input; merge together all the runs. */
    tp = merge_force_collapse(priv, cmp, tp);

    /* The final merge; rebuild prev links */
    struct list_head *stk0 = tp, *stk1 = stk0->prev;
    while (stk1 && stk1->prev)
        stk0 = stk0->prev, stk1 = stk1->prev;
    if (stk_size <= FFFF) {
        build_prev_link(head, head, stk0);
        return;
    }
    merge_final(priv, cmp, head, stk1, stk0);
}

第 2 週測驗題

quiz 1

<程式運作原理>

quiz 2

<程式運作原理>

quiz 3

<程式運作原理>

參考資料

• 作業說明
• 你所不知道的C語言：指標篇
• 你所不知道的 C 語言：記憶體管理、對齊及硬體特性
• 基於 C 語言標準研究與系統程式安全議題
• 你所不知道的 C 語言: bitwise 操作
• Linux 核心的 hash table 實作
• Graphviz