2025q1 Homework1 (lab0)

contributed by < reberu6 >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [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-8700 CPU @ 3.20GHz
CPU family:               6
Model:                    158
Thread(s) per core:       2
Core(s) per socket:       6
Socket(s):                1
Stepping:                 10
CPU(s) scaling MHz:       64%
CPU max MHz:              4600.0000
CPU min MHz:              800.0000
BogoMIPS:                 6399.96
Virtualisation:           VT-x
L1d:                      192 KiB (6 instances)
L1i:                      192 KiB (6 instances)
L2:                       1.5 MiB (6 instances)
L3:                       12 MiB (1 instance)
NUMA node0 CPU(s):        0-11

開發過程

目前透過自動評分系統得到的分數是 100/100。

`q_size`

Commit

此函式回傳佇列所包含的節點數量。

實作上使用了list_for_each()巨集，這本質上是一個走訪每一個節點的 for 迴圈，然後每走訪一個節點就對計數器加1即可計算節點的數量。若給定的佇列開頭指標不合法或是給定一空佇列，直接回傳 0 即可。

`q_new`

Commit

此函式會創建一個空的佇列並初始化成next和prev指標都指向自己。

在queue.h給定的函式定義中，將struct list_head的指標作為回傳值，可得知此處需要透過malloc來分配struct list_head這個結構所需之記憶體空間（此結構大小則透過sizeof()取得），才得以在函式結束時仍保留記憶體資訊。分配記憶體也有可能出現失敗的情況，所以在分配完畢時就判斷如果新建的new_list為空則代表分配失敗則函式回傳NULL。

`q_free`

Commit

此函式傳入佇列的位址後就會把整個佇列從記憶體中釋放。

處理head為NULL:
如果傳入的佇列的head是NULL的話就代表佇列本身就不存在而就不需要額外去釋放記憶體，所以就在程式的一開始就判斷。

透過走訪每個節點來進行記憶體的釋放：
原本想說只要使用list_head類型的指標從頭到尾走訪每個節點並使用free來釋放記憶就可以了，但是佇列有兩種類型的節點一種是list_head另一種則是element_t，所以無法直接操作element_t類型的節點。後來我想說head->next會指向element_t類型的節點，那直接把head->next指向的位置直接給element_t *類型的current就可以直接操作，而後面的操作就是分成兩種狀況 :

如果head下一個節點是自己的話代表沒有element_t類型的節點，所以就直接把head給釋放。
若有element_t類型的節點，先暫存current下一個節點next等我們釋放完element_t再把current移過去，所以一開始就先釋放節點的value接著釋放節點本身就可以了，最後往下個節點移動。
重複 2 以上直到current是head節點，也就是把element_t類型的節點都已是放完畢。













void q_free(struct list_head *head)
{
    if (!head)
        return;
    element_t *current = head->next;
    while (current != head) {
        element_t *next = current->list.next;
       free(current->value);
       free(current);
       current = next;
    }
    free(head);
}

進行編譯卻出現 :

queue.c: In function ‘q_free’:
queue.c:5:8: error: initialization of ‘element_t *’ from incompatible pointer type ‘struct list_head *’ [-Werror=incompatible-pointer-types]
   5  |     element_t *current = head->next;
      |                          ^~~~
queue.c:7:9: error: initialization of ‘element_t *’ from incompatible pointer type ‘struct list_head *’ [-Werror=incompatible-pointer-types]
   7  |         element_t *next = current->list.next;
      |                           ^~~~~~~

程式中第 5 和 7 都出現了指標類型不相容的錯誤，後來我看了指標的介紹發現我之前想的不對，不能直接把

element_t *current = head->next;

這是因為head->next的類型是list_head，而current所需element_t的類型，這會導致編譯失敗。雖然head下個節點的確是element_t的類型，但是事實上head->next是連結到element_t裡面的list_head結構的list，程式中的第 7 行也是同樣的錯誤，所以應該做的修正就是把current跟next的類型改成list_head來走訪每個節點。

那現在的問題就是由於current跟next類型是list_head的話要如何操控element_t類型的記憶體去釋放element_t中的value，所以只好創一個新的element_t類型的指標去接管這個記憶體，但之前說過head->next所連結的位置是element_t中的list，所以沒辦法取得下個節點的起始位置，這時要透過結構的記憶體排列來回推element_t的位置，例如 :

element_t tmp;

Address of tmp:       0x1000
Address of tmp.char:  0x1000
Address of tmp.list:  0x1000+sizeof(char *)

我們會知道tmp.list的位置，所以回推到tmp的位置就會是：
假設tmp.list的位置是0x1008的話，那麼0x1008 - sizeof(char *)則可得到tmp的位置。具體的計算如下：

element_t *real_pos = (element_t *)((char *)current - offsetof(element_t, list));

原本current是list_head類型的指標，但需要先把它轉成char類型的指標，這是因為在計算位址的時候，若是current - 1的話會依照list_head的單位計算，那麼假設current = 0x1008的話，減一之後也不會是0x1007而是current減去一個list_head的單位，所以若我們先把current轉成char類型的指標的話就能正確的計算，這是因為char的單位是 1 byte。

至於為何是用offsetof而不是sizeof去計算偏移量的原因是不同環境和編譯器的原因需要處理對齊的問題所以有些會有 padding，比如說 32 位元的電腦在存取資料時一次都是 4 bytes (32 bits)，而使用sizeof的話就會忽略那個可能性而導致出錯，offset本身就是用來計算結構體成員的偏移量（bytes），而sizeof則是計算一個類型的總大小。

`q_insert_head`

Commit
Commit 修正字串長度超過 4 個字元時記憶體釋放錯誤
Commit 修正指標更新順序，確保正確連結
Commit 精簡程式

此函式會在佇列的最前面插入一個元素 (element)。

佇列不存在 :
一開始就先判斷佇列是否存在比較好，避免後面的操作。

分配失敗 :
這跟q_new的檢查一樣，記憶體不一定分配就會成功。這裡要注意的是如果分配失敗的話，記得檢查前面有沒有分配的操作，有的話在這裡分配失敗需要釋放掉它。

插入最前面 :
插入最前面只需修改 4 個指標，比如說一開始是 :

      ->    ->      ->
head     a     ...     head
     <-    <-      <-

然後插入一元素b

在修改head->next之前，先把新增的元素b指向原本head->next所指的地方，比如說a，避免遺失a的位置。
接著把head->next指向新元素b。

完成後 :

head -> b -> a -> ... -> head

但向左的連結prev還是 :

head <- a <- ... <- head

所以需要以下操作 :

在修改a指向b，之前先把b指向a所指的地方，避免遺失head位置。
接著把a指向b

完成後 :

head <- b <- a <- head

字串處理 :
基於要求，需要把字串存入一塊新的記憶體空間。

所以我們得知道字串的長度來分配記憶體。可以靠字串最後一個字元是\0的特性來計算，只需透過while迴圈來進行迭代計算長度。
接著就可分配空間。
透過指標操作一個個的把字元複製到新的記憶體中，我們可以透過剛才計算出的長度來決定for迴圈要迭代幾次。

當元素的value超過 4 個字元的時候出現重複釋放的問題 :
我在想為何是 4 這個數字，因為程式中根本沒有直接使用到接近 4 的常數，後來才發現應該要直接分配字串長度加上\0的長度len，而不需要sizeof去計算，因為這樣反而是計算len這個變數型別的大小，len是int型別，所以之前每次分配記憶時都只有分配 4 bytes，這就導致了只要插入 4 個字元或以上時就會出現記憶體錯誤的問題。

--- a/queue.c
+++ b/queue.c
         len++;
     }
     len++;
-    char *value = malloc(sizeof(len));
+    char *value = malloc(len);
     if (!value)
         return false;

修正指標更新的順序確保連結正確
這個錯誤是在實做q_insert_tail時才發現的，我發現順序不對的話是沒法把元素插到尾端的，這時我想起在做q_insert_head好像沒特別意識到這件事，於是回去檢查後發現了錯誤。在實現q_insert_head後也有測試，但功能都正常，我想這是因為把head->next指向b的話是沒問題的，但被影響的是head->next-prev，也就是a的prev沒指向b，而是讓b指向了自己，所以這沒影響到後續要在最前面插入新的元素。在釋放測試時也正常是因為q_free是透過next來向右移動，而向右的連結都沒錯的話當然也可以正常釋放了。

-    head->next = &new->list;
     head->next->prev = &new->list;
+    head->next = &new->list;
     return true;
 }

`q_insert_tail`

Commit
Commit 精簡程式

程式基本上跟q_insert_head一樣，所以只須想出如何插入在最後面。

插入最後面 :
同樣只需修改 4 個指標，比如說一開始是 :

      ->      ->    ->
head     ...     a     head
     <-      <-    <-

然後插入一元素b在尾端，由於需要透過head->prev存取a，所以這個指標最後改 :

把b直接指向head。
透過修改head->prev->next讓a指向b。

完成後 :

head -> ... -> a -> b -> head

但向左的連結還是 :

head <- ... <- a <- head

所以需要以下操作 :

把b指向a（也就是head->prev所指的位置）。
修改head->prev指向b。

完成後，向左的連結就完成了 :

head <- ... <- a <- b <- head

`q_remove_head`

Commit
Commit 新增拷貝字串時的邊界條件
Commit 精簡程式

此函式會移除最前面的元素。

移除最前面的元素 :
比如說一開始是 :

      ->    ->    ->      ->
head     b     a     ...     head
     <-    <-    <-      <-

要將b移除的話，要注意head->next和head->next->next的變更順序是較低的，因為分別透過它們存取b和a。操作順序如以下 :

將a指向head。
因為要修改head->next，所以透過tmp將b的位置暫存。
將head->next指向a。
將b的next和prev指向NULL。

若傳入的sp非空且成功移除b :
由於bufsize的大小限制且最後得放\0，最多只能複製bufsize - 1個字元，所以透過for迴圈複製前bufsize - 1個字元到sp。

`q_remove_tail`

Commit
Commit 新增拷貝字串時的邊界條件
Commit 精簡程式

移除最後面的元素 :
比如說一開始是 :

      ->      ->    ->    ->
head     ...     a     b     head
     <-      <-    <-    <-

要移除b同樣也得注意操作順序 :

將a指向head。
透過tmp暫存b的位置。
將head指向a。
將b的next和prev指向NULL。

`q_delete_mid`

Commit
Commit 使用快慢指標技巧找到中間節點
Commit 精簡程式

一開始想到的方法是先計算出總共有幾個節點n，接著計算出中間節點的位置為第

⌊ n / 2 ⌋

個（從 0 開始計算），接著透過for迴圈迭代變更指標current的位置到中間節點的前一個（後來在使用快慢指標時發現其實直接移到中間節點也可以，因為雙向鏈結所以進行指標更新時b不會遺失a和c的位置），進行釋放和指標更新。

假如一開始只看向右的連結的話如下：

head -> a -> b -> c -> head

那透過走訪每個節點可以算出佇列的長度為 3 ，接著要走到a然後釋放b，但如果就這樣釋放b的話會導致遺失c的位置，所以順序如下：

$⌊ 3 / 2 ⌋ = 1$ ，a的索引是0，所以中間節點是b。
走到b的前一節點a。
把b的下一個節點c暫存。
釋放b並把a指向c。

接下來看向左的連結：

head <- a   b <- c <- head;

b已經被釋放了所以沒法從b到a，而c仍指向b原本的記憶體位置，但如果存取c->prev會導致未定義的行為。最後只須透過剛才暫存的指標讓c指向當前位置a，這樣一來就完成了刪除和正確連結。

完成後沒法通過提交檢查出現了NO dictionary found，由於它是fmtscan的執行結果，所以看了lab0-c/tools/fmtscan.c的內容後發現會用到/usr/share/dict/american-english和lab0-c/scripts/aspell-pws，因為aspell-pws存在所以去看american-english有沒有存在，發現沒有，後來執行sudo apt install wamerican安裝完後，有了american-english就可以了。

快慢指標
參考分析「快慢指標」實現找到中間的點，也了解雖然在演算法上的複雜度都是一樣的，但是根據操作的方式不同讓時間局部性產生差異，這需要了解硬體架構才有可能意識到這點。

`q_delete_dup`

Commit

刪除具有重複的字串的節點，就需要比對的動作，目前是想到用兩個指標來完成 :

先用一指標a指向要被比較的對象，另一指標b則指向比較的對象，如以下示意 :

         [a]=>=>=>
head <-> cat <-> dog <-> cat <-> pig <-> head
                 [b]=>=>=>

接著就是固定a，然後b不斷向右並與a的字串進行比對，有相同就是刪除元素並更新指標。
等b下個是尾端後，a就往下個元素移動。
重複 2 和 3 直到a到達最後一個元素就完成了所有的比對，在程式中我使用了while (a != b)來判斷是因為a不可能和b是同個元素，這樣就不需比對了。

完成後才發現做錯了，比如輸入[a, a, a]，結果出現ERROR: Queue has more than 0 elements，我一開始以為是要實現跟 LeetCode 相同的功能，後來回去看才發現是刪除所有有重複字串的元素，只保留原始佇列中不重複的字串。

input:    [a, a, a]
output:   [a]
expected: []

在修改的過程中程式的運作一直不如預期，所以使用 gdb 來看過程，結果發現：
雖然ae->value和be->value都是"a"，但是程式碼中ae->value == be->value的結果卻是false，這才發現因為ae->value是char的指標，所以比較的是指標的地址，所以不管怎麼比都是false，所以改用string.h中的strcmp比較字串是否相等。

完成q_delete_dup後發現，只要有相同的字串中間有別的字串的話就會出現錯誤，如以下示意：

intput:  [a b a]
output:  [b]

出現ERROR: Duplicate strings are in queue or distinct strings are not in queue雖然功能正確但還是出現了錯誤，這裡不確定是queue.h中的描述錯誤還是檢查程式的錯誤，但這個錯誤並沒有在make test中檢測出來。

`q_swap`

Commit

q_swap在實作上只需要修改 6 個指標就能完成兩個點的位置交換。

以下為示意：

        [c]
head <-> a <-> b <-> head

需要清楚的知道更改指標的順序，這樣一來就可以只透過一個指標修改。先把c指向佇列中的第一個元素a，接下來c->prev跟c->next會比較晚更改，這是分別為了操作head和b:

透過c->prev把head->next指向b。
透過c->next把b->prev指向head。

       [c]
     ------>
head <- a -> b <-> head
     <------

接下來就可修改c->prev跟c->next:

把c->prev指向b，也就是b在a前。
把c->next指向b->next，也就是head前。

              [c]
            ------>
head  <-> b <- a -> head
            <------

既然知道c-prev是b和c->next是head最後再更新一些指標就完成了：

把b->next指向a。
把head->prev指向a。

最後如以下：

              [c]
head <-> b <-> a <-> head

接著就是想元素有兩個以上的時候要怎麼處裡可以重複以上的動作，那麼經過以上的操作，可以知道c只要指向要交換的a與b相對位置中的a就能夠進行操作的話，接著只需要檢查後面有沒有元素可操作「交換」，有的話把c移到適當的位置即可。

假如新增兩元素x和y:

              [c]
head <-> b <-> a <-> x <-> y <-> head

如果a的下個元素如果是head代表沒其他元素則結束函式，否則c往下個元素移動。所以如果最後有成功移動的話則如以下：

                    [c]
head <-> b <-> a <-> x <-> y <-> head

因為至少要有兩個元素才能交換，所以需再檢查一次c的下個元素是不是head，如果不是的話代表有兩個元素足以進行「交換」，這時把此條件當作while的判斷條件，這是因為c已經到了跟一開始a和b相對位置中的a，所以透過此判斷可以決定while的內的交換過程要不要執行。

`q_reverse`

Commit

雖然q_reverse和q_swap在只有兩個元素時的效果一樣，但其實操作的過程不同，q_swap在操作的時候會把a放到b的後面，而q_reverse則是讓所有的next變成prev和prev變成next，達成第一個變最後一個，最後一個變第一個。目前是採用兩個指標達成q_reverse:

先用一指標a指向要被修改的對象，另一指標b則指向暫存位置的對象，如以下示意 :

        [a]   [b]
head <-> x <-> y <-> head

因為是反轉所以a的前一個head會變成a的下一個，修改a->next為a->prev所指。
接著a的前一個會是b，所以修改a->prev為b（剛才暫存b所以不怕 2 修改了a->next）。
結果如下，上方的箭頭是next，下方則是prev:

       [a]  [b]
    <--
head -> x <- y <-> head
          -->

判斷b是否在head的位置，如果不是a和b往下移動。
重複 2~4 直到b在head的位置則結束後可完成所有指標的修改。

              [a]    [b]
head <-> x <-> y <-> head

`q_reverseK`

Commit
Commit 精簡程式

雖然q_reverseK很像q_reverse，但是會每k個一組，進行反轉。q_reverseK的核心「反轉」可以和q_reverse很像，但需要做些修改 :

原本修改a->prev的時機點 :
原本是改完a->next之後接著修改a->prev，但是如果這麼改的話會發現 :

                [a]    [b]
head <-> x1 <-> x2 <-> y1 <-> y2 <-> head

如果a已經走到該組的尾端的時候，不應該把a->prev指向b，而是前一組的尾端，此時又會有兩種可能 :

a所在的組別是第一組的話，就得把a->prev設成head。
否則把a->prev指向前一組的尾端，所以得暫存前一組的尾端，而前一組的尾端暫存的時機就是在反轉那組時的頭部。

能反轉一組之後，接著就只需要算出要反轉幾組後透過for迴圈迭代反轉每一組。

元素不足以組成一組 :
那如果有些元素不足以組成一組時不須進行反轉，所以就把剛才暫存的尾端指向剩餘的部分的開頭即可（也就是b）。

`q_sort`

Commit Bubble sort
Commit Merge sort

在想如何排序的時候，我是用暴力法去排序，排完後複雜度是

O (n^{2})

還沒有達到make test要求的

O (n \log n)

，但想不出來，所以只好查 google 看還有甚麼排序的辦法時才發現我用的是 Bubble Sort 。

暴力法 (Bubble Sort) :
最一開始的想法就是：

假設是遞增排序的話，那麼最大的一定要位於最後面。
所以若有一個較大的數字在佇列的前方的話，想往後方要透過不斷比較然後把它往後移動，比如a和b一開始分別指向佇列中的第一個和第二個元素 :

        [a]   [b]
head <-> 4 <-> 3 <-> 2 <-> 1 <-> head

如果發現a的數字比b還大就交換位置 :

        [b]   [a]
head <-> 3 <-> 4 <-> 2 <-> 1 <-> head

所以若佇列中有n個節點且最大的數字放在最前方的話，那麼至少也得比較且移動n-1次才會到最後方，這部分可透過for迴圈迭代完成，交換的部分跟之前的q_swap是一樣的。

等到最大的數字放在佇列的最後方後，那麼未排好的部分只剩下前面的n-1個元素，所以就再對前n-1元素進行排序，透過head可以把a和b又放在最前方，接著就是迭代直到所有的元素排好 :

        [a]   [b]
head <-> 3 <-> 2 <-> 1 <-> 4 <-> head

這裡比較是用數字來舉例，但實際上會是字串，所以這個比較的動作就透過string.h裡的strcmp來達成比較的動作即可。

合併排序 (Merge sort)
合併排序概念上是透過分治法（由上而下）來解決，所以透過遞迴來實現的話是很適合，但是若採用遞迴的實現方式的話，會大量使用到 stack 的記憶體空間，尤其是遞迴深度較大的情況，所以採用由下而上的方式，直接處理最小的情況後，接著往上處理較大的情況，但是遇到了許多實作上的問題。

一開始為了實現合併排序，我把q_merge中的「合併兩個佇列」獨立成一個函式為merge_two，但想使用這個函式需要傳入兩個有head的佇列。

原本會傳入兩個佇列的head後，沒有輸出（回傳值）但會直接合併到第一個head的佇列當中。

那麼現在的問題是，由於是採用由下而上的方式，那麼需要把一個佇列切割成n個佇列之後兩兩合併後往上合併直到剩下一個佇列，這時想到使用跟q_merge中管理多個佇列的queue_contex_t的結構，但後來發現若要把每個元素變成佇列的話會需要分配記憶體空間給每個佇列的head，因為元素的數量是變數，所以我沒法每個元素都手動把head串上去和用queue_contex_t來管理，得用for迴圈迭代幫我達成，但是這樣的話會到用區域變數的head和queue_context_t的話，會迭代完後就消失，但是使用分配記憶體空間在q_sort是禁止的，所以這方法是不可行，最後我直接在傳入的佇列上進行操作。

實現的概念是這樣的，得分成幾個部分來討論 :
那麼如何分辨一個佇列是從哪開始到哪結束？
雖然一開始，每個子佇列都只有一個元素，所以只要用兩個list_head類型的指標指向兩個元素，再補上head （為了符合merge_two的輸入）進行合併的操作即可，但合併後會變成兩個，所以得知道開頭和結尾，否則無法知道head要如何連結。

假設已經合併完一輪，現在每個子佇列的元素最多為2的情況，現在要開始新一輪的合併，把要合併的兩個佇列分成左邊和右邊，分別稱為L和R，那麼L的開頭是現在會是佇列中的第一個元素，所以就標記成l_s。

如何計算佇列結尾的位置？
這時得想到佇列的元素數量變化為1、2、4、8、...，所以使用

for (int size = 1; size < n; size *= 2)

來計算每一輪子佇列元素的數量size，那麼它不可能會超過佇列的大小n。最後透過移動指標並計數的方式，就能找到L的結尾並標記成l_e，接著R的開頭會是l_e的下一個，R的結尾的定位方式也是一樣，最後會得到 :

         [  L  ]     [  R  ]
head <-> b <-> c <-> d <-> a <-> e <-> head
        [l_s] [l_e] [r_s] [r_e]

實際的操作方式
透過一個指標c來表示當前位置，等c走訪完一個整個佇列（n個元素）就完成了一輪的合併，下一輪合併開始c又會回到最前面，直到size >= n後就完成了，細節如下 :

一開始c會在第一個元素(head->next)的位置 :

size = 1
        [c]
head <-> b <-> c <-> d <-> a <-> e <-> head

一開始先判斷c是不是head，如果是的話代表沒有元素可以被當成佇列，所以結束這輪for迴圈；不是的話，透過size計數並移動c找到L跟R的開頭和結尾 :

size = 1
                    [c]
head <-> b <-> c <-> d <-> a <-> e <-> head
       [l_s] [r_s]
       [l_e] [r_e]

雖然透過 2. 一開始的檢查，可以知道至少有一個元素，但在合併前要先檢查r_s的位置，因為可以分成三種情況 :
a. L的元素不足，所以r_s會停留在head上。
b. R沒有元素，所以r_s會是head。
C. R的元素不足，但必定至少有一個所以可以跟L合併。
所以檢查，如果r_s是head的話，就不進行合併。
如果可合併的話，為了合併，先把每個子佇列補上head。

size = 1
                    [c]
head <->            <-> d <-> a <-> e <-> head
L: head <-> b <-> head
R: head <-> c <-> head

合併L跟R，由於merge_two會把結果合併到第一個傳入的佇列，所以得到 :

size = 1
                    [c]
head <->            <-> d <-> a <-> e <-> head
L: head <-> b <-> c <-> head

此時會發現其實在合併前要先暫存l_s的前一個位置，這樣在合併完後才能透過它和c把這個合併完的L插入佇列當中。執行L插入佇列當中。
現在已合併一組了，接著得判斷c是不是head，如果是的話代表這輪的合併已經結束了；不是的話，表示還有後續，那麼又會回到 2. ，直到這輪結束，重複好幾輪直到size >= n後停止。

其實在寫這個合併排序的過程中會擔心merge_two會不會不適用，但後面會發現，佇列有head是比較好的方式，這樣就不需要傳入佇列的開頭和結尾的位置。

`q_ascend & q_descend`

Commit
Commit 精簡程式

q_ascend和q_descend核心概念是一樣的，所以先講如何實現q_descend。

以q_descend來說，要求元素不可小於後面任一元素，所以得把不符合的部分刪除後，會得到一個遞減的佇列。那麼我的想法是 :

一開始先把指標t, a, b分別指向最後方三個元素 :

              [t]   [a]   [b]
head <-> 3 <-> 2 <-> 1 <-> 4 <-> head

固定t, a, b的相對位置，a和b開始不斷的比較把不符合的刪除，這樣一來可以把b前方比b小的刪掉直到b前方的a比它大後，接著所有指標往前移，接重複以上的動作後就會得到一個遞減的佇列，如以下示範 :

比較a和b的元素後可分成兩種情況：
a. a的沒比b的小 : 那麼t, a, b往前移即可。
b. a的比b的小 : 因為1比4小，所以a所指向的元素會被刪除 :

              [t]   [b]
head <-> 3 <-> 2 <-> 4 <-> head

接著透過t把a指向t指向的元素，然後t往前 :

        [t]   [a]   [b]
head <-> 3 <-> 2 <-> 4 <-> head

重複 1 和 2 直到a是head後停止後完成。

那麼q_ascend的話就會是，元素不可比的前方任一元素還小，否則刪除，那麼我們就把剛才的t, a, b改成a, b, t，同樣a與b不斷比較，但這次刪除的會是b，接著的操作核心概念都與q_descend相同，所以最後會得到一個遞增的佇列。

`q_merge`

Commit
Commit 把「合併兩個佇列」獨立成一個函式
Commit 精簡程式

q_merge會把所有佇列合併且排序後放到第一個佇列，還有就是合併前的的佇列必須是排序好的。雖然有很多個佇列要合併，但可以先考慮核心「兩個佇列如何合併」:

假設有兩個已排序佇列a和b :

a: [1 2 2 3]
b: [2 3 4 5]

比較兩佇列的第一個元素，並把較小的元素放到另一個佇列c當中 :

a: [  2 2 3]
b: [2 3 4 5]
c: [1]

重複 2 最後就能得到一個遞增的佇列。

合併的過程的概念是很直覺的，但實際操作過程中會有許多指標的操作 :

比如要暫存佇列的head，這樣一來在走訪一個佇列的過程中可以判斷一個佇列是不是空的了，如果是空的了就直接把c的佇列的尾端指向另一個佇列即可。
由於要搬到第一個佇列，所以其實c會是佇列a的head，還有剛才 1 的情況，如果另一個非空的佇列尾端不是第一個佇列的head的話需要改成第一個佇列的head。
把佇列a或b中的元素搬到c的話，需要透過 3 個指標，比如說x, y, z:
a. x和y的元素比較完後，把z指向較小的那個。
b. z和x都往下個元素移動
c. 重複 a 和 b 直到一個佇列為空

      [x]
a: [ha 1 2 2 3 ha]
      [y]
b: [hb 2 3 4 5 hb]
   [z]
c: [ha]

比較完後的移動 :

       [z][x]
a: [ha  1  2 2 3 ha]
       [y]
b: [hb  2 3 4 5 hb]
      [z]
c: [ha 1]

NULL-queue :
在我實現了q_merge後，發現 :
若我對兩個佇列進行合併後，接著釋放合併好的佇列，會出現有block沒有被釋放的錯誤訊息，此時我就在想，函式定義說會對queue_contex_t和它的q在外部釋放記憶體，所以我是不需要進行釋放的動作，那麼會不會是在合併完後把佇列變成「NULL-queue」這個動作造成的，NULL-queue 的定義我是依照2025 年 Linux 核心設計課程作業 —— lab0 (A)所提到的，所以我把第一個佇列以外的q指向NULL，把它指向NULL那它的佇列位置head位置不就遺失了嗎？要怎麼在外部進行釋放，所以我抱著此疑問去看其他同學們是如何做的，後來我看到 ginsengAttack 同學的開發紀錄後才發現其實是要把它變成「empty queue」，修改完後測試就通過了。

Reference

C 語言入門
2024 homework1 開發紀錄
- Dennis40816 開紀錄撰寫方式
- ginsengAttack q_merge的NULL-queue處理方式
排序演算法合併排序概念

2025q1 Homework1 (lab0)

開發環境

開發過程

q_size

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort

q_ascend & q_descend

q_merge

Reference

Read more

2025q1 Homework5 (assessment)

2025q1 Homework3

2025q1 Homework2 (quiz1+2)

2025q1 Homework4 (quiz3+4)

`q_size`

`q_new`

`q_free`

`q_insert_head`

`q_insert_tail`

`q_remove_head`

`q_remove_tail`

`q_delete_mid`

`q_delete_dup`

`q_swap`

`q_reverse`

`q_reverseK`

`q_sort`

`q_ascend & q_descend`

`q_merge`