changed 22 days ago  
Published Linked with GitHub

2025q1 Homework1 (lab0)

contributed by < ginsengAttack >

作業書寫規範:

  • 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
  • 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
  • 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
  • 不要在筆記內加入 [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
架構：                    x86_64
  CPU 作業模式：          32-bit, 64-bit
  Address sizes:          39 bits physical, 48 bits virtual
  字節序：                Little Endian
CPU:                      16
  CPU 列表：         0-15
供應商識別號：            GenuineIntel
  型號名稱：              Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
    CPU 家族：            6
    型號：                165
    每核心執行緒數：      2
    每通訊端核心數：      8
    座：                  1
    製程：                5
    CPU(s) scaling MHz:   23%
    CPU 最大 MHz：        4800.0000
    CPU 最小 MHz：        800.0000
    BogoMIPS：            5799.77
Virtualization features:  
  虛擬：                  VT-x
Caches (sum of all):      
  L1d:                    256 KiB (8 instances)
  L1i:                    256 KiB (8 instances)
  L2:                     2 MiB (8 instances)
  L3:                     16 MiB (1 instance)
NUMA:                     
  NUMA 節點：             1
  NUMA node0 CPU(s)：     0-15
Vulnerabilities:          
  Gather data sampling:   Mitigation; Microcode
  Itlb multihit:          KVM: Mitigation: VMX disabled
  L1tf:                   Not affected
  Mds:                    Not affected
  Meltdown:               Not affected
  Mmio stale data:        Mitigation; Clear CPU buffers; SMT vulnerable
  Reg file data sampling: Not affected
  Retbleed:               Mitigation; Enhanced IBRS
  Spec rstack overflow:   Not affected
  Spec store bypass:      Mitigation; Speculative Store Bypass disabled via prct
                          l
  Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointe
                          r sanitization
  Spectre v2:             Mitigation; Enhanced / Automatic IBRS; IBPB conditiona
                          l; RSB filling; PBRSB-eIBRS SW sequence; BHI SW loop, 
                          KVM SW loop
  Srbds:                  Mitigation; Microcode
  Tsx async abort:        Not affected

程式碼部份：

圖片

q_new

一開始我寫：

struct list_head *head=malloc(sizeof(struct list_head));
INIT_LIST_HEAD(head);
element_t *node=malloc(sizeof(element_t));
node->list=*head;
return &node->list;

思路是因為我記得在小考的時候有看過， linux核心的鏈節串列結構比較特別，是將 list_head嵌入結構當中，所以我想先建立一個 list_head的指標，然後再把它嵌入到 element_t當中。

element_t *node = malloc(sizeof(element_t));
if (!node) 
    return NULL;
INIT_LIST_HEAD(&node->list);
return &node->list;

後來我想到，只要我建立一個 element_t的空間，裡面自然有一個區塊是用來存 list_head的結構。

element_t *node = malloc(sizeof(element_t));
if (node) 
    INIT_LIST_HEAD(&node->list);
return &node->list;

然後過程中，一開始我的指標是指向 NULL，查看 queue.h 才知道具體格式，上述的程式碼是在同學建議下簡化的

有些網路上的寫法（同學看的），這邊都直接創立一個 list_head 節點而已，我覺得這是不太對的，這樣子佇列就只是無意義串接的鍊結串列而已，連存值的地方都沒有。

struct list_head *new = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(new);
return new;

搞錯了，我自作聰明，第一個指標不需要存值。

q_free

嘗試：

if (head) {
    struct list_head *del = NULL;
    struct list_head *pos;
    for(pos = head->next; pos!=head ; pos=pos->next){
        if (del) 
            free(list_entry(del,element_t,list));
        del=pos;
    }
}
if (head) 
    free(list_entry(head,element_t,list));

我知道要用 list_for_each 系列寫，先用熟悉的方法嘗試看看邏輯

目前看來是可以運行的，但是因為只有創建單個元素的節點，所以還不能完全確定是完善的。

struct list_head *pos = head->next;
while (pos != head) {
    pos = head->next;
    list_del(pos);
    element_t *node = list_entry(pos, element_t, list);
    free(node);
}
free(head);

這邊我發現自己對 head 的理解有問題，所以更新了一下程式碼，把想要刪除的節點先從佇列 "remove" 掉，然後再釋放記憶體空間。

結果顯示我還有空間未釋放，這邊我剛剛更新了 insert 的程式碼，所以我記得我有特別幫新節點的字串分配空間，如果釋放節點的空間，我只會將其中的 list head 和 "指向 string 的指標"刪除， string 本身還會存在，所以我也要先刪除 string 本身。

我在進行 new 測試的時候一直有問題，而且問題是出在釋放記憶體空間的時候，後來發現是沒有檢測 head 是否為空:

if (!head)
    return;

q_insert_head

element_t *node = malloc(sizeof(element_t));
node->value = s;
(node->list).next = *head;
(node->list).prev = (*head)->prev;
(*head)->prev = &node->list;
*head = &node->list;
if (!node) 
    return false;
else
    return true;

程式碼有誤，但是我還沒想明白怎更改 head 的位置，我直覺傳入的參數應該要是 list_head** 但不能修改這邊，所以之後再想想看辦法。

element_t *node = malloc(sizeof(element_t));
node->value = s;
list_add(&node->list,head);
return true;

我明白我錯哪裡了，跟剛剛前面 queue new 遇到的問題一樣，是加在 head 的後面。

但還是會遇到問題：

ERROR: Need to allocate and copy string for new queue element

我想過要先分配新空間，但是還是有一樣的狀況，最後發現問題出在對字串指標的處理，因為我直接指向傳入參數 s 的話，就沒有幫節點新增空間，所以最終使用 strdup 分配新空間給字串就好：

if (!head)
    return false;
element_t *node = malloc(sizeof(element_t));
node->value = strdup(s);
list_add(&node->list,head);
return true;

最終測試有問題，看測試命令應該是故意讓記憶體的配置出錯，所以我重點關注記憶體配置出錯的處理， strdup 本身也是記憶體分配的函式所以不能忽視。

最終是在同學提示下我才找到真正的問題點，我配置 element_t 失誤的話回傳 false 當然就沒問題，但是如果是在配置 node value 的時候失誤， element_t 卻還會存在，必須釋放。

if (!node->value) {
    free(node);
    return false;
}

q_insert_tail

element_t *tail = malloc(sizeof(element_t));
tail->value = s;
head->prev->next = &tail->list;
(tail->list).prev = head->prev;
head->prev = &tail->list;
(tail->list).next = head;
return true;

一開始我先用自己的方式寫，但是只有在加入第一個節點的時候不會有問題，所以我改用提供的 API 實做看看：

element_t *tail = malloc(sizeof(element_t));
tail->value = s;
list_add_tail(&tail->list,head);
return true;

還是有錯，問題和前一個相同，不贅述：

if (!head)
    return false;
element_t *node = malloc(sizeof(element_t));
node->value = strdup(s);
list_add_tail(&node->list, head);
return true;

q_remove_head

struct list_head *pos = NULL;
for (pos = head->next;pos != head;pos=pos->next) {
    if (strncmp(list_entry(pos,element_t,list)->value,sp,bufsize) == 0){
        list_del(pos);
        free(list_entry(pos,element_t,list)->value);
        free(list_entry(pos,element_t,list));
    }
}
return NULL;

一開始看不太懂，想說就是刪掉字串為 sp 的節點，不懂要回傳啥，感覺有點矛盾，但是他是說 "remove" ，好像跟回傳值不衝突，而且要回傳是 node ，同時不用釋放節點才對：

if (!head || head->next == head)
    return NULL;
element_t *node = list_entry(head->next, element_t, list);
strncpy(sp, node->value, bufsize);
list_del(&node->list);
return node;

這邊寫的時候還有遇到 string copy 的用法錯誤、忘記刪除節點。

後來測試的時候出現錯誤，錯誤大概是指要刪除的字串是 apple ，但讀到的卻是 apple_xxxxxx… 很明顯是結束字元的問題， strncopy 沒辦法把結束字元也複製，所以把 buffsize 減去一，然後手動在最後加上 '\0':

strncpy(sp, node->value, bufsize - 1);
sp[bufsize - 1] = '\0';

q_delete_mid

我有寫過這題 leetcode :
image
用指標的指標完成的，但是這個函數的部份好像用不到這個技巧，所以我直接寫：

struct list_head *slow = head->next;
const struct list_head *pos;
for (pos = head->next; pos->next != head && pos->next->next != head;
        pos = pos->next->next)
    slow = slow->next;
list_del(slow);
free(list_entry(slow, element_t, list)->value);
free(list_entry(slow, element_t, list));
return true;

沒啥難度，用快慢指標，快的走兩步慢的走一步，當快的走到盡頭慢的自然走到一半。

好像也可以用一個往前一個往右的方式寫，但是速度應該不會比較快，所以不改。

q_swap

struct list_head **cur = &head->next;
struct list_head *nex;
for (; *cur != head && (*cur)->next != head; cur = &(*cur)->next->next) {
    nex = (*cur)->next;
    (*cur)->next = nex->next;
    nex->next = *cur;
    nex->prev = (*cur)->prev;
    (*cur)->prev = nex;
    *cur = nex;
}

這題我用間接指標實做，讓 current 和 next 兩個指標做交換，接著 current 往後兩步。

我還有想到一個方法，就是把一個節點先 remove 後，再把它加入到後面，可以直接通過調取 API 來實現這段程式碼，但是也沒有比較快。

測試結果有誤，看了很久沒想到是 swap 的問題，然後仔細看了一下，發現是向前指標出錯了，假設我要將1.2.3三個節點做 swap，我的3沒有把 prev 改成1。

nex->next->prev = *cur;

加在迴圈內的第三行。

q_reverse

struct list_head *first = head->next;
list_move_tail(first,head);
for (struct list_head *pos = head->next;pos != first;){
    list_move_tail(pos,head);
    pos = head->next;
}

想說把每個節點丟到最後面，結果輸出的佇列完全沒變，才發現邏輯有錯，應該是從最後一個節點開始把所有的節點依序丟到最後，或者乾脆改從第一個節點開始把節點一須丟到最前面:

struct list_head *cur = head->next,*nex;
for(nex = cur->next;cur != head;) {
    list_move(cur,head);
    cur = nex;
    nex = cur->next;
}

q_sort

我先試著使用泡沫排序來實做，參考整數的排序法：

for(int i=0;i<sort.size();i++){
    for(int j=0;j<sort.size()-1;j++){
        if(sort[j]>sort[j+1])
            swap(sort[j],sort[j+1]);
    }
}

這邊要考慮到，我是 j 和 j+1 做交換，所以要注意範圍，一開始就是這部份沒注意到所以出錯了，然後我使用 list move 實做出：

for (int i=0;i<q_size(head)+1;i++){
        for(struct list_head *pos=head->next;pos->next != head;){
            if (list_entry(pos,element_t,list)->value > list_entry(pos->next,element_t,list)->value) {
                list_move(pos->next,pos);
            }else 
                pos = pos->next;
        }
    }

很明顯我誤會 list move的用法了，把它當成純粹的 swap 在用，所以我這段操作完全沒意義，所以我又修改：

for (int i=0;i<q_size(head);i++){
    for(struct list_head *pos=head->next;pos->next != head;){
        if (list_entry(pos,element_t,list)->value > list_entry(pos->next,element_t,list)->value) 
            list_move(pos,pos->next);
        else 
            pos = pos->next;
    } 
}

我一開始以為 move 功能是把 node 加到 head 前面，所以寫 list_move(pos,pos->next) ，又發現前面的參數才是 node 所以改成相反，然後又發現他是將 node 加到 head之後，所以 pos->next 才是 head ，又改相反。

但是測試的時候發現一直有問題，最後知道是字串比較的部份出錯，所以改用 strcmp 解決：

for (int i=0;i<q_size(head);i++){
    for(struct list_head *pos=head->next;pos->next != head;){
        if (strcmp(list_entry(pos,element_t,list)->value,list_entry(pos->next,element_t,list)->value)>0) 
            list_move(pos,pos->next);
        else 
            pos = pos->next;
    } 
}

之後改成 merge sort:

void q_sort(struct list_head *head, bool descend)
{
    struct list_head *list = head->next;
    list_del(head);
    list = merge_sort(list);
    list_add_tail(head,list);
}

struct list_head* merge_sort(struct list_head *head) 
{
    int len = q_size(head);
    if (len<=1) {
        if (len == 0) 
            return head;
        else if (strcmp(list_entry(head, element_t, list)->value,
                   list_entry(head->next, element_t, list)->value) > 0) {
            list_move(head,head->next);
            return head->next;
        }
        return head;
    }
    struct list_head *list1 = head;
    struct list_head *list2 = head;
    for (int i = len / 2; i >= 0; i--)
        list2 = list2->next;
    struct list_head *tmp = list2->prev;
    list2->prev = list1->prev;
    list1->prev = tmp;
    list1->prev->next = list1;
    list2->prev->next = list2;
    list1 = merge_sort(list1);
    list2 = merge_sort(list2);
    struct list_head *trace1 = list1;
    struct list_head *trace2 = list2;
    bool list1_bool = false,list2_bool = false;
    head = strcmp(list_entry(list1,element_t,list)->value,
    list_entry(list2,element_t,list)->value) < 0 ? list1:list2;
    do {
        if (trace1 == head && list1_bool) {
            struct list_head *tmp = trace2;
            trace2 = trace2->next;
            list_add_tail(tmp, trace1);
            list2_bool = true;
        }else if (strcmp(list_entry(trace1, element_t, list)->value,
                          list_entry(trace2, element_t, list)->value) <= 0) {
            trace1 = trace1->next;
            list1_bool = true;
        }else {
            struct list_head *tmp = trace2;
            trace2 = trace2->next;
            list_add_tail(tmp, trace1);
            list2_bool = true;
        }
    }while(trace2 != list2 || !list2_bool);
    return head;
}

程式有點亂，會想辦法精簡。

程式碼的判斷有問題，我將佇列分割成兩段之後，會選擇兩個新佇列首個元素最小的作為 head ，既是回傳值，又是走訪第一個佇列的中止條件，但是如果兩個佇列首元素一樣大，我一開始會優先把第二個佇列的首元素設置成 head，但是後續把兩個佇列合併的時候，我卻會優先把佇列一的元素放入合併完成的佇列。

這樣首元素一樣大的時候，我會把佇列二的首元素設置成 head 實際上的 head 卻是佇列一的。

再次精簡程式碼， merge_two ：

void merge_two(struct list_head *list1, struct list_head *list2)
{
    struct list_head *list1_pos = list1->next;
    for (struct list_head *pos = list2->next;pos != list2 ;) {
        if (list1_pos != list1 && strcmp(list_entry(list1_pos,element_t,list)->value,list_entry(pos,element_t,list)->value) < 0) 
            list1_pos = list1_pos->next;
        else {
            struct list_head *add = pos;
            pos = pos->next;
            list_del(add);
            list_add_tail(add,list1_pos);
        }
    }
}

if (!head || list_empty(head) || head->next->next == head)
    return;

struct list_head *list2 = head;
struct list_head *fast = head->next;
while (fast != head && fast->next != head) {
    list2 = list2->next;
    fast = fast->next->next;
}

struct list_head left;
list_cut_position(&left, head, list2);
q_sort(head,descend);
q_sort(&left,descend);
merge_two(head,&left);

改成用上面兩段就可以清楚的達到要求。

q_delete_dup

if (!head || head->next == head) 
        return false;
q_sort(head,false);
struct list_head **cur = &head->next;
while ((*cur)->next != head && *cur != head){
    if(strcmp(list_entry(*cur,element_t,list)->value,list_entry((*cur)->next,element_t,list)->value) == 0){
        struct list_head *tmp = (*cur)->next;
        while (tmp != head && strcmp(list_entry(tmp,element_t,list)->value,list_entry(*cur,element_t,list)->value) == 0)
            tmp = tmp->next;
        *cur = tmp;
        } else 
            cur = &(*cur)->next;
    }

return true;

輸出結果正確，但是顯示錯誤，我推測是因為沒釋放記憶體？或是指標沒處理好？

if (!head || head->next == head)
    return false;
q_sort(head, false);
struct list_head **cur = &head->next;
while ((*cur)->next != head && *cur != head) {
    if (strcmp(list_entry(*cur, element_t, list)->value,
                   list_entry((*cur)->next, element_t, list)->value) == 0) {
        struct list_head *tmp = (*cur)->next;
        while (tmp != head &&
                   strcmp(list_entry(tmp, element_t, list)->value,
                          list_entry(*cur, element_t, list)->value) == 0) {
                struct list_head *del = tmp;
                tmp = tmp->next;
                list_del(del);
                free(list_entry(del, element_t, list)->value);
                free(list_entry(del, element_t, list));
            }
            struct list_head *del = *cur;
            tmp->prev = (*cur)->prev;
            *cur = tmp;
            free(list_entry(del, element_t, list)->value);
            free(list_entry(del, element_t, list));
        } else
            cur = &(*cur)->next;
    }
return true;

我稍微調整了一下，但還是有錯。

有人說我的程式碼很醜，待改。

q_ascend

這題沒啥難度， leetcode 很快就解出來了，但是實做一直有問題：

if (!head || list_empty(head))
        return 0;
int number = 1;
char *s = list_entry(head->prev, element_t, list)->value;
for (struct list_head *pos = head->prev; pos != head; pos = pos->prev) {
    if (strcmp(s, list_entry(pos, element_t, list)->value) < 0)
            list_del(pos);
    else {
            s = list_entry(pos, element_t, list)->value;
            number++;
    }
}
return number;

主要問題是出在 list_del 那行，參考函式內部邏輯：

#ifdef LIST_POISONING
    node->next = NULL;
    node->prev = NULL;
#endif

我本來以為受刪除節點的 next 跟 prev 還會串接在原處，所以沒有進行特別的處理，導致發生問題，然後同時還必須把刪除的節點空間釋放掉：

if (!head || list_empty(head))
    return 0;
int number = 0;
char *s = list_entry(head->prev, element_t, list)->value;
for (struct list_head *pos = head->prev; pos != head;) {
    if (strcmp(s, list_entry(pos, element_t, list)->value) < 0) {
        struct list_head *del = pos;
        pos = pos->prev;
        list_del(del);
        free(list_entry(del,element_t,list)->value);
        free(list_entry(del,element_t,list));
    }else {
        s = list_entry(pos, element_t, list)->value;
        number++;
        pos = pos->prev;
    }
}
return number;

q_reverseK

這題我想用 reverse 的函數來寫，把程式碼分割之後一個一個丟進函數中再連接起來，函數的邏輯跟之前寫的 q_reverse 相同，但是因為丟入函數的佇列不會有 head ，所以一開始以為會有點麻煩，後來仔細想想，佇列的第一個元素根本不用做操作，所以從第二個元素開始走訪就好。

程式碼：

void reverse(struct list_head *head,struct list_head *tail)
{
    struct list_head *left = head;
    tail = tail->next;
    do {
        struct list_head *tmp = head->next;
        list_del(head->next);
        list_add_tail(tmp,left);
        left = left->prev;
    }while (head->next != tail);
}
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (k==1 || !head || head->next == head)
        return;
    for (struct list_head *pos = head->next;pos != head;) {
        struct list_head *tail = pos;
        for (int i = 0;i < k-1;i++) {
            tail = tail->next;
            if (tail == head) 
                return;
        }
        reverse(pos,tail);
        pos = pos->next;
    }
}

依次把 head 的下一個節點丟到最左邊，直到 tail 。

遇到兩個困難，一開始我用 list_add_tail 但是要先刪除節點，所以我用 list_move 的概念實做：

struct list_head *tmp = head->next;
list_del(head->next);
list_add_tail(tmp,left);

第二個問題，我沒有把 pos 指標處理好，我用 pos 指標和 tail 指標分別表示開頭跟結尾，假設要兩兩反轉1->2->3->4，我的指標會先在1跟2兩個位置，反轉完之後，我設置 :
pos=tail->next
希望 pos 指標能從2移動到3，但是由於我已經成功反轉了1跟2，所以指向1的 pos 指標還是指在1而 tail 也還是指向2，所以 tail 的 next 又會跑回1，應該設置 pos 的 next 就好，因為 pos 此刻必然在這一段排序好的佇列的最後一個位置。

q_merge

把之前merge sort 當中的 merge 分離出來寫成獨立的 fuction merge two：

struct list_head *head;
head = strcmp(list_entry(list1, element_t, list)->value,
                  list_entry(list2, element_t, list)->value) <= 0
               ? list1
               : list2;
struct list_head *trace1 = list1;
struct list_head *trace2 = list2;
bool list1_bool = false, list2_bool = false;
do {
    if (trace1 == head && list1_bool) {
        struct list_head *tmp2 = trace2;
        trace2 = trace2->next;
        list_add_tail(tmp2, trace1);
        list2_bool = true;
    } else if (strcmp(list_entry(trace1, element_t, list)->value,
                         list_entry(trace2, element_t, list)->value) <= 0) {
        trace1 = trace1->next;
        list1_bool = true;
    } else {
        struct list_head *tmp2 = trace2;
        trace2 = trace2->next;
        list_add_tail(tmp2, trace1);
        list2_bool = true;
    }
} while (trace2 != list2 || !list2_bool);
    return head;

有錯的程式碼：

if (!head || head->next == head)
        return 0;   
    else if (head->next->next == head)  
        return q_size(list_entry(head->next,queue_contex_t,chain)->q);
    int num = q_size(head);
    int firstPos = 0;
    struct list_head *first = NULL;
    struct list_head *tail;
    for (struct list_head *pos = head->next; pos != head; pos = pos->next) {
        if (list_entry(pos,queue_contex_t,chain)->q->next != list_entry(pos,queue_contex_t,chain)->q) {
            first = list_entry(pos,queue_contex_t,chain)->q->next;
            list_del(list_entry(pos,queue_contex_t,chain)->q);
            if (pos != head->next) //this 2
                list_entry(pos,queue_contex_t,chain)->q = NULL;
            break;
        }else if (pos != head->next)
            list_entry(pos,queue_contex_t,chain)->q = NULL;//this 3
        firstPos++;
    }
    if (!first || firstPos == num)
        return 0;
    tail = first->next;
    for (int i = firstPos+1;i < num; i++) {
        if (list_entry(tail,queue_contex_t,chain)->q->next == list_entry(tail,queue_contex_t,chain)->q) {
            list_entry(tail,queue_contex_t,chain)->q = NULL;//this 4
            continue;
        }
        struct list_head *link = list_entry(tail,queue_contex_t,chain)->q->next;
        list_del(list_entry(tail,queue_contex_t,chain)->q);
        list_entry(tail,queue_contex_t,chain)->q = NULL;
        first = merge_two(first,link);
        tail = tail->next;
    }
    list_add_tail(list_entry(head->next,queue_contex_t,chain)->q,first);//this 1
    if (descend) 
        q_reverse(head);
    return q_size(list_entry(head->next,queue_contex_t,chain)->q);//this 5

走投無路，但突然發現有一個 size 欄位根本沒用到，所以我的很多判斷都可以簡化，然後應該也要更新 size 值：

if (!head || head->next == head)
        return 0;   
    else if (head->next->next == head)  
        return list_entry(head->next,queue_contex_t,chain)->size;
    int num = q_size(head);
    int firstPos = 0;
    int totalSize = 0;
    struct list_head *first = NULL;
    struct list_head *tail;
    for (struct list_head *pos = head->next; pos != head; pos = pos->next) {
        if (list_entry(pos,queue_contex_t,chain)->size != 0) {
            first = list_entry(pos,queue_contex_t,chain)->q->next;
            totalSize = list_entry(pos,queue_contex_t,chain)->size;
            list_del(list_entry(pos,queue_contex_t,chain)->q);
            if (pos != head->next) //this 2
                list_entry(pos,queue_contex_t,chain)->q = NULL;
            break;
        }else if (pos != head->next)
            list_entry(pos,queue_contex_t,chain)->q = NULL;//this 3
        firstPos++;
    }
    if (!first || firstPos == num)
        return 0;
    tail = first->next;
    for (int i = firstPos+1;i < num; i++) {
        if (list_entry(tail,queue_contex_t,chain)->size == 0) {
            list_entry(tail,queue_contex_t,chain)->q = NULL;//this 4
            continue;
        }
        struct list_head *link = list_entry(tail,queue_contex_t,chain)->q->next;
        list_del(list_entry(tail,queue_contex_t,chain)->q);
        list_entry(tail,queue_contex_t,chain)->q = NULL;
        totalSize += list_entry(tail,queue_contex_t,chain)->size;
        list_entry(tail,queue_contex_t,chain)->size = 0;
        first = merge_two(first,link);
        tail = tail->next;
    }
    list_add_tail(list_entry(head->next,queue_contex_t,chain)->q,first);//this 1
    if (descend) 
        q_reverse(head);
    list_entry(head->next,queue_contex_t,chain)->size = totalSize;
    return totalSize;//this 5

但還是錯。真的沒想法了，請 grok 幫我看一下問題：

tail = first->next;//wrong

我明明是把 first 設置成第一個非空佇列的第一個非 head 元素，而 tail 則應該用來走訪每一個佇列，而不是佇列的節點，所以加入：

tail = pos->next;

還有我想透過 q_reverse 生成遞減佇列，但是我不應該是把佇列的列表反轉，而是反轉佇列本身才對：

q_reverse(list_entry(head->next,queue_contex_t,chain)->q);

改正後問題從：

# Test of insert_head, insert_tail, remove_head, reverse and merge
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer

變成：

ERROR: Freed queue, but 2 blocks are still allocated

此時的程式碼：

if (!head || head->next == head)
        return 0;   
    else if (head->next->next == head)  
        return list_entry(head->next,queue_contex_t,chain)->size;
    int num = q_size(head);
    int firstPos = 0;
    int totalSize = 0;
    struct list_head *first = NULL;
    struct list_head *tail;
    for (struct list_head *pos = head->next; pos != head; pos = pos->next) {
        if (list_entry(pos,queue_contex_t,chain)->size != 0) {
            first = list_entry(pos,queue_contex_t,chain)->q->next;
            totalSize = list_entry(pos,queue_contex_t,chain)->size;
            list_del(list_entry(pos,queue_contex_t,chain)->q);
            tail = pos->next;
            if (pos != head->next) //this 2
                list_entry(pos,queue_contex_t,chain)->q = NULL;
            break;
        }else if (pos != head->next)
            list_entry(pos,queue_contex_t,chain)->q = NULL;//this 3
        firstPos++;
    }
    if (!first || firstPos == num)
        return 0;
    for (int i = firstPos+1;i < num; i++) {
        if (list_entry(tail,queue_contex_t,chain)->size == 0) {
            list_entry(tail,queue_contex_t,chain)->q = NULL;//this 4
            continue;
        }
        struct list_head *link = list_entry(tail,queue_contex_t,chain)->q->next;
        list_del(list_entry(tail,queue_contex_t,chain)->q);
        list_entry(tail,queue_contex_t,chain)->q = NULL;
        totalSize += list_entry(tail,queue_contex_t,chain)->size;
        list_entry(tail,queue_contex_t,chain)->size = 0;
        first = merge_two(first,link);
        tail = tail->next;
    }
    list_add_tail(list_entry(head->next,queue_contex_t,chain)->q,first);//this 1
    if (descend) 
        q_reverse(head);
    list_entry(head->next,queue_contex_t,chain)->size = totalSize;
    return totalSize;//this 5

雖然測資沒有第一個佇列是空的，但這段程式碼是可以避免前面佇列是空的的問題。

然後我發現問題點了：題目要求將非第一個佇列皆設置為"空佇列"，並非"NULL" 所以我一直把指標直接設置成 NULL 完全是錯誤的，所以它才會一直跳出有記憶體空間沒有被刪除，我推測可能是外部函式尋找後面的空佇列進行釋放的時候，因為我設置成 NULL 所以節點沒辦法被找到進而無法刪除，我規格沒看清楚，卡了超級久。

接著，我把 merge sort 的 merge two 擷取出來變成一個 function ，然後交給 merge 使用，並且我改善了 merge sort的實做方式，不用切開 head:

if (!head || head->next == head)
    return 0;
else if (head->next->next == head)
    return list_entry(head->next, queue_contex_t, chain)->size;
struct list_head *first = list_entry(head->next,queue_contex_t,chain)->q;
for (struct list_head *pos = head->next->next;pos != head;pos = pos->next) {
if(list_entry(pos,queue_contex_t,chain)->size != 0) {
        merge_two(first,list_entry(pos,queue_contex_t,chain)->q);
        list_entry(head->next,queue_contex_t,chain)->size += list_entry(pos,queue_contex_t,chain)->size;
        list_entry(pos,queue_contex_t,chain)->size = 0;
    }       
}
return list_entry(head->next,queue_contex_t,chain)->size;

shuffle


    int len = q_size(head);
    for (struct list_head *pos = head->prev ; len > 1 ;len--) {
        int rand = rand()%(len - 1 + 1) + 1;
        struct list_head *swap = head;
        while (rand != 0) {
            rand--;
            swap = swap->next;
        }
        struct list_head *record = pos->prev;
        list_del(pos);
        list_add_tail(pos,swap);
        list_del(swap);
        list_add(swap,record);
        pos = record;
    }
Select a repo