HackMD
2025q1 Homework1 (lab0)
contributed by < hwz222 >
實做佇列各函式
TODO: 95/100 未通過 constant time 測試
commit 196cf10
動態配置新的 list_head 作為新佇列開頭，配置後檢查是否配置成功，並使用 INIT_LIST_HEAD 巨集初始化成員指標變數 next prev 指向自己位址。
q_free
commit a5dabbb
我的實做方法是在走訪佇列同時釋放每個 element_t 記憶體，考慮到此函式在走訪時會對佇列結構做更改，我使用巨集 list_for _each_safe 走訪佇列並釋放 element_t 成員的記憶體空間，最後再釋放佇列頭部的 list_head 。
q_insert_head
commit bef50fe
先判斷佇列開頭指標與插入字串指標是否為空指標，接著動態配置 element_t 與其成員變數 value 記憶體空間, value 使用 strdup() 函式進行動態配置，確保配置成功後使用巨集 list_add 將節點插入至佇列頭部。
q_insert_tail
commit bef50fe
實做方式與 q_insert_head 相似，最後插入則是使用 q_insert_tail 插入節點至佇列尾部。
q_remove_head
commit e3aea57
使用巨集 list_first_entry 搭配 list_del 找出佇列第一個元素並切斷成員變數 list 與前後元素之連結但並不釋放空間；將移出元素之 value 透過 strncpy 淺複製至 sp 指標。
q_remove_tail
commit e3aea57
與 q_remove_head 相似，尋找佇列尾端元素搭配的巨集改為 list_last_entry 實做。
q_size
commit f372fbf
檢查佇列頭部非空指標後使用 list_for_each 走訪佇列同時計算佇列大小。
q_delete_mid
commit d03210a
- 使用快慢指標
slowfast走訪佇列，考慮佇列長度為奇數時，排在第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
走訪佇列時使用 next_lh 紀錄下個即將走訪的元素。比對與現在走訪的元素，若相同使用與 q_delete 相同方式切斷與鄰元素的連接並釋放記憶體空，繼續下個節點的比對，直到沒有相同元素出現，釋放 curr_lh 本身所配置記憶體，繼續走訪下個相異元素。
q_swap
commit 0bfda59
一開始採取的實做方案為讓佇列元素兩兩一組，交換兩成員變數 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
一開始的實做方式是走訪佇列，並交換每個元素的 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
走訪佇列時每 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
從佇列尾端開始反向走訪，維護一個 upper_bound 使得下個走訪對象不能
q_descend
commit 7865873
從佇列尾端開始反向走訪，維護一個 lower_bound 使得下個走訪對象不能
mergeSort_merge
commit f41ce0b
使用兩個指標 ptr1 ptr2 紀錄兩個佇列開頭， merged 指標作為要被合併到的佇列，比較開頭大小後將較小/大的元素移到 merged 的尾端，當兩佇列指標都走訪完畢，兩佇列就完成合併至 merged 佇列，最後使用 list_splice 將 merged 將所有佇列元素連結回第一個佇列完成合併。
改進方向：使用雙重指標進行合併，減少不必要記憶體空間
q_sort
commit f41ce0b
使用快慢指標找出中間元素，並使用巨集 list_cut_position 將原佇列遞迴分割成兩部份，分別進行排序，再使用 mergeSort_merge 將兩佇列合併。
改進方向：引入 list_sort 實做 bottom up 非遞迴排序
q_merge
commit 703ba03
傳入參數 head 指向第一個佇列的開頭，使用 Mergesort_merge 逐步合併，將第二個佇列合併至第一個，直到剩下一個佇列就完成所有佇列的合併。
