# 2024q1 Homework1 (lab0) contributed by < [Petakuo](https://github.com/Petakuo) > ## 開發環境 ```shell $ 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: 46 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 24 On-line CPU(s) list: 0-23 Vendor ID: GenuineIntel Model name: 13th Gen Intel(R) Core(TM) i7-13700 CPU family: 6 Model: 183 Thread(s) per core: 2 Core(s) per socket: 16 Socket(s): 1 Stepping: 1 CPU max MHz: 5200.0000 CPU min MHz: 800.0000 BogoMIPS: 4224.00 ``` ## 指定佇列的操作 ### `q_new` :::danger 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利) ::: 利用 `INIT_LIST_HEAD` 可將 next 及 prev 指向自己，以形成<s>空(的)鏈結</s> 空的鏈結串列。 :::danger 確認「空鏈結」用語是否精準，「鏈結」是用來形容「串列」，後者才是主體 ::: ### `q_free` ```c void q_free(struct list_head *head) { if(head == NULL) return; element_t *entry, *safe; list_for_each_entry_safe(entry, safe, head, list){ q_release_element(entry); } free(head); } ``` 可使用 `ist_for_each_entry_safe` 逐一走訪<s>搜尋</s> 鏈結串列，接著使用 `q_release_element` 將他們釋放，但始終編譯不過，最後問了 [Shiang1212](https://github.com/Shiang1212) 才知道 head 也要被釋放才行。 ### `q_sort` ```c list_qsort(&list_less); list_qsort(&list_greater); list_splice(&list_less, &pivot); list_splice_tail(&list_greater, &pivot); ``` :::warning 避免漢語的歧異。 ::: 此題為老師給我的測驗題，由於程式是以遞迴的形式對 pivot 左側及右側 <s>左右</s> 的 <s>list</s> 子串列進行排序，因此我需填寫將他們合併的程式碼，在這裡我使用了 `list_splice` 將比 pivot 小的串列連接至 pivot 左邊，接著使用 `list_splice_tail` 將比 pivot 大的串列連接至 pivot 右邊，但沒辦法編譯過，還在尋找原因。 :::danger 改進你的漢語表達。 ::: :::info 原本編譯後被告知 : Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped). 因此將 ```c list_splice(&list_less, &pivot); list_splice_tail(&list_greater, &pivot); ``` 改寫為 ```c list_splice_tail_init(&list_less, head); list_add_tail(&pivot->list, head); list_splice_tail(&list_greater, head); ``` 雖然已經編譯的過，但仍不知為何排序並非遞增。 ::: 仍然不知原因為何，因此參考 [Shawn531](https://github.com/Shawn531) 的程式碼，它利用了 merge sort 來實做。 ```c while (fast != head && fast->next != head) { slow = slow->next; fast = fast->next->next; } return slow; ``` 首先，利用快慢指標的方法到整個串列的中間節點，由於 slow pointer 一次走一步且 fast pointer 一次走兩步，因此當 fast pointer 走到最後一個節點時 slow pointer 會剛好在中間節點，此時跳出 while 迴圈並回傳 slow pointer 即可。 ```c struct list_head *mid = midPoint(head); list_cut_position(&a_head, head, mid); list_splice_init(head, &b_head); ``` 接著將串列由剛才找到的中間節點分為兩串列，目的是在於之後的排序和合併。 ```c while (a_head->next != a_head && b_head->next != b_head) { element_t *a_e = list_entry(a_head->next, element_t, list); element_t *b_e = list_entry(b_head->next, element_t, list); if (descend) { if (strcmp(a_e->value, b_e->value) >= 0) list_move_tail(a_head->next, c_head); else list_move_tail(b_head->next, c_head); } else { if (strcmp(a_e->value, b_e->value) <= 0) list_move_tail(a_head->next, c_head); else list_move_tail(b_head->next, c_head); } } if (a_head->next != a_head) list_splice_tail(a_head, c_head); if (b_head->next != b_head) list_splice_tail(b_head, c_head); ``` 再來是合併的程式碼，首先，當兩串列皆非空的話，將串列的首個節點中的值拿來比大小，並且將較小的取出並連接於 `c_head` 後方，最後再判斷是否有串列為空，將非空的串列整個連接於 `c_head` 後方即可。 ```c q_sort(&a_head, descend); q_sort(&b_head, descend); merge(&a_head, &b_head, head, descend); ``` 最後一步，進行遞迴，將已分開的串列個別進行排序，再將排序好的串列合併起來。 ### `q_insert_head` ```c element_t *node = malloc(sizeof(element_t)); node->value = strdup(s); list_add(&node->list, head); return true; ``` 利用 `strdup` 可將指標的內容複製給要加入的節點，接著再使用 `list_add` 將節點從頭部新增至鏈結串列。 ### `q_insert_tail` 概念與 `q_insert_head` 大致上一樣，唯一的不同是需要從鏈結串列的尾端插入，因此將 `list_add` 改成 `list_add_tail` 即可。 由於編譯後被告知未處理 `node == NULL` 的情況，因此新增了 ```c if (node == NULL) return false; ``` 但不知為何不是 constant time ，還在尋找原因。 ### `q_remove_head` ```c if (sp) { strncpy(sp, node->value, bufsize - 1); sp[bufsize - 1] = '\0'; } ``` 一開始我不懂 `char *sp` 和 `size_t bufsize` 的作用為何，後來參考了 [Shawn531](https://github.com/Shawn531) 的程式碼並查詢資料才知道是因為 `list_del` 將節點刪除後並不會釋放其佔用的記憶體，因此需複製 `node->value` 至 `sp` ，以便後續的操作。 <s>[IBM](https://www.ibm.com/docs/zh-tw/i/7.5?topic=functions-strncpy-copy-strings#strncpy__title__5) 對 `strncpy()` 的解釋 : strncpy() 函數會將 string2 的 count 個字元複製到 string1。 如果 count 小於或等於 string2的長度，則空值字元 (\0) 不會 附加至複製的字串。 如果 count 大於 string2的長度，則 string1 結果會以空值字元 (\0) 填補，直到達到長度 count。 </s> :::danger 查閱 C 語言規格書和 Linux man page，以第一手材料為主。 ::: :::info 以下為 C99 對 **`strncpy`** 函式的說明 : >1. The strncpy function copies not more than **n** characters (characters that follow a null character are not copied) from the array pointed to by **s2** to the array pointed to by **s1**. If copying takes place between objects that overlap, the behavior is undefined. >2. If the array pointed to by **s2** is a string that is shorter than **n** characters, null characters are appended to the copy in the array pointed to by **s1**, until **n** characters in all have been written. >3. The strncpy function returns the value of **s1**. ::: ### `q_remove_tail` 概念與 `q_remove_head` 大致上一樣，將 `list_first_entry` 改為 `list_last_entry` 即可。 ### `q_size` 宣告一整數型別以計數，並利用 `list_for_each_entry` 走訪鏈結串列。 ### `q_delete_mid` ```c element_t *dnode = list_entry(ptr, element_t, list); q_release_element(dnode); list_del(ptr); return true; ``` 找到鏈結串列長度的中間值，並新增一指標指向該位置，最後將元素及節點一同刪除即可。 ### `q_swap` 利用 `list_move` 函式可將兩節點交換，但我在實作時忽略了它是環狀鏈結串列，把交換的條件設定成 `while(node->next != NULL)` ，因此導致程式進入無窮迴圈，在參考 [2020leon](https://github.com/2020leon) 後將其改為 `node != head && node->next != head` 而成功。 ### `q_reverse` 首先由 head 開始逐一走訪，每到下一個節點就呼叫 `list_move` 函式將該節點移動到 head 之前，如此走訪完就能得到反轉後的鏈結串列。 ### `q_reverseK` ```c int c = 1; while (next != head) { while (c <= k && next != head) { next = node->next; list_move(node, new_head); node = next; c++; } new_head = next->prev; c = 1; ``` 在 `q_reverse` 的概念下新增一個整數型態的變數，用來計算已被反轉的節點個數，每當數量到達指定的 K 時會重新計算。 原先 c 的設定是 0，但在應用時我發現此程式總是會反轉 K+1 個節點，才想到 c 語言的 index 是從 0 開始，因此將其改為 1。 :::danger 查閱 C 語言規格書，以理解為何 array subscript 的索引值從 0 開始。 ::: :::info 以下為 C99 對 array subscript 的說明 : >A postfix expression followed by an expression in square brackets **[]** is a subscripted designation of an element of an array object. The definition of the subscript operator **[]** is that **E1[E2]** is identical to **(*((E1)+(E2)))**. Because of the conversion rules that apply to the binary **+** operator, if **E1** is an array object (equivalently, a pointer to the initial element of an array object) and **E2** is an integer, **E1[E2]** designates the **E2**-th element of **E1** (counting from zero). 因此索引值需從 0 開始，計算出來的位址才會是正確的。 ::: ### `q_ascend` ```c if (strcmp(current_e->value, next_e->value) > 0) { list_del(current); q_release_element(current_e); len--; flag = 1; break; } ``` 此題我參考了 [Shawn531](https://github.com/Shawn531) 的程式碼，他利用了 `strcmp` 函式來比較節點間元素的大小，並且設置了 flag 來確定了指標下一步要移動到哪，以分辨哪些節點該被刪除。 :::info 以下為 C99 對 **`strcmp`** 的說明 : >1. The **strcmp** function compares the string pointed to by **s1** to the string pointed to by **s2**. >2. The **strcmp** function returns an integer greater than, equal to, or less than zero, accordingly as the string pointed to by **s1** is greater than, equal to, or less than the string pointed to by **s2**. ::: ### `q_descend` 此題和 `q_ascend` 用了相同的概念，把 `strcmp` 的條件從 `< 0` 改為 `> 0` 即可達到相反的效果。 ### `q_delete_dup` ```c list_for_each_entry_safe (entry, safe, head, list) { if (entry->list.next != head && strcmp(entry->value, safe->value) == 0) { list_del(&entry->list); q_release_element(entry); flag = 1; } else if (flag) { list_del(&entry->list); q_release_element(entry); flag = 0; } } ``` 此題我是參考 [jeremy90307](https://github.com/jeremy90307) 的程式碼，首先用 `list_for_each_entry_safe` 走訪每一個節點，並用 `strcmp` 來比較兩節點間 value 的大小，若相同則表示兩節點都必須被刪除，除此之外，宣告了 flag 來進行下個節點是否該刪除的判斷，若有節點被刪除，則 flag 會被改為 1 ，而下個節點會因為 flag 的值為 1 進入被刪除的動作。 ### q_merge ```c while (q_current != head) { queue_contex_t *current_contex = list_entry(q_current, queue_contex_t, chain); list_splice_init(current_contex->q, q_contex->q); q_current = q_current->next; } q_sort(q_contex->q, descend); return q_contex->size; ``` 此題主要的概念為先將各個串列合併起來，最後再用上述 q_sort 函式進行排序。 `queue_contex_t` 之解釋 ： ```c typedef struct { struct list_head *q; struct list_head chain; int size; int id; } queue_contex_t; ``` `q` 為指向佇列頭部的指標，而 `chain` 則是將個佇列的頭部串連起來，可以透過它來走訪各個串列，而 `size` 和 `id` 分別紀錄佇列的長度和的編號。