2025q1 Homework1 (lab0)

contributed by <eric895888>

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [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 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ ldd --version
ldd (Ubuntu GLIBC 2.35-0ubuntu3.9) 2.35
Copyright (C) 2024 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Written by Roland McGrath and Ulrich Drepper.

$ 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:             11th Gen Intel(R) Core(TM) i5-11300H @ 3.10GHz
    CPU family:           6
    Model:                140
    Thread(s) per core:   2
    Core(s) per socket:   4
    Socket(s):            1
    Stepping:             1
    CPU max MHz:          4400.0000
    CPU min MHz:          400.0000
    BogoMIPS:             6220.80

queue.c 開發過程

q_new

在實作過程中發現到new_node要先檢查 head 是否為 NULL，原本沒有檢查是否成功配置記憶體位置給new_node會導致執行錯誤。

list_head *q_new()
{
    list_head *new_node = (list_head *)malloc(sizeof(list_head));
    
    if (!new_node) {
        return NULL;  
    }

    new_node->prev = new_node;
    new_node->next = new_node;

    return new_node;  
}

q_free

先依序訪問各個節點並將其刪除且釋放記憶體，一開始忘記最後加上free(head)導致鏈結串列已空但仍有記憶體佔用的情況發生。

list_for_each_entry_safe (curr, safe, head, list) 
    q_release_element(curr);

q_insert_head

確保記憶體分配成功後才進行插入節點node到head後方，使用 strdup() 複製字串，避免修改原字串導致錯誤，再更新雙向鏈結串列的 next 和 prev 指標，確保鏈結完整，使用的是list.h裡的list_add()去完成。

q_insert_tail

跟上面的區別在於更新雙向鏈結串列的連接不同改成插入節點 node 到 head 前方，使用的是list.h裡的list_add_tail()去完成。

q_remove_head

一開始判斷是否為空,後來利用 container_of() 找出 head 的 next 節點，把node->value的值存 bufsize 給sp，而sp的最後一個字元改成結束符號'\0'。

if (sp && node->value) {
    strncpy(sp, node->value, bufsize );
    sp[bufsize - 1] = '\0';  
}

刪除節點的方式是利用list.h裡list_del()改變前後節點的連結。

q_remove_tail

一開始判斷是否為空,後來利用 container_of() 找出 head 的 next 節點，其餘與q_insert_tail() 作法相同。

q_size

針對雙向連結串列走訪一次判斷是不是又回到 head ，並使用 count 紀錄個數。

q_delete_mid

這邊採用的是快慢指標的方式去尋找中間節點，再利用 list_del 刪除鏈結串列找到的中間節點及q_release_element() 釋放那個節點的記憶體。

struct list_head *slow = head->next, *fast = head->next; //first element

while (fast != head && fast->next != head) {
    slow = slow->next;
    fast = fast->next->next;
}

q_delete_dup

用 list_for_each_safe() 來走訪鏈表，其中 curr 指向當前節點，safe 指向下一個節點，以確保在刪除節點時不影響遍歷。在循環中，若 curr 和 safe 的值相同則刪除 curr，並標記 dup = true 表示當前值有重複。如果 dup 為 true，代表前一個元素是重複的，因此刪除 node，直到遇到不同的值時，將 dup 重置為 false。最後，成功執行後返回 true，表示刪除了重複元素。
但是原始leecode中的題目只會給排序好的鏈結串列作為輸入，我的作法目前也只能刪除連續的重複值。

q_swap

做到 q_reverseK() 才發現 q_swap() 相當於 q_reverseK(head, 2)。

q_reverse

例如 head <-> A <-> B <-> C <-> D <-> head，curr初始指向head，針對每一個節點的next及prev做反轉。

truct list_head *prev = head->prev, *curr = head, *next = head->next;

while (next != head) {
    next = curr->next;
    curr->next = prev;
    curr->prev = next;
    prev = curr;
    curr = next;
}

q_reverseK

用len 計算是否等於k再運用list_cut_position()，切下長度為k的連結串列存到splited_list_head中，再把splited_list_head反轉，透過list_splice（）去原本的位置。

q_sort

使用另外撰寫的merge_sort（）先拆分成一半分成左右區塊再繼續遞迴呼叫merge_sort（）繼續拆分，之後使用two_list_merge（）進行合併再依照descend的布林值決定是否降序排列。

q_ascend

對於任意一個在佇列中的節點，其前面的節點必定要小於自己，且其後面的節點必定大於自己。

q_descend

對於任意一個在佇列中的節點，其前面的節點必定要大於自己，且其後面的節點必定小於自己。

q_merge

會使用到 queue_contex_t 這個結構，看了許多資料才知道使用這個結構來做這題會更方便實作，使用list_for_each_entry（） 走訪鏈表中每個 queue_contex_t ，並將每個佇列 (curr->q) 中的元素移動到 tmp 中，最後呼叫q_sort（）對tmp 排序，並放回head所指向的第一個佇列。

queue_contex_t *first = list_first_entry(head, queue_contex_t, chain);
queue_contex_t *curr;

list_for_each_entry(curr, head, chain){
    list_splice_init(curr->q, &tmp);
}

q_sort(&tmp, descend);
list_splice_init(&tmp, first->q);