2024q1 Homework1 (lab0)

contributed by < wayne10823014 >

Reviewed by weihsinyeh

1. 邊寫程式碼邊更新開發紀錄，很多程式沒被紀錄進來。
2. commit 49f4d09 143行 char *maxVal = NULL; 這個拿掉。解決辦法就是每次 commit 前整理程式碼。
3. commit 826d272 寫程式前先看好規則的優點：避免浪費時間。
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

將語系設定為 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;
}

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

出現了兩個問題

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

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

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

避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(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;

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

改進你的漢語表達。

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);

參閱 free(3) 可知 "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;
     }

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

q_sort