---
# System prepended metadata

title: 2023q1 Homework1 (lab0)

---

# 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