# 2024q1 Homework1 (lab0)
contributed by < [wayne10823014](https://github.com/wayne10823014) >

### Reviewed by `weihsinyeh`
1. 邊寫程式碼邊更新開發紀錄，很多程式沒被紀錄進來。
2. [commit 49f4d09](https://github.com/wayne10823014/lab0-c/commit/49f4d09eb9c1a6835f7b296c0b2e650404819815) 143行 `char *maxVal = NULL;` 這個拿掉。解決辦法就是每次 commit 前整理程式碼。
3. [commit 826d272](https://github.com/wayne10823014/lab0-c/commit/826d272ca606f81146c56e4676e640624cc1a497) 寫程式前先看好規則的優點：避免浪費時間。
4. 減少多餘的大括號，判斷式裡面只有一行就可以拿掉。優點無用的大括號一旦減少，那就有更多的行來寫註解。

## 開發環境

$ gcc --version
(Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

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) i5-8265U CPU @ 1.60GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            11
    CPU max MHz:         3900.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3600.00

:::warning
將語系設定為 `C`，亦即執行 `export LC_ALL=C`，再執行上方的命令，這樣才會得到英文的訊息。
:::

## 針對佇列操作的程式碼實作
### `q_insert_head`
一開始的程式碼為以下

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *node = malloc(sizeof(element_t));
    if (!node) {
        return false;
    }
    char *str = malloc(sizeof(char) * strlen(s) + 1);
    if (!str) {
        return false;
    }
    strcpy(str, s);
    node->value = str;
    list_add(&node->list, head);
    return true;
}

:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::

出現了兩個問題
1. strcpy <s>函數</s> 函式被警告為危險函式，建議使用 strncpy 進行替代。 strncpy 允許指定最大複製<s>字符數</s> 位元組的數量，從而避免緩衝區溢出的問題。
2. 在檢查 str 是否成功配置的條件中，遇到 "記憶體洩漏: node" 的問題。發現 str 在 malloc <s>分配</s> 配置時失敗，應該釋放先前為 node 配置的空間。

:::warning
function 一字多義，務必依據場景提供合適的翻譯。對應到數學公式，function 應翻譯為「函數」，後者就像是台「機器」，它能夠將集合 A 裡面的每個元素「唯一地」對應到集合 B 裡的一個元素。但在 C 語言一類的通用程式語言中，function 未必具備數學函數的意涵，也就是缺乏「唯一對應」的特性，例如對於 time 來說，給定同樣的輸入，卻會在不同時間點得到不同的結果，在 C 語言一類的通用程式語言中，甚至可省略傳回值，後者就不符合「函數」的行為。因此，當在通用的程式設計中，function 應翻譯為「函式」，表示「衍生自數學函數的常式 (routine)」。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)

allocate 翻譯為「配置」，而非「分配」，是為了跟「分發」(dispatch) 區隔，二者都會在作業系統領域多次出現。
:::

:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::

修正後

     char *str = malloc(sizeof(char) * strlen(s) + 1);     
     if (!str) {
+        free(node);
         return false;
     }
-    strcpy(str, s);     
+    strncpy(str, s,strlen(s) + 1);
     node->value = str;
     list_add(&node->list, head);
     return true;

:::warning
使用 diff 工具程式來產生程式碼差異，注意縮排
:::

:::danger
改進你的漢語表達。
:::

### `q_free`
一開始的程式碼為以下

void q_free(struct list_head *l)
{
    if (!l) {
        return;
    }
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, l, list) {
        free(entry);
    }
    free(l);
}

出現 "已釋放佇列，但仍分配 52199562 個區塊" 的錯誤。檢查後發現已釋放 entry 配置的空間，但 entry 內的 value 所使用的空間並未一併釋放。因此需要添加程式碼來釋放 value 所擁有的空間

修正後

     }
     element_t *entry, *safe;
     list_for_each_entry_safe (entry, safe, l, list) {
+        if (entry->value) {
+            free(entry->value);
+        }
         free(entry);
     }
     free(l);

:::warning
參閱 [free(3)](https://man7.org/linux/man-pages/man3/free.3.html) 可知 "If ptr is NULL, no operation is performed."，意味著你不用撰寫形如 `if (entry->value) { free(entry->value); }` 的程式碼，直接呼叫 `free` 即可，不用額外的 `if` 敘述。
:::

根據規格書中
>The free() function frees the memory space pointed to by ptr,which must have been returned by a previous call to malloc() or related functions. Otherwise, or if ptr has already been freed,undefined behavior occurs. If ptr is NULL, no operation is performed.

在 ptr 為 NULL 的情況下，使用 free() 釋放 ptr 不會有任何作用。

修正多餘的 if 判斷式

     }
     element_t *entry, *safe;
     list_for_each_entry_safe (entry, safe, l, list) {
-        if (entry->value) {
-            free(entry->value);
-        }
+        free(entry->value);
         free(entry);
     }
     free(l);

### `q_delete_mid`
一開始的程式碼為以下

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head)) {
        return false;
    }
    struct list_head *node = head;
    for (struct list_head *fast = head; fast && fast->next;
        fast = fast->next->next) {
        node = node->next;
    }
    element_t *tmp = list_entry(node, element_t, list);
    list_del(node);
    free(tmp->value);
    free(tmp);
    return true;
}

出現 "錯誤：時間限制已超過。可能是你的程式碼進入了無限迴圈，或者你的程式碼效率不足" 。發現因為題目是雙向鏈結串列，若繼續使用原本在 LeetCode 上的寫法，會造成 for 迴圈永遠無法停止。同時，修正了 fast 與 node 初始位置設定錯誤造成的問題。

修正後

     if (!head || list_empty(head)) {
         return false;
     }
-    struct list_head *node = head;
-    for (struct list_head *fast = head; fast && fast->next;
+    struct list_head *node = head->next;
+    for (struct list_head *fast = head->next;
+         fast != head->prev && fast->next != head->prev;
          fast = fast->next->next) {
          node = node->next;
     }

:::warning
善用 List API，撰寫更精簡的程式碼。
:::

### `q_sort`