2025q1 Homework1 (lab0)

contributed by <I-Ying-Tsai>

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [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 字元

開發環境

i-ying-tsai@i-ying-tsai-G5-KF5:~/linux2025/lab0-c$ uname -a
Linux i-ying-tsai-G5-KF5 6.11.0-17-generic #17~24.04.2-Ubuntu SMP PREEMPT_DYNAMIC Mon Jan 20 22:48:29 UTC 2 x86_64 x86_64 x86_64 GNU/Linux

i-ying-tsai@i-ying-tsai-G5-KF5:~/linux2025/lab0-c$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

i-ying-tsai@i-ying-tsai-G5-KF5:~/linux2025/lab0-c$ ldd --version
ldd (Ubuntu GLIBC 2.39-0ubuntu8.4) 2.39
Copyright (C) 2024 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Written by Roland McGrath and Ulrich Drepper.

i-ying-tsai@i-ying-tsai-G5-KF5:~/linux2025/lab0-c$ 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:             13th Gen Intel(R) Core(TM) i7-13620H
    CPU family:           6
    Model:                186
    Thread(s) per core:   2
    Core(s) per socket:   10
    Socket(s):            1
    Stepping:             2
    CPU(s) scaling MHz:   33%
    CPU max MHz:          4900.0000
    CPU min MHz:          400.0000
    BogoMIPS:             5836.80

實作 queue.[ch]

q_new a31f615

目的
建立並初始化一個 Linux Kernel 風格的雙向鏈結串列（doubly linked list）頭節點。

1. 請求 head 大小的記憶體空間(透過 malloc)。
2. 檢查記憶體配置 (memory allocation) 是否成功，若是失敗，則返回 NULL。
3. 使用 INIT_LIST_HEAD 初始化該節點，使其的 prev 和 next 都指向自己。
4. 返回該 head 地址。

---

q_free a31f615

目的
釋放整個鏈結串列佔用的記憶體，避免記憶體洩漏 (memory leak)。

1. 若 head 為 NULL，則直接返回，避免無效操作。
2. 使用 list_for_each_safe 進行走訪，確保在刪除節點時不影響遍歷順序。
   • 若使用 list_for_each，則刪除當前節點後，next 指標將指向已被釋放的記憶體，可能導致 迷途指標 (dangling pointer) 或 segmentation fault。
   • list_for_each_safe 會預先存儲 next 節點，確保刪除當前節點後，能繼續正確遍歷。
3. 使用 list_entry 取得 element_t 結構，確保可以正確存取 value。
4. 使用 list_del 將節點從鏈結串列中移除。
5. 釋放 element_t->value，確保字串記憶體被回收。
6. 釋放 element_t 本身，確保節點記憶體被回收。
7. 釋放 head 本身，確保鏈結串列頭部的記憶體也被回收。

---

q_insert_head fce1b7c

目的
在鏈結串列的頭部插入一個新的元素。

1. 檢查 head 和 s 是否為 NULL，確保鏈結串列有效。
2. 分配 element_t 節點的記憶體，確保成功分配。
3. 使用 strdup 為 value 分配記憶體，確保成功存儲字串。
4. 使用 list_add 將該節點插入 head 之後，確保新節點成為新的頭部
5. 返回 true 表示成功，或 false 表示失敗。

---

q_insert_tail 6d84b0c

目的
在鏈結串列的尾端插入一個新的元素。

1. 檢查 head 和 s 是否為 NULL，確保鏈結串列有效，避免無效操作。
2. 分配 element_t 節點的記憶體 (malloc)，確保成功分配，避免 NULL 指標操作。
3. 使用 strdup 為 value 分配記憶體，確保字串內容獨立，不受外部變更影響。
   • 若 strdup 失敗，則釋放 element_t 節點，避免記憶體洩漏。
4. 使用 list_add_tail 插入節點至 head 之前，確保新節點成為尾部節點。
5. 返回 true 表示成功，或 false 表示失敗。

---

q_remove_head feef7ff

目的
從鏈結串列的頭部刪除一個節點，並返回該節點的指標。

1. 檢查 head 是否為 NULL 或 list_empty(head)，確保鏈結串列有效，避免無效操作。
2. 獲取 head 之後的第一個節點 (head->next)，確保該節點可移除。
3. 使用 list_del 從鏈結串列中移除該節點，確保鏈結完整且不影響其他節點。
4. 若 sp 非空，則複製 value 到 sp，並確保字串長度不超過 bufsize，防止 buffer overflow。
5. 返回刪除的節點指標 (element_t *)，由呼叫者負責釋放記憶體 (free(node))。

比較：

• 使用 list_del 直接移除節點，確保 O(1) 時間複雜度。

---

q_remove_tail feef7ff

目的
從鏈結串列的尾部刪除一個節點，並返回該節點的指標。

1. 檢查 head 是否為 NULL 或 list_empty(head)，確保鏈結串列有效，避免無效操作。
2. 獲取 head 之前的最後一個節點 (head->prev)，確保該節點可移除。
3. 使用 list_del 將該節點從鏈結串列中移除，確保鏈結完整且不影響其他節點。
4. 若 sp 非空，則複製 value 到 sp，並確保字串長度不超過 bufsize，防止 buffer overflow。
5. 返回刪除的節點指標 (element_t *)，由呼叫者負責釋放記憶體。

比較：

• 使用 list_del 直接移除尾部節點，確保 O(1) 時間複雜度，不影響其他節點。

---

q_delete_mid 3f716d0

目的
刪除鏈結串列的中間節點。

1. 若鏈結串列為空，則返回 false。
2. 使用快慢指標 (slow & fast) 找到中間節點。
   • 如果使用 q_size 計算長度，再走訪到 n/2 位置刪除，則時間複雜度為 O(2n) = O(n)。
   • 快慢指標法只需 O(n) 時間，且無需額外變數，更高效。
3. 使用 list_del 將該節點從鏈結串列中移除。
4. 釋放該節點的 value 及其記憶體，確保無記憶體洩漏。
5. 返回 true 表示刪除成功。

---

q_delete_dup 3f716d0

目的
刪除鏈結串列中所有重複的節點，只保留唯一值的節點。

1. 檢查 head 是否為 NULL 或 list_empty(head)，確保鏈結串列有效，避免無效操作。
2. 走訪鏈結串列，檢查相鄰節點是否擁有相同 value。
3. 若發現重複值，則刪除所有具有該值的節點，確保最終結果中該值完全消失。
4. 使用 list_del 移除節點，並 free 該節點的 value 及其記憶體，防止記憶體洩漏。
5. 返回 true 表示至少刪除了一個重複節點，否則返回 false。

---

q_swap 5567955

目的
交換鏈結串列中每兩個相鄰的節點。

1. 若鏈結串列為空或只有一個節點，則直接返回。
2. 走訪鏈結串列，成對交換相鄰的節點。
3. 使用 list_move 進行交換，確保鏈結關係正確。
   • 如果直接交換節點內部的 value，會降低時間複雜度，但不符合 Linux 內核的鏈結串列設計，因為節點通常存儲指標而非具體值。

---

q_reverse 97d2cb0

目的
反轉鏈結串列的順序，使原本的頭節點變為尾節點，尾節點變為頭節點。

1. 若鏈結串列為空或只有一個節點，則直接返回。
2. 走訪鏈結串列，交換 next 和 prev 指標。
3. 若使用 list_move，可以逐個將節點移動到 head 之前，達到反轉效果，但時間複雜度較高。
4. 更好做法是直接修改 next 和 prev 指標，時間複雜度為 O(n)。

---

q_reverseK 3d95a49

目的
將鏈結串列的節點按照 k 個為一組進行反轉。

1. 若 k <= 1 或鏈結串列長度小於 k，則無需反轉。
2. 計算鏈結串列的長度，確保至少有 k 個節點。
3. 使用 list_for_each_safe 遍歷鏈結串列，每 k 個節點作為一組進行反轉。
4. 若使用 q_reverse 逐個處理 k 個節點，則需要額外的子串列管理邏輯，但可以利用 list_move_tail 簡化操作。
5. 確保反轉後相鄰組之間的連接關係正確，防止鏈結斷裂。

---

q_sort 3d95a49

目的
對鏈結串列內的元素進行排序（遞增或遞減），提升查詢效率。

1. 若 head 為 NULL 或為空，則直接返回。
2. 使用合併排序（merge sort）進行排序，時間複雜度為 O(n log n)，適用於鏈結串列。
   • 若使用C涵式庫中的快速排序（quick sort），則需頻繁變更指標，導致性能下降。
3. 透過 merge_sort 遞迴拆分鏈結串列，使用快慢指標 (slow & fast) 找到中間節點。
4. 使用預先寫好的 merge 涵式合併排序好的子鏈結串列，並根據 descend 參數決定排序順序。
5. 重新建立 head，確保首尾節點連結正確。

---

q_ascend 5cebf2f

目的
移除鏈結串列中 左側值大於右側某個值 的所有節點，使得最終結果呈現遞增順序。

1. 若 head 為 NULL 或為空，則直接返回 0。
2. 從鏈結串列尾部向前走訪，確保右側的節點已確認。
3. 使用 min_elem 變數追蹤當前最小值，若當前節點值大於 min_elem，則刪除該節點。
4. 使用 list_del 移除節點，並釋放該節點的 value 及其記憶體。
5. 更新 head->prev 以確保鏈結串列結構完整，最後返回剩餘節點數。

---

q_descend 3d95a49

目的
移除鏈結串列中 左側值小於右側某個值 的所有節點，使得最終結果呈現遞減順序。

1. 若 head 為 NULL 或為空，則直接返回 0。
2. 從鏈結串列尾部向前走訪，確保右側的節點已確認。
3. 使用 max_elem 變數追蹤當前最大值，若當前節點值小於 max_elem，則刪除該節點。
4. 使用 list_del 移除節點，並釋放該節點的 value 及其記憶體。
5. 返回剩餘的節點數量。

---

q_merge 11bbebe

目的
將多個鏈結串列合併為一個有序鏈結串列（遞增或遞減）。

1. 若 head 為 NULL 或為空，則返回 0。
2. 取得第一個 queue_contex_t 作為主佇列 (main_ctx)，確保合併後仍有主鏈結串列存在。
3. 走訪所有子佇列 (ctx->q)，將所有節點移動至 main_ctx->q 的尾部。
4. 使用 q_sort 重新對合併後的鏈結串列進行排序，確保最終結果有序。
5. 確保所有子鏈結串列清空，並更新 size 記錄總元素數量。
6. 返回合併後的鏈結串列大小。

比較：

• 若使用 最小堆積 (min-heap) 進行合併，則可降低排序開銷。

---

整合網頁伺服器

---

在 qtest 提供新的命令 shuffle

1. 介紹

在 qtest 中新增了一個名為 shuffle 的命令，其功能是隨機排列 queue 中的元素。為了確保公平性，我們使用 Fisher-Yates Shuffle 演算法，使每個排列的機率相等。本報告將詳細描述 q_shuffle 的實作方式、測試方法以及測試結果。

---

2. q_shuffle 的實作

2.1 Fisher-Yates Shuffle

Fisher-Yates Shuffle 是一種常用於 均勻隨機打亂 陣列的演算法，其原理如下：

1. 從 最後一個元素 開始，隨機選擇一個索引 j（0 ≤ j ≤ i）。
2. 交換 當前元素 arr[i] 與 arr[j] 的位置。
3. 持續執行直到所有元素都已經處理。

我的 q_shuffle 函數實作如下：

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || head->next == head->prev) {
        return;
    }

    int len = q_size(head);
    element_t **arr = malloc(len * sizeof(element_t *));
    if (!arr)
        return;

    struct list_head *cur = head->next;
    for (int i = 0; i < len; i++, cur = cur->next) {
        arr[i] = list_entry(cur, element_t, list);
    }

    srand(time(NULL));

    for (int i = len - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        if (i != j) {
            list_move(&arr[i]->list, &arr[j]->list);
        }
    }

    q_show(3);
    free(arr);
}

2.2 shuffle 命令的新增

在 qtest.c 中，我新增了 do_shuffle 來呼叫 q_shuffle，並且報告執行結果。

static bool do_shuffle(int argc, char *argv[])
{
    if (!current || !current->q) {
        report(1, "No queue created");
        return false;
    }

    q_shuffle(current->q);
    return true;
}

並加上 ADD_COMMAND(shuffle, "Shuffle elements in queue", ""); 來讓 qtest 支援 shuffle 命令。

3. 測試

由測試用的 Python 腳本 test_shuffle.py 測試，得出以下結果以及作圖。

i-ying-tsai@i-ying-tsai-G5-KF5:~/linux2025/lab0-c$ python3 test_shuffle.py
Expectation:  41666
Observation:  {'1234': 41807, '1243': 41685, '1324': 41933, '1342': 41378, '1423': 41784, '1432': 41697, '2134': 41739, '2143': 41481, '2314': 41766, '2341': 42083, '2413': 41585, '2431': 41735, '3124': 41610, '3142': 41633, '3214': 41857, '3241': 41499, '3412': 41837, '3421': 41343, '4123': 41784, '4132': 41813, '4213': 41640, '4231': 41628, '4312': 41456, '4321': 41227}
Chi-Square sum:  21.61868189891038

在這個測試中，虛無假設 H₀ 是：

q_shuffle() 產生的所有排列是均勻分布的，且各種排列的機率相等。

---

查表發現，在自由度為 23 的情況下，χ² = 21.6 對應的 p 值大於 0.10。

---