2025q1 Homework1 (lab0)

contributed by <TonyLinX>

作業書寫規範:

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

開發環境

$ uname -a
Linux sag-System-Product-Name 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

$ 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.

$ 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.

$ 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):                   8
  On-line CPU(s) list:    0-7
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz
    CPU family:           6
    Model:                158
    Thread(s) per core:   2
    Core(s) per socket:   4
    Socket(s):            1
    Stepping:             9
    CPU(s) scaling MHz:   100%
    CPU max MHz:          4500.0000
    CPU min MHz:          800.0000
    BogoMIPS:             8400.00

queue.c - 開發紀錄

q_new()

Commit: c0543ae

目標: 創建一個空的 queue。
設計想法: 使用 INIT_LIST_HEAD 來完成創建一個空的 queue，使程式碼更加簡潔。

實作流程

使用 malloc 來配置 struct list_head 的空間。
透過 INIT_LIST_HEAD 將 next 和 prev 指向自己，使其成為一個獨立的空佇列。
如果 malloc 失敗，應回傳 NULL。

Commit: 79759aa

目標: 修正 q_new() 中的 *new 參數名字改成 *head。
設計想法: 讓程式碼更加直觀。
改動內容:

-    struct list_head *new = malloc(sizeof(struct list_head));
-    if (new == NULL)
+    struct list_head *head = malloc(sizeof(struct list_head));
+    if (!head)
         return NULL;
 
-    INIT_LIST_HEAD(new);
-
-    return new;
+    INIT_LIST_HEAD(head);
+    return head;

q_free()

Commit: a48f43d

目標: 實作 q_free 以釋放佇列記憶體。
設計想法: 使用 list_for_each_safe 遍歷整個 queue，並透過 list_entry 計算該 list_head 的 element 的位址就可以釋放指定的記憶體位址，使程式碼更加簡潔。

實作流程

檢查 head 是否為 NULL，如果 head 為 NULL，則直接返回，不執行任何操作。
透過 list_for_each_safe 安全遍歷 queue 中所有 element_t 節點，確保刪除時不影響迭代過程。
透過 list_entry 計算出該element_t 節點的記憶體位址。
釋放 element_t 本身之前，先釋放其 value，避免記憶體洩漏。
釋放 element_t 節點，確保所有 queue 節點被適當釋放。
最後釋放 head 所指向的 list_head，確保 queue 本身的記憶體也被釋放。

q_insert_head()

Commit: 3c5ce1b

目標: 實作 q_insert_head 以支援頭部插入元素。
設計想法: 函式會動態分配空間給新節點與其字串，並在分配失敗時適當處理，防止記憶體洩漏。此方法確保插入操作為 O(1) 複雜度，同時維持 queue 的一致性。

實作流程

檢查 head 以及 s 是否為 NULL，若其一為 NULL，則回傳 false，不執行任何操作。
配置 new_element_t 節點的記憶體，確保新節點可以存儲字串。
配置並複製 s 到 new_element_t 的 value，確保字串內容獨立存儲。
若字串分配失敗，釋放 new_element_t，避免記憶體洩漏，並回傳 false。
透過 list_add 將新節點插入 head 之後，維持 queue 的雙向鏈結串列結構。
成功插入後回傳 true，確保操作結果可用於錯誤處理。

q_insert_tail()

Commit: 81d5ec5

目標: 實作 q_insert_tail 以支援尾部插入元素
設計想法: 與 q_insert_head 一樣，只是插入的位置變成 queue 的 tail。

實作流程

檢查 head 是否為 NULL，如果 head 為 NULL，則回傳 false，不執行任何操作。
配置 new_element_t 節點的記憶體，確保新節點可以存儲字串。
分配並複製 s 到 element_t 的 value，確保字串內容獨立存儲。
若字串分配失敗，釋放 new_element_t，避免記憶體洩漏，並回傳 false。
透過 list_add_tail 將新節點插入 head 之前，維持 queue 的環狀雙向鏈結串列結構。
成功插入後回傳 true，確保操作結果可用於錯誤處理。

q_remove_head()

Commit: 88e02fc

目標: 實作 q_remove_head 以移除佇列的頭部元素。
設計相法: q_remove_head() 負責移除 queue 中的第一個元素，但不釋放記憶體，這符合 remove 與 delete 的區別。當提供輸出緩衝區時，函式會複製被移除的字串，並確保不會發生溢位。

實作流程

檢查 head 是否為 NULL 或 head 是否為空，若為 NULL 或 head->next 指向 head 則回傳 NULL，避免錯誤操作。
取得 head->next，即佇列的第一個 element_t 節點，作為要移除的節點。
透過 list_del 解除該節點與佇列的鏈結，使其脫離佇列，但不釋放其記憶體，符合 remove 而非 delete 的概念。
如果 sp 非 NULL，則將 element_t->value 的字串複製至 sp，最多 bufsize-1 字元，並在結尾補上 '\0'。
回傳移除的 element_t 指標，以便後續使用或釋放。

q_remove_tail()

Commit: a7a18e0

目標: 實作 q_remove_tail 以移除佇列的尾部元素
設計想法: 與 q_remove_head 設計類似，只是 remove 的位置變成 queue的 tail。

實作流程

檢查 head 是否為 NULL 或 head 是否為空，若為 NULL 或 head->prev 指向 head，則回傳 NULL，避免錯誤操作。
取得 head->prev，即佇列的最後一個 element_t 節點，作為要移除的節點。
如果 sp 非 NULL，則將 element_t->value 的字串複製至 sp，最多 bufsize-1 字元，確保字串結尾有 '\0'。
透過 list_del 解除該節點與佇列的鏈結，使其脫離佇列，但不釋放其記憶體，以符合 remove 而非 delete 的概念。
回傳移除的 element_t 指標，以便後續使用或釋放。

q_size()

Commit: dbfc425

目標: 實作 q_size 以獲取佇列中的元素數量。
設計想法: 使用 list_for_each 來遍歷節點，確保 O(n) 時間複雜度，並提升可讀性與可維護性。

實作流程

檢查 head 是否為 NULL 或 list_empty(head)，若為 NULL 或空，則回傳 0。
初始化計數變數 number 為 0，用於記錄 queue 中的元素數量。
使用 list_for_each 迭代 queue 中的所有節點，並遞增 number 記錄節點數量。
最後回傳 number，作為 queue 的長度。

q_delete_mid()

Commit: b05ef28

目標: 使用 q_size 改進 q_delete_mid 以提升可讀性。
設計想法: 此方法先以 O(n) 計算 queue 的長度，以確定中間索引，然後再以 O(n) 遍歷鏈結串列，確保能準確定位並刪除節點。

實作流程

檢查 head 是否為 NULL 或 queue 是否為空，若為 NULL 或 list_empty(head)，則回傳 false，不執行任何操作。
使用 q_size(head) 計算 queue 的長度，並儲存於 size 變數中。
計算中間節點索引，使用 mid_index = size / 2。
使用 for loop 找到中間節點，從 head->next 開始遍歷 mid_index 次，找到對應的節點。
透過 list_del(node) 解除該節點與 queue 的鏈結，確保不影響其他節點。
釋放 element_t 節點的 value 記憶體，確保字串內容不會洩漏。
釋放 element_t 本身，確保整個節點的記憶體被正確回收。
回傳 true 表示刪除成功，確保函式運行結果可被上層函式使用。

q_delete_dup()

Commit: afcc69e

目標: 實作 q_delete_dup 以刪除重複的元素
設計想法: 由於在這個題目中 queue 已經排序，所有重複節點都會是連續的，因此可以透過一次 O(n) 遍歷來完成 in-place 刪除，不需要額外的儲存空間。通常，在未排序的 queue 中，使用 hash table 來記錄出現過的字串能有效避免 O(n²) 的時間複雜度。然而，在此題目中，因為所有相同的字串已經是相鄰的，雜湊表並不能提供額外的優勢，直接遍歷 queue 來刪除相鄰的重複值即可達到最佳效率。

實作流程

檢查 head 是否為 NULL 或 queue 是否為空，如果是則直接回傳 false，不執行任何操作。
初始化 current 指標，指向 queue 的第一個元素 (head->next)，準備開始遍歷 queue。
進入 while (current != head) 迴圈，確保遍歷 queue 的所有元素。
取得 current 節點的內容 (element_t)，準備檢查是否有重複的值。
初始化 next 指標，指向 current->next，並設置 duplicate = false 變數，用來追蹤 current 是否需要被刪除。
進入 while (next != head) 迴圈，檢查 current->value 是否與 next->value 相等，當相等就直接刪除該點，直到找到不一樣的節點。
若 duplicate == true，則表示 current 也是重複的，需要刪除：
- 使用 list_del(current) 解除 current 節點與 queue 的鏈結。
- 釋放 current 節點的記憶體 value 和 element_t。
更新 current = next，繼續遍歷 queue，檢查下一個節點。

q_swap()

Commit: 09fb11d

目標: 實作 q_swap 以交換相鄰的節點
設計想法: 該函式透過遍歷 queue，將每對相鄰的節點進行交換，且不需要額外的記憶體配置。該方法能在 O(n) 的時間內完成操作。

實作流程

檢查 queue 是否為空或只有一個節點。
初始化 first 和 second 指標。
進入 while (first != head && second != head)，遍歷 queue，每次交換一對節點。

q_reverse()

Commit: 673ac5e

目標: 實作 q_reverse 以反轉 queue 內的元素順序。
設計想法: 此函式會透過 list_move，每個節點依序移動到 queue 的前端，避免不必要的記憶體操作，並維持 O(n) 的時間複雜度。

實作流程

檢查 queue 是否為空或 NULL：
- 若 head == NULL 或 list_empty(head)，則 queue 無需反轉，直接返回。
初始化 current 和 safe 指標，準備遍歷 queue：
- current 用來指向當前處理的節點。
- safe 用來暫存 current->next，確保刪除或移動 current 後，仍能存取下一個節點。
使用 list_for_each_safe 遍歷 queue，並將 current 節點移動至 head 之前：
- list_move(current, head) 將當前 current 節點移動至 head 之後，使 queue 反轉。
- list_for_each_safe 確保遍歷時不會因為節點移動導致無限迴圈或錯誤存取。

q_reversek()

Commit: 70b0100

目標: 實作 q_reverseK 以反轉 queue 中每 k 個節點的順序
設計想法: 函式在進行反轉前，會先確認 queue 是否包含完整的 k 個節點，以避免處理不完整的群組。透過 list_move 進行 in-place 反轉，使演算法達到 O(n) 時間複雜度，且不會進行額外的記憶體配置。

實作流程

檢查 queue 是否為空 NULL，或 k 是否無效。
初始化 current 和 safe 指標，current 為當前要處理的節點，safe 用來確認當前 group 是否有足夠的 k 個元素可供反轉。
遍歷 queue，每次處理 k 個節點。

q_sort()

Commit: c01e743

目標: 實作 q_sort 以排序 queue 中的元素，可選擇遞增或遞減排序
設計想法:
- 這次用插入排序來實現 q_sort()，實作方式為 in-place sorting，並且不會額外配置新的記憶體。但最差的情況下時間複雜度為 O(n^2)。

實作流程

檢查 queue 是否為空或僅有單一節點。
初始化 sorted，用來存放排序後的節點：
- 使用 INIT_LIST_HEAD(&sorted) 初始化 sorted 為空鏈結串列。
從原始 queue 取出節點並插入 sorted：
- 當 queue 內還有節點時，執行以下步驟：
- 取出 head->next，即 queue 的第一個節點，並使用 list_del(node) 將其從 queue 中移除。
- 遍歷 sorted，找到正確的插入位置。
若 node 尚未插入，則將其加入 sorted 的尾端。
將 sorted 內的排序結果合併回 head。

q_ascend()

Commit: 6fa239e

目標: 實作 q_ascend 移除違反遞增順序的節點
設計想法:
- 該函式從右向左掃描，追蹤目前為止遇到的最小值。如果某個節點的值大於此最小值，就將其移除。這種做法確保了最佳的 O(n) 解法，僅需掃描列表一次，並能立即釋放不必要的節點。

實作流程

檢查 queue 是否為 NULL 或空：
- 若 head == NULL 或 list_empty(head)，則直接返回 0。
- 若 list_is_singular(head)（僅有一個節點），則直接返回 1。
初始化變數：
- 設定 current = head->prev，從 queue 尾端開始遍歷。
- min_val 設定為最後一個節點的值，作為目前遇到的最小值。
從尾端向左遍歷 queue：
- 若 current->value > min_val：
  - 代表 current 右側存在比它更小的值，因此將 current 從 queue 中刪除。
  - 釋放記憶體 current_entry->value 和 current_entry。
- 若 current->value < min_val：
  - 更新 min_val = current->value，因為遇到了一個更小的元素。
- 若 current->value == min_val：
  - 保持不變，繼續遍歷，確保穩定排序。
遍歷完成後，回傳目前 queue 中的元素數量 q_size(head)。

q_descend()

Commit: 11201ce

目標: 實作 q_descend 以移除右側更大值的節點
設計想法:
- 該函數從右向左掃描，追蹤遇到的最大值。如果某個節點的值小於此最大值，
  則將其移除。此方法保證 O(n) 最佳解，能夠立即釋放不必要的節點，並確保正確性。

實作流程

檢查 queue 是否為 NULL 或空：
- 若 head == NULL 或 list_empty(head)，則直接返回 0。
- 若 list_is_singular(head)（僅有一個節點），則直接返回 1。
初始化變數：
- 設定 current = head->prev，從 queue 尾端開始遍歷。
- max_val 設定為最後一個節點的值，作為目前遇到的最大值。
從尾端向左遍歷 queue：
- 若 current->value < max_val：
  - 代表 current 右側存在比它更大的值，因此將 current 從 queue 中刪除。
  - 釋放記憶體 current_entry->value 和 current_entry。
- 若 current->value > max_val：
  - 更新 max_val = current->value，因為遇到了一個更大的元素。
- 若 current->value == max_val：
  - 保持不變，繼續遍歷，確保穩定排序。
遍歷完成後，回傳目前 queue 中的元素數量 q_size(head)。

q_merge()

Commit: 5553243

目標: 使用 q_merge 合併多個已排序的佇列
設計想法:
- 此方法透過重用現有佇列結構來避免記憶體分配，並利用 list_splice_tail() 來確保高效合併。透過就地合併，該函數可保留原始佇列的內容，同時確保只有第一個佇列仍然包含元素。合併後會執行排序以維持順序，確保正確性。此函數的時間複雜度為 O(n log k)，其中 k 為佇列數量。

實作流程

檢查 queue 是否為 NULL 或只有一個 queue：
- 若 head == NULL，則無法進行合併，直接返回 0。
- 若 list_is_singular(head)（僅有一個 queue），則直接回傳第一個 queue 的大小，無需合併。
初始化變數：
- current = head->next，從鏈結的第一個 queue 開始遍歷。
- 設定 first_queue_contex_t 為 head->next，作為合併的目標 queue。
遍歷 head 所指向的 queue 並合併：
- 從 current->next 開始遍歷，將所有 queue 合併至 first_queue_contex_t->q。
- 若 current_queue_contex_t->size > 0，則執行：
  - list_splice_tail_init(current_queue_contex_t->q, first_queue_contex_t->q) 將當前 queue 連接到第一個 queue 的尾端。
更新 first_queue_contex_t->size：
- 透過 q_size(first_queue_contex_t->q) 來確保 queue 的長度資訊正確。
對合併後的 queue 進行排序：
- 執行 q_sort(first_queue_contex_t->q, descend) 來維持合併後的順序。
回傳合併後的 queue 大小。

2025q1 Homework1 (lab0)

開發環境

queue.c - 開發紀錄

q_new()

q_free()

q_insert_head()

q_insert_tail()

q_remove_head()

q_remove_tail()

q_size()

q_delete_mid()

q_delete_dup()

q_swap()

q_reverse()

q_reversek()

q_sort()

q_ascend()

q_descend()

q_merge()

Read more

linux2025-homework2

linux2025-ideas