# 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
Sign in with Wallet
Connect another wallet