HackMD
2025q1 Homework1 (lab0)
contributed by <Louis-Wup>
開發環境
$ 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): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i7-11370H @ 3.30GHz
CPU family: 6
Model: 140
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 1
CPU(s) scaling MHz: 20%
CPU max MHz: 4800.0000
CPU min MHz: 400.0000
BogoMIPS: 6604.80
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 192 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 5 MiB (4 instances)
L3: 12 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-7
Git 使用方法
我找到一個適合初學者的 git 教學網站
網站：https://www.runoob.com/git/git-tutorial.html
針對佇列操作的程式碼實作
在以下內容中， list_head 型態的變數與 element_t 型態的變數，都將稱為「節點」而非「元素」，因此即使使用如 list_for_each_entry_safe 等函式也會稱為「遍歷節點」，而非「遍歷元素」，而其 element_t 的 value 則稱為「節點內元素」或是「元素」。此外，注意所有佇列的實作皆為「雙向環狀鏈結串列」，因此若看到「遍歷佇列」等語句，其所指就是「遍歷鍊結串列」。不過，上述兩點配合前後文應能輕易理解其含意。
了解佇列連接方式
在實做前建議先了解該題目佇列的連接方式，否則 q_merge() 有可能會不知如何下手
第一張圖是分別的樣子，以及指標的指向
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
第二張圖是佇列，也就是 element_t 串接的樣子
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
第三張圖是 queue_contex_t 串接的樣子 特別注意 size 部分
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
第四章就是完整的樣子
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
自行添加用以輔助的函式
- q_new_element()
- q_delete_element()
- q_strncmp()
- q_swap_two_node()
- q_bubble_sort()
- q_merge_sort()
- q_merge_two_lists()
q_new()
commit: aad1da5
目標：建立空佇列
想法與簡易流程：
- 使用
malloc分配記憶體空間並檢查是否成功 - 使用 "list.h" 中的
INIT_LIST_HEAD使其指標指向自身後回傳
q_free()
目標：釋放所有被佇列所佔用的記憶體空間
想法與簡易流程：
- 檢查佇列是否存在，若不存在則結束
- 遍歷佇列中的所有節點，將其從佇列中移除後，使指標指向自身，並釋放記憶體
- 釋放佇列頭部所佔的記憶體空間
紀錄：
使用 "list.h" 的 list_for_each_entry_safe 時，因未正確理解變數 entry 與 safe 的功能，導致誤修改了錯誤的節點。實際上， entry 雖作為遍歷時的變數，仍可被修改，這是因為 safe 在 entry 變更前，已先記錄下一個要走訪的節點。如此，即使 entry 被刪除或修改，遍歷仍能透過 safe 賦值給 entry ，確保正確性。
- element_t *entry = NULL, *tmp = NULL;
- list_for_each_entry_safe (entry, tmp, head, list) {
- list_del_init(&tmp->list);
- q_release_element(tmp);
+ element_t *entry = NULL, *safe = NULL;
+ list_for_each_entry_safe (entry, safe, head, list) {
+ list_del_init(&entry->list);
+ q_release_element(entry);
q_new_element()
目標：生成新的佇列節點
想法與簡易流程：
- 使用
malloc分配節點的記憶體空間並檢查是否成功 - 使用
malloc分配字串的記憶體空間並檢查是否成功，若失敗則 釋放步驟 1 分配的記憶體 - 使用
strncpy複製字串 - 回傳指向該節點的指標
紀錄：
一開始實作時忘記處理若 malloc 申請字串失敗時要釋放步驟 1. 分配的記憶體，導致在執行 make test 時，終端機出現錯誤。
TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
ERROR: Freed queue, but 3 blocks are still allocated
之後查看檔案 "trace-11-malloc.cmd"，發現當 malloc 失敗後嘗試清空佇列時，會出現仍有節點未釋放的訊息。使用 Valgrind 檢查後，也確認問題發生在 q_new_element 函式。最終找出原因是當字串記憶體請求失敗時，忘記釋放節點步驟 1. 所佔用的記憶體空間，導致了這個記憶體洩漏的問題。
Freeing queue
ERROR: Freed queue, but 1 blocks are still allocated
==11558== 42 bytes in 1 blocks are definitely lost in loss record 1 of 2
==11558== at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==11558== by 0x10F90B: alloc (harness.c:146)
==11558== by 0x10FA5E: test_malloc (harness.c:176)
==11558== by 0x10FE61: q_new_element (queue.c:44)
==11558== by 0x10FEEE: q_insert_tail (queue.c:75)
==11558== by 0x10CF78: queue_insert (qtest.c:233)
==11558== by 0x10D090: do_it (qtest.c:288)
==11558== by 0x10E74D: interpret_cmda (console.c:181)
==11558== by 0x10ED12: interpret_cmd (console.c:201)
==11558== by 0x10F7FC: run_console (console.c:659)
==11558== by 0x10DB3C: main (qtest.c:1444)
==11558==
==11558== 64 bytes in 1 blocks are still reachable in loss record 2 of 2
==11558== at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==11558== by 0x10F90B: alloc (harness.c:146)
==11558== by 0x10FA5E: test_malloc (harness.c:176)
==11558== by 0x10FE48: q_new_element (queue.c:40)
==11558== by 0x10FEEE: q_insert_tail (queue.c:75)
==11558== by 0x10CF78: queue_insert (qtest.c:233)
==11558== by 0x10D090: do_it (qtest.c:288)
==11558== by 0x10E74D: interpret_cmda (console.c:181)
==11558== by 0x10ED12: interpret_cmd (console.c:201)
==11558== by 0x10F7FC: run_console (console.c:659)
==11558== by 0x10DB3C: main (qtest.c:1444)
==11558==
new_node->value = (char *) malloc(strlen(str) + 1);
- if (!new_node->value)
+ if (!new_node->value) {
+ free(new_node);
return NULL;
+ }
q_insert_head() & q_insert_tail()
commit: 067d4f6
目標：建立節點並插入佇列開頭 / 結尾
想法與簡易流程：
- 確認佇列是否存在
- 使用
q_new_element建立新節點並檢查是否成功 - 使用
list_add/list_add_tail將節點插入佇列頭部 / 尾部
q_remove_head() & q_remove_tail()
commit: 1774c2c
目標：移除佇列開頭 / 結尾節點，並將內容複製到指定變數
想法與簡易流程：
- 確認佇列是否存在或為空
- 使用
list_first_entry/list_last_entry取得指向佇列中的第一個 / 最後一個節點的指標 - 將該節點從佇列中移除，並讓其指標指向自身
- 若該節點內元素非
NULL，則使用strncpy將其複製到指定變數sp後回傳
q_delete_element()
commit: b3a4024
目標：刪除特定節點
想法與簡易流程：
- 使用
list_del_init將節點從佇列中移除，並讓其指標指向自身 - 呼叫
q_release_element釋放該節點佔用的記憶體空間
q_delete_mid()
commit: aefa58c
目標：刪除佇列中央的節點
想法與簡易流程：
- 檢查佇列是否存在或為空，若是則回傳
false - 透過快慢指標的技巧，取得指向中央節點的指標
- 透過
q_delete_element刪除該節點
紀錄：
一開始沒通過靜態程式分析
Running static analysis...
queue.c:146:28: style: Variable 'fast' can be declared as pointer to const [constVariablePointer]
for (struct list_head *fast = head->next;
之後將 const 補上去以增加安全行後通過了。
struct list_head *slow_mid = head->next;
- for (struct list_head *fast = head->next;
+ for (const struct list_head *fast = head->next;
fast != head && fast->next != head; fast = fast->next->next) {
slow_mid = slow_mid->next;
}
q_strncmp()
commit: 7991e1e
目標：比較節點內元素的大小
想法與簡易流程：
- 使用
strlen取得兩個比較對象的字串長度 - 將較長字串的長度作為參數傳遞給
strncmp使用並回傳結果
紀錄：
這個函式主要是為了提高程式的可讀性，降低自身出錯的機率，因為原本的 q_delete_dup 就因為可讀性實在太差，導致我疏忽，未更新 strncmp 中使用的字串長度限制，這種錯誤可能會有潛在的安全問題，且在特定類型的輸入下會直接導致結果出錯（詳細於q_delete_dup說明），因此我決定做出該函式。
此外，當我將程式上傳時，未通過靜態程式碼檢查，需要補上 const 來提升安全性。
int q_strncmp(const struct list_head *a, const struct list_head *b)
{
- element_t *e_a = list_entry(a, element_t, list);
- element_t *e_b = list_entry(b, element_t, list);
+ const element_t *e_a = list_entry(a, element_t, list);
+ const element_t *e_b = list_entry(b, element_t, list);
...
return strncmp(e_a->value, e_b->value, n);
}
q_delete_dup()
目標：若佇列內存在內容重複的節點，則將含有重複內容之節點全部刪除
想法與簡易流程：
- 檢查佇列是否存在或為空，或是只有一個節點
- 使用兩個指標
from和to，分別標記內容重複的起始與結束節點。遍歷佇列時，若遇到內容重複的節點，則將變數delete設為true，並繼續遍歷，直到找到內容不同的節點或佇列結束 - 若
delete為true，則將其重設為false，並刪除from到to（含）的所有節點 - 若遍歷結束則完成，否則回到步驟 2
紀錄：
一開始我想使用 "list.h" 的 list_for_each_entry_safe 來遍歷佇列，不過這樣寫需要在遍歷的開頭檢查比較字串是否為空，因為一開始並沒有比較對象，像是
list_for_each_entry_safe(entry, safe, head) {
if (!from)
from = entry;
else if(q_strncmp(from, entry))
...
}
而用 macro 又不能使第一個取得的節點變成 head->next->next 。因此，若每次迴圈開頭都必須執行一個除了第一次一定為 false 的 if 判斷，會對不具備分支預測，或者僅具備靜態分支預測（if 總是預測不會跳轉）的電腦造成大量時間浪費。於是我決定改為手動寫 while 迴圈來遍歷。
之後在上傳時沒通過靜態檢測，有兩部份要改，首先是要補上 const 增加安全性
queue.c:173:16: style: Variable 'e_from' can be declared as pointer to const [constVariablePointer]
element_t *e_from = NULL, *e_to = NULL;
^
queue.c:173:32: style: Variable 'e_to' can be declared as pointer to const [constVariablePointer]
element_t *e_from = NULL, *e_to = NULL;
- element_t *e_from = NULL, *e_to = NULL;
+ element_t const *e_from = NULL, *e_to = NULL;
接著是另一個問題，要將變數 n 放進迴圈內宣告
queue.c:174:9: style: The scope of the variable 'n' can be reduced. [variableScope]
int n = 0;
queue.c:174:11: style: Variable 'n' is assigned a value that is never used. [unreadVariable]
int n = 0;
- int n = 0;
while (from != head && to != head) {
e_from = list_entry(from, element_t, list);
e_to = list_entry(to, element_t, list);
- n = strlen(e_from->value) > strlen(e_to->value)
+ int n = strlen(e_from->value) > strlen(e_to->value)
? strlen(e_from->value) + 1
: strlen(e_to->value) + 1;
這部分我有些疑慮，我是故意將變數 n 放在迴圈外宣告，這樣可以避免變數 n 一直被重複宣告，避免不必要的開銷，我認為這樣做可能會對效能有所幫助。因此，接下來我打算查找相關資料或進行實驗，來驗證這樣的處理是否真的會對效能產生影響。
TODO : 變數於迴圈內重複宣告是否有效能影響
後來我自己測試時發現原始版本還存在一個問題是在移動 to 指標時，未更新傳遞給 strncmp 的字串長度限制。雖然測試資料沒有出現問題，但存在著潛在的安全風險，以及可能導致錯誤的結果。因此，我決定一方面修掉該問題，一方面提高程式碼可讀性，將 list_entry 以及大量使用 strlen 的部分移到另一個函式 q_strncmp 中，這樣程式碼相比原本變得更加簡潔。
while (from != head && to != head) {
- e_from = list_entry(from, element_t, list);
- e_to = list_entry(to, element_t, list);
- int n = strlen(e_from->value) > strlen(e_to->value)
- ? strlen(e_from->value) + 1
- : strlen(e_to->value) + 1;
- while (to != head && !strncmp(e_from->value, e_to->value, n)) {
+ while (to != head && !q_strncmp(from, to)) {
delete = true;
to = to->next;
- e_to = list_entry(to, element_t, list);
}
q_swap_two_node()
原始版本 commit: b4f7c6c
目標：將傳入的兩節點互換位置
想法與簡易流程：
- 判斷是否為相鄰節點，若是則步驟 2 後結束，否則步驟 3 後結束
- 先宣告變數紀錄
left->prev和right->next後，處理left和right的指標，再處理left->prev和right->next - 先宣告變數紀錄
left->prev,left->next,right->prev以及right->next後，處理left和right的指標，再處理left->prev,left->next,right->prev以及right->next
紀錄：
該方法需要判斷傳入的兩節點是否相鄰，因此需要一個 if-else 的判斷式，但修改內容又有大部分雷同，因此嘗試使用教授上課教的間接指標把 if-else 去掉，不過沒有成功，因此後來又上網查找是否有方法把 if-else 判斷移除後，成功找到了，該方法也確實是透過間接指標來處理特例，以下是討論串連結。
Reference（最後一個回答） ： https://stackoverflow.com/questions/20095529/swapping-nodes-in-double-linked-list
q_reverse()
目標：將佇列反轉
想法與簡易流程：
- 檢查佇列是否存在、為空或僅有一個節點
- 使用
list_for_each_safe遍歷佇列，將每個節點的next指向原本的prev，並將prev指向原本的next - 最後，同樣調整
head的next和prev，完成整個佇列的反轉
紀錄：
我的初始實作方法是透過兩個指標，一個正向、一個反向逐一走訪，並在每一步使用 q_swap_two_node 交換節點。為了確保正確性，我額外使用了兩個指標來記錄下一步要訪問的節點。然而，這種方法雖然直觀，但包含過多的 if-else 判斷與額外的指標變更，影響效率。
後來，我在網路上找到了一種更好的方式，不僅消除了 if-else 判斷與不必要的指標變動，還省去了 q_swap_two_node 的使用，更重要的是，這個方法同樣適用於單向鏈結串列的反轉。
以下是簡化的程式碼比對，詳細內容請參閱 commit 9664572。
演算法 Reference: https://takeuforward.org/data-structure/reverse-a-doubly-linked-list/
github 內程式碼中並未移除 q_swap_two_node
此處的「移除」只是表示新的實作方法已經不再依賴該函式
- q_swap_two_node()
- {
- if (l->next == r) {
- ...
- } else {
- ...
- }
- }
q_reverse()
{
- while (l != r) {
- ...
- q_swap_two_node(l, r);
- if (l->prev == r)
- break;
- ...
- }
+ list_for_each_safe (entry, safe, head) {
+ entry->next = entry->prev;
+ entry->prev = safe;
+ }
+ ...
}
q_reverseK()
commit: fb0a58e
目標：以 k 個節點為一組反轉
想法與簡易流程：
這個函式的主要實做想法是一次將佇列前 k 個節點取出並反轉後，放入其他佇列尾部，不斷重複到整個佇列都完成反轉
- 檢查佇列是否存在、為空、僅有一個節點或 k = 1
- 建立兩個雙向環狀鍊結串列
tmp_list和reverse_list，前者用於暫存從head移走的 k 個節點以便後續反轉，後者用於存放所有反轉後的節點 - 遍歷佇列，每當走訪第 k 個節點時，使用
list_cut_position將其移動至tmp_list，再使用q_reverse反轉，最後透過list_splice_tail_init將排序好的節點加入reverse_list - 最後，使用
list_splice將reverse_list併回head，完成以每 k 個節點為一組的整個佇列的反轉
紀錄：
當時最一開始我的想法其實是使用 list_cut_position 以每 k 個節點為單位儲存到一個新型態的鍊結串列，這個鍊結串列每個節點都為一個雙向環狀鍊結串列與 next 指標，之後只要透過 list_cut_position 以每 k 個節點為一組組成鏈接串列後，每組反轉在串接即可，但準備實作後發現兩個問題，第一個是若 k 很小，則需要大量的而外空間，最差要 O(n) 的額外空間，第二個是該函式沒有回傳值，換言之該函式不能有失敗的風險，否則若失敗了自己也不會知道，因此不能使用含有 malloc 這類有可能失敗的函式。
q_swap()
commit: fb0a58e
目標：節點兩兩一組反轉
簡易流程：
- 將 k = 2 作為參數傳遞給
q_reverseK
q_ascend() / q_descend()
目標：將佇列從小到大 / 從大到小排列，若遇到順序錯誤的節點直接刪除
想法與簡易流程：
- 檢查佇列是否存在或為空，或僅有一個節點
- q_ascend(): 使用兩個指標
small和big，並分別初始化為head->next以及head->next-next後，一起從佇列頭部向尾部遍歷，途中若遇到順序錯誤的節點直接刪除，順序正確則計數器值加一 - q_descend(): 使用兩個指標
big和small，並分別初始化為head->prev->prev以及head->prev後，一起從佇列尾部向頭部遍歷，途中若遇到順序錯誤的節點直接刪除，順序正確則計數器值加一
- 回傳計數計值
紀錄：
一開始我計算回傳值時犯了錯，原以為 small 和 big 指標都有指向節點，所以初始值應該為 2，但其實應該是 0，因為 while loop 還會比較一次。結果執行時出現了 Segmentation fault ，於是我使用 Valgrind 檢測程式後，得到了以下錯誤訊息：
==18817== Invalid read of size 1
==18817== at 0x4850367: strcmp (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==18817== by 0x10BD5F: do_ascend (qtest.c:755)
==18817== by 0x10E74D: interpret_cmda (console.c:181)
==18817== by 0x10ED12: interpret_cmd (console.c:201)
==18817== by 0x10F7FC: run_console (console.c:659)
==18817== by 0x10DB3C: main (qtest.c:1444)
==18817== Address 0xdeadbeef is not stack'd, malloc'd or (recently) free'd
==18817==
Segmentation fault occurred. You dereferenced a NULL or invalid pointer==18817=
發現是 qtest 裡面 strcmp 出問題，因此立刻想到是比較到不應該比較的部份，並發現是回傳大小出錯導致 qtest 裡面迴圈跑過頭。修正後，錯誤訊息轉變為有些節點未釋放，但 "queue.c" 以及 "queue.h" 該函式上方英文說明都為 remove ，因此我去仔細查看 "queue.h" 該函式的詳細說明後，發現其中有一行指出
// Memory allocated to removed nodes must be freed.
因此，我將節點的移除操作改為刪除，變得可以成功執行了。最後，我還發現原本 lab0-c 的 repository 中已經有人提交了相關的 pull request ，只是尚未通過。
此外在實作 q_descend 函式時突然想到， LeetCode 中的題目是單向鍊結串列，所以無法直接反向搜尋，而一時之間又想不出好解法，我就去 LeetCode 找解法，找到一個跟上述 ascend 類似的作法（Reference裡面的第三種解法），它的時間複雜度是 O(n)，空間複雜度是 O(1)，不過最重要的是這個作者對他的解法提供了圖解，使人能夠輕鬆理解其邏輯。
Reference : https://leetcode.com/problems/remove-nodes-from-linked-list/solutions/5073124/remove-nodes-from-linked-list/
q_bubble_sort()
目標：將佇列從大到小 / 從小到大排序
想法與簡易流程：
- 宣告一個指標
ptr_end，並將其設為head - 透過指標
ptr_a和ptr_b從佇列頭部開始，逐一向ptr_end走訪，直到遇到ptr_end。在這個過程中，若發現需要調整順序的節點，則使用q_swap_two_node函式進行交換 - 在每一輪遍歷後，更新
ptr_end為ptr_end->prev，並重複步驟 2 ，直到ptr_end指向head->next為止
紀錄：
該函式一開始是實做在 q_sort ，想說只是 Bubble Sort 且之前已經實作過 q_swap_two_node ，所以可以簡單快速地實現這個排序。然而，結果還是出現了錯誤。第一個錯誤是在交換節點後，指標順序會對調，我忘記將指標復原成原來的順序。第二個錯誤是在 Bubble Sort 的內層迴圈中，我用來作為終止條件的指標指向的節點是可以交換的，因此當該節點被交換時，會導致終止條件出現錯誤。後來成功修復後因為效能考量（測試資料效能測試沒過），就將該函式移出 q_sort 獨自存在，並改用 Merge Sort 來實做 q_sort 。
後來測試時發現，我的作法雖然從小到大是穩定排序，但從大到小不是，因為我的作法是單純使用 xor 運算，等號的有無會造成其中一個方向的排序變成不穩定，還需要想有沒有除了 if-else 以外的解決方法。
// 下方是 Bubble sort 使否交換的判斷
if ((q_strncmp(ptr_a, ptr_b) > 0) ^ descend) {
q_swap_two_node(ptr_a, ptr_b);
...
}
TODO: 解決從大到小的不穩定排序。
q_merge_sort()
commit: 487a0c5
目標：將佇列從大到小 / 從小到大排序
想法與簡易流程：
- 檢查佇列是否為空或只有一個節點，若是，則直接回傳該佇列。
- 使用快慢指標方法，找到 Merge Sort 的中間斷開點。
- 宣告並建立新的佇列（注意，這裡我沒有使用
malloc，而是直接宣告）。 - 使用
list_cut_position來將佇列一分為二。 - 分別對這兩個子佇列遞迴呼叫
q_merge_sort。 - 合併兩個已排序的佇列後回傳合併結果。
紀錄：
這個函式不實作在 q_sort 內的原因是，原本使用 Bubble Sort 實作 q_sort ，但由於效率問題，測試資料無法通過，因此我改為使用 Merge Sort 實作。然而，我希望保留 Bubble Sort 的實作，因為未來可能還有使用的機會，所以我將 Bubble Sort 以及 Merge Sort 獨立出來，並讓 q_sort 決定應該呼叫哪個函式。至於步驟 3，我故意不使用 malloc 來產生新佇列，因為 q_sort 函式沒有回傳值，應盡量避免失敗的可能性，所以不使用可能會失敗的 malloc ，且這樣的宣告方式可以在函式結束時自動釋放記憶體空間，無需手動 free ，如此還避開了大量的 malloc 及 free 的使用。另外，雖然回傳值其實是可以省略的，我也注意過並測試過了，但不回傳似乎有些不太對勁，因此我還是保留了讓函式有回傳值。
q_sort()
相關 commit 請移步到 q_bubble_sort() 以及 q_merge_sort()
目標：將佇列從大到小 / 從小到大排序
想法與簡易流程：
- 呼叫
q_merge_sort
q_merge_two_lists()
初始版本 commit: 58c552e
修正版 commit: 8f8acdd
再修正版 commit: 05da83b
目標：將兩個排序過得佇列合併，並依然保持由大到小 / 由小到大排列
想法與簡易流程：
實作方式是以 head_a 為開頭，依序串接節點，當其中一個佇列串接完畢後，直接將剩餘佇列銜接至尾部並回傳。
- 宣告
ptr指向head_a，用來指向需更新的位置 - 宣告
a和b分別指向head_a->next和head_b->next - 使用
a和b逐一走訪各自的佇列，並透過q_strncmp取得下一個應該加入的節點的指標給node（指向 指向目標節點的指標）後更新指標，直到其中一個佇列遍歷完畢 - 將剩餘的佇列直接串接到
head_a的尾部，最後回傳head_a
紀錄：
一開始我的想法是額外宣告一個佇列，然後將要合併的佇列逐一加入該佇列裡，當有一個完成時，另一個直接串起來，最後在將整條合併後的佇列指派給 head_a 後回傳。不過後來發覺裡面有沒必要的操作，像是額外開一個佇列，以及把佇列還回去，我明明可以直接用 head_a 當開頭來串接其他節點，還有我想到在上課的 linked list 和非連續記憶體操作 中有使用間接指標去減少 if-else statement 大括號裡面的程式碼的技巧，雖然我還需要查資料或做實驗了解為什麼要這麼做，明明一樣都是一個 if-else 的判斷加特定行數須執行，這些程式在 if-else 的大括號裡面跟外面執行究竟有沒有效能上的差異，還是只是因為這樣程式碼比較"乾淨"。
TODO: 實驗程式碼在 if-else 大括號裡面和外面對效能有無影響。
下方為部份差異，可以看到透過間接指標，將 if-else 大括號裡的程式碼提出來，使程式碼變比較乾淨，至於詳細改動請看 修正版 commit: 8f8acdd
- INIT_LIST_HEAD(ptr);
- while (a != head_a && b != head_b) {
- if ((q_strncmp(a, b) ^ descend) < 0) {
- ptr->next = a;
- a->prev = ptr;
- a = a->next;
- } else {
- ptr->next = b;
- b->prev = ptr;
- b = b->next;
- }
- ptr = ptr->next;
- }
+ for (struct list_head **node = NULL; a != head_a && b != head_b;
+ *node = (*node)->next) {
+ node = (q_strncmp(a, b) ^ descend) < 0 ? &a : &b;
+ ptr->next = *node;
+ (*node)->prev = ptr;
+ ptr = (*node);
+ }
後來測試又發現上述程式碼有兩個問題，第一個是把運算順序打反了
- node = (q_strncmp(a, b) ^ descend) < 0 ? &a : &b;
+ node = ((q_strncmp(a, b) < 0) ^ descend) ? &a : &b;
按照之前的版本，這個 descend 根本無法對 q_strncmp 的結果造成什麼影響，除了 LSB 可能會差個一；改正後是再比較大小後，根據 descend 判斷是否選擇另一個節點。而另外一個問題則是跟 q_bubble_sort 一樣，因為對同大小處理的不同，在從大到小排序時會是不穩定排序，而有沒有除了 if-else 以外的解決方法目前仍在尋找中。
TODO: 解決從大到小的不穩定排序。
q_merge()
commit: 58c552e
目標：將多個排序過得佇列合併，並依然保持由大到小 / 由小到大排列
想法與簡易流程：
直接透過 q_merge_two_list 不斷頭尾合併，直到最後剩一個佇列即可
- 取得一共有多少佇列，並判斷是否須往下執行
- 使用雙層迴圈，外層負責判斷還須多少輪內層迴圈，內層迴圈負責頭尾佇列的合併。
- 回傳
q_size的結果
紀錄：
一開始對於 queue_contex_t 的結構不是很了解，花了一堆時間使用 printf 來推測具體結構，終於推測出來，結果放在該區塊最一開始了，不過了解區塊架構後，剩下就簡單了，基本沒碰到什麼問題，就是對問題敘述有一個疑惑
However, q_merge() is responsible for making the queues to be NULL-queue, except the first one.
那到底要不要將 q 指向 NULL 呢，因為沒有那就不符合題目敘述，將 queues 變成 NULL-queue, 而是 Empty-queue, 但如果指向 NULL ，那那些 queue 的 head 不就沒有 free ，變成 memory-leak 嘛？目前（沒有 sync）我測試是有沒有指向 NULL 都會過就是了。
在 qtest 提供新的命令 shuffle
實做 q_shuffle()
依照 Fisher–Yates shuffle 演算法實做 q_shuffle() 很簡單，比較需要額外注意的是我們正常隨機取 0 ~ n-1 的整數時會直接對 rand() 後的結果模 n ，當佇列很小時，每個元素被選擇的機率基本還是維持均勻分佈，但當佇列大到一定程度時，分佈就不均勻了，每次被選擇的基本都將是 0 ~ RAND_MAX 的節點，因此我將取得變數的部份改成如下：
- struct list_head *ptr = head;
- for (int r = rand() % turn + 1; r; r -= 1) {
+ struct list_head *ptr = head->next;
+ int r = rand();
+ for (r = (int) ((float) r / ((unsigned) RAND_MAX + 1) * turn); r;
+ r -= 1) {
ptr = ptr->next;
}
不過即使是目前這種方法，當佇列遠遠大於 RAND_MAX 時，節點被選擇的機率仍舊不會是均勻分佈，每次選擇時都會有幾個節點是無法被選到的，這是因為我們的亂數相較於佇列長度有限，這裡舉個例子：
- 假設佇列長度為 100000 ， 而
RAND_MAX為 32767 (C99 Standard 只保證RAND_MAX大於等於 32767)，則透過上面方法隨機出 r 為 32766 和 32767 時，對佇列的選擇會是節點 99993 和 99996 ，因為
可以發現不但跳過了 99994 和 99995 ，且 99997 ~ 99999 的節點根本不能被選到（假定32767已經是最大亂數），這是因為亂數小於佇列長度必然的限制，就像我們不能用 1 bit 表達 0, 1, 2 一樣，我們沒有足夠大的亂數可以去表達所有我們希望出現的數字，若非要表達只能產生第二個亂數。因此我們可以發現當佇列長度遠大於 RAND_MAX 時仍舊不會是均勻分佈（這裡注意隨著每次進行，乘上的數字會越來越小，所以真正從頭到尾無法被選到的數字只有最後幾個節點，至於其他節點則是輪流無法被選擇），但至少可以取得後面的節點，相較於直接取模仍舊好多了。
新增命令到 qtest
commit: 1702b1e
基本上，參考其他命令（如 descend）就可以輕鬆加入 shuffle 命令。只需要宣告 do_shuffle() ，然後在 console_init() 中使用 ADD_COMMAND() 加入命令它即可。比較麻煩的是，因為作業規定不能修改 "queue.h" ，所以 q_shuffle() 直接放在 "queue.c" 裡時， "qtest.c" 會無法使用它。這是因為 "qtest.c" 只有 include "queue.h" ，而 "queue.h" 又沒有宣告 q_shuffle() 。
如果讓 "qtest.c" 直接 include "queue.c" 也是不應該的。最後，我找到了一個解決方案，使用 extern ，只需要在 do_shuffle() 上方加上：
extern void q_shuffle(struct list_head *head);
這樣 "qtest.c" 就能正確調用 "queue.c" 中的 q_shuffle() 了。
