# 2025q1 Homework1 (lab0)
contributed by < [`reberu6`](https://github.com/reberu6?tab=repositories) >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ 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](https://github.com/reberu6/lab0-c/commit/263224155be1843d71daa685b7a2c2015fd22b0b)
此函式回傳佇列所包含的節點數量。
實作上使用了`list_for_each()`巨集，這本質上是一個走訪每一個節點的 for 迴圈，然後每走訪一個節點就對計數器加`1`即可計算節點的數量。若給定的佇列開頭指標不合法或是給定一空佇列，直接回傳 0 即可。
### `q_new`
>[Commit](https://github.com/reberu6/lab0-c/commit/771381c16d7d391f5c9898aa7d4f35ef89752dc8)
此函式會創建一個空的佇列並初始化成`next`和`prev`指標都指向自己。
在`queue.h`給定的函式定義中，將`struct list_head`的指標作為回傳值，可得知此處需要透過`malloc`來分配`struct list_head`這個結構所需之記憶體空間（此結構大小則透過`sizeof()`取得），才得以在函式結束時仍保留記憶體資訊。分配記憶體也有可能出現失敗的情況，所以在分配完畢時就判斷如果新建的`new_list`為空則代表分配失敗則函式回傳`NULL`。
### `q_free`
>[Commit](https://github.com/reberu6/lab0-c/commit/88f22be6e797d1a79ff3eb5150fa1a4bfdfb3b67)
此函式傳入佇列的位址後就會把整個佇列從記憶體中釋放。
**處理`head`為`NULL`:**
如果傳入的佇列的`head`是`NULL`的話就代表佇列本身就不存在而就不需要額外去釋放記憶體，所以就在程式的一開始就判斷。
**透過走訪每個節點來進行記憶體的釋放：**
原本想說只要使用`list_head`類型的指標從頭到尾走訪每個節點並使用`free`來釋放記憶就可以了，但是佇列有兩種類型的節點一種是`list_head`另一種則是`element_t`，所以無法直接操作`element_t`類型的節點。後來我想說`head->next`會指向`element_t`類型的節點，那直接把`head->next`指向的位置直接給`element_t *`類型的`current`就可以直接操作，而後面的操作就是分成兩種狀況 :
1. 如果`head`下一個節點是自己的話代表沒有`element_t`類型的節點，所以就直接把`head`給釋放。
2. 若有`element_t`類型的節點，先暫存`current`下一個節點`next`等我們釋放完`element_t`再把`current`移過去，所以一開始就先釋放節點的`value`接著釋放節點本身就可以了，最後往下個節點移動。
3. 重複 2 以上直到`current`是`head`節點，也就是把`element_t`類型的節點都已是放完畢。
```c=
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 都出現了指標類型不相容的錯誤，後來我看了[指標的介紹](https://youtu.be/KXaoMKbRLKc?si=1vFNC8D3qjQWBD6i)發現我之前想的不對，不能直接把
```c
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`的位置，例如 :
```c
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`的位置。具體的計算如下：
```c
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](https://github.com/reberu6/lab0-c/commit/39716f785bdbf2c377d15472dc146d1eaf6ea404)
>[Commit](https://github.com/reberu6/lab0-c/commit/832dd1d8747d1bfa1de74d731d869b387e85dcb4) 修正字串長度超過 4 個字元時記憶體釋放錯誤
>[Commit](https://github.com/reberu6/lab0-c/commit/1aba5305aa2865e900bcc8407eff254c1466f7ec) 修正指標更新順序，確保正確連結
>[Commit](https://github.com/reberu6/lab0-c/commit/fab2bacf29ce0d26086951e203342d7f95135fde) 精簡程式
此函式會在佇列的最前面插入一個元素 (element)。
**佇列不存在 :**
一開始就先判斷佇列是否存在比較好，避免後面的操作。
**分配失敗 :**
這跟`q_new`的檢查一樣，記憶體不一定分配就會成功。這裡要注意的是如果分配失敗的話，記得檢查前面有沒有分配的操作，有的話在這裡分配失敗需要釋放掉它。
**插入最前面 :**
插入最前面只需修改 4 個指標，比如說一開始是 :
```
-> -> ->
head a ... head
<- <- <-
```
然後插入一元素`b`
1. 在修改`head->next`之前，先把新增的元素`b`指向原本`head->next`所指的地方，比如說`a`，避免遺失`a`的位置。
2. 接著把`head->next`指向新元素`b`。
完成後 :
```
head -> b -> a -> ... -> head
```
但向左的連結`prev`還是 :
```
head <- a <- ... <- head
```
所以需要以下操作 :
1. 在修改`a`指向`b`，之前先把`b`指向`a`所指的地方，避免遺失`head`位置。
2. 接著把`a`指向`b`
完成後 :
```
head <- b <- a <- head
```
**字串處理 :**
基於要求，需要把字串存入一塊新的記憶體空間。
1. 所以我們得知道字串的長度來分配記憶體。可以靠字串最後一個字元是`\0`的特性來計算，只需透過`while`迴圈來進行迭代計算長度。
2. 接著就可分配空間。
3. 透過指標操作一個個的把字元複製到新的記憶體中，我們可以透過剛才計算出的長度來決定`for`迴圈要迭代幾次。
**當元素的`value`超過 4 個字元的時候出現重複釋放的問題 :**
我在想為何是 4 這個數字，因為程式中根本沒有直接使用到接近 4 的常數，後來才發現應該要直接分配字串長度加上`\0`的長度`len`，而不需要`sizeof`去計算，因為這樣反而是計算`len`這個變數型別的大小，`len`是`int`型別，所以之前每次分配記憶時都只有分配 4 bytes，這就導致了只要插入 4 個字元或以上時就會出現記憶體錯誤的問題。
```diff
--- 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`來向右移動，而向右的連結都沒錯的話當然也可以正常釋放了。
```diff
- head->next = &new->list;
head->next->prev = &new->list;
+ head->next = &new->list;
return true;
}
```
### `q_insert_tail`
> [Commit](https://github.com/reberu6/lab0-c/commit/1aba5305aa2865e900bcc8407eff254c1466f7ec)
>[Commit](https://github.com/reberu6/lab0-c/commit/fab2bacf29ce0d26086951e203342d7f95135fde) 精簡程式
程式基本上跟`q_insert_head`一樣，所以只須想出如何插入在最後面。
**插入最後面 :**
同樣只需修改 4 個指標，比如說一開始是 :
```
-> -> ->
head ... a head
<- <- <-
```
然後插入一元素`b`在尾端，由於需要透過`head->prev`存取`a`，所以這個指標最後改 :
1. 把`b`直接指向`head`。
2. 透過修改`head->prev->next`讓`a`指向`b`。
完成後 :
```
head -> ... -> a -> b -> head
```
但向左的連結還是 :
```
head <- ... <- a <- head
```
所以需要以下操作 :
1. 把`b`指向`a`（也就是`head->prev`所指的位置）。
2. 修改`head->prev`指向`b`。
完成後，向左的連結就完成了 :
```
head <- ... <- a <- b <- head
```
### `q_remove_head`
> [Commit](https://github.com/reberu6/lab0-c/commit/d2bdbc552a5b60e8874fbfec77ca733f611d6ae9)
> [Commit](https://github.com/reberu6/lab0-c/commit/b11b41a1ec95ff1e0db70ec428d651990827bc61) 新增拷貝字串時的邊界條件
>[Commit](https://github.com/reberu6/lab0-c/commit/fab2bacf29ce0d26086951e203342d7f95135fde) 精簡程式
此函式會移除最前面的元素。
**移除最前面的元素 :**
比如說一開始是 :
```
-> -> -> ->
head b a ... head
<- <- <- <-
```
要將`b`移除的話，要注意`head->next`和`head->next->next`的變更順序是較低的，因為分別透過它們存取`b`和`a`。操作順序如以下 :
1. 將`a`指向`head`。
2. 因為要修改`head->next`，所以透過`tmp`將`b`的位置暫存。
3. 將`head->next`指向`a`。
4. 將`b`的`next`和`prev`指向`NULL`。
**若傳入的`sp`非空且成功移除`b` :**
由於`bufsize`的大小限制且最後得放`\0`，最多只能複製`bufsize - 1`個字元，所以透過`for`迴圈複製前`bufsize - 1`個字元到`sp`。
### `q_remove_tail`
>[Commit](https://github.com/reberu6/lab0-c/commit/cf386fea5d4499fdd5729944eedc421cbd816e92)
>[Commit](https://github.com/reberu6/lab0-c/commit/b11b41a1ec95ff1e0db70ec428d651990827bc61) 新增拷貝字串時的邊界條件
>[Commit](https://github.com/reberu6/lab0-c/commit/fab2bacf29ce0d26086951e203342d7f95135fde) 精簡程式
**移除最後面的元素 :**
比如說一開始是 :
```
-> -> -> ->
head ... a b head
<- <- <- <-
```
要移除`b`同樣也得注意操作順序 :
1. 將`a`指向`head`。
2. 透過`tmp`暫存`b`的位置。
3. 將`head`指向`a`。
4. 將`b`的`next`和`prev`指向`NULL`。
### `q_delete_mid`
>[Commit](https://github.com/reberu6/lab0-c/commit/14358950dcf35fa975a0b8b38db3751f5cf6d943)
>[Commit](https://github.com/reberu6/lab0-c/commit/f79389830d861ad8d090545a6a77643914b873b6) 使用快慢指標技巧找到中間節點
>[Commit](https://github.com/reberu6/lab0-c/commit/fab2bacf29ce0d26086951e203342d7f95135fde) 精簡程式
一開始想到的方法是先計算出總共有幾個節點`n`，接著計算出中間節點的位置為第$\lfloor{n/2}\rfloor$個 （從 0 開始計算），接著透過`for`迴圈迭代變更指標`current`的位置到中間節點的前一個 （後來在使用快慢指標時發現其實直接移到中間節點也可以，因為雙向鏈結所以進行指標更新時`b`不會遺失`a`和`c`的位置），進行釋放和指標更新。
假如一開始只看向右的連結的話如下：
```
head -> a -> b -> c -> head
```
那透過走訪每個節點可以算出佇列的長度為 3 ，接著要走到`a`然後釋放`b`，但如果就這樣釋放`b`的話會導致遺失`c`的位置，所以順序如下：
1. $\lfloor{3/2}\rfloor=1$，`a`的索引是`0`，所以中間節點是`b`。
2. 走到`b`的前一節點`a`。
3. 把`b`的下一個節點`c`暫存。
4. 釋放`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`就可以了。
**快慢指標**
參考[分析「快慢指標」](https://hackmd.io/@sysprog/ry8NwAMvT)實現找到中間的點，也了解雖然在演算法上的複雜度都是一樣的，但是根據操作的方式不同讓時間局部性產生差異，這需要了解硬體架構才有可能意識到這點。
### `q_delete_dup`
>[Commit](https://github.com/reberu6/lab0-c/commit/8e549223b0b03ed1fe73290ed1bdc1c9e9699533)
刪除具有重複的字串的節點，就需要比對的動作，目前是想到用兩個指標來完成 :
1. 先用一指標`a`指向要被比較的對象，另一指標`b`則指向比較的對象，如以下示意 :
```
[a]=>=>=>
head <-> cat <-> dog <-> cat <-> pig <-> head
[b]=>=>=>
```
2. 接著就是固定`a`，然後`b`不斷向右並與`a`的字串進行比對，有相同就是刪除元素並更新指標。
3. 等`b`下個是尾端後，`a`就往下個元素移動。
4. 重複 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](https://github.com/reberu6/lab0-c/commit/42ea75c45f2b8065d446da6e43023a43feb7f4f8)
`q_swap`在實作上只需要修改 6 個指標就能完成兩個點的位置交換。
以下為示意：
```
[c]
head <-> a <-> b <-> head
```
需要清楚的知道更改指標的順序，這樣一來就可以只透過一個指標修改。 先把`c`指向佇列中的第一個元素`a`，接下來`c->prev`跟`c->next`會比較晚更改，這是分別為了操作`head`和`b`:
1. 透過`c->prev`把`head->next`指向`b`。
2. 透過`c->next`把`b->prev`指向`head`。
```
[c]
------>
head <- a -> b <-> head
<------
```
接下來就可修改`c->prev`跟`c->next`:
1. 把`c->prev`指向`b`，也就是`b`在`a`前。
2. 把`c->next`指向`b->next`，也就是`head`前。
```
[c]
------>
head <-> b <- a -> head
<------
```
既然知道`c-prev`是`b`和`c->next`是`head`最後再更新一些指標就完成了：
1. 把`b->next`指向`a`。
2. 把`head->prev`指向`a`。
最後如以下：
```
[c]
head <-> b <-> a <-> head
```
接著就是想元素有兩個以上的時候要怎麼處裡可以重複以上的動作，那麼經過以上的操作，可以知道`c`只要指向要交換的`a`與`b`相對位置中的`a`就能夠進行操作的話，接著只需要檢查後面有沒有元素可操作「交換」，有的話把`c`移到適當的位置即可。
假如新增兩元素`x`和`y`:
```
[c]
head <-> b <-> a <-> x <-> y <-> head
```
1. 如果`a`的下個元素如果是`head`代表沒其他元素則結束函式，否則`c`往下個元素移動。所以如果最後有成功移動的話則如以下：
```
[c]
head <-> b <-> a <-> x <-> y <-> head
```
2. 因為至少要有兩個元素才能交換，所以需再檢查一次`c`的下個元素是不是`head`，如果不是的話代表有兩個元素足以進行「交換」，這時把此條件當作`while`的判斷條件，這是因為`c`已經到了跟一開始`a`和`b`相對位置中的`a`，所以透過此判斷可以決定`while`的內的交換過程要不要執行。
### `q_reverse`
>[Commit](https://github.com/reberu6/lab0-c/commit/5650b26158838732fe0d445e7e19e6c6f805a276)
雖然`q_reverse`和`q_swap`在只有兩個元素時的效果一樣，但其實操作的過程不同，`q_swap`在操作的時候會把`a`放到`b`的後面，而`q_reverse`則是讓所有的`next`變成`prev`和`prev`變成`next`，達成第一個變最後一個，最後一個變第一個。目前是採用兩個指標達成`q_reverse`:
1. 先用一指標`a`指向要被修改的對象，另一指標`b`則指向暫存位置的對象，如以下示意 :
```
[a] [b]
head <-> x <-> y <-> head
```
2. 因為是反轉所以`a`的前一個`head`會變成`a`的下一個，修改`a->next`為`a->prev`所指。
3. 接著`a`的前一個會是`b`，所以修改`a->prev`為`b`（剛才暫存`b`所以不怕 2 修改了`a->next`）。
結果如下，上方的箭頭是`next`，下方則是`prev`:
```
[a] [b]
<--
head -> x <- y <-> head
-->
```
4. 判斷`b`是否在`head`的位置，如果不是`a`和`b`往下移動。
5. 重複 2~4 直到`b`在`head`的位置則結束後可完成所有指標的修改。
```
[a] [b]
head <-> x <-> y <-> head
```
### `q_reverseK`
>[Commit](https://github.com/reberu6/lab0-c/commit/d70b7a4892a38d949396c4beb1913251c595b7d8)
>[Commit](https://github.com/reberu6/lab0-c/commit/fab2bacf29ce0d26086951e203342d7f95135fde) 精簡程式
雖然`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`，而是前一組的尾端，此時又會有兩種可能 :
1. `a`所在的組別是第一組的話，就得把`a->prev`設成`head`。
2. 否則把`a->prev`指向前一組的尾端，所以得暫存前一組的尾端，而前一組的尾端暫存的時機就是在反轉那組時的頭部。
能反轉一組之後，接著就只需要算出要反轉幾組後透過`for`迴圈迭代反轉每一組。
**元素不足以組成一組 :**
那如果有些元素不足以組成一組時不須進行反轉，所以就把剛才暫存的尾端指向剩餘的部分的開頭即可（也就是`b`）。
### `q_sort`
>[Commit](https://github.com/reberu6/lab0-c/commit/803fa573239a19c8b46b530c8c64f267efe36f26) Bubble sort
>[Commit](https://github.com/reberu6/lab0-c/commit/8b6bcd68a781889b8b33448b53c245a0b2596ad7) Merge sort
在想如何排序的時候，我是用暴力法去排序，排完後複雜度是 $O(n^2)$ 還沒有達到`make test`要求的 $O(n\log n)$ ，但想不出來，所以只好查 google 看還有甚麼排序的辦法時才發現我用的是 Bubble Sort 。
**暴力法 (Bubble Sort) :**
最一開始的想法就是：
1. 假設是遞增排序的話，那麼最大的一定要位於最後面。
2. 所以若有一個較大的數字在佇列的前方的話，想往後方要透過不斷比較然後把它往後移動，比如`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`是一樣的。
3. 等到最大的數字放在佇列的最後方後，那麼未排好的部分只剩下前面的`n-1`個元素，所以就再對前`n-1`元素進行排序，透過`head`可以把`a`和`b`又放在最前方，接著就是迭代直到所有的元素排好 :
```
[a] [b]
head <-> 3 <-> 2 <-> 1 <-> 4 <-> head
```
4. 這裡比較是用數字來舉例，但實際上會是字串，所以這個比較的動作就透過`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、...`，所以使用
```c
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`後就完成了，細節如下 :
1. 一開始`c`會在第一個元素(`head->next`)的位置 :
```
size = 1
[c]
head <-> b <-> c <-> d <-> a <-> e <-> head
```
2. 一開始先判斷`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]
```
3. 雖然透過 2. 一開始的檢查，可以知道至少有一個元素，但在合併前要先檢查`r_s`的位置，因為可以分成三種情況 :
a. `L`的元素不足，所以`r_s`會停留在`head`上。
b. `R`沒有元素，所以`r_s`會是`head`。
C. `R`的元素不足，但必定至少有一個所以可以跟`L`合併。
所以檢查，如果`r_s`是`head`的話，就不進行合併。
4. 如果可合併的話，為了合併，先把每個子佇列補上`head`。
```
size = 1
[c]
head <-> <-> d <-> a <-> e <-> head
L: head <-> b <-> head
R: head <-> c <-> head
```
6. 合併`L`跟`R`，由於`merge_two`會把結果合併到第一個傳入的佇列，所以得到 :
```
size = 1
[c]
head <-> <-> d <-> a <-> e <-> head
L: head <-> b <-> c <-> head
```
6. 此時會發現其實在合併前要先暫存`l_s`的前一個位置，這樣在合併完後才能透過它和`c`把這個合併完的`L`插入佇列當中。執行`L`插入佇列當中。
7. 現在已合併一組了，接著得判斷`c`是不是`head`，如果是的話代表這輪的合併已經結束了；不是的話，表示還有後續，那麼又會回到 2. ，直到這輪結束，重複好幾輪直到`size >= n`後停止。
其實在寫這個合併排序的過程中會擔心`merge_two`會不會不適用，但後面會發現，佇列有`head`是比較好的方式，這樣就不需要傳入佇列的開頭和結尾的位置。
### `q_ascend & q_descend`
>[Commit](https://github.com/reberu6/lab0-c/commit/d511ceaf015035223445a48652e7db4e75d86881)
>[Commit](https://github.com/reberu6/lab0-c/commit/fab2bacf29ce0d26086951e203342d7f95135fde) 精簡程式
`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`比它大後，接著所有指標往前移，接重複以上的動作後就會得到一個遞減的佇列，如以下示範 :
1. 比較`a`和`b`的元素後可分成兩種情況：
a. **`a`的沒比`b`的小 :** 那麼`t, a, b`往前移即可。
b. **`a`的比`b`的小 :** 因為`1`比`4`小，所以`a`所指向的元素會被刪除 :
```
[t] [b]
head <-> 3 <-> 2 <-> 4 <-> head
```
2. 接著透過`t`把`a`指向`t`指向的元素，然後`t`往前 :
```
[t] [a] [b]
head <-> 3 <-> 2 <-> 4 <-> head
```
3. 重複 1 和 2 直到`a`是`head`後停止後完成。
那麼`q_ascend`的話就會是，元素不可比的前方任一元素還小，否則刪除，那麼我們就把剛才的`t, a, b`改成`a, b, t`，同樣`a`與`b`不斷比較，但這次刪除的會是`b`，接著的操作核心概念都與`q_descend`相同，所以最後會得到一個遞增的佇列。
### `q_merge`
>[Commit](https://github.com/reberu6/lab0-c/commit/697e89550755f5e32a4beba31456da21927a7ff2)
>[Commit](https://github.com/reberu6/lab0-c/commit/0d6521e2e62ffaf0f3d60e6377e3a821facebf2b) 把「合併兩個佇列」獨立成一個函式
>[Commit](https://github.com/reberu6/lab0-c/commit/fab2bacf29ce0d26086951e203342d7f95135fde) 精簡程式
`q_merge`會把所有佇列合併且排序後放到第一個佇列，還有就是合併前的的佇列必須是排序好的。雖然有很多個佇列要合併，但可以先考慮核心「兩個佇列如何合併」:
1. 假設有兩個已排序佇列`a`和`b` :
```
a: [1 2 2 3]
b: [2 3 4 5]
```
2. 比較兩佇列的第一個元素，並把較小的元素放到另一個佇列`c`當中 :
```
a: [ 2 2 3]
b: [2 3 4 5]
c: [1]
```
3. 重複 2 最後就能得到一個遞增的佇列。
合併的過程的概念是很直覺的，但實際操作過程中會有許多指標的操作 :
1. 比如要暫存佇列的`head`，這樣一來在走訪一個佇列的過程中可以判斷一個佇列是不是空的了，如果是空的了就直接把`c`的佇列的尾端指向另一個佇列即可。
2. 由於要搬到第一個佇列，所以其實`c`會是佇列`a`的`head`，還有剛才 1 的情況，如果另一個非空的佇列尾端不是第一個佇列的`head`的話需要改成第一個佇列的`head`。
3. 把佇列`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)](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a)所提到的，所以我把第一個佇列以外的`q`指向`NULL`，把它指向`NULL`那它的佇列位置`head`位置不就遺失了嗎？要怎麼在外部進行釋放，所以我抱著此疑問去看其他同學們是如何做的，後來我看到 [ginsengAttack](https://hackmd.io/2Ug8ThcdSN-nfJ3N7P3_sA?view#q_ascend) 同學的開發紀錄後才發現其實是要把它變成「empty queue」，修改完後測試就通過了。
## Reference
* [C 語言入門](https://feis.studio/c)
* [2025 homework1 開發紀錄](https://hackmd.io/@sysprog/linux2025-homework1)
* [Dennis40816](https://hackmd.io/@dennis40816/linux2025-homework1#q_descend) 開紀錄撰寫方式
* [ginsengAttack](https://hackmd.io/2Ug8ThcdSN-nfJ3N7P3_sA?view#q_ascend) `q_merge`的`NULL-queue`處理方式
* [排序演算法](https://hackmd.io/@coherent17/Sy79MIyju) 合併排序概念
Sign in with Wallet
Connect another wallet