2025q1 Homework1 (lab0)

contributed by <NeedToDebugMyLife>

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [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):                   8
  On-line CPU(s) list:    0-7
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz
    CPU family:           6
    Model:                158
    Thread(s) per core:   2
    Core(s) per socket:   4
    Socket(s):            1
    Stepping:             9
    CPU(s) scaling MHz:   90%
    CPU max MHz:          4500.0000
    CPU min MHz:          800.0000
    BogoMIPS:             8400.00
    Flags:                fpu vme de pse tsc msr pae mce cx8 apic se
                          p mtrr pge mca cmov pat pse36 clflush dts 
                          acpi mmx fxsr sse sse2 ss ht tm pbe syscal
                          l nx pdpe1gb rdtscp lm constant_tsc art ar
                          ch_perfmon pebs bts rep_good nopl xtopolog
                          y nonstop_tsc cpuid aperfmperf pni pclmulq
                          dq dtes64 monitor ds_cpl est tm2 ssse3 sdb
                          g fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2
                          apic movbe popcnt tsc_deadline_timer aes x
                          save avx f16c rdrand lahf_lm abm 3dnowpref
                          etch cpuid_fault epb pti ssbd ibrs ibpb st
                          ibp fsgsbase tsc_adjust bmi1 avx2 smep bmi
                          2 erms invpcid mpx rdseed adx smap clflush
                          opt intel_pt xsaveopt xsavec xgetbv1 xsave
                          s dtherm ida arat pln pts hwp hwp_notify h
                          wp_act_window hwp_epp md_clear flush_l1d a
                          rch_capabilities
Caches (sum of all):      
  L1d:                    128 KiB (4 instances)
  L1i:                    128 KiB (4 instances)
  L2:                     1 MiB (4 instances)
  L3:                     8 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-7
Vulnerabilities:          
  Gather data sampling:   Mitigation; Microcode
  Itlb multihit:          KVM: Mitigation: VMX unsupported
  L1tf:                   Mitigation; PTE Inversion
  Mds:                    Mitigation; Clear CPU buffers; SMT vulnera
                          ble
  Meltdown:               Mitigation; PTI
  Mmio stale data:        Mitigation; Clear CPU buffers; SMT vulnera
                          ble
  Reg file data sampling: Not affected
  Retbleed:               Mitigation; IBRS
  Spec rstack overflow:   Not affected
  Spec store bypass:      Mitigation; Speculative Store Bypass disab
                          led via prctl
  Spectre v1:             Mitigation; usercopy/swapgs barriers and _
                          _user pointer sanitization
  Spectre v2:             Mitigation; IBRS; IBPB conditional; STIBP 
                          conditional; RSB filling; PBRSB-eIBRS Not 
                          affected; BHI Not affected
  Srbds:                  Mitigation; Microcode
  Tsx async abort:        Mitigation; TSX disabled

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

`q_new`

程式碼

完整程式實作

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));

    if (!head)
        return NULL;

    INIT_LIST_HEAD(head);

    return head;
}

實作說明

使用 malloc() 來配置記憶體空間
使用 list.h 中的 INIT_LIST_HEAD() 來初始化標頭節點的指標(指向自己)

特殊狀況處理

檢查記憶體配置是否成功，如果失敗則回傳 NULL
```
if (!head)
    return NULL;
```

`q_free`

程式碼

完整程式實作

void q_free(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *cur = head->next;

    while (cur != head) {
        struct list_head *tmp;
        tmp = cur;
        cur = cur->next;

        list_del(tmp);
        q_release_element(list_entry(tmp, element_t, list));
    }

    free(head);
}

實作說明

使用迴圈走訪節點並釋放每個節點的記憶體空間，走訪完成後再釋放標頭節點的空間

使用 list.h 中的 list_del() 來移除指定節點
使用 queue.h 中的 q_release_element() 釋出記憶體空間

特殊狀況處理

檢查標頭節點 head 是否存在 (是否已執行 q_new())，如果不存在則結束執行
```
if (!head)
    return NULL;
```

`q_insert_head`

程式碼

完整程式實作

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    char *str = strdup(s);
    strcat(str, "\0");

    element_t *node = malloc(sizeof(element_t));

    // malloc failure handle
    if (!str) {
        free(node);
        return false;
    }

    if (!node) {
        free(str);
        return false;
    }

    node->value = str;
    list_add(&node->list, head);

    return true;
}

實作說明

建立一個新節點，並將節點插入到佇列的第一個位置 (head->next)
element_t 結構中有兩個元素 (char* value 以及 struct list_head list)，其中 value 是一個指標。因此在分配記憶體空間時，value 只有被分配到一個 char 的大小，所以還需要再額外分配一個記憶體空間來儲存該節點對應的字串。

使用 malloc() 來配置 node 的記憶體空間
使用 strdup() 來配置 value 指向的字串記憶體空間，同時將輸入 s 複製到配置好的空間內
使用 list.h 中的 list_add() 將節點插入到佇列開頭。

特殊狀況處理

檢查標頭節點 head 是否存在 (是否已執行 q_new())，如果不存在則回傳 false
```
if (!head)
    return NULL;
```

檢查記憶體配置是否成功，只要其中一個 (str, node) 配置失敗就代表節點建立失敗，需釋放已配置的空間，並回傳 false

// if str allocation fail
if (!str) {
    free(node);
    return false;
}

// if node allocation fail
if (!node) {
    free(str);
    return false;
}

問題紀錄

strcmp 和 strdup

`q_insert_tail`

程式碼

完整程式實作

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    char *str = strdup(s);
    strcat(str, "\0");

    element_t *node = malloc(sizeof(element_t));

    // malloc failure handle
    if (!str) {
        free(node);
        return false;
    }

    if (!node) {
        free(str);
        return false;
    }

    node->value = str;
    list_add_tail(&node->list, head);

    return true;
}

實作方式

建立一個新節點，並將節點插入到佇列的最後一個位置 (head->prev)

程式邏輯和 q_insert_head() 相同，差別在於 q_insert_tail() 使用 list.h 中的 list_add_tail() 將節點插入到佇列結尾。

`q_remove_head`

程式碼

完整程式實作

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *node = list_entry(head->next, element_t, list);
    char *str = strndup(node->value, bufsize - 1);

    strcat(str, "\0");
    strncpy(sp, str, bufsize);

    list_del(&node->list);

    return node;
}

實作說明

移除 (不是刪除) 佇列的第一個節點 (head->next)，並將移除的節點值記錄到 sp 內

使用 strndup() 配置一個大小為 bufsize-1 的空間來紀錄移除節點的 value (需要額外補上結束符號 \0 )
使用 strncpy() 紀錄的 value 複製到 stack pointer 內
使用 list.h 中的 list_empty() 檢查佇列是否為空
使用 list.h 中的 list_entry() 取得對應節點
使用 list.h 中的 list_del() 來移除指定節點

特殊狀況處理

檢查標頭節點 head 是否存在 (是否已執行 q_new())，如果不存在則回傳 NULL

檢查佇列是否有節點，如果沒有則回傳 NULL

if (!head || list_empty(head))
    return NULL;

`q_remove_tail`

程式碼

完整程式實作

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *node = list_entry(head->prev, element_t, list);
    char *str = strndup(node->value, bufsize - 1);

    strcat(str, "\0");
    strncpy(sp, str, bufsize);

    list_del(&node->list);

    return node;
}

實作說明

移除 (不是刪除) 佇列的最後一個節點 (head->prev)，並將移除的節點值記錄到 sp 內

程式邏輯和 q_remove_head() 相同，差別在於 q_remove_tail() 移除的是佇列最後一個節點 (head->prev)

`q_size`

程式碼

完整程式實作

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    int size = 0;
    struct list_head *cur = head->next;

    while (cur != head) {
        size++;
        cur = cur->next;
    }

    return size;
}

實作說明

使用迴圈對佇列做遞移檢查。每走訪一個節點，size 遞增 1，直到走訪到 head (走訪一輪)

使用 list.h 中的 list_empty() 檢查佇列是否為空

特殊狀況處理

檢查標頭節點 head 是否存在 (是否已執行 q_new())，如果不存在則結束執行

檢查佇列是否有節點，如果沒有則回傳 NULL

if (!head || list_empty(head))
    return 0;

`q_delete_mid`

程式碼

完整程式實作

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    int size = q_size(head) / 2;
    struct list_head *tmp = head->next;

    for (int i = 0; i < size; i++)
        tmp = tmp->next;

    list_del(tmp);
    q_release_element(list_entry(tmp, element_t, list));

    return true;
}

實作說明

使用迴圈對佇列做遞移檢查直到中間節點，

使用 q_size()/2 計算佇列的中點索引
使用 list.h 中的 list_empty() 檢查佇列是否為空
使用 list.h 中的 list_del() 來移除指定節點
使用 queue.h 中的 q_release_element() 釋出記憶體空間

特殊狀況處理

檢查標頭節點 head 是否存在 (是否已執行 q_new())，如果不存在則回傳 false

檢查佇列是否有節點，如果沒有則回傳 false

if (!head || list_empty(head))
    return false;

`q_delete_dup`

程式碼

完整程式實作

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    char *str = strdup("");
    struct list_head *cur = head->next;

    while (cur->next != head) {
        struct list_head *tmp;
        tmp = cur;
        cur = cur->next;

        if (strcmp(list_entry(tmp, element_t, list)->value, str) == 0 ||
            strcmp(list_entry(tmp, element_t, list)->value,
                   list_entry(cur, element_t, list)->value) == 0) {
            free(str);
            str = strdup(list_entry(tmp, element_t, list)->value);

            list_del(tmp);
            q_release_element(list_entry(tmp, element_t, list));
        }
    }

    if (strcmp(list_entry(cur, element_t, list)->value, str) == 0) {
        list_del(cur);
        q_release_element(list_entry(cur, element_t, list));
    }

    free(str);
    return true;
}

實作說明

因為輸入的佇列皆已完成排序，所以有相同值的節點必定相鄰
每次比較兩相鄰節點，如果節點值相同則刪除節點並記錄重複節點值
每次更新紀錄節點值時都需要釋放並重新分配空間，因為每次紀錄的節點值長度未必相同。也無法配置固定長度的空間，因為無法確定節點值的長度上限是多少。

使用 strcmp() 比較兩個節點的 value 是否相同 (等於 0 時相同)
使用 strdup() 配置一個空間來紀錄重複節點的 value
使用 free() 移除配置的空間
使用 list.h 中的 list_empty() 檢查佇列是否為空
使用 list.h 中的 list_entry() 取得對應節點
使用 list.h 中的 list_del() 來移除指定節點
使用 queue.h 中的 q_release_element() 釋出記憶體空間

節點比較

如果當前節點 (tmp) 和下一個節點值 (cur) 相同，則刪除當前節點
如果當前節點 (tmp) 和紀錄的字串值 (str) 相同，則刪除當前節點

特殊狀況處理

檢查標頭節點 head 是否存在 (是否已執行 q_new())，如果不存在則回傳 false

檢查佇列是否有節點，如果沒有則回傳 false

if (!head || list_empty(head))
    return false;

問題紀錄

while 迴圈的終止條件為 cur->next != head 而不是 cur != head，是因為當 cur 為最後一個節點 (cur->next == head) 時，會將 cur 再往後移動一個節點 (cur = cur->next)，此時的 cur 等於 head (cur == head)，但因為 head 沒有 value 元素，所以執行 list_entry(cur, element_t, list) 時就會產生錯誤

(已解決) ⭢ 將 str 的初值設為 "\0" (或"")

無法將 str 設為 NULL，因為 strcmp() 不支援 NULL 的比較
因為 str 的初值為 "\0",在還沒檢查到重覆節點時，str 的值不會產生任何改變，所以在執行 free(str) 時會產生錯誤。因此需要再 free(str) 外使用一個 if 判斷式來做檢查

(已解決) ⭢ 將 str 的賦值由直接指派改為使用 strdup 分配

原先的寫法是直接將 str 的值設為 "\0" (或 "" )，但會導致執行 free(str) 時產生錯誤 (因為沒有配置空間所以無法進行釋放)，所以需要額外的條件判斷
因為 while 迴圈的終止條件為 cur->next != head，所以實際上最後一個節點不會被檢查到，如果最後一個節點也包含重複值，就無法進行刪除。因此需要在 while 迴圈外使用一個 if 判斷式來做檢查

`q_swap`

程式碼

完整程式實作

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *cur = head->next;
    struct list_head *next = cur->next;

    while (cur != head && next != head) {
        list_del(cur);
        list_add(cur, next);
        cur = cur->next;
        next = cur->next;
    }
}

實作說明

將 cur 節點移動 (移除+插入) 到下一個節點後方 (cur->next->next) 就可以實現兩節點的交換

使用 list.h 中的 list_empty() 檢查佇列是否為空
使用 list.h 中的 list_is_singular() 檢查佇列是否只包含一個節點
使用 list.h 中的 list_del() 來移除指定節點
使用 list.h 中的 list_add() 來將移除節點插入到指定節點後方

特殊狀況處理

檢查標頭節點 head 是否存在 (是否已執行 q_new())，如果不存在則結束執行
檢查佇列是否有節點，如果沒有或只有一個節點 (只有一個無法進行交換) 則結束執行
```
if (!head || list_empty(head) || list_is_singular(head))
    return;
```

`q_reverse`

程式碼

完整程式實作

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *cur = head->prev;

    while (cur != head) {
        struct list_head *tmp;
        tmp = cur;
        cur = cur->prev;
        list_move_tail(tmp, head);
    }
}

實作說明

由佇列最後一個節點 (head->prev) 向前走訪，每走訪一個節點就將該節點移動到佇列最後

使用 list.h 中的 list_empty() 檢查佇列是否為空
使用 list.h 中的 list_is_singular() 檢查佇列是否只包含一個節點
使用 list.h 中的 list_move_tail() 來將指定節點移動到指定節點後方

特殊狀況處理

檢查標頭節點 head 是否存在 (是否已執行 q_new())，如果不存在則結束執行
檢查佇列是否有節點，如果沒有或只有一個節點 (只有一個無法進行交換) 則結束執行
```
if (!head || list_empty(head) || list_is_singular(head))
    return;
```

`q_reverseK`

完整程式實作

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head))
        return;

    int size = q_size(head);
    if (k > size || k < 2)
        return;

    if (k == 2) {
        q_swap(head);
        return;
    }

    struct list_head *tmp = head->next;
    struct list_head *cur = head->next;
    struct list_head *reverse_h = head->next;
    struct list_head *reverse_t = head->next;

    for (int i = 0; i < size; i++) {
        tmp = cur;
        cur = cur->next;

        if (i % k == k - 1) {
            tmp->next = head;
            head->prev = tmp;
            q_reverse(head);

            reverse_t->next = head->next;
            head->next->prev = reverse_t;

            if (i == k - 1)
                reverse_h = head->next;

            reverse_t = head->prev;

            head->next = cur;
            cur->prev = head;
        }
    }

    if (head->next != head) {
        reverse_t->next = head->next;
        head->next->prev = reverse_t;

        reverse_t = tmp;
    }

    head->prev = reverse_t;
    head->next = reverse_h;

    reverse_h->prev = head;
    reverse_t->next = head;
}

實作說明

將佇列每 K 個節點分為一組，分別對每組做 q_reverse()，再將反轉後的每個佇列重新組合成一個完整的佇列

使用 list.h 中的 list_empty() 檢查佇列是否為空
使用 list.h 中的 list_entry() 取得對應節點
使用 list.h 中的 list_del() 來移除指定節點
使用 q_size() 計算佇列的長度
使用 q_swap() 對兩節點做交換
使用 q_reverse() 計算反轉節點順序

特殊狀況處理

檢查標頭節點 head 是否存在 (是否已執行 q_new())，如果不存在則結束執行

檢查佇列是否有節點，如果沒有則結束執行

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

檢查 K 值是否為合法數值，如果不是則結束執行
```
if (k > size || k < 2)
    return;
```
- 如果 k 值大於佇列長度，則為非法數值
- 如果 k 值等於1，則不需要做交換
- 如果 k 值小於1，則為非法數值

檢查 K 值是否為 2，如果是則執行 q_swap()

if (k == 2) {
    q_swap(head);
    return;
}

如果 k 值等於 2，效果等同執行 q_swap()(兩兩交換)

`q_sort`

完整程式碼

void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    int counter = 0;
    int mid = q_size(head) / 2 - 1;

    struct list_head *cut = head->next;

    while (counter != mid) {
        cut = cut->next;
        counter++;
    }

    struct list_head head1;
    struct list_head head2;

    INIT_LIST_HEAD(&head1);
    INIT_LIST_HEAD(&head2);

    list_splice_tail(head, &head2);
    list_cut_position(&head1, &head2, cut);
    INIT_LIST_HEAD(head);

    q_sort(&head1, descend);
    q_sort(&head2, descend);

    const char *str1 = NULL;
    const char *str2 = NULL;

    struct list_head *tmp;
    struct list_head *cur1 = (&head1)->next;
    struct list_head *cur2 = (&head2)->next;

    while (cur1 != &head1 && cur2 != &head2) {
        str1 = list_entry(cur1, element_t, list)->value;
        str2 = list_entry(cur2, element_t, list)->value;

        if (descend) {
            if (strcmp(str1, str2) >= 0) {
                tmp = cur1;
                cur1 = cur1->next;
            } else {
                tmp = cur2;
                cur2 = cur2->next;
            }
        } else {
            if (strcmp(str1, str2) <= 0) {
                tmp = cur1;
                cur1 = cur1->next;
            } else {
                tmp = cur2;
                cur2 = cur2->next;
            }
        }
        list_del(tmp);
        list_add_tail(tmp, head);
    }

    list_splice_tail(&head1, head);
    list_splice_tail(&head2, head);
}

實作說明

以 merge sort 演算法進行實作
將佇列由中點分割為兩個部分，並對每個子佇列遞迴使用 merge sort，直到佇列長度等於 1。使用兩個指標從兩個子佇列標頭節點分別向後走訪，比較當前節點值大小，並依據 descend 對節點做排序，重複比較直到其中一個佇列的所有節點合併完成，最後再將剩餘的另一個佇列加到已排序好的佇列後方。

使用 q_size()/2 計算佇列的中點索引
使用 list.h 中的 list_empty() 檢查佇列是否為空
使用 list.h 中的 list_is_singular() 檢查佇列是否只包含一個節點
使用 list.h 中的 list_del() 來移除指定節點
使用 list.h 中的 INIT_LIST_HEAD() 初始化節點
使用 list.h 中的 list_splice_tail() 將一佇列的所有節點移動到另一佇列的後方
使用 list.h 中的 list_add_tail() 來將指定節點移動到指定節點後方
使用 list.h 中的 list_cut_position() 將佇列分割為兩個子佇列
使用 list.h 中的 list_entry() 取得對應節點
使用 strcmp() 比較兩個節點的 value 是否相同 (等於 0 時相同)

特殊狀況處理

檢查標頭節點 head 是否存在 (是否已執行 q_new())，如果不存在則結束執行
檢查佇列是否有節點，如果沒有或只有一個節點 (只有一個無法進行交換) 則結束執行
```
if (!head || list_empty(head) || list_is_singular(head))
    return;
```

節點比較

如果排序方法為 descend (descend == true)，則刪除當前比較節點中的最大值
如果排序方法為 ascend (descend == false)，則刪除當前比較節點中的最小值

問題紀錄

實作方式採用遞迴對佇列作分割 (呼叫 q_sort())，因為 q_sort() 的第一個參數為一指向佇列的標頭節點 (struct list_head *head)，所以需要額外串接一個 list_head 標頭節點到子佇列上。因為本題無法使用 malloc() 來，所以需要將原佇列的 head 節點串接到子佇列上才能使用 q_sort()。

因為使用了比較暴力了方法來將標頭節點串接到子佇列上 (只對第一個節點和標頭節點做串接)，所以串接後的子佇列就不是一個雙向環狀鏈結串列了。因此也沒辦法使用 list_splice_tail 函式，只能使用迴圈逐個串接節點。

(已解決) ⭢ 使用靜態宣告的方式宣告兩個暫時的標頭節點

宣告兩個暫時的標頭節點 head1 和 head2，用來串接分割的兩個子佇列 (作為子佇列的標頭節點)，以利佇列遞迴呼叫 q_sort()

因為有標頭節點的存在，所以可以直接使用 list_splice_tail 函式直接將剩餘的子佇列所有節點直接接到已排序好的佇列後方 (取代原先使用迴圈逐個搬動節點)

原程式碼 (使用搬動 head 節點的方式)

void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    int counter = 0;
    int half = q_size(head) / 2;

    const char *str1 = NULL;
    const char *str2 = NULL;

    struct list_head *tmp;
    struct list_head *cur1;
    struct list_head *cur2;

    struct list_head *cut = head->next;

    while (counter != half) {
        cut = cut->next;
        counter++;
    }

    tmp = head->prev;

    head->prev = cut->prev;
    cut->prev->next = head;
    q_sort(head, descend);
    cur1 = head->next;

    head->prev = tmp;
    head->next = cut;
    cut->prev = head;
    tmp->next = head;
    q_sort(head, descend);
    cur2 = head->next;

    INIT_LIST_HEAD(head);

    while (cur1 != head && cur2 != head) {
        str1 = list_entry(cur1, element_t, list)->value;
        str2 = list_entry(cur2, element_t, list)->value;

        if (descend) {
            if (strcmp(str1, str2) >= 0) {
                tmp = cur1;
                cur1 = cur1->next;
            } else {
                tmp = cur2;
                cur2 = cur2->next;
            }
        } else {
            if (strcmp(str1, str2) <= 0) {
                tmp = cur1;
                cur1 = cur1->next;
            } else {
                tmp = cur2;
                cur2 = cur2->next;
            }
        }
        list_add_tail(tmp, head);
    }

    while (cur1 != head) {
        tmp = cur1;
        cur1 = cur1->next;
        list_add_tail(tmp, head);
    }

    while (cur2 != head) {
        tmp = cur2;
        cur2 = cur2->next;
        list_add_tail(tmp, head);
    }
}

在比較兩佇列的節點值時，會出現其中一個佇列的節點先被移除完的情況，這時就無法繼續執行節點值的比較
- 如果是佇列1的節點先被移除完 ➩ 將佇列2的剩餘節點依序移動到已排序佇列
- 如果是佇列2的節點先被移除完 ➩ 將佇列1的剩餘節點依序移動到已排序佇列
因為上述兩種狀況皆可能發生，所以需要額外的判斷式來檢查哪個佇列才是已完全移除的佇列。
(已解決) ⭢ 移除 if 條件判斷

在重新查看 list.h 中的 list_splice_tail 函式後，注意到函式內有著這一段程式:
```
static inline void list_splice_tail(struct list_head *list, struct list_head *head)
{
    struct list_head *head_last = head->prev;
    ...
        
    // ⭣
    if (list_empty(list))
        return;

    ...
}
```
可以發現輸入的佇列如果為空，就會直接結束函式的執行。
因此這一部分的檢查是可以直接省略的。

`q_ascend`

程式碼

完整程式實作

int q_ascend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    struct list_head *tmp;
    struct list_head *cur = head->prev;

    char *min = strdup(list_entry(cur, element_t, list)->value);

    while (cur != head) {
        tmp = cur;
        cur = cur->prev;

        if (strcmp(list_entry(tmp, element_t, list)->value, min) > 0) {
            list_del(tmp);
            q_release_element(list_entry(tmp, element_t, list));
        } else {
            free(min);
            min = strdup(list_entry(tmp, element_t, list)->value);
        }
    }
    free(min);

    return q_size(head);
}

實作說明

由佇列最後一個節點 (head->prev) 向前走訪，並以最一個節點值作為整個佇列的最大值
佇列的每個節點值都必須小於左側的每一個節點值

使用 strdup() 配置一個空間來紀錄當前檢查到的當前最小值
使用 list.h 中的 list_empty() 檢查佇列是否為空
使用 list.h 中的 list_entry() 取得對應節點
使用 list.h 中的 list_del() 來移除指定節點
使用 queue.h 中的 q_release_element() 釋出記憶體空間
使用 free() 移除已配置的空間
使用 q_size() 計算最終佇列的長度

節點比較

如果當前節點 (tmp) 小於等於當前紀錄最小值節點值 (min)，則將最小節點值更新為當前節點值 (tmp = min)
如果當前節點 (tmp) 大於當前紀錄最小值節點值 (min)，則刪除當前節點

特殊狀況處理

檢查標頭節點 head 是否存在 (是否已執行 q_new())，如果不存在則回傳 0

檢查佇列是否有節點，如果沒有則回傳 0

if (!head || list_empty(head))
    return 0;

`q_descend`

程式碼

完整程式實作


























int q_descend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    struct list_head *tmp;
    struct list_head *cur = head->prev;

    char *max = strdup(list_entry(cur, element_t, list)->value);

    while (cur != head) {
        tmp = cur;
        cur = cur->prev;

        if (strcmp(list_entry(tmp, element_t, list)->value, max) < 0) {
            list_del(tmp);
            q_release_element(list_entry(tmp, element_t, list));
        } else {
            free(max);
            max = strdup(list_entry(tmp, element_t, list)->value);
        }
    }
    free(max);

    return q_size(head);
}

實作說明

由佇列最後一個節點 (head->prev) 向前走訪，並以最一個節點值作為整個佇列的最小值
佇列的每個節點值都必須大於左側的每一個節點值

程式邏輯和 q_ascend() 相同，差別在於 q_descend() 刪除的是比當前紀錄最大節點值 (max) 大的節點

`q_merge`

程式碼

完整程式實作

int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return 0;

    if (list_is_singular(head))
        return q_size(list_entry(head->next, queue_contex_t, chain)->q);

    int total = 0;
    struct list_head result;
    struct list_head *cur = head->next;

    INIT_LIST_HEAD(&result);

    while (cur != head) {
        total += list_entry(cur, queue_contex_t, chain)->size;
        cur = cur->next;
    }

    for (int i = 0; i < total; i++) {
        cur = head->next;

        while (list_empty(list_entry(cur, queue_contex_t, chain)->q) &&
               cur != head)
            cur = cur->next;

        queue_contex_t *context_cur = list_entry(cur, queue_contex_t, chain);
        queue_contex_t *context_max = list_entry(cur, queue_contex_t, chain);
        queue_contex_t *context_min = list_entry(cur, queue_contex_t, chain);

        const element_t *element_cur;
        const element_t *element_max =
            list_entry(context_cur->q->next, element_t, list);
        const element_t *element_min =
            list_entry(context_cur->q->next, element_t, list);

        while (cur != head) {
            context_cur = list_entry(cur, queue_contex_t, chain);

            if (context_cur->size != 0) {
                element_cur = list_entry(context_cur->q->next, element_t, list);

                if (descend) {
                    if (strcmp(element_cur->value, element_max->value) > 0) {
                        element_max = element_cur;
                        context_max = context_cur;
                    }
                } else {
                    if (strcmp(element_cur->value, element_min->value) < 0) {
                        element_min = element_cur;
                        context_min = context_cur;
                    }
                }
            }
            cur = cur->next;
        }

        struct list_head *node;

        if (descend) {
            node = context_max->q->next;
            context_max->size--;
        } else {
            node = context_min->q->next;
            context_min->size--;
        }

        list_del(node);
        list_add_tail(node, &result);
    }

    list_splice_tail_init(&result,
                          list_entry(head->next, queue_contex_t, chain)->q);

    int size = q_size(list_entry(head->next, queue_contex_t, chain)->q);
    list_entry(cur, queue_contex_t, chain)->size = size;

    return size;
}

實作說明

使用靜態配置分配一個暫時的標頭節點 (result)。由第一個子佇列向後走訪，比較所有子佇列的第一個節點，並找出當前的最小(大)節點值。找出後將該節點從對應子佇列中移除，並插入到暫時的佇列中，同時將對應子佇列的 size 值減 1。重複比較直到所有節點都已加到暫時的佇列中。最後再將暫時佇列中的所有節點搬動到第一個子佇列。
使用2個 element_t 的指標和2個 queue_contex_t 的指標來記錄當前最小(大)節點以及節點所在的 queue_context

使用 q_size() 計算佇列的長度
使用 list.h 中的 list_empty() 檢查佇列是否為空
使用 list.h 中的 list_is_singular() 檢查佇列是否只包含一個節點
使用 list.h 中的 list_entry() 取得對應節點
使用 list.h 中的 INIT_LIST_HEAD() 初始化節點
使用 list.h 中的 list_del() 來移除指定節點
使用 list.h 中的 list_add_tail() 來將指定節點移動到指定節點後方
使用 list.h 中的 list_splice_tail() 將一佇列的所有節點移動到另一佇列的後方
使用 list.h 中的 list_splice_tail_init() 將一佇列的所有節點移動到另一佇列的後方並初始化原佇列的標頭節點
使用 strcmp() 比較兩個節點的 value 是否相同 (等於 0 時相同)

特殊狀況處理

檢查標頭節點 head 是否存在 (是否已執行 q_new())，如果不存在則回傳 0

檢查是否有子佇列，如果沒有則回傳 0

if (!head || list_empty(head))
    return 0;

檢查是否只有一個子佇列，如果只有一個則回傳子佇列的長度

if (list_is_singular(head))
    return q_size(list_entry(head->next, queue_contex_t, chain)->q);

節點比較

如果排序方法為 descend (descend == true)，則將當前比較節點中的最大節點加入暫時佇列的最尾端，並將最大節點所在的 queue_contex_t 的 size 減 1
如果排序方法為 ascend (descend == false)，則將當前比較節點中的最小節點加入暫時佇列的最尾端，並將最小節點所在的 queue_contex_t 的 size 減 1

make test result

100/100

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

程式碼

實作說明

特殊狀況處理

節點比較

make test result

Read more

2025q1 Homework2 (quiz1+2)

2025q1 Homework1 (ideas)

`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`