# 2023q1 Homework1 (lab0) contributed by < `ericlai1021` > ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 11.2.0-19ubuntu1) 11.2.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) i7-8550U CPU @ 1.80GHz CPU family: 6 Model: 142 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 Stepping: 10 BogoMIPS: 3983.99 ``` ## 開發過程 ### q_new :::danger 注意書寫規範：中英文間用一個半形空白字元區隔。 :notes: jserv > 了解，已修正 ::: 使用 `malloc` 動態配置一個自定義結構 `list_head` 大小的記憶體空間，若成功配置記憶體空間，則使用 `INIT_LIST_HEAD` 來初始化，否則，直接回傳 `NULL` ```c struct list_head *q_new() { struct list_head *head = malloc(sizeof(*head)); if (head) INIT_LIST_HEAD(head); return head; } ``` ### q_free 想法是走訪鏈結串列的所有節點，並逐一刪除該節點，所以選擇使用 `list_for_each_entry_safe` 巨集來實作之，作法如下: 1. 若此鏈結串列為空或NULL，則直接釋放該空間 2. 否則，透過 `list_for_each_entry_safe` 來逐一走訪每個節點 3. 先將當前節點移出鏈結串列 `l` ，再將該節點釋放空間 4. 最後，釋放鏈結串列 `l` 開頭的節點 ```c void q_free(struct list_head *l) { if (!l || list_empty(l)) { free(l); return; } element_t *entry, *safe; list_for_each_entry_safe (entry, safe, l, list) { list_del(&entry->list); q_release_element(entry); } free(l); return; } ``` ### q_insert_head 思考過程如下: 1. 因為要插入一個節點，因此需要先配置一個 `element_t` 大小的空間 2. 若配置失敗，直接回傳 `false` 3. 計算新節點的 `value` 所需要的字串長度，注意這邊要將字串結尾符號也納入計算 4. 為新節點的 `value` 配置空間，若配置失敗，則將該節點的空間釋放，並直接回傳 `false` 5. 透過 `strncpy` 函式來將參數字串 `s` 複製到新節點的 `value` 6. 最後將新節點加入到鏈節串列 `head` 當中，並回傳 `true` ```c bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *node = malloc(sizeof(*node)); if (!node) return false; size_t len = strlen(s) + 1; node->value = malloc(sizeof(char) * len); if (!node->value) { free(node); return false; } strncpy(node->value, s, len); list_add(&node->list, head); return true; } ``` ### q_insert_tail 作法同 `q_insert_head` 唯一的差別在把 `list_add` 改成 `list_add_tail` ### q_remove_head 這部分參考同學 <[`YSRossi`](https://hackmd.io/@YSRossi/lab0-2023#q_remove_head)> 的共筆，並與同學指教解題過程。 思考過程如下: 1. 首先處理邊界條件 2. 取得鏈結串列 `head` 的第一個節點 3. 將該節點移除鏈結串列 `head` 4. 將移走的節點的 `value` 複製到 `sp` 中 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *node = list_first_entry(head, element_t, list); list_del_init(&node->list); if (sp) { strncpy(sp, node->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return node; } ``` ### q_remove_tail 作法同 `q_remove_head` 唯一的差別在把 `list_first_entry` 改成 `list_last_entry` ### q_size 根據課程作業說明 [`lab0`](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-a) 的範例程式，透過 `list_for_each` 巨集來走訪鏈結串列，並用一個 `int` 變數來計算節點個數 ```c int q_size(struct list_head *head) { if (!head || list_empty(head)) return 0; int size = 0; struct list_head *pos; list_for_each (pos, head) size++; return size; } ``` ### q_delete_mid 思考過程如下: 1. 首先處理邊界條件 2. 宣告兩個 `list_head` 型態指標變數 `forward` 與 `backward` 分別表示往順向與逆向走 3. 當 `forward == backward` 或 `forward` 與 `backward` 相鄰時，表示已經走到中間節點 4. 將中間節點刪除，並回傳 `true` ```c bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (!head || list_empty(head)) return false; struct list_head *forward = head->next, *backward = head->prev; while (forward != backward && forward->next != backward) { forward = forward->next; backward = backward->prev; } list_del_init(forward); element_t *entry = list_entry(forward, element_t, list); q_release_element(entry); return true; } ``` ### q_delete_dup 因為輸入是已排序好的鏈結串列，所以直觀的想法就是從頭走訪整條鏈結串列的所有節點，只要鄰近兩點的 `value` 一樣，表示要將所有持有該 `value` 的節點都刪除，具體作法如下: 1. 首先處理邊界條件，這邊要注意的是鏈結串列的節點必須至少兩個，否則沒有實作的意義 2. 利用 `list_for_each_entry_safe` 巨集在走訪整條鏈結串列時就算刪除當前節點，即 `entry` ，也能夠過 `safe` 繼續走訪 3. 加入一變數 `del` 用來標記需要被移除的節點 4. 比較當前節點 `entry` 與下一個節點 `safe` 的 `value` 是否相等 5. 若相等，則將 `del` 標記為下一個節點 `safe` ，並移除當前節點 `entry` 6. 若不相等且 `del` 不為空，則將 `del` 移除，並將 `del` 設為空，避免重複釋放記憶體 ```c bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head || list_empty(head) || list_is_singular(head)) return false; element_t *entry, *safe; element_t *del = NULL; list_for_each_entry_safe (entry, safe, head, list) { if ((&safe->list != head) && !strcmp(entry->value, safe->value)) { del = safe; list_del(&entry->list); q_release_element(entry); } else if (del) { list_del(&del->list); q_release_element(del); del = NULL; } } return true; } ``` ### q_swap 這部分由於後面會實作 `q_reverseK` 函式，而 `q_swap` 函式就是 `q_reverseK` 的特例，即 K 設為 2 ，這麼做不但可以使程式更精簡，也使程式更易於維護 ```c void q_swap(struct list_head *head) { // https://leetcode.com/problems/swap-nodes-in-pairs/ q_reverseK(head, 2); } ``` ### q_reverse 最直觀的作法就是透過 `list_for_each_safe` 巨集走訪過整條鏈結串列的節點，將當前節點的 `next` 指標指向當前節點的 'prev' 指標，再將當前節點的 `prev` 指標指向下一個節點 `safe` ，最後別忘了將 `head->next` 指向 `head->prev` ，並將 `head->prev` 指向鏈結串列的第一個節點，即 `safe` 指標所指的地方 ```c void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *node, *safe; list_for_each_safe (node, safe, head) { node->next = node->prev; node->prev = safe; } head->next = head->prev; head->prev = safe; } ``` ### q_reverseK 這題最直觀的想法就是利用 `list_cut_position` 函式將鏈結串列每K個切出來，接著利用先前實作過的 `q_reverse` 函式將切分出來的鏈結串列做反轉，最後再透過 `list_splice` 函式將切分出來的鏈結串列接回原本的鏈結串列當中。 實際研讀過 <[`list.h`](https://github.com/ericlai1021/lab0-c/blob/master/list.h)> 當中 `list_cut_position` 與 `list_splice` 兩個函式的程式碼後得出以下流程: 1. 首先處理邊界條件，這裡只要鏈結串列不為空或 `NULL` 演算法即可成立 2. 創造一個新的鏈結串列 `new_head`，用來串接被切分出來的鏈結串列 3. 用 `list_for_each_safe` 巨集走訪整條鏈結串列，搭配一個 `cnt` 判斷是否走過 K 個節點 4. 當 `cnt == k` 用 `list_cut_position` 函式切分出一條具有 K 個節點的鏈節串列，並用 `new_head` 去串接 6. 使用先前實作過的 `q_reverse` 函式將 `new_head` 做反轉 7. 接著要將反轉過後的鏈結串列 `new_head` 接回去原本的鏈結串列 `head` 當中，這邊為了搭配 `list_cut_position` 函式當中要求第一個引數的鏈結串列必須為空，所以使用 `list_splice_init` 函式將兩條鏈結串列串接起來之後，將 `new_head` 設為空 8. 更新要被切分出來的起始指標 `cut` 要注意這邊 `cut` 是更新為 `safe->prev` 而不是當前節點 `node` ，因為使用 `list_cut_position` 函式之後 `node` 跟 `safe` 就不相連了 ```c void q_reverseK(struct list_head *head, int k) { // https://leetcode.com/problems/reverse-nodes-in-k-group/ if (!head || list_empty(head)) return; LIST_HEAD(new_head); struct list_head *node, *safe, *cut = head; int cnt = 0; list_for_each_safe (node, safe, head) { if (++cnt == k) { list_cut_position(&new_head, cut, node); q_reverse(&new_head); list_splice_init(&new_head, cut); cut = safe->prev; cnt = 0; } } } ``` ### q_sort 初步嘗試參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 實作，選擇當中為 stable sort 的 Merge Sort 來實作之。 首先， [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 實作當中使用的是單向鏈結串列，所以我們也需要對原先的雙向環狀鏈結串列做調整，這裡只是簡易的破壞單向的環狀結構即可達到演算法的目的，作法就是將串列的最後一個節點的 `next` 指向 NULL ```c head->prev->next = NULL; ``` 接著傳入串列的第一個節點的指標給 `mergeSortList` 函式做排序，排序完再接回串列的 head ```c head->next = mergeSortList(head->next); ``` 實作 Merge Sort 當中會包含兩個函式 `mergeSortList` 跟 `merge` ， `mergeSortList` 會傳入未排序過的鏈結串列的開頭指標，並回傳已排序好的鏈結串列的開頭指標。由於 Merge Sort 為 [`divide-and-conquer`](https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm) 演算法，在 divide 階段會不斷將串列切分成兩條大小一樣的子串列，直到不能再切分為止 (即串列當中只剩下一個元素)，這邊搭配快慢指標來找到串列的中間元素，接著將串列切分成兩條子串列 ```c struct list_head *fast = head->next; struct list_head *slow = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } fast = slow->next; slow->next = NULL; ``` ### q_descend 此題要求刪除一個節點左邊所有小於該節點的 `value` 的節點，換個角度去思考，也就是說，只要從鏈結串列的開頭往前 (即 `prev` 指標) 去走訪，只要遇到一個節點的 `value` 小於上一個走訪節點的 `value` ，就將該節點刪除。 實際操作如下: 1. 首先處理邊界條件，這裡只要 `head` 不為空或 `NULL` 演算法即可成立 2. 用一個變數 `pos` 初始化指向 `head->prev` ，即鏈結串列最後一個節點 3. 宣告一個字串變數 `maxStr` 初始化為空字串 4. 往 `prev` 指標的方向持續走訪鏈結串列 5. 若當前節點的 `value` 小於 `maxStr` ，就刪除該節點 6. 否則，將 `maxStr` 指向當前節點的 `value` 7. 走訪完所有節點就回傳鏈結串列的 size ```c int q_descend(struct list_head *head) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ if (!head || list_empty(head)) return 0; struct list_head *pos = head->prev; char *maxStr = ""; while (pos != head) { element_t *entry = list_entry(pos, element_t, list); pos = pos->prev; if (strcmp(entry->value, maxStr) < 0) { list_del(&entry->list); q_release_element(entry); } else { maxStr = entry->value; } } return q_size(head); } ``` ### q_merge