2025q1 Homework1 (lab0)

contributed by <DrXiao>

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [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):                   24
On-line CPU(s) list:      0-23
Vendor ID:                GenuineIntel
Model name:               13th Gen Intel(R) Core(TM) i7-13700F
CPU family:               6
Model:                    183
Thread(s) per core:       2
Core(s) per socket:       16
Socket(s):                1
Stepping:                 1
CPU(s) scaling MHz:       23%
CPU max MHz:              5200.0000
CPU min MHz:              800.0000
BogoMIPS:                 4224.00  
L1d:                      640 KiB (16 instances)
L1i:                      768 KiB (16 instances)
L2:                       24 MiB (10 instances)
L3:                       30 MiB (1 instance)                     
NUMA node(s):           1
NUMA node0 CPU(s):      0-23

* GitHub 檔案庫：[DrXiao/lab0-c](https://github.com/DrXiao/lab0-c)

不用在此提及 repository 資訊，你該聚焦在細節。

注意 markdown 的項目編號，也就是內文該用 ## 和 ###，避免過深的縮排

開發前處理

在開發 labo-c 時，因為 sysprog21/lab0-c 本身後來又有不少 pull request 被合併，故每當有新的修改，會隨時同步到自己的檔案庫後，才繼續開發下去。

為所有佇列操作介面提供初步實作

對應到 commit aea1a33

在 GitHub 上產生 lab0-c 的檔案庫後，第一個想法是先為所有的佇列操作撰寫可以運作的程式碼，先了解每個操作函式應該要達成什麼目的，爾後尋找改進的機會，接著會一一說明目前的實作原理

`q_new()`

以 lab0-c 設計的佇列操作介面來說，會設想開發者會以 Linux 核心風格的 list_head 結構體，以該結構體的指標去維護整個佇列，因此 q_new() 的目的即是適當地建立一空佇列，動態配置記憶體後，將佇列本身的指標作為該函式的回傳值，爾後讓開發者以其他介面操作佇列。

故這裡的步驟很簡單：

動態配置一個 list_head 的物件，協助初始化該物件的指標後，就回傳該物件的記憶體位置。
但若遭遇動態配置失敗，則回傳 NULL。（爾後使用佇列的開發者要自行注意對應的處理）

因此目前 queue.c 中，即可見到上面步驟的實作

`q_free()`

因為是以動態配置記憶體的方式，提供開發者使用佇列，自然也要有對應的釋放記憶體的操作，讓開發者釋放不再使用的佇列。

而這裡做的事情，自然是逐一走訪一個佇列中仍存在的節點，並對每一個節點進行記憶體的釋放，最後再釋放 q_new() 而來的 list_head 物件（即佇列的開頭指標）。

而這裡的實作步驟如下：

以 list_for_each_safe() 巨集，配合兩個 list_head 指標，分別命名為 curr 、 safe，走訪所有節點
使用 element_t 的指標、curr 指標再加上 list_entry() 巨集，即可取得節點的開頭位址，爾後
- 對每一個節點進行移除操作，將前一節點、下一節點互相鏈結起來
- 先釋放節點維護的資料，即 element_t 的 value 的記憶體，再釋放節點本身的記憶體
走訪完所有節點以後，最後釋放 head

~~warning~~

不要濫用 warning 標示

但這裡其實最初實作時，是使用 list_for_each_entry_safe 處理，但在要 git commit 時，Git hook（或是說 cppcheck ）會產生下面的訊息：

Following files need to be cleaned up:
queue.c
Running static analysis...
queue.c:35:5: style: Label 'int' is not used. [unusedLabel]
    list_for_each_entry_safe (curr_elem, safe_elem, head, list) {
    ^
queue.c:272:5: style: Label 'int' is not used. [unusedLabel]
    list_for_each_entry (curr_elem, head, list) {
    ^
queue.c:303:5: style: Label 'int' is not used. [unusedLabel]
    list_for_each_entry (curr_elem, head, list) {
    ^

Fail to pass static analysis.

似乎是 cppcheck 認為我定義了一個名為 int 的 jump label（可用 goto 進行無條件跳躍），但沒有被使用從而輸出這道訊息，類似的情形也發生在 list_for_each_entry 上。

目前這裡不確定是我當時候使用上真的有問題，還是 Git hook 撰寫的規則有潛在瑕疵，或許後續再擇時來釐清。

`q_insert_head()` 、 `q_insert_tail()`

這兩個函式都是為佇列增加節點的操作，共通點都是會給定「佇列的開頭指標」、「新節點的資料」，唯獨差別在於前者要將新節點安插在佇列的第一個位置，而後者則要將新節點插入在佇列的最尾端。

故這裡的步驟如下：

先動態配置 element_t 物件
再利用 element_t 的 value 指標，配置記憶體。
- 因為此處佇列每一節點的資料即是一道字串，故使用 strdup()，直接完成動態配置及複製字串的操作
將新節點安插至適當位置後，便回傳 true
- 以 q_insert_head() 來說，就要使用 list_add()，即可將節點插入在第一個位置
- 相對地，q_insert_tail() 就是使用 list_add_tail()，將節點放在最後一個位置
若遭遇動態配置失敗，釋放已配置的記憶體後，就回傳 false

`q_remove_head()` 、 `q_remove_tail()`

類似於前面討論增加節點，這兩個函式都是移除節點，差別僅在於要操作的佇列的開頭節點還是尾端的節點。

然而，以這兩個函式的設計來說，若開發者有給定合法的字元陣列及其大小的話，就要將移除節點的資料，複製到該字元陣列裡面。最後移除成功後，要將所移除的節點的記憶體位址作為回傳值，回傳給呼叫者

處理步驟：

若佇列開頭指標是 NULL，或是佇列本身是空佇列，就直接回傳 NULL
若有節點可移除，就利用 element_t 指標、佇列的開頭指標、list_entry()，取得某個節點的開頭位址
- q_remove_head 要使用 head->next ，配合巨集來取得第一個節點的開頭位址
- q_remove_tail 則要用 head->prev ，配合巨集取得最後一個節點的開頭位址
若有給定合法的字元指標（sp 不為 NULL），就利用 strncpy() 、 bufsize ，將移除節點的資料，複製到 sp 裡。
最後利用 list_del() 斷開移除節點的鏈結，並回傳移除節點的開頭位址
- q_remove_head 使用 list_del() 時要帶入 head->next。
- q_remove_tail 則帶入 head->prev。

不過目前的實作存在一些缺失，導致 trace-07-string 的測試項目失敗，後續會釐清並改進

`q_size()`

這個函式是用來計算並回傳佇列所包含的節點數量，實作上只需要透過一個 list_head 指標一個計數器，搭配 list_for_each() 巨集，逐一走訪每一個節點並對計數器的值加 1 即可。

而當然地，若給定的佇列開頭指標不合法或是給定一空佇列，直接回傳 0 即可。

`q_delete_mid()`

這個函式的用意是，刪除佇列的正中間的那個節點，這裡以兩個例子舉例

包含奇數個節點的佇列

若給定一個奇數個節點（假設數量是 $n$ ）的佇列，要刪除的就是第 $\frac{n + 1}{2}$ 個節點。

假設 $n$ 是 5 為例，要刪除的就是第 3 個節點（正中間的節點）
包含偶數個節點的佇列

給定一個奇數個節點（假設數量是 $n$ ）的佇列，要刪除的就是第 $\frac{n}{2}$ 個節點。

假設 $n$ 是 4 為例，要刪除的就是第 2 個節點。因為偶數的關係，對於第 2 與第 3 個節點來說，都可說是「正中間」，但此處定義要刪除的是最靠近 head 的那個中間節點

因為佇列在 q_new() 時，僅使用 list_head 指標維護整個佇列，除此之外，不會儲存其他資訊。因此最直接的作法，可以先走訪整個陣列一次，得知佇列節點的數量後，再走訪到正中間的節點並移除。

不過在指標操作上，可以使用快慢指標的技巧，準備兩個 list_head，分別命名為 slow、fast，都先指向第一個節點，爾後利用迴圈走訪佇列時：

slow: 每次走訪一個節點後，前往下一個節點，即 slow->next
fast: 每次走訪一個節點後，前往下下一個節點，即 fast->next->next

這裡將兩個指標的移動以走路的步數來比喻，因為每次移動時，fast 會比 slow 還要快一步，故當 slow 走了 $n$ 步時，fast 就走了 $2 n$ 步。基於這樣的特性也就代表，若 fast 已經抵達佇列的尾端節點，slow 剛好走到整個佇列的一半，也就是正中間的節點。如此，透過快慢指標，只要用一個迴圈讓兩個指標走訪，fast 走訪完整個佇列的那一刻，slow 所指向的節點就是正中間的節點。

因此在 q_delete_mid() 的實作裡，就使用前述的兩個指標、一個 element_t 的指標（del_elem），在 fast 走訪完佇列後，讓 del_elem 利用 list_entry() 與 slow，取得正中間的節點本體，最後再進行刪除即可。

考慮到 List API 針對「環狀」且「雙向」的鏈結串列，改寫上述的 fast-slow pointer 手法並比較。

而最後再說明一些細節處理：

一個佇列包含 n 個節點，
- 若 $n$ 是偶數，fast 指標最後會順利地回到佇列的開頭指標（head），並且 slow 也找到適當的正中間節點
- 若 $n$ 是奇數，則要小心處理，因為每次走兩步的關係，會有一次剛好走到第 $n$ 個節點（即最後一個節點），此時若再次移動兩步，又會移動到第一個節點，從而讓迴圈繼續下去。最終 slow 會得到非預期的節點。
- 因此迴圈進行時，要同時判斷 fast->next、fast->next->next 是否都不會回到 head
這個函式明確是要進行刪除而非移除，故斷開正中間節點的鏈結後，也要釋放該節點所配置的記憶體

`q_delete_dup()`

這個函式的用意是若給定已排序的佇列，若有重複出現的資料，就要將帶有相同資料的節點全部刪除，舉例如下：

delete-dup-before

上圖可見，佇列當中，有三個節點都擁有字串 "alpha"，以 q_delete_dup() 的行為來說，最終應刪除這三個節點，最後使佇列留下那些資料僅出現一次的那些節點：

delete-dup-after

故最終，整個佇列會留下兩個節點（分別包含 "beta" 、 "gamma"）

因為該函式認定佇列是已經排序過的，所以若有重複的字串出現，它們所在的節點必定是相鄰的，故可以用兩個指標（以下以 curr、iter 代稱）走訪整個佇列處理，具體手法下：

利用 list_for_each() + curr 開始走訪節點，而iter 在每次執行迴圈內容的一開始，都指向 curr 的下一個節點。
適當利用 element_t 指標及 list_entry() 後，比較 curr 與 iter 所在節點的字串
- 若相同，以一個布林變數標記為 true，代表有重複的字串出現，爾後 iter 則移動至下一個節點，且重複第 2 步
- 若不同，前進至第 3 步
利用布林變數得知重複的狀況
- 若有發現有重複的字串出現，則開始移動 curr，將 curr 所在的節點開始，到 iter 的前一個節點，通通進行刪除。
- 若沒有重複的字串，不需要做其他動作

這邊接續前面的舉例，配合示意圖輔助說明上述步驟：
delete-dup-steps-rm-alpha

上圖可見，iter 會如同前述步驟所述，因為節點資料與 curr 相同，故不斷往下走，直至走到帶有 "beta" 的節點而停止，而顯而易見地，curr 到 iter->prev 之前的節點，都帶有 "alpha" 字串，故這些節點都要刪除，而接下來會如下圖所示：
delete-dup-steps-no-rm

因為前面遭遇重複資料的節點， curr 逐一走訪這些節點並刪除後，就會移動到 iter 所在的節點。爾後 iter 再度指向 curr 的下一個節點，重複前述步驟。

curr 指向 "beta" 的節點時，iter 會指向 "gamma" 的節點，這時發現沒有重複出現的字串，不需要刪除節點。故 curr 直接因為 list_for_each() 直接走向下一個節點（即是 iter 所在的節點）
curr 指向 gamma 的節點時，因為 iter 已經回到佇列的開頭指標，仍未發現有重複的資料出現，故不須刪除節點

最後，curr 會再次往下走一步，同樣地回到佇列的開頭指標，此時即完成了該函式的操作。

`q_swap()`

這個函式的用意是，將佇列的所有節點，每兩個相鄰節點組成一對，爾後將每一對節點的位置互相交換。（若遭遇奇數個節點，則最後一個節點不做處理）

針對這個操作，只需要如下處理：

依序走訪第 1、3、5 … 個位置的節點
透過 list_head 的 next 成員，存取這些奇數位置節點的下一個節點，即第 2、4、6 … 個位置的節點
直接將成對的節點，以 list_move()，互換成對節點的位置即可

故實作上可見，用了 list_for_each() 及 list_head 指標（命名為 curr）走訪節點，並以 list_move() 將 curr->next 移動到 curr 之前，這樣成對的節點便可互換位置。

最後這邊的細節是：

curr 原先指向奇數位置的節點，進行位置互換後，curr 本來所指向節點，其位置索引值自然會變成偶數，直接透過 list_for_each() 隱含的 curr = curr->next，即可前往下一個奇數位置的節點。也就是說 list_move() 完成後，不需要思考 curr 是否要另外處理移動的問題。
list_move() 的第一個參數確實是帶入 curr->next，表示要移動偶數位置的節點，但第二個參數須注意的是，要帶入 curr->prev，代表說 curr->next 指向的節點要移動到 curr->prev 所指向的節點的後面。

`q_reverse()`

這個操作是反轉整個佇列，也就是說

第一個節點變成最後一個節點，最後一個節點變成第一個節點
第二個節點變成倒數第二個節點，倒數第二個節點變成第二個節點
…

這裡的處理只需要依序走訪所有節點，將每一個節點的 list_head，prev 與 next 成員所儲存的記憶體位址互換即可。然而佇列的開頭指標（head）因為本質上也是儲存一個 list_head 物件，next 儲存第一個節點的位址、prev 儲存最後一個節點的位址，因此「交換 next 與 prev 儲存的內容」的動作，同樣地也要作用在 head 所指向的 list_head 物件上。

如此歸納後，可以更簡單的說，只要依序走訪佇列當中所有的 list_head 物件，對每個物件交換其兩個指標的內容，即可完成佇列反轉。

`q_reverseK()`

這個函式與 q_reverse() 類似，目的是為佇列進行反轉動作，不同的是，是每一定數量的節點進行局部的反轉。

開發者可在該函式當中，用第二個參數 k，指定每 k 個節點進行反轉，舉例如下：
reverseK

上圖舉例一個包含 6 個節點的佇列，在指定 k 為 3 並執行 reverseK() 以後，

會將前 3 個節點 "alpha" <--> "gamma" <--> "beta" 視作一組，反轉後即得到 "beta" <--> "gamma" <--> "alpha"
而後 3 個節點也是相似的道理，如上圖所示，最後會變成 "bbb" <--> "ttt" <--> "ppp" 的順序。

實作上，以 list_for_each() 與 list_head 指標（命名為 curr）來走訪佇列，爾後準備另一個 list_head 指標（命名為 iter），先指向 curr 所指向的節點，爾後不斷往下一個節點前進且邊計數，直至數了 k 個節點，就對 curr 與 iter 之間的節點，開始實施反轉。

接下來接續前述的例子（6 個節點的佇列、將 k 指定為 3 進行 q_reverseK()），搭配數張圖片探討處理方式：

最一開始，curr 與 iter 皆會指向同一個節點
iter 會邊往下一個節點前進邊計數，直至計數累積到 3，爾後可見 iter 會抵達第 4 個節點

這時候即是要把 curr 到 iter->prev 之間的所有節點（包含 curr 與 iter->prev 指向的節點），視作同一組，並實施反轉處理。
這時候在開始反轉前，先透過另外 3 個指標 prev 、 new_head 與 new_tail（後續可得知這些指標的用途），分別指向 curr->prev、iter->prev 與 curr。

爾後與 q_reverse() 雷同，逐步移動 curr 指標，直到抵達 iter 所指向的節點，將該組每一個節點的 list_head，next 與 prev 所儲存的記憶體位址互換。
當 curr 逐步移動、逐步處理 list_head 的兩個指標，抵達 iter 指向的節點後，中間各個指標的指向，一度會如下圖所示（多留意前 3 個節點的 next 與 prev 指標的指向）：

觀摩上圖可見，某些指標的指向會指向不對的節點，故這裡要額外處理下列事項：
- prev 指向的 list_head 物件（這裡只是剛好是佇列的開頭指標 head）， prev->next 應變成指向 new_head 所指向的節點。
- 剛剛以「分組」的概念，來說明要進行反轉的那些節點們，我們可以將每一個分組視作一個「子」佇列（或是說「子」鏈結串列），new_head 的含意就是子佇列的反轉後，子佇列真正的第一個節點，而明顯地，new_head->prev 應該要指向 prev 所指向的節點。
- new_tail 就是指反轉後，子佇列的最後一個節點，而 new_tail->next 應要指向
  curr 所指向的節點。
- curr 此時是反轉前，子佇列最後一個節點（第 3 個節點）的下一個節點，此時也要修正 curr->prev 的指向，應該指到 new_tail 所指向的節點。
到此，一旦完成第 4 點最後提及的 4 個修改指標指向的操作，最後就完成了一組節點的反轉了：

該圖的上半部是完成修改指標後的樣貌，下半部的圖示則是依據上半部，適當調整前 3 個節點在圖中的相對位置而已。

如此可見，前 3 個節點已經適當地反轉了，該修改的指標指向也都修正到。

最終，只要透過如前述的處理方式，適當地找出要反轉的節點區間，反轉子佇列的所有節點，並適當修正 4 個指標的指向，不斷分組處理後，即可完成對整個佇列的局部反轉。

而最後只要稍加注意，若分組分到最後，剩餘的節點不足 k 個的話，就不對這些剩餘的節點處理

`q_sort()`

該函式了行為是為佇列的所有元素進行排序（升序或是降序），原先測試的要求，是必須以時間複雜度 $O (n \log n)$ 的排序演算法，完成佇列的排序，這樣才能通過 trace-15-perf 的測試項目。

不過此處暫時先以選擇排序法處理，後者實際上是時間複雜度為 $O (n^{2})$ 的排序法，這樣做主要是為了先了解 qtest 及相關的測試項目，使用佇列操作的情況，所以先以一個簡單的演算法代替。

後續會再改寫為合併排序法，改進這個函式的效能。

`q_ascend()`

q_ascend() 的目的是讓整個佇列變成一個升序排序的佇列，但不是進行排序，而是針對每一個節點而言，在它之後有某個節點的字串比前者要小，就把後者自記憶體中刪除。

也就是說，透過刪除節點的方式，僅留下部份節點，使這些節點的資料是升序的。實作上目前也是採取簡單明瞭的方法，先走訪一個節點，爾後自這個節點的下一個節點往後找，若找到某些節點的字串比前者小，就把這些節點刪除。

`q_descend()`

該函式與 q_descend 雷同，但是要將佇列變成一個降序排序的佇列，這個操作同樣可能會刪除某些節點。

實作上，是從佇列的最後一個節點開始，逐步走訪節點並逐步往前一個節點移動，直至回到佇列的開頭。每走訪一個節點時，就掃描這個節點的前面，是否有其他節點的字串小於當前的節點，若有找到某些節點使前述的情況成立，就刪除這些節點。

`q_merge()`

q_merge() 是可以給定多個已排序的佇列，將這些佇列合併成一個仍保持排序的佇列。

而給定兩個佇列要合併時，實作時只需要透過兩個 list_head 指標，分別走訪兩個佇列的節點

第 2 個佇列的指標（這裡以 q2_curr 代稱）指向某個節點後，會先固定不動，第 1 個佇列的指標（以 q1_curr 代稱）則會逐步移動。
q2_curr 即是要被合併到第 1 個佇列的某個節點，為了找到適當的插入位置，q1_curr 就是拿來逐步在第一個佇列走訪，爾後找到某個適當的節點，q1_curr 可拿來協助將 q2_curr 安插在適當的位置上。
q1_curr 與 q2_curr 各自走訪到某個節點時，會用 list_entry() + element_t 指標，爾後取得字串並比較。
- 若發現 q1_curr 須排在 q2_curr 之後，就把 q2_curr 自第 2 個佇列移除，並插入在 q1_curr 之前。爾後 q2_curr 指標指向第 2 個佇列的新的第一個節點，也就是原先移動前，q2_curr 的下一個節點 q2_curr->next。
- 反之，q1_curr 直接往下一個節點前進。
可能會有兩種情況發生
- q1_curr 已經走回第 1 個佇列的開頭指標 head，若第 2 個佇列還有剩餘的節點，直接將這些節點移動至第 1 個佇列的尾端，隨後即可結束合併流程。
- 第 2 個佇列已經成為一個空佇列，表示所有節點都被合併至第 1 個佇列，此時不用再繼續做下去，可直接結束合併流程

這樣一來，q1_curr 與 q2_curr 會各自走訪一個佇列，透過上述方式，即可完成兩個佇列合併。

不過 q_merge() 是給定多個佇列，進行合併，目前的手法是會將第 2, 3, 4… 個佇列，一一取出，透過前述手法合併回第 1 個佇列。

額外實作的 `cmp_ascend()` 、 `cmp_descend()` 函式

因為 q_sort() 本身的第二個參數，可以決定要讓佇列以升序或是降序的方式排序，故準備了這兩個全域的靜態比較函式，這兩個函式皆是給定 2 個字串，進行比較後便回傳適當的布林值。

這兩個靜態函式的參數都命名為 str1 與 str2，排序演算法須將兩個不同的元素代入靜態函式內，若回傳值得到 true，則排序演算法要將那兩個元素的位置交換。其中須注意代入兩個元素時，兩個元素的位置必定是相對地，一個在前一個在後，而位在前面的元素要代入 str1，後面的元素則代入 str2 當中。

這兩個比較函式，本質上會呼叫 strcmp() 進行字串比較

若是 cmp_ascend()，會回傳「strcmp() 的回傳值是否大於 0」。
- 這樣的含意是若 str1 比 str2 還要大，那麼以升序方式來講，這兩個字串就應該要交換。
- 反之若 str1 小於或等於 str2，則代表兩個元素的相對位置正確，是升序的，不需要交換
若是 cmp_descend()，則會回傳「strcmp() 的回傳值是否小於 0」。
- 道理與 cmp_ascend() 相同，只是判斷的是某兩個元素之間是否是降序的。

如此，q_sort() 再準備一個函式指標陣列，準備兩個指標分別指向上述兩個比較函式，
，最後只須透過 descend 參數，就可以直接呼叫對應的比較函式。這樣不需要用分支判斷要使用升序還是降序的比較方式。

而這兩個比較函式，也會拿去輔助 q_merge() 的實作。

額外定義的 `q_is_empty()` 巨集

因為實作前述的函式時，有很多時候需要判斷佇列是否是一個空佇列，而判斷的方式自然是使用佇列的開頭指標 head，判斷其所維護 list_head 物件的 next 是否指向 head 本身。

在 list.h 中，原先已經有 list_empty() 函式，裡頭已經定義前述所需的判斷式，不過因為是要判斷「佇列是否是空佇列」，因此還是定義了 q_is_empty() 巨集，給定 head 後，會再協助代換成 list_empty() 函式，最終仍回傳為 head->next == head。

改進初步實作

修正 `q_remove_head()` 、 `q_remove_tail()` 的錯誤

當呼叫移除節點的函式的時候，若有給定合法的 sp 指標，這些移除節點的函式會將移除節點的字串，協助複製到 sp 指標所指向的字元陣列當中（其中陣列大小可由 bufsize 得知）。

原先實作上使用 strncpy()，這樣即可依據 bufsize 複製適當的字元數量到 sp 當中，而考量要容納 '\0' 字元，strncpy() 最後一個參數會代入 bufsize - 1，爾後進行複製。

後來發現 strncpy() 的複製處理，有可能剛好複製 bufsize - 1 個字元，但沒有附加 '\0' 字元，從而導致 sp 所最終儲存的字串，後續使用時會發生錯誤（如 printf() 輸出的字串，長度超過 bufsize - 1 個字元）

因此針對這兩個移除節點的函式，只要在呼叫 strncpy() 以後，主動為 sp 附加一個 \0，即可解決前述的缺陷：

實施修改後，對應到 commit 4809388

將 `q_sort()` 改為使用合併排序法

原先 q_sort() 使用選擇排序法去處理佇列的排序，後來透過 qtest 進行測試後，已知佇列的排序除了注意比較大小的方式外，還要特別注意各個指標的指向是否正確，後者會是一個要特別注意的點。

爾後為了滿足測試項目的要求，已將該函式改為合併排序法進行排序，前述的修改對應到 commit ac55cdf。

因為 lab0-c 的佇列本質上是用鏈結串列實作，接下來會以「鏈結串列」為主要術語，說明 q_sort() 的合併排序法是如何進行的。

對鏈結串列實施合併排序法，觀念與對陣列排序相同，都是先將所有元素視為個體，先兩兩合併，成為一個較小、已排序的子串列/子陣列後，再將相鄰的子串列/子陣列不斷地兩兩合併並排序，直至合併到只剩下一組串列/陣列後，即是排序完畢了。

以下先不論原先 lab0-c 的設計，先以一個儲存數個整數的鏈結串列，搭配數張圖片說明：

mergesort-0

首先上圖可見一個鏈結佇列中，包含了數個整數（1 ~ 8），若要實施合併排序法，首先須如下圖所示意，先將整個鏈結串列分割成 8 個子鏈結串列（每個子串列僅包含一個節點）
mergesort-0-1

上圖下半部以虛線示意，將鏈結串列分割成了 8 個子串列，這樣便完成了第一步。接著要依序將所有子串列兩兩合併並排序，不斷進行合併且排序後，即可完成整個鏈結串列的排序，前面這一段描述，可以用下面這張圖示意：
mergesort-1-4

這裡搭配圖中，由上至下逐步解釋其含意

第 1 步完成分割子串列後，接下來先將 8 個子串列兩兩進行合併，爾後整個串列的樣貌如第 2 步所示
第 2 步此時會有 4 個已排序的子串列，因仍包含諸多子串列，故再次進行兩兩合併，爾後前進至第 3 步
第 3 步此時已經剩下 2 個已排序的子串列，再度合併後，即是第 4 步呈現的樣貌
第 4 步此時發現剩下 1 個已排序的子串列，後者事實上就是整個已排序完畢的鏈結串列，故此時排序完成。

以上，便是鏈結串列實施合併排序法的原理，與陣列的差異，僅僅只是在記憶體中，節點之間是離散的分佈，故要用指標走訪這些節點而已。

然而，lab0-c 模仿 Linux 核心，建立「雙向」且「環狀」的鏈結串列，並且連維護串列的方式，都與 Linux 核心相同，接下來將以實作的角度（但串列節點的資料仍假設儲存整數），講解應注意的細節：

首先這裡先沿用前述鏈結串列的例子，但示意圖畫出 list_head 物件在各個節點的樣貌：
mergesort-details

爾後要注意的細節列舉及說明如下：

如何分割串列為多個子串列？

因為鏈結串列的節點在記憶體是離散的，無法像陣列一樣用索引值（或是已知的陣列大小）快速地進行分割，而對應的作法是，設法用 list_head 指標，找到正中間的節點：
mergesort-details-1

這樣一來，就可以用這個指向正中間節點的指標（對應圖中的 mid_ptr），做第一次的分割，換言之，排序整個鏈結串列，相當於先排序 head->next ~ mid_ptr 這個子串列以及 mid_ptr->next ~ head->prev 這個子串列，最後再合併兩個子串列即可。

當然對於子串列的排序，同樣是用指標找到子串列的中間節點，不斷遞迴下去，直至無法再分割時便開始將更小的子串列，不斷排序並合併回原本的串列。

而前述也提及了關鍵字「遞迴」，所以在實作上，有先定義了名為 q_sort_interval() 的靜態函式，這裡僅列出做出關鍵行為的程式碼：

static int q_sort_interval(struct list_head *head, 
                           struct list_head *tail,
                           bool (*cmp)(const char *, const char *))
{
    /* Handle the simplest cases */
    if (head->next == tail) {
        ...
        return 1;
    }
    ...
    ...
    
    /* Split the lists into two sub-lists and sort them. */
    q_sort_interval(head, mid_ptr, cmp);
    ...
    q_sort_interval(mid_ptr->next, tail, cmp);
    
    /* Merge two sub-lists. */
    ...
    ...
}

static void q_sort(struct list_head *head, bool descend)
{
    bool (*cmp[2])(const char *, const char *) = {cmp_ascend, cmp_descend};

    if (!head || q_is_empty(head))
        return;

    q_sort_interval(head->next, head->prev, cmp[descend]);
}

透過 q_sort_interval()，後者可給定鏈結串列的第一個節點指標、最後一個節點的指標以及排序的比較方式（給定比較函式的指標），即會實施排序。其中須注意 q_sort_interval() 不可以給定空串列。

若遭遇某些最簡單的排序案例，就會直接將串列排序後並結束執行
- 最簡單的案例，即是 q_sort_interval() 發現該串列只有一個節點或是兩個節點，若是後兩者其一的話，直接視情況交換兩個元素的位置或是直接結束執行即可。
反之若串列的節點數量夠多，則會分割成兩個串列後，遞迴地呼叫自己兩次，排序兩個子串列。排序完畢後，就會將兩個已排序的子串列進行合併。

如此，q_sort() 本身只需要呼叫 q_sort_interval()，給定真正的第一個節點與最後一個節點的記憶體位址（即 head->next 與 head->prev），這樣即可完成整個串列的排序。

list_head 物件的兩個指標處理

前面第 1 點已經提及可用遞迴搭配指標的方式，不過這裡要提及第二個細節，就是實作上若僅用指標是不夠的，要用到指標的指標（或稱間接指標）的操作技巧，具體原因進一步說明如下：

mergesort-details-bug

原先會預期 q_sort_interval() 代入開頭節點與結尾節點的指標並完成串列的排序，但因為前述並沒有提到 head 所指向的 list_head 物件，其 next 與 prev 指標要如何適當調整，故若處理不當，即便排序完畢，head 所維護的 list_head 也會指向錯誤的節點（如上圖的下半部所呈現）。

再來看一個例子，因為會不斷分割成小的串列並排序，所以也有這樣的例子：
mergesort-details-bug2

從前面的例子不難觀察到，原先的串列不斷地分割完後，會先合併 4 與 1 的節點並排序，再來合併 7 與 3 的節點並排序。上圖假設 4 與 1 的節點已排序變成先 1 後 4，再來處理 7 與 3 的節點。

而處理帶有 3 與 7 的子串列時，會遭遇到與剛剛類似的理由，因為 q_sort_interval() 僅代入開頭節點與結尾節點，所以 7 的節點與 3 的節點確實可以排序到，但這個子串列前一與後一節點的指標沒有被調整到（即上圖下半部 4 的節點的 next 指標、5 的節點的 prev 指標），這樣走訪串列時仍會得到錯誤的順序。

如此可以這樣歸納說明：「q_sort_interval() 若參數僅用指標，無法處理（子）串列前一個 list_head 物件與後一個 list_head 物件的指標。」

因此，可以用間接指標的技巧，

static int q_sort_interval(struct list_head **head, 
                           struct list_head **tail,
                           bool (*cmp)(const char *, const char *))
{
    /* Handle the simplest cases */
    if (head->next == tail) {
        ...
        return 1;
    }
    ...
    ...
    
    /* Split the lists into two sub-lists and sort them. */
    q_sort_interval(head, &mid_ptr, cmp);
    ...
    q_sort_interval(&mid_ptr->next, tail, cmp);
    
    /* Merge two sub-lists. */
    ...
    ...
}

static void q_sort(struct list_head *head, bool descend)
{
    bool (*cmp[2])(const char *, const char *) = {cmp_ascend, cmp_descend};

    if (!head || q_is_empty(head))
        return;

    q_sort_interval(&head->next, &head->prev, cmp[descend]);
}

將參數改寫為 struct list_head ** 的型態後，就可以解決前面提及的問題，讓子串列被排序後，在子串列前後的 list_head 物件的指標也被調整到。

雖說光靠 struct list_head * 也可以存取子串列前後的 list_head 物件並修改，但這樣就要在程式碼中加入「若子串列排序後，開頭/結尾節點有改變，就要調整子串列前後 list_head 物件的指標」的處理。

在你所不知道的 C 語言: linked list 和非連續記憶體教材中，有一段「移除鏈結串列的節點」程式碼，如果僅用指標，就要做出額外的特例處理，但用指標的指標，就可以省去特例處理，從而讓程式碼變得簡潔。所以 q_sort_interval() 參數型態改用指標的指標，也是類似的道理。

如此，透過前述手法，q_sort_interval() 即可適當地完成串列的排序，從而順利完成 q_sort 的實作，滿足時間複雜度的要求。

修改 `q_delete_mid()` 的手法並比較

原先 q_delete_mid() 採用快慢指標的手法，找到正中間的節點並刪除之，但考慮 List API 建立雙向且環狀的鏈結串列，還有另一個實作思維：

以一個圓形的操場來比喻，若兩人自操場的同一點，背對背行進行走操場，以速率相同但行進方向相反的方式繞著操場走，交會的那一刻，兩人都剛好走了操場圓周長的一半。故針對環狀且雙向的鏈結串列，可以利用兩個指標，一個從開頭節點往結尾節點的方向移動，另一個節點，從結尾節點開始往開頭節點的方向走，兩個指標在迴圈中不斷地移動（僅移動一步），當兩個指標交會的那一刻，也可以找到正中間的節點。

依循上述的手法進行修改後，對應到 improve-q_delete-mid 分支的 commit c837f44

為了比較前後的執行時間差異，找出真正最佳的那個方法，後來有追加一些程式，做了一些前置準備後，利用一些手法產生測量數據並比較。

追加 `measure` 命令

在 qtest 內建的命令列，雖然已經有 time 命令可以測量某個命令的執行時間，但這個命令的輸出時間，精確度只能到毫秒等級，而且一次只能執行一次命令。

為了可以「下一次命令，執行多次動作」，後續自行追加了 measure 命令，在執行 qtest 後，可用 help 命令見到說明如下：

cmd> help
..
..
  measure     n cmd arg .. | Using clock_gettime to measure the time for each execution
..
..

也就是說，我新做的 measure 命令與 time 命令類似，但前者使用 clock_gettime() 來測量執行時間（精確度達到奈秒等級），並且第一個參數 n 即是可執行給定的命令（cmd arg）n 次，並用標準輸出（或者說利用 report() 函式），將每一次執行的時間呈現在命令介面上。

舉例來說，可以以下列方式執行命令：

cmd> new
l = []
cmd> measure 5 it RAND
l = [jceids]
elapsed time: 22777
l = [jceids gebwxleul]
elapsed time: 16983
l = [jceids gebwxleul pynqvwtc]
elapsed time: 17329
l = [jceids gebwxleul pynqvwtc vfvdaby]
elapsed time: 14588
l = [jceids gebwxleul pynqvwtc vfvdaby iwllwfjk]
elapsed time: 18163

上面這段 qtest 的操作，是先新增一個空佇列後，爾後執行 measure 5 it RAND，意思就是 it RAND 這個操作被執行 5 次，而每執行完一次後，會輸出 elapsed time: ... 的訊息。這樣一來，開發者若要測量某個佇列操作的執行時間，可以透過 measure 命令，讓某個操作被執行多次並輸出每一次的執行時間，接著可以進一步做的事情，就是收集這多次的時間，進行分析後，得知該操作的平均執行時間（注意是在自己環境上的平均執行時間）。

上述追加 measure 命令的修改，對應到 commit ef57f26

設計 `q_delete_mid()` 的測試實驗

設計初步的測試命令序列

有了自己撰寫的 measure 命令後，我初步便設計了以下的命令序列（建立 testcase.cmd 檔案）

testcase.cmd

new
it RAND 10000
log result-mytest
measure 30 dm
free

這樣一來，即可測試 10000 個節點下，移除 30 次正中間節點的執行時間。不過因為是直接移除 30 個節點，會輸出 30 次 elapsed time: ... 的訊息，並且將輸出訊息也儲存到 result-mytest 檔案中

這裡要注意：

第一次的 elapsed time: ... 訊息：是自 10000 個節點中，移除正中間節點的執行時間
第二次的 elapsed time: ... 訊息：是自 9999 個節點中，移除正中間節點的執行時間
第三次的 elapsed time: ... 訊息：是自 9998 個節點中，移除正中間節點的執行時間
…

亦即那 30 次執行移除正中間節點時，遭遇的節點總數量不同，故要注意這樣的區別。

爾後在終端機，可以用下列 shell 命令，使用 qtest 來測試 testcase.cmd

cat testcase.cmd | ./qtest > /dev/null

這樣就可以用 cat 將 testcase.cmd 欲執行的所有操作，透過 shell 的管線（pipe）一次性地送到 qtest 內執行。

而假設想執行 100 次 qtest 及設計好的測試命令組合，並取得平均時間，就要執行上述的 shell 命令 100 次，產出 100 個 result-mytest 檔案後，自行取出裡面的內容，再計算平均執行時間。（具體的計算方式，會在第 3 點論述）

為了可以自動化執行前面的過程、計算平均執行時間、產出測試圖表，於是接下來就設計了一系列地測試工具。

建立自動化測試的腳本




































#!/bin/sh

if [ "$1" = "" ] || [ "$2" = "" ] || [ "$3" = "" ]; then
	echo "Usage: ./test_script.sh <n> <init_node> <rm_node"
	echo "run a testcase n times and produce analysis figure."
	exit 1
fi

testcase="
new
it RAND $2
log result-mytest
measure $3 dm
free
"

mkdir -p result-mytest-dir

git checkout master
make
for i in $(seq 1 $1); do
	echo "$testcase" | ./qtest > /dev/null
	mv result-mytest result-mytest-dir/result-mytest$i
done
mv result-mytest-dir/result-mytest* measurement/mytest-master || exit 1

git checkout improve-q_delete_mid
make
for i in $(seq 1 $1); do
	echo "$testcase" | ./qtest > /dev/null
	mv result-mytest result-mytest-dir/result-mytest$i
done
mv result-mytest-dir/result-mytest* measurement/mytest-improve || exit 1

cd measurement
python3 measure.py $1 $2

這個 shell 腳本會進行數項操作，這邊配合行號並描述上述的執行過程

L1 - L7：提示命令執行方式為 ./test-script.sh <n> <init_node> <rm_node>
- 因為前面提及的 testcase.cmd 固定是初始有 10000 個節點，並移除 30 次節點，所以 <init_node> 可以指定初始節點、<rm_node> 可以指定要移除的次數，增加測試的彈性
- 而 <n> 可指定使用 qtest 執行命令序列 $n$ 次，產出 $n$ 個 result-mytest 的測試結果檔案
L9 - L14：這裡用名為 testcase 的變數，儲存稍後欲執行的命令序列，而實際上就是前面提及的 testcase.cmd 所包含的命令，不過將 10000 置換為 $2、30 置換為 $3，這樣可以透過在 shell 下命令時，彈性地修改初始節點數量、移除正中間節點的次數
L17：因為會產出多個 result-mytest 檔案，所以會用 mkdir 產生一個目錄，後續會將所有 result-mytest 檔案存放至 result-mytest-dir 目錄下
L19 - L33：
- 針對 q_delete_mid() 的實作，在 master 支線採用快慢指標的作法，improve-q_delete_mid 採用新的作法（兩個指標向正中間移動的作法），接著必須先後切換至兩個分支上，編譯並執行 qtest 並執行 testcase 的命令，爾後產出 result-mytest 並進行後續分析
- 所以這裡會自動執行 git checkout，
  - 先切換到 master 支線，以 make 編譯 qtest 並透過 for 迴圈執行 qtest $n$ 次，並將每一次產生的 result-mytest 移動到 result-mytest-dir 目錄，且在檔案名稱最後面附加號碼。執行完後，會將 result-mytest-dir 下多個 result-mytest 檔案，存放到 measurement/mytest-master 目錄下
  - 爾後再次 git checkout，切換到 improve-q_delete_mid，並做一樣的事情，但最後 result-mytest-dir 下的所有檔案，會通通移動到 measurement/mytest-improve 目錄底下

L35 - L36：

根據我自己的設計來講，執行 test_script.sh 以後，最後會得到類似下列的目錄及檔案：

.
├── console.c
...
├── measurement
│   ├── measure.py
│   ├── mytest-master
│   │   ├── result-mytest1
│   │   ├── result-mytest2
│   │   ...
│   └── mytest-improve
│       ├── result-mytest1
│       ├── result-mytest2
│       ...
│
├── qtest
...

也就是說，master 與 improve-q_delete_mid 兩個分支各自的測試結果，會分別存放至 measurement/mytest-master 及 measurement/mytest-improve 底下。
（其中 measurement 是自行預先建立好的目錄、measure.py 後續會說明其用意）

接著就是透過 cd 切換工作目錄至 measurement 內，爾後啟用 measure.py，透過 Python 程式進行分析

透過 Python 分析、計算平均執行時間、產出圖表

經過前面的 shell 腳本，最終會得到許多的 result-mytest<n> 檔案（<n> 是 shell 腳本最終給定的編號），亦即多次執行結果，如果觀察 result-mytest<n>，不難發現我們可以將這多次的執行結果，自行想像並展開成一個表格

假設執行 ./test_script.sh 50 1000 100 的話，亦即 mytest-master 與 mytest-improve 目錄，最終都應可以得到各自的 result-mytest1 ~ result-mytest50，爾後可以像下方這樣展開成兩個表格

mytest-master
+--------------------+--------+--------+               +---------+
|           \ sample |        |        |               |         |
| total nodes \      |   1    |   2    | . . . . . . . |   50    |
+--------------------+--------+--------+               +---------+
| 1000               | 170012 | 160020 |               | 1611116 |
+--------------------+--------+--------+               +---------+
| 999                | 166611 | 165432 |                     .
+--------------------+--------+--------+                     .   
| 998                | 165555 | 164353 | . . . . . . .       . 
+--------------------+--------+--------+
.                                         .
. . . . . . . . . . . .. . . . . . . . .     .
.                                                .
+--------------------+                                 +---------+
| 901                | . . . . . . . . . . . . . . . . | 1443232 |
+--------------------+                                 +---------+

mytest-improve
+--------------------+--------+--------+               +---------+
|           \ sample |        |        |               |         |
| total nodes \      |   1    |   2    | . . . . . . . |   50    |
+--------------------+--------+--------+               +---------+
| 1000               | 171012 | 164420 |               | 1613216 |
+--------------------+--------+--------+               +---------+
| 999                | 164611 | 165432 |                     .
+--------------------+--------+--------+                     .   
| 998                | 165555 | 157353 | . . . . . . .       . 
+--------------------+--------+--------+
.                                         .
. . . . . . . . . . . .. . . . . . . . .     .
.                                                .
+--------------------+                                 +---------+
| 901                | . . . . . . . . . . . . . . . . | 1333232 |
+--------------------+                                 +---------+

如第一點所述，因為移除多個節點的過程中，節點的總數量是同時遞減，故勢必要以總節點數量區分收集到的多次執行時間，所以上述表格就有了 total nodes，表示在對應的總節點數量下，移除節點的執行時間。
接著因為透過 test_script 執行了 50 次 qtest，所以會有縱軸的 sample，這樣可以清晰地見到 total nodes 的每一個項目，都有 50 次執行時間的數據。

如果可以理解前述的說明，就可以知道接下來要這樣處理：

mytest-master
+--------------------+--------+
|           \ average|        |
| total nodes \      |        |
+--------------------+--------+
| 1000               | 160612 |
+--------------------+--------+
| 999                | 160011 |
+--------------------+--------+
| 998                | 163355 |
+--------------------+--------+
.              .              . 
.              .              .
.              .              .   
+--------------------+--------+
| 901                | 141212 |
+--------------------+--------+

mytest-improve
+--------------------+--------+
|           \ average|        |
| total nodes \      |        |
+--------------------+--------+
| 1000               | 157312 |
+--------------------+--------+
| 999                | 156611 |
+--------------------+--------+
| 998                | 154555 |
+--------------------+--------+
.              .              . 
.              .              .
.              .              .  
+--------------------+--------+
| 901                | 142002 |
+--------------------+--------+

因為原先的表格，每一列都有 50 次數據，所以可以取平均值，得知特定總節點數量下，移除正中間節點的平均執行時間，最終算完平均值的表格，就可以將其繪製曲線圖，從而比較 master 與 improve-q_delete-mid 的實作，從視覺化的圖表中，得知執行時間的差異並找出最佳的實作

因此，為了將所有的 result-mytest<n>，轉換成表格、計算每一項目的平均值、並畫出曲線圖，這裡採用撰寫 Python 腳本的策略，完成前述要做的事情，而 Python 腳本的實作如下：

import matplotlib.pyplot as plt
import numpy as np
import sys

base_name = "result-mytest"

def outlier_filter(data, threshold = 2):
    data = np.array([y for y in data])
    z = np.abs((data - data.mean()) / data.std())
    return data[z < threshold]

def parse_data(path, cases, init_node):
    all_data = None
    for i in range(cases):
        j = 0
        data = []
        with open(path + "/" + base_name + "%d"%(i + 1), "r") as f:
            for line in f:
                if line.startswith("elapsed time:"):
                    exec_time = int(line.split(":")[1].strip())
                    data.append([init_node - j, exec_time])
                    j += 1
            if all_data:
                for i in range(len(all_data)):
                    all_data[i].append(data[i][1])
            else:
                all_data = data
    
    for i in range(len(all_data)):
        filtered_data = outlier_filter(all_data[i][1:]).mean()
        all_data[i] = [all_data[i][0], filtered_data]

    return all_data
    

def main():
    if len(sys.argv) < 3:
        print("Usage: python3 measure.py <num_of_data> <init_node>")
        exit(1)

    num = int(sys.argv[1])
    init_node = int(sys.argv[2])
    plt.figure(figsize=(8, 6))

    master_data = parse_data("mytest-master", num, init_node)
    improve_data = parse_data("mytest-improve", num, init_node)

    x_values, y_values = zip(*master_data)
    plt.plot(x_values, y_values, marker='o', linestyle='-',
             color='b', label="fast-slow pointer")

    x_values, y_values = zip(*improve_data)
    plt.plot(x_values, y_values, marker='o', linestyle='-',
             color='g', label="Two pointers move toward to each other")

    plt.legend()
    plt.show()

if __name__ == "__main__":
    main()

因為上述的程式碼並未上傳到 GitHub 上，故呈現在此並解說：

執行方式：python3 measure.py <n> <init_node>
- 透過 shell 的參數，告知 result-mytest<n> 的 <n> 最高是多少
- 因為 result-mytest<n> 的內容並沒有初始總節點的資訊，所以透過 <init_node> 告知這個腳本，每一次測試的初始總節點數量
parse_data() 即是給定 mytest-master 或是 mytest-improve 字串後，會去指定的目錄下讀取 result-mytest1 ~ result-mytest<n>，並轉成 Python 的 list 物件（就是將收集到的數據做成表格），爾後會對每一列的數據取平均值，變成算完平均值的表格
- 考量數據可能會有極端值的存在，故有參考 2022 年 - K04: fibdrv 的說明，可以用統計手法去除極端值，所以中間還有設計 outlier_filter() 函式，讓 parse_data() 先除去極端值後再計算平均值。
main 函式就是呼叫 parse_data() 後，得到兩種表格，分別對應 master 與 improve-q_delete_mid 的執行時間數據。接著呼叫 matplotlib 的繪圖功能，將兩條曲線畫出來。

綜合前面的說明，執行 test_script.sh，指定取樣次數、初始總節點數量、要移除正中間節點的次數以後，接著腳本會協助到兩個分支上測試並產出測試數據，最後 Python 腳本程式可以協助產出類似下方的圖表：

Figure_1

圖中的橫軸即是總節點數量、縱軸則是執行時間（單位是奈秒），所以圖中的每一個點，都代表對應的總節點數量下，移除正中間節點的平均時間。

修改 `q_delete_mid` 的小結

透過修改 q_delete_mid() 的手法並比較的說明，我原先設想可以收集多次執行時間的數據後，得知 q_delete_mid() 的平均執行時間並繪製圖表後，就可以比較這個函式修改前後的差異。

不過後來有多用 test_script 執行數次，有發現到以下的現象

執行 ./test_script.sh 50 10000 100 兩次
- 第一次可見是新方法比較快
- 但第二次竟然顯示舊方法比較塊

後來嘗試修改初始節點數量，也會有類似的情形

執行 ./test_script.sh 50 30000 100 兩次
執行 ./test_script.sh 50 50000 100 兩次

原先預期不論怎麼執行 test_script.sh，都必定會顯示某一種方法比較快，但從前面的描述可以得知，test_script.sh 會告訴我有時候是新方法比較快，有時則是舊方法比較快，這樣無從判斷哪一個方法是最佳的實作。

或許是我設想的實驗方式，有未考量到的影響因素，從而導致有時是新方法比較快，有時則是舊方法比較快，後續或許要更周全地考量實驗方式與測試環境，才能更正確地分析並找出最佳的實作。

2025q1 Homework1 (lab0)

開發環境

開發前處理

為所有佇列操作介面提供初步實作

q_new()

q_free()

q_insert_head() 、 q_insert_tail()

q_remove_head() 、 q_remove_tail()

q_size()

q_delete_mid()

q_delete_dup()

q_swap()

q_reverse()

q_reverseK()

q_sort()

q_ascend()

q_descend()

q_merge()

額外實作的 cmp_ascend() 、 cmp_descend() 函式

額外定義的 q_is_empty() 巨集