2024q1 Homework1 (lab0)

contributed by < 164253 >

Reviewed by 96121503

• q_insert_head 中提到，沒有檢查 node 及 val 是否為空和有檢查的情況，可以補上兩種情況計算速度的比較結果。

後來發現不檢查會造成錯誤的記憶體釋放，因此不用測試這種錯誤作法

開發環境

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

空間滿了所以沒裝雙系統 所以我是 windows10 的 WSL2

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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) i5-10210U CPU @ 1.60GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            12
    BogoMIPS:            4224.00

實作指定佇列操作

目前本機 100 分， git push 後僅有 95 分，無法通過第 17 筆的常數複雜度測試

q_new

配置一個 list_head ，如果沒有空間要繼續嘗試直到成功
接著用 INIT_LIST_HEAD 初始化並回傳 list_head

q_free

用 list_for_each_entry_safe 走訪所有節點，由於要刪除遇到的節點，所以用 safe 版
將途經節點的字串及節點本身釋放掉 最後釋放 head

q_insert_head

配置一個 element_t 並用 strdup 處理字串配置
原本跳過 node 和 val 記憶體配置失敗的情況，但會造成錯誤的釋放記憶體

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *node = malloc(sizeof(element_t));
    char *val = strdup(s);
-   if (!node || !val || !head) {
-       free(node);
-       free(val);
-       return false;
-   }
-   node->value = val;
-   list_add(&node->list, head);
-   return true;
    
+   bool flag = false;
+   if (head && node && val) {
+       node->value = val;
+       list_add(&node->list, head);
+       flag = true;
+   } else {
+       if (node)
+           free(node);
+       if (val)
+           free(val);
+   }
+   return flag;
}

若 node, val, head 中記憶體有問題，釋放掉已經配置的記憶體

此處沒有檢查 node, val 是否為 NULL ，雖然不影響函式結果，但之後需要實驗補上速度差異

不檢查會造成錯誤的記憶體釋放，因此無須討論這種狀況

否則將 val 字串給 node ，並用 list_add 將 node 插入至 head

改進你的漢語表達

q_insert_tail

原本我複製 q_insert_head 的內容並改掉 list_add ，但有許多重複程式碼
因此改為呼叫 q_insert_head(head->prev, s) 達成插入在最後一項的功能

bool q_insert_tail(struct list_head *head, char *s)
{
-   element_t *node = malloc(sizeof(element_t));
-   char *val = strdup(s);
-    if (!node || !val || !head) {
-        free(node);
-        free(val);
-        return false;
-    }
-    node->value = val;
-    list_add_tail(&node->list, head);
-    return true;
+    return q_insert_head(head->prev, s);
}

q_remove_head

若 list 指向 NULL 或者是空的，終止並回傳 NULL
否則用 list_first_entry 找到第一個元素，並用 list_del 移除他
將他的 value 存至 sp

q_remove_tail

和 q_insert_tail 一樣 可以簡單的用 q_remove_head 完成
但由於 q_remove_head 是刪除 head 的下一個元素 應該傳入 head->prev->prev 才對

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
-   return q_remove_head(head->prev, sp, bufsize);
+   return list_empty(head) ? NULL
+                           : q_remove_head(head->prev->prev, sp, bufsize);
}

q_size

特別處理 head 指向 NULL 的情況
其餘用 list_for_each 走訪過所有節點，並記錄共有幾個元素即可

q_delete_mid

原本是用快慢指標的技巧找到中間那項並刪除

針對環狀且雙向的佇列，是否有更快的方法？

考慮雙向環狀的條件可以發現，用兩個指標從頭和尾向對方移動，
只需要存取

$n$ 個節點就好，不需要快慢指標的

$\frac{3}{2}n$個

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
-   struct list_head *slow = head, *fast = head;
-   while (fast->next != head->prev && fast->next->next != head->prev) {
-       slow = slow->next;
-       fast = fast->next->next;
-   }
-   list_del(slow);
-   q_release_element(list_entry(slow, element_t, list));
+   struct list_head *tail;
+   q_find_mid(head, head, tail);
+   list_del(head);
+   q_release_element(list_entry(head, element_t, list));
    return true;
}

由於 q_sort 採用 merge sort ，也需要尋找中間那項，獨立成函式 q_find_mid

q_delete_dup

走訪除了第一個以外的節點
檢查上一個節點和現在的是否相同，重複就刪掉上一個，並記錄這個節點也是重複的
若上一個和現在不同但被記錄，也要將上一個刪除

由於和 q_ascend 與 q_descend 有許多重疊，使用另一個子函式一併實現

q_swap

先將最後一項的 next 設為 NULL ，每遇到兩個節點就把他們的連結互換
由於 head 被留下來最後接回去，至少有一個 next 指針可以拿來更改
每修改一個指針，就會多出一個指向重複節點的指針，因此自由度始終是一，可以執行到底
最初實作時沒有注意到 head 和他後面那項會被交換，要存下來的是 head->next

後來直接用 q_reverse(head, 2) 取代

void q_swap(struct list_head *head)
{
    q_reverse(head, 2);
}

q_reverse

走訪所有節點並交換 prev, next
用 do while 一直執行到遇到 head

q_reverseK

可以重用 q_reverse 來實作，需要注意必須傳入環狀佇列，要將第 K 個跟第一個連起來

TODO: 改進程式碼的重用程度。

q_ascend, q_descend

要求回傳一個非嚴格遞增或遞減的佇列，一種想法是用 monostack，但均攤需要

$O(2n)$
可以反過來做，如果下一個節點會破壞性質，就把他刪掉
為了重用程式碼 q_descend 可以選擇反轉後用 q_ascend 再反轉，並改成刪除左邊的節點
但需要

$O(3n)$

由於和 qdelete_dup 有許多重疊，使用另一個子函式一併實現，改進原本重用率低的問題

q_merge

考量到要在 q_sort 中重用，我將 q_merge_two 獨立出來，整個 list 每兩項合併一次
若還有兩項以上重複進行，且會一直合併至只剩一個 list
但因為需要保留 queue_contex_t 的結構，結束函式後程式會自己回收
所以實際上不能把相鄰項直接移除，採用清空被合併的 list ，每次要合併時尋找非空的 list

許多同學實作上把所有 list 合併到第一個，假設總共

$n$ 個節點

$q$ 個 list
第一個 list 中有

$n-q+1$ 個節點，總共會需要

$q-1$ 次合併
比較則要

$\frac{(q-1)((n-q+1)+(n-1))}{2}=\frac{-q^2+(2n+2)q-(n+1)}{2}$
走訪

$n$ 個節點
比較次數最多發生在

$q=n+1+\sqrt{n(n+1)}$ ，但

$q$ 最多只能到

$n-1$
所以實際上最多比較次數會是

$\frac{(n-2)(n+1)}{2}$

而我的作法要

$q-1$ 次合併，走訪

$n^2$ 個節點，比較

$n{\log }_{2}n$ ，證明見 2024-3-19 課程簡記

走訪節點的成本是固定的，但比較取決於資料型別，若是字串成本會很高

q_sort

採用 merge sort ，將整個 list 切割開，並呼叫 q_merge_two 當作 n 個長度一的 list 合併
現在用 q_delete_mid 中尋找中點的做法，亦可用 q_reverseK ， K 設為 q_size()+1>>1