2025q1 Homework1 (lab0)

contributed by < wcc-gh >

作業書寫規範:

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

實作queue.c

q_new

目的

建立空佇列

實作流程

1. 配置記憶體空間給 list head
2. 若配置失敗，回傳 NULL
3. 若成功，呼叫 INIT_LIST_HEAD 建立 list head

q_free

目的

釋放分配給整個佇列的記憶體空間

實作流程

1. 檢查佇列是否存在，若不存在則直接 return
2. 透過 list_for_each_entry_safe 逐一走訪並釋放節點

• 釋放順序： 節點的 value -> 節點本身

element_t *node, *safe;
    list_for_each_entry_safe (node, safe, head, list) {
        free(node->value);
        free(node);
    }

• 這裡會檢測出 Uninitialized variable: safe [legacyUninitvar]，所以先將 safe 設為 NULL ， 但我認為不用設初值也能正常運作

4. 釋放 head

q_insert_head

目的

自佇列的開頭處插入新節點

實作流程

1. 檢查佇列是否存在，若不存在則直接 return
2. 依序配置記憶體給節點及節點的 value

• 若 value 配置失敗要釋放配置給節點的記憶體

3. 將傳入的字串複製至節點的 value

• 一開始使用 strcpy 會被偵測為 Dangerous function ，根據建議改用 strncpy
  – The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination.
  – 但這邊手動分配了足夠大小的 memory，我認為用 strcpy 應該也沒問題

4. 呼叫 list_add 將節點插入至佇列開頭

q_insert_tail

目的

自佇列的尾端插入新節點

實作流程

與 q_insert_head 相似，最後呼叫 list_add_tail 將節點插入至佇列尾端

q_remove_head

目的

1. 移出佇列第一個元素，並回傳其位址
2. 將該元素的 value 複製至指定的 buffer sp

實作流程

1. 檢查若無佇列或佇列為空，回傳 NULL
2. 呼叫list_first_entry 取得第一個元素位址，並將其移出佇列
3. 複製 value 至 sp

• 為避免 value 長度超過 buffer size ，使用 strncpy，並手動在尾端加入空字元

4. 回傳位址

q_remove_tail

目的

1. 移出佇列最後一個元素，並回傳其位址
2. 將該元素的 value 複製至指定的 buffer sp

實作流程

與 q_remove_head 相似，中間呼叫 list_last_entry 取得最後一個元素位址

q_size

目的

回傳佇列中元素個數

實作流程

1. 檢查若無佇列則回傳 0
2. 呼叫 list_for_each 走訪佇列並計算元素個數
3. 回傳

q_delete_mid

目的

刪除佇列中的位於中間的元素

• 若佇列長度為偶數，刪除靠近尾端的元素

實作流程

1. 檢查若無佇列或空佇列則回傳 false
2. 計算欲移除的元素之 index
3. 走訪陣列找到該元素
   利用快慢指標直接找到該元素
4. 將其移出佇列，並釋放記憶體

• 釋放順序： 元素的 value -> 元素本身

q_delete_dup

目的

刪除佇列中所有相同 value 之元素

• 佇列必須為已排序狀態

實作流程

1. 檢查若無佇列或空佇列則回傳 false
2. 呼叫 list_for_each_entry_safe 走訪整個佇列

bool del = false;
    list_for_each_entry_safe (node, safe, head, list) {
        if (&safe->list != head && strcmp(node->value, safe->value) == 0) {
            list_del(&node->list);
            free(node->value);
            free(node);
            del = true;
        } else if (del) {
            list_del(&node->list);
            free(node->value);
            free(node);
            del = false;
        }
    }

如果目前元素與下一個元素 value 相同刪除該元素，並利用一個布林值 del 追蹤與之前的元素是否相同，以便刪除最後一個重複的元素

q_swap

目的

每兩個元素互相交換位置，若只剩一個節點則保持不動

實作流程

1. 檢查若無佇列或佇列長度 < 2 則不需要操作
2. 呼叫 list_for_each_safe 走訪佇列

• 以布林值 s 控制每兩個迴圈進行一次交換

3. 使用 list_move 讓目前元素與前一元素交換位置

bool s = false;
    list_for_each_safe (node, safe, head) {
        if (s)
            list_move(node, node->prev->prev);
        s = !s;
    }

• list_move(struct list_head *node, struct list_head *head) 原本是將節點移至串列的開頭，但實際上是移動至第二個參數的下一個節點，所以用 list_move(node, node->prev->prev) 交換前後節點位置

q_reverse

目的

反轉整個佇列

實作流程

1. 檢查若無佇列或佇列長度 < 2 則不需要操作
2. 呼叫 list_for_each_safe 走訪整個佇列，並交換每個元素的 next prev 指標
3. 交換 head 的 next prev 指標

q_reverseK

目的

每 k 個元素元素一組進行反轉

實作流程

1. 檢查若無佇列或佇列長度 < k 則不需要操作
2. 計算需反轉的節點數量 (最後未達 k 個節點不需反轉)
3. 利用變數 count 進行分組，紀錄每組的開頭，並在該組結束時以反轉過的順序接上其他組

q_sort

目的

將佇列元素做升序/降序排序

實作流程

1. 檢查若無佇列或佇列長度 < 2 則不需要操作
2. 斷開最後一個節點與 head 的連結，之後的流程作為單向鍊結串列操作
3. 根據 Linked List Sort 中的 Merge Sort 進行操作

• 原本在 Merge 的部份是利用遞迴的方式，但在測試時用長度 2000000 的佇列進行排序會發生 stack overflow ，所以改用迴圈來避免

4. Merge sort 完成後再重建雙向鍊結串列

q_ascend

目的

刪除元素使佇列中剩餘元素呈現升序排列

實作流程

1. 反向走訪佇列，紀錄目前經過的元素最小值 min ，若當前元素比 min 大則刪除該元素
2. 呼叫 q_size 回傳剩餘元素數量

q_descend

目的

刪除元素使佇列中剩餘元素呈現降序排列

實作流程

1. 反向走訪佇列，紀錄目前經過的元素最大值 max ，若當前元素比 max 小則刪除該元素
2. 呼叫 q_size 回傳剩餘元素數量

q_merge

目的

將一串佇列合併為一個佇列，維持降序/升序排序

實作流程

1. 檢查若無佇列或只有一個佇列，直接回傳元素數量
2. 將所有佇列合併至第一個佇列
3. 呼叫 q_sort 進行排序
4. 呼叫 q_size 回傳總元素數量