# 2025q1 Homework1 (lab0)
contributed by <`TonyLinX`>

:::info
作業書寫規範:

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

## 開發環境

$ 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`](https://github.com/sysprog21/lab0-c/commit/c0543aeb2ff11768ceecd8827dc6f386677d610c)

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

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

:::
<br>

Commit: [`79759aa`](https://github.com/sysprog21/lab0-c/commit/79759aa5db323c3e331902163d5b6c5bb635e7ad)
- **目標**: 修正 `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`](https://github.com/sysprog21/lab0-c/commit/a48f43deaf40fadff86fd7431c76374143376cb6)
- **目標**: 實作 `q_free` 以釋放佇列記憶體。
- **設計想法**: 使用 `list_for_each_safe` 遍歷整個 `queue`，並透過 `list_entry` 計算該 `list_head` 的 `element` 的位址就可以釋放指定的記憶體位址，使程式碼更加簡潔。
:::spoiler 實作流程

* 檢查 `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`](https://github.com/sysprog21/lab0-c/commit/3c5ce1bacdf8fec3aff9c04c54c1567a9275fc01)
- **目標**: 實作 `q_insert_head` 以支援頭部插入元素。
- **設計想法**: 函式會動態分配空間給新節點與其字串，並在分配失敗時適當處理，防止記憶體洩漏。此方法確保插入操作為 `O(1)` 複雜度，同時維持 queue 的一致性。
:::spoiler 實作流程

* 檢查 `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`](https://github.com/sysprog21/lab0-c/commit/81d5ec57c6fe5073c6e75943adcac3a28bcdc2e9)
- **目標**: 實作 `q_insert_tail` 以支援尾部插入元素
- **設計想法**: 與 `q_insert_head` 一樣，只是插入的位置變成 `queue` 的 `tail`。
:::spoiler 實作流程
* 檢查 `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`](https://github.com/sysprog21/lab0-c/commit/88e02fc25df9ad51b44025a740d54feb5be2328d)
- **目標**: 實作 `q_remove_head` 以移除佇列的頭部元素。
- **設計相法**: `q_remove_head()` 負責移除 `queue` 中的第一個元素，但不釋放記憶體，這符合 `remove` 與 `delete` 的區別。當提供輸出緩衝區時，函式會複製被移除的字串，並確保不會發生溢位。
:::spoiler 實作流程
* 檢查 `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`](https://github.com/sysprog21/lab0-c/commit/a7a18e08c9e357fd62d4404ffbe09a630846560e)
- **目標**: 實作 `q_remove_tail` 以移除佇列的尾部元素
- **設計想法**: 與 `q_remove_head` 設計類似，只是 `remove` 的位置變成 `queue`的 `tail`。
:::spoiler 實作流程

* 檢查 `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`](https://github.com/sysprog21/lab0-c/commit/dbfc4251b907004e9014bdeee9f46039bfef0acc)
- **目標**: 實作 `q_size` 以獲取佇列中的元素數量。
- **設計想法**: 使用 `list_for_each` 來遍歷節點，確保 `O(n)` 時間複雜度，並提升可讀性與可維護性。
:::spoiler 實作流程

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

:::

### q_delete_mid()
Commit: [`b05ef28`](https://github.com/sysprog21/lab0-c/commit/b05ef280b83387b2f9b9182d0772812fadc5deb0)
- **目標**: 使用 `q_size` 改進 `q_delete_mid` 以提升可讀性。
- **設計想法**: 此方法先以 `O(n)` 計算 `queue` 的長度，以確定中間索引，然後再以 `O(n)` 遍歷鏈結串列，確保能準確定位並刪除節點。
:::spoiler 實作流程
* 檢查 `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`](https://github.com/sysprog21/lab0-c/commit/afcc69e7886b0d17074be0f09aec943083cb060c)
- **目標**: 實作 `q_delete_dup` 以刪除重複的元素
- **設計想法**: 由於在這個題目中 `queue` 已經排序，所有重複節點都會是連續的，因此可以透過一次 `O(n)` 遍歷來完成 `in-place` 刪除，不需要額外的儲存空間。通常，在未排序的 `queue` 中，使用 `hash table` 來記錄出現過的字串能有效避免 `O(n²) `的時間複雜度。然而，在此題目中，因為所有相同的字串已經是相鄰的，雜湊表並不能提供額外的優勢，直接遍歷 `queue` 來刪除相鄰的重複值即可達到最佳效率。
:::spoiler 實作流程

* 檢查 `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`](https://github.com/sysprog21/lab0-c/commit/09fb11d2e5ef48a9d28e2f3a844e0b889fd0316e)
- **目標**: 實作 `q_swap` 以交換相鄰的節點
- **設計想法**: 該函式透過遍歷 `queue`，將每對相鄰的節點進行交換，且不需要額外的記憶體配置。該方法能在 `O(n)` 的時間內完成操作。
:::spoiler 實作流程

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

:::

### q_reverse()
Commit: [`673ac5e`](https://github.com/sysprog21/lab0-c/commit/673ac5e89534451c12535ed022cbe2a94a4e5410)
- **目標**: 實作 `q_reverse` 以反轉 `queue `內的元素順序。
- **設計想法**: 此函式會透過 `list_move`，每個節點依序移動到 `queue` 的前端，避免不必要的記憶體操作，並維持 `O(n)` 的時間複雜度。
:::spoiler 實作流程

* 檢查 `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`](https://github.com/sysprog21/lab0-c/commit/70b01002e28312369e0a3581aa4b827240d4f37f)
- **目標**: 實作 `q_reverseK` 以反轉 `queue` 中每 `k` 個節點的順序
- **設計想法**: 函式在進行反轉前，會先確認 `queue` 是否包含完整的 `k` 個節點，以避免處理不完整的群組。透過 `list_move` 進行 `in-place` 反轉，使演算法達到 `O(n)` 時間複雜度，且不會進行額外的記憶體配置。
:::spoiler 實作流程

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

:::

### q_sort()
Commit: [`c01e743`](https://github.com/sysprog21/lab0-c/commit/c01e7434cba531349918a3582d876a1985d8f3cf)
- **目標**: 實作 `q_sort` 以排序 `queue` 中的元素，可選擇遞增或遞減排序
- 設計想法:
- 這次用插入排序來實現 `q_sort()`，實作方式為 `in-place sorting`，並且不會額外配置新的記憶體。但最差的情況下時間複雜度為 `O(n^2)`。
:::spoiler 實作流程

* 檢查 `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`](https://github.com/sysprog21/lab0-c/commit/6fa239e3c5923b9e28231d2032faeab6e08088a3)
- **目標**: 實作 `q_ascend` 移除違反遞增順序的節點
- **設計想法**:
- 該函式從右向左掃描，追蹤目前為止遇到的最小值。如果某個節點的值大於此最小值，就將其移除。這種做法確保了最佳的 `O(n)` 解法，僅需掃描列表一次，並能立即釋放不必要的節點。
:::spoiler 實作流程
* 檢查 `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`](https://github.com/sysprog21/lab0-c/commit/11201ce7ed95df6458abefe385e860d72ae1bf2c)
- **目標**: 實作 `q_descend` 以移除右側更大值的節點
- **設計想法**:
- 該函數從右向左掃描，追蹤遇到的最大值。如果某個節點的值小於此最大值，
則將其移除。此方法保證 `O(n)` 最佳解，能夠立即釋放不必要的節點，並確保正確性。
:::spoiler 實作流程
* 檢查 `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`](https://github.com/sysprog21/lab0-c/commit/5553243897f4d2290a647e267973167dcbda4fc8)

- **目標**: 使用 `q_merge` 合併多個已排序的佇列

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

:::spoiler 實作流程
* 檢查 `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` 大小。

:::