2025q1 Homework1 (lab0)

contributed by <kk908676>

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
• 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
• 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
• HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
• 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
• 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
• 避免使用不必要的 emoji 字元

開發環境

$ hostnamectl 
Operating System: Ubuntu 24.04.1 LTS              
Kernel: Linux 5.15.167.4-microsoft-standard-WSL2

$ gcc --version                                         
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$ lscpu
Architecture:           x86_64
CPU op-mode(s):         32-bit, 64-bit
Address sizes:          39 bits physical, 48 bits virtual
Byte Order:             Little Endian
CPU(s):                 16
On-line CPU(s) list:    0-15
Vendor ID:              GenuineIntel
Model name:             Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
CPU family:             6
Model:                  165
Thread(s) per core:     2
Core(s) per socket:     8
Socket(s):              1
Stepping:               5
CPU(s) scaling MHz:     29%
BogoMIPS:               5808.02    
L1d:                    256 KiB (8 instances)
L1i:                    256 KiB (8 instances)
L2:                     2 MiB (8 instances)
L3:                     16 MiB (1 instance) 

佇列實作與改進

q_new

宣告一個結構指標queue，透過 malloc 配置記憶體，並使用 list.h 中的INIT_LIST_HEAD 進行初始化，讓 next 和 prev 都指向 queue 本身。需要注意的是，當記憶體配置失敗時，返回 return

struct list_head *q_new()
{
    struct list_head *queue = malloc(sizeof(struct list_head));

    if (!queue) {
        return NULL;
    }

    INIT_LIST_HEAD(queue);

    return queue;
}

q_free

使用 While 走訪每個節點。在走訪的過程中，將節點逐個刪除

void q_free(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *cur = head->next;

    while (cur != head) {
        struct list_head *temp = cur;
        cur = cur->next;

        element_t *item = container_of(temp, element_t, list);
        free(item->value);
        free(item);
    }

    free(head);
}

q_insert_head

原始版本 :

• 使用 strdup() 可以動態配置字串的記憶體空間，沒有使用 strncpy() 的原因是需要另外計算字串長度
• 判斷 head 是否為空佇列，是的話直接新增為下一個節點，否則宣告一個結構指標 old 記錄下一個節點再進行新增

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *item = (element_t *) malloc(sizeof(element_t));
    if (!item) {
        return false;
    }
    item->value = strdup(s);

    if (head->next == head) {
        head->next = &item->list;
        head->prev = &item->list;
        item->list.next = head;
        item->list.prev = head;
    } else {
        struct list_head *old = head->next;
        head->next = &item->list;
        old->prev = &item->list;
        item->list.next = old;
        item->list.prev = head;
    }

    return true;
}

改進版本 :

• 不必考慮 head 是否為空佇列，因為我們只需要宣告一個指標指向 head 的下一個進行插入
• 把原本的程式瑪使用 list.h 中的 list_add() 函式代替，將新增的節點添加在佇列的開頭

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *item = malloc(sizeof(element_t));
    if (!item)
        return false;

    item->value = strdup(s);
    if (!item->value) {
        free(item);
        return false;
    }

    list_add(&item->list, head);
    return true;
}

q_insert_tail

作法與 q_insert_head() 差異在於節點插入的位置不同，使用 list_add_tail() 函式將節點新增在尾端

-   list_add(&item->list, head);
+   list_add_tail(&item->list, head);

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *item = malloc(sizeof(element_t));
    if (!item) {
        return false;
    }

    item->value = strdup(s);
    if (!item->value) {
        free(item);
        return false;
    }

    list_add_tail(&item->list, head);
    return true;
}

q_remove_head

• 在佇列不為空的情況下，宣告一個結構指標 remove 指向 head->next
• 使用 list.h 中的 list_del() 將節點從 linked list 上 remove，成為單獨的節點

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    struct list_head *remove = head->next;
    element_t *re_item = container_of(remove, element_t, list);

    list_del(remove);

    if (sp != NULL) {
        strncpy(sp, re_item->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return re_item;
}

q_remove_tail

作法與 q_remove_head() 差不多相同，差異在於移除節點的位置不同，結構指標 remove 指向的是 head->prev

-   struct list_head *remove = head->next;
+   struct list_head *remove = head->prev;

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    struct list_head *remove = head->prev;
    element_t *re_item = container_of(remove, element_t, list);

    list_del(remove);

    if (sp != NULL) {
        strncpy(sp, re_item->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return re_item;
}

q_size

使用 while 走訪每個節點並計算其節點數量

int q_size(struct list_head *head)
{
    if (!head || head->next == head)
        return 0;

    int count = 0;
    struct list_head *temp = head->next;
    while (temp != head) {
        count++;
        temp = temp->next;
    }

    return count;
}

q_delete_mid

使用 q_size() 計算節點數量，算出 ⌊n / 2⌋ 即為我們想要刪除的節點

bool q_delete_mid(struct list_head *head)
{
    struct list_head *temp = head;

    int count = q_size(head);
    if (!head)
        return false;
    if (list_empty(head))
        return true;

    count = count / 2 + 1;
    while (count != 1) {
        temp = temp->next;
        count -= 1;
    }
    element_t *re_item = container_of(temp->next, element_t, list);

    temp->next->next->prev = temp;
    temp->next = temp->next->next;

    free(re_item->value);
    free(re_item);

    return true;
}

q_delete_dup

函式假設： *head 是排序好的鏈結串列
在 While 中我們會透過 cur 來指向當前的節點並走訪完整個鏈結串列，接著跟下一個節點也就是 temp 來檢查是否有節點重複的情況，如果發生了會先刪除 temp 指向的節點，當重複的節點都刪除完後有 bool dup 來紀錄當前的節點是否也要進行刪除

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    struct list_head *cur = head->next;

    while (cur != head) {
        element_t *node1 = container_of(cur, element_t, list);
        struct list_head *temp = cur->next;
        bool dup = false;

        while (temp != head) {
            element_t *node2 = container_of(temp, element_t, list);

            if (strcmp(node1->value, node2->value) == 0) {
                dup = true;
                temp = temp->next;
                list_del(&node2->list);
                free(node2->value);
                free(node2);
            } else {
                break;
            }
        }

        struct list_head *next = cur->next;
        if (dup) {
            list_del(cur);
            free(node1->value);
            free(node1);
        }
        cur = next;
    }
    return true;
}

q_swap

當目前節點大於一個時，宣告兩個結構指標 node1 、 node2 進行兩兩的交換

void q_swap(struct list_head *head)
{
    int count = q_size(head);
    if (count == 0 || count == 1)
        return;

    while (count > 1) {
        struct list_head *temp = head;

        element_t *node1 = container_of(temp->next, element_t, list);
        element_t *node2 = container_of(temp->next->next, element_t, list);

        temp = head->next->next->next;

        head->next = &node2->list;
        temp->prev = &node1->list;

        node2->list.next = &node1->list;
        node2->list.prev = head;
        node1->list.next = temp;
        node1->list.prev = &node2->list;

        count -= 2;
        head = head->next->next;
    }
}

q_reverse

使用 cur 走訪原始的鏈結串列，再使用 cur 、 temp 紀錄當前節點以及下一個節點並交換彼此的指標來反轉鏈結串列

void q_reverse(struct list_head *head)
{
    int count = q_size(head);
    if (count == 0 || count == 1)
        return;

    struct list_head *cur = head;
    struct list_head *temp = head->next;

    do {
        cur->next = cur->prev;
        cur->prev = temp;
        temp = temp->next;
        cur = cur->prev;
    } while (cur != head);
}

q_reverseK

temp : 指向未完成反轉的串列
count ： 紀錄訪問節點個數
每當訪問 K 個節點， 就將那 K 個節點透過 list_cut_position(&head_to, temp, node) 切出來放到 head_to ，並透過 q_reverse() 反轉，使用 list_splice(&head_to, temp) 把 head_to 接回 temp ，最後更新 temp 指向未完成反轉的串列

void q_reverseK(struct list_head *head, int k)
{
    if (list_empty(head) || q_size(head) == 1 || k == 1)
        return;

    int count = 0;

    struct list_head *node, *safe;
    struct list_head *temp = head;

    list_for_each_safe (node, safe, head) {
        count++;
        if (count == k) {
            struct list_head head_to;
            INIT_LIST_HEAD(&head_to);

            list_cut_position(&head_to, temp, node);
            q_reverse(&head_to);
            list_splice_init(&head_to, temp);

            temp = safe->prev;
            count = 0;
        }
    }
}

merge_two_list

宣告一結構參數 temp 用來暫存合併結果，當鏈結串列 L1 與 L2 都不為空時取出各自開頭節點進行比較，較小者會被移動至 temp 的尾端。當有一鏈結串列為空時，將另一鏈結串列剩餘的節點全部移動至 temp 的尾端，最後將結果從temp 移動回 L1

void merge_two_list(struct list_head *L1, struct list_head *L2)
{
    struct list_head temp;
    INIT_LIST_HEAD(&temp);

    while (!list_empty(L1) && !list_empty(L2)) {
        element_t *node1 = container_of(L1->next, element_t, list);
        element_t *node2 = container_of(L2->next, element_t, list);
        if (strcmp(node1->value, node2->value) < 0) {
            list_move_tail(&node1->list, &temp);
        } else {
            list_move_tail(&node2->list, &temp);
        }
    }

    if (!list_empty(L1))
        list_splice_tail_init(L1, &temp);
    else
        list_splice_tail_init(L2, &temp);

    list_splice(&temp, L1);
}

q_sort

原始版本 :
採用的排序演算法為 Bubble Sort ，時間複雜度為

$O(n^2)$ ，在 make test 測試時，trace-14-complexity.cmd 會因為處理時間過久而無法通過檢測

---     trace-14-perf   0/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order

void q_sort(struct list_head *head, bool descend)
{
    int count = q_size(head);
    if (count == 0 || count == 1)
        return;

    for (int i = count; i > 0; i--) {
        struct list_head *cur = head;
        struct list_head *temp = head->next->next->next;
        for (int j = 0; j < i - 1; j++) {
            element_t *node1 = container_of(cur->next, element_t, list);
            element_t *node2 = container_of(cur->next->next, element_t, list);

            if (strcmp(node1->value, node2->value) > 0) {
                cur->next = &node2->list;
                temp->prev = &node1->list;

                node2->list.next = &node1->list;
                node2->list.prev = cur;
                node1->list.next = temp;
                node1->list.prev = &node2->list;
            }

            cur = cur->next;
            temp = temp->next;
        }
    }

    if (descend) {
        q_reverse(head);
    }
}

改進版本 :
採用的排序演算法為 Merge Sort ，時間複雜度為

$O(logn)$

void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *fast = head->next;
    struct list_head *slow = head;

    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    struct list_head half;
    INIT_LIST_HEAD(&half);
    list_cut_position(&half, head, slow);

    q_sort(&half, descend);
    q_sort(head, descend);
    merge_two_list(head, &half);
}

q_ascend / q_descend

q_ascend 和 q_descend 使用相同的方法，差異只在其中 strcmp() 比較節點資訊的是大於還是小於

這裡以 q_descend 作範例說明 :
宣告 cur 為目前節點、 temp 為下一個節點，首先需要先將鏈結串列做反轉，如果當前節點的值比前一個節點小（不符合升序），刪除當前節點直到走訪完整個鏈結串列，最後將鏈結串列再次反轉恢復為原始順序

int q_ascend(struct list_head *head)
{
    int count = q_size(head);
    if (count == 0 || count == 1)
        return count;

    q_reverse(head);

    struct list_head *cur = head->next;
    struct list_head *temp = head->next->next;

    while (temp != head) {
        const element_t *node1 = container_of(cur, element_t, list);
        element_t *node2 = container_of(temp, element_t, list);

        if (strcmp(node1->value, node2->value) < 0) {
            list_del(&node2->list);
            free(node2->value);
            free(node2);
            temp = cur->next;
        } else {
            cur = cur->next;
            temp = temp->next;
        }
    }

    q_reverse(head);

    return q_size(head);
}

q_merge

宣告 cur 為第一個佇列，使用 list.h 中的 list_for_each_safe 走訪所有的佇列，將他們的節點移動到第一個佇列的尾部，並更新第一個佇列的大小（ size ），最後根據 descend 進行升序或降序排序

int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return 0;

    queue_contex_t *q_head = container_of(head->next, queue_contex_t, chain);

    if (q_head->chain.next == q_head->chain.prev)
        return q_head->size;

    struct list_head *cur;
    struct list_head *safe;
    queue_contex_t *cur_queue;

    list_for_each_safe (cur, safe, head) {
        if (cur == &q_head->chain) {
            continue;
        }
        cur_queue = container_of(cur, queue_contex_t, chain);
        list_splice_tail_init(cur_queue->q, q_head->q);
        q_head->size += cur_queue->size;
    }

    q_sort(q_head->q, descend);
    return q_head->size;
}