2025q1 Homework1 (lab0)

contributed by < kurtislin >

作業書寫規範:

  • 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
  • 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
  • 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
  • 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
  • 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
  • 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
  • HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
  • 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
  • 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
  • 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
  • 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
  • 避免使用不必要的 emoji 字元

開發環境

$gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          46 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   24
  On-line CPU(s) list:    0-23
Vendor ID:                GenuineIntel
  Model name:             13th Gen Intel(R) Core(TM) i7-13700
    CPU family:           6
    Model:                183
    Thread(s) per core:   2
    Core(s) per socket:   16
    Socket(s):            1
    Stepping:             1
    CPU(s) scaling MHz:   55%
    CPU max MHz:          5200.0000
    CPU min MHz:          800.0000
    BogoMIPS:             4224.00

用linked list實做queue

q_new,q_free Commit 732fa62

new 和 free 是密切相關的操作

q_new
建立新的鍊結串列的節點 回傳初始化完成的queue
q_free
遍歷鍊結串列 釋放所有節點 最後還要釋放head

q_insert_head , q_insert_tail Commit aab9360

q_insert_head 在佇列的頭部插入新元素
q_insert_tail 在佇列的尾部插入新元素

  • 首先檢查輸入參數的有效性
  • 為新元素分配記憶體
  • 為字串值創建一個副本
  • 使用 list.h 中定義的 list_add 函數將節點添加到頭部
  • 返回操作結果

q_size,q_remove_head,q_remove_tail Commit 3066919

q_size 在計算佇列裡的元素數量
q_remove_head,q_remove_tail 在移除佇列的頭部元素和尾部元素

在實作 q_remove_head 和 q_remove_tail 函數時，我們採用輸出參數模式，透過 sp 緩衝區參數和返回值同時提供元素指針與元素內容。這種設計讓單一函數調用能夠返回多種資訊，提升了函數的靈活性，使調用者可根據需求選擇獲取所需的資料形式。

q_reverse Commit c04198f

q_reverse將佇列所有元素反轉

q_swap Commit a46fa1d

q_swap 將相鄰的節點交換

q_delete_mid q_reverseK Commit d3a52e3

q_delete_mid 利用快慢指標實現
q_reverseK 利用temporary list 實現，在q_reverseK 函數中，我使用了 struct list_head temp_head 而不是指標 struct list_head *temp_head 來宣告臨時頭節點，主要有以下原因：

堆疊（Stack）分配 vs. 堆（Heap）分配:

直接宣告 struct list_head temp_head 會在函數的堆疊上分配記憶體
使用指標 struct list_head *temp_head 則需要使用 malloc 從堆中分配記憶體，並在使用完後需要 free
堆疊分配更快速，也不需要擔心記憶體洩漏

q_delete_mid Commit a290040

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    bool removed = false;
    struct list_head *node = head->next;

    while (node != head && node->next != head) {
        element_t *curr_elem = list_entry(node, element_t, list);
        element_t *next_elem = list_entry(node->next, element_t, list);

        if (!strcmp(curr_elem->value, next_elem->value)) {
            removed = true;
            char *dup_val = curr_elem->value;

            while (node != head) {
                element_t *check_elem = list_entry(node, element_t, list);
                if (!strcmp(check_elem->value, dup_val)) {
                    struct list_head *tmp = node->next;
                    list_del(node);
                    q_release_element(check_elem);
                    node = tmp;
                } 
                else 
                    break;
            }
        } 
        else 
            node = node->next;
    }

    return removed;
}

以上是我一開始的代碼但是不管怎麼測試都會剩下一個元素

測試資料中沒有要刪除的元素時也會有以下問題

l = [1 2 3 4]
cmd> dedup
ERROR: Calling delete duplicate on null queue

之後發現問題是出現在執行q_release_element(check_elem)時，釋放了元素的記憶體，包括 check_elem->value。但是dup_val 指針是指向 curr_elem->value，所以造成懸空指標，之後改成char *dup_val = strdup(curr_elem->value);就可以了

Select a repo