2025q1 Homework1 (lab0)

contributed by < awkai99 >

作業書寫規範:

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

$ 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):                 12
On-line CPU(s) list:    0-11
Vendor ID:              GenuineIntel
Model name:             Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
CPU family:             6
Model:                  158
Thread(s) per core:     2
Core(s) per socket:     6
Socket(s):              1
Stepping:               10
CPU(s) scaling MHz:     18%
CPU max MHz:            4500.0000
CPU min MHz:            800.0000
BogoMIPS:               5199.98 
Virtualization:         VT-x
L1d cache:              192 KiB
L1i cache:              192 KiB
L2 cache:               1.5 MiB
L3 cache:               12 MiB             
NUMA node(s):           1
NUMA node0 CPU(s):      0-11

針對佇列操作的程式碼實作

q_new()

• 函式用途：建立新的「空」佇列
• 程式碼：Commit b62c9b4

q_free()

• 函式用途：釋放佇列所佔用的記憶體
• 程式碼：

q_insert_head()

• 函式用途：在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)

q_insert_tail()

• 函式用途：在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)

q_remove_head()

• 函式用途：在佇列開頭 (head) 移去 (remove) 給定的節點

q_remove_tail()

• 函式用途：在佇列尾端 (tail) 移去 (remove) 給定的節點

q_size()

• 函式用途：計算目前佇列的節點總量

q_delete_mid()

• 函式用途：移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List

q_delete_dup()

• 函式用途：在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II

q_swap()

• 函式用途：交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs

q_reverse()

• 函式用途：以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點

q_reverseK()

• 函式用途：類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列，詳見 LeetCode 25. Reverse Nodes in k-Group

q_sort()

• 函式用途：以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法

q_ascend()

參閱 LeetCode 2487. Remove Nodes From Linked List，注意節點間的順序

q_descend()

q_merge()

合併所有已排序的佇列，並合而為一個新的已排序佇列，詳見 LeetCode 23. Merge k Sorted Lists