# 2025q1 Homework1 (lab0)
contributed by < `hwz222` >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 實做佇列各函式
`TODO: 95/100 未通過 constant time 測試`

###
> commit [196cf10](https://github.com/hwz222/lab0-c/commit/196cf10efc1dfd45ca30910cc3cf3ee9b323ec25)

動態配置新的 list_head 作為新佇列開頭，配置後檢查是否配置成功，並使用 `INIT_LIST_HEAD` 巨集初始化成員指標變數 `next` `prev` 指向自己位址。

### q_free
> commit [a5dabbb](https://github.com/hwz222/lab0-c/commit/a5dabbb60db4cad818ae5c86125861070c21e140)

我的實做方法是在走訪佇列同時釋放每個 `element_t` 記憶體，考慮到此函式在走訪時會對佇列結構做更改，我使用巨集 `list_for _each_safe` 走訪佇列並釋放 `element_t` 成員的記憶體空間，最後再釋放佇列頭部的 `list_head` 。

### q_insert_head
> commit [bef50fe](https://github.com/hwz222/lab0-c/commit/bef50fee531e01bc81cbe85d2fc7198db5b474f1)

先判斷佇列開頭指標與插入字串指標是否為空指標，接著動態配置 `element_t` 與其成員變數 `value` 記憶體空間, `value` 使用 `strdup()` 函式進行動態配置，確保配置成功後使用巨集 `list_add` 將節點插入至佇列頭部。

### q_insert_tail
> commit [bef50fe](https://github.com/hwz222/lab0-c/commit/bef50fee531e01bc81cbe85d2fc7198db5b474f1)

實做方式與 `q_insert_head` 相似，最後插入則是使用 `q_insert_tail` 插入節點至佇列尾部。

### q_remove_head
> commit [e3aea57](https://github.com/hwz222/lab0-c/commit/e3aea57943fd2fa6693ab5cad1c3ad7751d4dd4b)

使用巨集 `list_first_entry` 搭配 `list_del` 找出佇列第一個元素並切斷成員變數 `list` 與前後元素之連結但並不釋放空間；將移出元素之 `value` 透過 `strncpy` 淺複製至 `sp` 指標。

### q_remove_tail
> commit [e3aea57](https://github.com/hwz222/lab0-c/commit/e3aea57943fd2fa6693ab5cad1c3ad7751d4dd4b)

與 `q_remove_head` 相似，尋找佇列尾端元素搭配的巨集改為 `list_last_entry` 實做。

### q_size
> commit [f372fbf](https://github.com/hwz222/lab0-c/commit/f372fbf89b6ce44367010b80859faface57ee352)

檢查佇列頭部非空指標後使用 `list_for_each` 走訪佇列同時計算佇列大小。

### q_delete_mid
> commit [d03210a](https://github.com/hwz222/lab0-c/commit/d03210a6e5232529dd256087f54ce4716e45a473)

- 使用快慢指標 `slow` `fast` 走訪佇列，考慮佇列長度為奇數時，排在第 $⌊n / 2⌋$ 個元素要執行 `delete` 操作，迴圈的結束條件設定為當 `fast` 的下下指標指向 `head` 時，`slow` 指標剛好位於中心元素。：

while (fast->next != head && fast->next->next != head) {
    slow = slow->next;
    fast = fast->next->next;
}

- `delete` 刪除元素時，先使用一指標變數紀錄刪除節點位址，再使用 `list_del` 斷開中間節點於左右節點連結，再釋放該元素之成員及自身配置的記憶體空間。

element_t *del_elem = list_entry(slow, element_t, list);
list_del(slow);
free(del_elem->value);
free(del_elem);

### q_delete_dup
> commit [b562292](https://github.com/hwz222/lab0-c/commit/b5622922b0140fb40918f999b393b40511c4b8a7)

走訪佇列時使用 `next_lh` 紀錄下個即將走訪的元素。比對與現在走訪的元素，若相同使用與 `q_delete` 相同方式切斷與鄰元素的連接並釋放記憶體空，繼續下個節點的比對，直到沒有相同元素出現，釋放 `curr_lh` 本身所配置記憶體，繼續走訪下個相異元素。

### q_swap
> commit [0bfda59](https://github.com/hwz222/lab0-c/commit/0bfda598160e28a364302527c6e35dd244860df2)

一開始採取的實做方案為讓佇列元素兩兩一組，交換兩成員變數 `list` 內的值，即可達到順序對調的效果 ; 改善程式碼整潔度，使用巨集 `list_move` 將要交換的後節點移位到前節點之前，一樣達到交換效果。

- tmp = current->next;
- list_del(cur->next);
- list_add(tmp,seg_head);
+ list_move(curr->next, seg_head)

### q_reverse
> commit [29eb433](https://github.com/hwz222/lab0-c/commit/29eb4339436707f63184efcee27e898095ac3254)

一開始的實做方式是走訪佇列，並交換每個元素的 `list->prev` 及 `list->next` 可達到反轉佇列效果 ; 為改善程式碼的整潔度使用 `list_for_each_safe` 及 `list_move` 實做反轉佇列，走訪時將元素移到頭節點，走訪到尾端時等同於反轉整個佇列。

- struct list_head *ptr = head, *tmp;
- do {
-     tmp = ptr->prev;
-     ptr->prev = ptr->next;
-     ptr->next = tmp;
-     ptr = ptr->prev;
- } while (ptr != head);
+ struct list_head *safe, *ptr;
+ list_for_each_safe(ptr, safe, head) 
+     list_move(ptr, head);

### q_reverseK
> commit [f7c6eac](https://github.com/hwz222/lab0-c/commit/f7c6eac844f0e7cee7a3d6337d4bfaf434fc7e05)

走訪佇列時每 $K$ 個元素當成一個看成一個佇列，此子佇列開頭為一個子佇列結尾，用與 `q_reverse` 相同的方式將每個元素移到開頭完成反轉子佇列。

for (int i = 0, bound; i + k <= length;) {
    bound = i + k;
    while (i < bound) {
        tmp = curr->next;
        list_move(curr, seg_head);
        curr = tmp;
        i++;
    }
    seg_head = curr->prev;
}

### q_ascend
> commit [7865873](https://github.com/hwz222/lab0-c/commit/78658738d5e96458aa670a4c0d60ac53b5541b39)

從佇列尾端開始反向走訪，維護一個 `upper_bound` 使得下個走訪對象不能 $>$ 該元素，並持續更新使佇列嚴格遞增，大於則移除。

### q_descend
> commit [7865873](https://github.com/hwz222/lab0-c/commit/78658738d5e96458aa670a4c0d60ac53b5541b39)

從佇列尾端開始反向走訪，維護一個 `lower_bound` 使得下個走訪對象不能 $<$ 該元素，並持續更新使佇列嚴格遞減，小於則移除。

### mergeSort_merge
> commit [f41ce0b](https://github.com/hwz222/lab0-c/commit/f41ce0b6fb13a4f7c23ad92660ca38f473f06dde)

使用兩個指標 `ptr1` `ptr2` 紀錄兩個佇列開頭， `merged` 指標作為要被合併到的佇列，比較開頭大小後將較小/大的元素移到 `merged` 的尾端，當兩佇列指標都走訪完畢，兩佇列就完成合併至 `merged` 佇列，最後使用 `list_splice` 將 `merged` 將所有佇列元素連結回第一個佇列完成合併。

改進方向：使用雙重指標進行合併，減少不必要記憶體空間

### q_sort
> commit [f41ce0b](https://github.com/hwz222/lab0-c/commit/f41ce0b6fb13a4f7c23ad92660ca38f473f06dde)

使用快慢指標找出中間元素，並使用巨集 `list_cut_position` 將原佇列遞迴分割成兩部份，分別進行排序，再使用 `mergeSort_merge` 將兩佇列合併。

改進方向：引入 `list_sort` 實做 bottom up 非遞迴排序

### q_merge
> commit [703ba03](https://github.com/hwz222/lab0-c/commit/703ba03dad8d624acf58d1fd8ef9f6886bf704e6)

傳入參數 `head` 指向第一個佇列的開頭，使用 `Mergesort_merge` 逐步合併，將第二個佇列合併至第一個，直到剩下一個佇列就完成所有佇列的合併。