# 2025q1 Homework1 (lab0)
contributed by < `mincch` >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ 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: 48 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 3750H with Radeon Vega Mobile Gfx
CPU family: 23
Model: 24
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 1
BogoMIPS: 4591.23
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1g
b rdtscp lm constant_tsc rep_good nopl tsc_reliable nonstop_tsc cpuid extd_apicid pni pclmulqdq ssse3 fma cx16 sse4_1 sse4_2 movbe pop
cnt aes xsave avx f16c rdrand hypervisor lahf_lm cmp_legacy svm cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw topoext perfctr_co
re ssbd ibpb vmmcall fsgsbase bmi1 avx2 smep bmi2 rdseed adx smap clflushopt sha_ni xsaveopt xsavec xgetbv1 clzero xsaveerptr virt_ssb
d arat npt nrip_save tsc_scale vmcb_clean flushbyasid decodeassists pausefilter pfthreshold v_vmsave_vmload
Virtualization features:
Virtualization: AMD-V
Hypervisor vendor: Microsoft
Virtualization type: full
Caches (sum of all):
L1d: 128 KiB (4 instances)
L1i: 256 KiB (4 instances)
L2: 2 MiB (4 instances)
L3: 4 MiB (1 instance)
```
## CODE
### `q_new`
建立一個空的佇列，使用 `lish.h` 中的 `INIT_LIST_HEAD()`來初始化`next` 和 `prev` 指標。
### `q_free`
遍歷佇列後，逐一地釋放所有節點，剛開始採用 `free(node) + free(node->value)`，後來發現 `list.h` 中有 `q_release_element(node)` 可以用一行來幫助我釋放所有節點。
第一次在遍歷節點時，沒有注意到應該要先將 c->next 儲存，否則當 c 被釋放時，就無法找到下一個節點，會導致錯誤。所以這邊我先用一個 *next 來儲存 c 的下一個節點，這樣在遍歷所有節點時才不會發生問題。
```clike
while (c != head) {
struct list_head *next = c->next;
element_t *n = container_of(c, element_t, list);
q_release_element(n);
c = next;
}
```
### `q_insert_head`
element_t *new_node = malloc(sizeof(element_t));
什麼時候需要 malloc()？
當函式結束後仍然需要存活的變數（例如 queue 的節點）時，應該分配記憶體到 heap，避免區域變數在 stack 被釋放。
queue 的元素數量是 動態變化的，無法預先知道需要多少記憶體，因此必須使用 malloc() 來動態分配。
new_node->value = strdup(s);
`strdup(s)` 會 在堆區 (heap) 動態分配一塊記憶體，並複製 s 的內容到新記憶體中。
INIT_LIST_HEAD(&new_node->list);
讓自已自成一個list最後再用list_add接回原本的head
首先我先配置一個新節點new_node，並用這個new_node來儲存要寫入的資料，寫入完後使用 `list_add`將我要寫入的元素插入在head之前。
原本使用 `malloc() + strcpy()` 但是這樣需要額外的`strlen()`計算長度並且要檢查 malloc() 是否成功，額外增加程式碼。
所以我採用了`strdup()`，因為它可以動態分配一塊記憶體，並複製 s 的內容到新記憶體中。
### `q_insert_tail`
直接使用`q_insert_head`，只需要將head改成head->prev，因為我要插入元素在尾巴就相當於我要把元素插入在head->prev。
### `q_remove_head`
使用 `lish.h` 中的 `lise_del` 來移除節點，剛開始使用 `list_del(head)` 會產生`Segmentation fault occurred`，查詢後才發現在Linux linked list 中，head 只是鏈結串列的「標頭 (dummy node)」，不存實際資料。head->next 才是指向第一個有效的節點，這個節點才包含真正的 value。
在說明中有提到 : `If sp is non-NULL and an element is removed, copy the removed string to *sp
(up to a maximum of bufsize-1 characters, plus a null terminator.)`
所以我用 `strncpy` 來限制複製的長度為bufsize -1 ，並且在最後加上 `'/0'` 當作 null terminator。
### `q_remove_tail`
`q_remove_tail` 和 `q_remove_head` 差別就是在取出要移除的節點時是使用`list_last_entry` 可以直接找到list中的最後一點去進行刪除的動作。
### `q_delete_mid`
在雙向鏈結串列中尋找中間節點時，最直覺的方法是遍歷兩次：
1.計算 queue 的長度 n
2.再走 n/2 步來找到中間節點
但這樣的做法需要兩次遍歷，時間複雜度為 O(2n) = O(n)。
而快慢指標只需要一次遍歷 (O(n)) 就能找到中間節點，效率更高。
參考[分析快慢指標](https://hackmd.io/NDN4SlBNQvCVZZ1YgYBtHg?view)
用快慢指標來尋找中間點，遍歷佇列時，當慢指標走一步時，快指標多走一步，這樣在快指標走完全部時，慢指標會剛好停在中間點，需要注意的是慢指標的初始化，若是使用 `slow = head` 這樣會導致當長度是偶數時找中間點會少走一格。接著就是使用`list_del` 和 `q_release_element` 來處理要被刪除的節點。
### `q_delete_dup`
用一個current node 和 next node去進行比較，使用 `strcmp` 來比較兩個節點是否相同，如果相同就把 next node 刪除後用 `continue`，因為當 `cur->value == next->value`，這代表 next 是重複的，刪除 next，但不移動 cur，讓 cur 繼續和下一個節點比較。這樣可以確保刪除所有重複的節點，而不會漏掉某些重複點。並且我會用一個check來儲存current node是否也為重複的節點，當 `check==true` 時，cur 也應該被刪除
### `q_swap`
原本使用這段code去遍歷，並且逐一的左右交換
```clike
while (cur != head && cur->next != head) {
list_move(cur->next, cur->prev);
cur = cur->next;
}
```
` list_move(target, new_prev) `會將 target 移動到 new_prev 之後，這樣 cur->next 會插入到 cur->prev 之後，相當於交換 cur 和 cur->next。
但是後面做到了 `q_reverseK` 時發現了當 k==2 時就和 `q_swap` 功能一樣，就把他修改成，也能達到一樣的效果。
```clike
q_reversek(head, 2);
```
### `q_reverseK`
每 k 個節點為一組，將該組的鏈結順序反轉。如果最後一組不足 k 個節點，則保持原順序不變。`q_size(head)` 會計算 queue 內的節點數量。
如果 count < k，則 while (count >= k) 不會執行，queue 保持原樣。
`list_move(cur, prev)` 將 cur 移動到 prev 的前面，達成反轉效果。
### `q_sort`
最初使用quick sort來實做排序，但是在worst cose的時間複雜度會到 O(N^2)會有超時的問題，所以我利用merge sort來進行排序，原本的list分成左右兩半，遞迴去排序兩個list，最後再用 `q_merge_list` 來合併兩個list。
在 `q_merge_list` 中先確認兩個list不為空，接著開始比較兩個list的第一個節點，根據是升序或是降序來選擇比較大或比較小的點，不斷重複直到有一個list為空，就把還有node的list全部插到list的尾端。
比較 left_list 和 right_list 的首節點:
```clike
element_t *first_node = list_first_entry(left_list, element_t, list);
element_t *second_node = list_first_entry(right_list, element_t, list);
```
根據 descend（or ascend）決定比較方式：
```clike
bool tag = (descend)
? strcmp(first_node->value, second_node->value) > 0
: strcmp(first_node->value, second_node->value) < 0;
```
選擇較小或較大的節點，將其移動到 temp :
```clike
list_move_tail(&add_first->list, &temp);
```
為什麼 slow 從 head 開始？
q_sort() 的目標是拆分整個 queue，所以 slow 需要指向「前半部分的最後一個節點」。
快慢指針的起點選擇影響了最終的分割點：
slow = head：這樣 slow 會停在前半部分的最後一個節點，確保 list_cut_position() 正確切割。
fast = head->next：這樣 fast 會比 slow 先走一步，確保 slow 在正確的中點位置。
找到 head 的 中間點 (slow)，然後用 list_cut_position() 切割 head 為 first 和 head 兩部分，再遞迴排序。
head → A → B → C → D → E → F → head
first → A → B → C → first
head → D → E → F → head
和 `q_delmid()` 不同的是slow開始為若為偶數個node
del mid 會刪除第第n/2個node 但是merge sort要找到剛好一半的位置
最後一行 q_merge_two(head, &first, descend);
head 是排序結果要放回的地方
first 是要合併進 head 的另一個已排序的鏈結串列
如果交換 head 和 first，會導致 head 變成 first，從而影響排序結果。
### `q_descend`
刪除其右側任意位置具有更大值的節點的每個節點。從尾巴比較回來紀錄最大值，若前一點<最大值則把前一點刪除，繼續往下比較，如果遇到的節點大於現在的最大值就更新並且從該節點開始往前比較。
為什麼從尾巴開始遍歷?
確保「最大值/最小值」在遍歷時是已知的，這樣我們能夠立即決定是否刪除當前節點，而不需要回溯或額外的記憶體。單遍歷 O(n) 即可完成刪除，不需要額外存儲最大值/最小值。
舉例:
A → B → C → D → E → F
遍歷順序：F → E → D → C → B → A
F 是當前最大值，保留它。
E < F，刪除 E。
D < F，刪除 D。
C < F，刪除 C。
B < F，刪除 B。
A < F，刪除 A。
最後queue剩下 F
如果我們從 A 開始遍歷：
A 的右側還有 B, C, D, E, F，但我們不知道最右側的最大值 F。
我們無法立即決定 A 是否該刪除，因為我們還沒走到 F！
接著當 B 被檢查時，我們仍然不知道 F 是否存在。
這樣的設計可能會讓我們錯過刪除某些節點，或需要回溯來修正錯誤，導致時間複雜度增加。這會讓我們的函式無法在 O(n) 內完成刪除，因為我們可能會回頭檢查已經遍歷過的節點。
### `q_ascend`
和 `q_descend` 相同方法將原本是前一點較小值刪除，改成是前一點較大值刪除。
### `q_merge`
queue_contex 結構
```clike
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
queue_contex_t *first = list_first_entry(head, queue_contex_t, chain);
list_first_entry() 用來取得 head 鏈結串列中的第一個 queue_contex_t。
這個 first 會存放所有合併後的 q。
chain 是 queue_contex_t 的 list_head 成員，用來將 queue_contex_t 連接成鏈結串列。
head → QC1 (q = [1, 4, 6]) → QC2 (q = [2, 5]) → QC3 (q = [3, 7]) → head
first = QC1 (q = [1, 4, 6])
struct list_head *cur = first->chain.next;
cur 指向 head 鏈結中的第二個 queue_contex_t (即 QC2)。
目標是從 QC2 開始，依次合併 queue。
list_splice_init(cur_q->q, first->q);
list_splice_init(source, dest);
會把source所有node移動到dest的後面
cur_q->size = 0;
我把cur_q->q移動到first後cur_q->q 變成空的，但 cur_q->size 還是原本的大小。所以需要將它變成0。
最後將合併後的queue根據升序或降序進行 `q_sort()` 排序
Sign in with Wallet
Connect another wallet