2025q1 Homework1 (lab0)

contributed by <As7r1d>

作業書寫規範:

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

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 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.

$ 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) i5-8250U CPU @ 1.60GHz
    CPU family:           6
    Model:                142
    Thread(s) per core:   2
    Core(s) per socket:   4
    Socket(s):            1
    Stepping:             10
    CPU max MHz:          3400.0000
    CPU min MHz:          400.0000
    BogoMIPS:             3600.00

開發過程

q_new

功能： 根據作業要求建立新的空佇列。
透過程式碼可以觀察到:
- NULL queue 表示佇列未成功初始化，Empty queue 表示佇列已初始化但無元素。而 q_new 函式是要求建立一個 Empty queue 。
- 空佇列（Empty queue）結構：
  - 1 個 head 指標去指向空佇列
  - head 所指向的 next (head->next) 指向 head 自己
  - head 所指向的 prev (head->prev) 指向 head 自己
實作內容：
- 從 list.h 標頭檔中發現有許多已定義 API 可用，所以我使用INIT_LIST_HEAD 達成該函式要求，並且使用 malloc 配置記憶體區塊給 head。
程式碼：Commit 20e2f3d

qtest 執行：

./qtest
cmd> new
l = []
cmd> ih a
l = [a]
cmd> ih b
l = [b a]
cmd> ih c
l = [c b a]
cmd> free
l = NULL

q_free

功能： 釋放佇列所佔用的記憶體。
想法:
- 追蹤 queue.h 標頭檔中，發現定義 element_t ，element_t 表示鏈結串列中之元素。
- q_free 函式釋放 element_t 所佔據的空間。
- element_t
- 結構：
  - 指向字元陣列
  - 雙向鏈結串列之節點
實作內容：
- 先檢查 head 是否為 NULL。
- 使用 list.h 中 list_for_each_safe 來遍歷佇列中 element_t 並刪除節點。
- 使用 list.h 中 list_del 從鏈結串列中移除該節點。
- free(entry->value)：如果 value 指標指向的記憶體不為 NULL，則釋放。
- free(entry)：釋放 element_t 節點本身。
- 釋放 head
程式碼：Commit 20e2f3d

qtest 執行：

./qtest
cmd> new
l = []
cmd> ih a
l = [a]
cmd> ih b
l = [b a]
cmd> free
l = NULL

q_insert_head 和 q_insert_tail

功能：
- q_insert_head：在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)。
- q_insert_tail ：在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)。
想法:
- 這兩個函式的核心概念相同，主要差異在於插入的位置不同
- 會使用到 strdup() 為一個字串分配新的記憶體，並把原始字串的內容複製過去。這樣就不會跟原始字串共用同一塊記憶體。
實作內容：
- 檢查 head 是否為 NULL ，如果 head 為 NULL，直接回傳 false。
- malloc(sizeof(element_t)) 動態配置記憶體空間給新節點。
  如果 malloc 失敗，回傳 false。
- strdup(s) 為 value 配置記憶體並存入字串內容，複製字串 s 並存入 value。
```
new_element->value = strdup(s);
if (!new_element->value) {
    free(new_element);
    return false;
}
list_add(&new_element->list, head);
```
- 將新節點加入佇列
  - q_insert_head：用 list_add(&new_element->list, head) 把新節點加到佇列開頭。
  - q_insert_tail：用 list_add_tail(&new_element->list, head) 把新節點加到佇列尾端。
- 成功插入後回傳 true
程式碼：Commit d0eaa19

qtest:

cmd> new
l = []
cmd> ih a
l = [a]
cmd> ih b
l = [b a]
cmd> it c
l = [b a c]
cmd> it d
l = [b a c d]

q_remove_head 和 q_remove_tail

功能：
- q_remove_head：在佇列開頭 (head) 移去 (remove) 給定的節點。
- q_remove_tail：在佇列尾端 (tail) 移去 (remove) 給定的節點。
- 這兩個函式會回傳被移除的 element_t 節點，但不會幫你 free()。

實作內容：

q_remove_head：取 head->next 第一個節點。
q_remove_tail：取 head->prev 即最後一個節點。
使用 list_entry(node, type, member) 從 struct list_head * 回推到 type *（element_t *）。

    if (!head || list_empty(head)) {
        return NULL;
    }
    struct list_head *first = head->next;

    element_t *element = list_entry(first, element_t, list);

如果 sp 不是 NULL，就複製字串內容
為了確保不會超過緩衝區的大小，把 element->value 複製到 sp，但最多只會複製 bufsize - 1 個字元
加上 \0 ，確保字串結束。

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

程式碼： Commit 5eb769f

qtest:

l = [c b a]
cmd> rh
Removed c from queue
l = [b a]
cmd> rt
Removed a from queue
l = [b]

q_size

**功能：**計算目前佇列的節點總量
**實作內容：**就是透過 while 迴圈遍歷整個鏈結串列，從 head->next 開始，沿著 next 一直走，直到回到 head 為止，每走一個節點就讓 count 加 1，最後回傳總數。
程式碼：Commit 189849e

qtest:

cmd> ih a
l = [a]
cmd> ih b
l = [b a]
cmd> ih c
l = [c b a]
cmd> size
Queue size = 3
l = [c b a]

q_delete_mid

功能： 移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List

實作內容： 使用快慢指針的方式找到中間點，slow 指標一次前進 1 步，fast 指標一次前進 2 步。當 fast 走到底時，slow 剛好走到中間節點。

while (fast->next != head && fast->next->next != head) {
    slow = slow->next;
    fast = fast->next->next;
}
element_t *element = list_entry(slow, element_t, list);
list_del(slow);

程式碼：Commit 9795cc0

qtest:

cmd> size
Queue size = 3
l = [c b a]
cmd> dm
l = [c a]

q_delete_dup

功能： 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II
實作內容：
current 代表目前正在檢查的節點。從佇列的第一個有效節點開始，不包含 head。一一比對 current 和後面的所有節點，找出重複的字串。
```
struct list_head *current = head->next;
```
strcmp() 比對兩個字串，如果相等，表示找到重複的節點
```
if (strcmp(current_element->value, compare_element->value) == 0) 
```
如果 found_duplicate 為 true，代表 current 這個節點也有重複，直接刪掉。如果沒有重複，current 就繼續往下一個節點移動。
```
if (found_duplicate) {
    list_del(current);
 }
```
程式碼： Commit 9795cc0

qtest:

l = [c b c c a]
cmd> dedup
ERROR: Duplicate strings are in queue or distinct strings are not in queue
l = [b a]

由於會出現上述error，目前還在修正。

q_swap

功能： 交換佇列中鄰近的節點。
實作內容：
- 如果佇列長度<= 1，不需要交換，直接返回。
- 取得 current（第一個節點）和 current->next（第二個節點），刪除 second 節點，然後將它插入到 first 之前。更新current節點繼續進行交換下一對節點
```
struct list_head *first = current;
struct list_head *second = current->next;
list_del(second);
list_add(second, first->prev);
current = first->next;
```
程式碼： Commit d9a5993

qtest:

l = [h g f e d c b a]
cmd> swap
l = [g h e f c d a b]
cmd>

q_reverse

功能： 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點。
實作內容：
- 遍歷整個佇列並交換 next 和 prev
```
while (current != head) {
    temp = current->next;

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

    current = temp;
}
```
temp = current->next ：暫存 current->next，確保反轉後能找到下一個節點。
current->next = current->prev ：讓 next 指向原本的 prev。
current->prev = temp ：讓 prev 指向原本的 next
程式碼：Commit a745816

qtest:

l = [g h e f c d a b]
cmd> reverse
l = [b a d c f e h g]

q_reverseK

功能： 類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列，詳見 LeetCode 25. Reverse Nodes in k-Group
實作內容：
list_cut_position() 這個函式，它能夠直接將前 k 個節點切割出來形成一個新的鏈結。當 k 個節點被切割出來後，接下來反轉。這裡直接利用了 q_reverse()，因為它已經能夠有效地反轉整個雙向鏈結串列，所以不需要再手寫反轉邏輯，這樣可以讓程式碼更模組化，提升可讀性。
反轉後的 k 個節點需要拼接回結果，因此使用 list_splice_tail() 來將反轉後的區塊加到一個新的 result 鏈結。
最後，處理剩餘不足 k 的節點時，直接將它們拼接到 result，不做任何反轉。
程式碼： Commit a745816

qtest:

l = [j i b a d c f e h g]
cmd> reverseK 2
l = [i j a b c d e f g h]

q_sort

功能： 以遞增順序來排序鏈結串列的節點。
實作內容：
- 選擇 Merge Sort 來實現
- 將鏈結串列拆成兩半，這樣可以遞迴地對較小的部分進行排序，最終再合併回去，然後再使用快慢指標來找出鏈結串列的中間點（ slow 一次走 1 步，fast 一次走 2 步，fast 到達尾端時，slow 剛好在中間點）
- 透過 list_cut_position(&left, head, slow) 將 head 後半段的節點分割成 left，這樣 head 和 left 各自代表原來的前半段和後半段。
```
struct list_head left;
struct list_head *fast, *slow;

INIT_LIST_HEAD(&left);
slow = head->next;
fast = head->next->next;

while (fast != head && fast->next != head) {
    slow = slow->next;
    fast = fast->next->next;
}
list_cut_position(&left, head, slow);
q_sort(&left, descend);
q_sort(head, descend);
```
- 要合併排序後的兩個部，去比較 left 和 head 的第一個節點，根據 strcmp() 的結果來決定排序方式，使用 list_del(chosen) 從原來的鏈結中移除這個節點，list_add_tail(chosen, &result) 將選出的節點加入 result。重複這個過程，直到 left 或 head 其中一個先變空。
程式碼：Commit 4d3fa7e

執行 make test 時發現排序是unstable：

# Test of insert_head and remove_head
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
# Test of insert_head, insert_tail, remove_head, reverse and merge
# Test of insert_head, insert_tail, size, swap, and sort
ERROR: Not stable sort. The duplicate strings "bear" are not in the same order.
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
ERROR: Not stable sort. The duplicate strings "bear" are not in the same order.
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
ERROR: Not stable sort. The duplicate strings "gerbil" are not in the same order.
# Test of truncated strings
# Test operations on empty queue
# Test remove_head with NULL argument
# Test operations on NULL queue
# Test of malloc failure on insert_head
# Test of malloc failure on insert_tail
# Test of malloc failure on new
# Test performance of insert_tail, reverse, and sort
Warning: Skip checking the stability of the sort because the number of elements 2000000 is too large, exceeds the limit 100000.
# 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: Not stable sort. The duplicate strings "vujqm" are not in the same order.
ERROR: Not stable sort. The duplicate strings "vujqm" are not in the same order.
ERROR: Not stable sort. The duplicate strings "iwkui" are not in the same order.
ERROR: Not stable sort. The duplicate strings "iwkui" are not in the same order.
ERROR: Not stable sort. The duplicate strings "cqson" are not in the same order.
Error limit exceeded.  Stopping command execution
# Test performance of insert_tail
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Testing insert_tail...(0/10)

因此修改如下，使排序成為stable：

- if ((descend && cmp > 0) || (!descend && cmp < 0)) 
+ if ((descend && cmp >= 0) || (!descend && cmp <= 0))

qtest:

l = [i j a b c d e f g h]
cmd> sort
l = [a b c d e f g h i j]

q_descend 和 q_ascend

功能：
- q_ascend：移除所有右側有更小值的節點，最後只保留從左到右遞增的節點。
- q_descend：移除所有右側有更大值的節點，最後只保留從左到右遞減的節點。
實作內容：
這兩個函式的目標類似，一開始的思路是左到右遍歷並檢查右側的節點，但當節點過多時對於較大的鏈結串列會很慢。因此參考 LeetCode 2487. Remove Nodes From Linked List 。直接從左到右遍歷並檢查右側的節點，如果我們先反轉鏈結串列，從右側開始往左掃描，那麼右側的節點已經是處理過的，這樣我們只需要單向遍歷一次，時間複雜度變成 O(n)。

反轉鏈結串列：
```
q_reverse(head);
```
這樣我們從左到右遍歷時，其實是從原本的最右側往左掃描。

遍歷 cur，確保 cur 是目前掃描到的最大(最小)值。next_node 負責檢查 cur 之後的節點。針對 q_ascend，如果 next_node 有比 cur 小的值，就刪除 next_node;針對 q_descend，如果 next_node 有比 cur 大的值，就刪除 next_node。最後透過 list_del() 安全移除 next_node，並釋放記憶體。

struct list_head *cur = head->next;

while (cur != head) {
    struct list_head *next_node = cur->next;
    while (next_node != head) {
        element_t *cur_element = list_entry(cur, element_t, list);
        element_t *next_element = list_entry(next_node, element_t, list);

        struct list_head *next_next = next_node->next;
        if (strcmp(cur_element->value, next_element->value) < 0) {
            list_del(&next_element->list);
            free(next_element->value);
            free(next_element);
        }
        next_node = next_next;
    }
    cur = cur->next;
}

程式碼： Commit 4d3fa7e

qtest:

l = [b a d c f e h g j i]
cmd> ascend
l = [a c e g i]

l = [h d b a c e g i]
cmd> descend
l = [i]

q_merge

**功能：**合併所有已排序的佇列，並合而為一個新的已排序佇列
實作內容：
當在構思 q_merge 這個函式時，要將多個已排序的鏈結串列合併為一個，並且根據 descend 參數來選擇升序或降序排序。不需要頻繁地比較和插入，而是透過 list_splice_tail() 一次性合併所有鏈結串列，再進行一次排序。

取出 head 內的第一個 queue_contex_t：

    queue_contex_t *first_ctx = list_entry(head->next, queue_contex_t, chain);
    struct list_head *result_queue = first_ctx->q;

queue_contex_t 是一個封裝鏈結串列的結構，其中 q 存放具體的鏈結串列。first_ctx->q 會作為合併後的最終結果。

遍歷 head 內的所有 queue_contex_t，將所有鏈結串列合併：

struct list_head *chain_node = head->next->next;
while (chain_node != head) {
    queue_contex_t *current_ctx = list_entry(chain_node, queue_contex_t, chain);
    struct list_head *current_queue = current_ctx->q;

    if (!list_empty(current_queue)) {
        list_splice_tail(current_queue, result_queue);
        first_ctx->size += current_ctx->size;

        INIT_LIST_HEAD(current_queue);
        current_ctx->size = 0;
    }

    chain_node = chain_node->next;
}

遍歷 head 內的所有 queue_contex_t，取得 current_queue（當前佇列）。如果 current_queue 不是空的，將 current_queue 透過 list_splice_tail() 併入 result_queue，然後更新 first_ctx->size，因為 result_queue 現在包含了更多節點。清空 current_queue，避免重複計算。繼續遍歷 head 內的下一個 queue_contex_t。

最後對 result_queue 進行排序

q_sort(result_queue, descend);

最終合併後的大小

return first_ctx->size;

程式碼：Commit 4d3fa7e

qtest:

l = [f d c b a]
cmd> new
l = []
cmd> ih g
l = [g]
cmd> ih h
l = [h g]
cmd> ih a
l = [a h g]
cmd> ih b
l = [b a h g]
cmd> merge
l = [a a b b c d f g h]

2025q1 Homework1 (lab0)

開發環境

開發過程

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_descend 和 q_ascend

q_merge

論文〈Dude, is my code constant time?〉

以 Valgrind 分析記憶體問題

2025q1 Homework1 (lab0)

開發環境

開發過程

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_descend 和 q_ascend

q_merge

論文〈Dude, is my code constant time?〉

以 Valgrind 分析記憶體問題

Read more

2025q1 Homework2 (quiz1+2)

2025q1 Homework3 (kxo)

2025q1 Homework4 (quiz3+4)

linux2025-ideas