2024q1 Homework1 (lab0)

contributed by < w96086123 >

Reviewed by weihsinyeh

1. commit 8477620 說list_for_each_entry_safe 可以解決 older solution don't free element. 的原因會讓讀者更清楚修改的用意。
2. commit 77f096a 看merge的程式碼讓我發現原來可以這樣使用 LIST API ，而不用寫得很冗長。可以將想法寫到 commit 裡面。
3. 除了在 commit 裡面紀錄修改，也可以把每次 modify 的原因寫在開發紀錄裡面。好處就是自己有哪些問題可以順便紀錄，而不用在 commit 的前要先把自己有疑慮的程式註解掉，節省麻煩。

開發環境

​​​​$ gcc --version
​​​​(Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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):                  12
​​​​  On-line CPU(s) list:   0-11
​​​​Vendor ID:               GenuineIntel
​​​​  Model name:            Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
​​​​    CPU family:          6
​​​​    Model:               158
​​​​    Thread(s) per core:  2
​​​​    Core(s) per socket:  6
​​​​    Socket(s):           1
​​​​    Stepping:            10
​​​​    CPU max MHz:         4100.0000
​​​​    CPU min MHz:         800.0000
​​​​    BogoMIPS:            4399.99

指定的佇列操作

q_new

使用 git rebase -i 重新撰寫 git commit message，務必詳閱作業說明提及的規範

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

利用 malloc 進行記憶體配置，並利用 list.h 中的 INIT_LIST_HEAD 讓 head 自己指向自己，達成空佇列的表示。

改進你的漢語表達。

q_free

使用 git rebase -i 重新撰寫 git commit message，務必詳閱作業說明提及的規範

先理解 list_for_each_entry_safe 這個巨集

留意資訊科技詞彙翻譯

此巨集代表的是將 List 更迭，過程中會將 next 讀入並且存起來，此作法稱為 safe ，因此適合用於刪除 List 的時使用。
並且需要搭配我希望可以搭配 q_release_element ，因此我選擇使用 list_for_each_entry_safe 。

將 List 更迭一次。在的過程中，將當前的 node 進行刪除，並將該空間釋放出來，達到釋放佇列的空間。

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

q_insert_head

先理解 element_t 這個型態裡包含什麼

typedef struct {
    char *value;
    struct list_head list;
} element_t;

可知 element_t 中會儲存值與前後節點的指向

先建立一個 element_t 的型態並命名為 new_element ,後將 s 複製給 new_element 的 value ，並且利用 list_add_head 這個巨集進行在 head 的地方插入，若以上動作都可完成，傳回 ture ，否則回傳 false

q_insert_tail

使用 git rebase -i 重新撰寫 git commit message，務必詳閱作業說明提及的規範

與 q_insert_head 作法相似。不同之處為利用的巨集不同，此功能需要用到的巨集為 list_add_tail 。

q_remove_head

使用 git rebase -i 重新撰寫 git commit message，務必詳閱作業說明提及的規範

由於註解上只有寫 Remove an element from head of queue ，但回傳的型態是 element_t，因此要先了解回傳的內容是什麼

由於回傳的型態為 element_t ，因此可以猜測實作的方式為將 head 由佇列中刪除，且不用釋放原有的空間，並返回 head 即可。

q_remove_tail

使用 git rebase -i 重新撰寫 git commit message，務必詳閱作業說明提及的規範

與 q_remove_head 相似，只需要將提取的地方由 first 改成 last 即可。

q_delete_mid

使用 git rebase -i 重新撰寫 git commit message，務必詳閱作業說明提及的規範

直觀作法為先取得 queue 的大小，並且除以2取得中間的索引值，後將中間節點移除並且釋放空間。

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

由於上課有提到快慢指標的方式，嘗試使用此作法。

為何要捨近求遠？教材已針對上述議題討論，你該在此展現自己的洞見。

q_delete_dup

建立兩個指標 prev and current ，藉由比較指標的內容來判斷是否有重複，若有重複則將 current 所指向的內容刪除，並且將 current 指向下一個點，若沒有相同，則將 prev and current 指向各至的下一個節點。

改進你的漢語表達。

原有的刪除方式會遺留一個重複的節點，因此結果出錯。
所以加入一個 bool 變數判斷目前節點是否曾為重複的。若目前節點與下個節點數值不一樣且 bool 為真時，則刪除目前節點，已解決原有的問題。

q_swap

參考 Han1018，他利用了迴圈的處理方式，先分成初始化、條件式和計算方式三個部份，初始化的部份，會先建立兩個指標，個別指向 head->next 和 head->next->next，條件式的條件為只有其中一個指標為 head 時則跳出迴圈，計算方式的部份則是個別指標往後跳兩格，達到處理一對的效果。

不要說「似乎」「有點」這種不清晰的話語，工程人員說話要精準。學員投入時間到這門課程，就是希望自己的專業素養能提升，你既然發現他人的不足，就該清楚陳述你認為更好的方案，並予以討論。

假裝有禮貌，無助於討論。

但是這位同學的指標名稱不好，分別為 li 和 tmp ，這樣的寫法無法很容易判斷相互關係，因此我將指標名稱改成 pre 和 current ，提昇可讀性。

你的開發紀錄當然反映出「你的觀點」，因此不用說「個人認為」，清楚闡述考量即可。在第 3 次作業中，你可充分發揮。

q_reverse

利用 list_for_each_safe 的操作，可以一次取得目前與下一個節點。在遍歷的過程中，進行以下操作，將目前節點的 next 與 prev 進行交換，直到結束。

q_reverseK

原本想要利用 q_reverse 進行修改，但發現如果用此方式需要進行切割，所以會產生多於步驟，譬如：切割。因此改成移動 head 與將目前的 node 移動至當前 head 的方法，進行處理。
另外每組需要交換的數量要設定為輸入值減一，理由為，因為使用的方法為將 node 移動至當前的 head 並且初始開始移動的 node 為 head->next ，因此每組實際移動的量只有輸入值減一。

q_sort

Sort 有許多種方法，譬如： quick sort ， merge sort 等等。
因為原本需要提供 merge 方法，因此我實作 merge sort ，實作方法如下。

1. 使用快慢指針尋找中間節點。
2. 利用 list_cut_position 和 list_splice 進行切割。
3. 利用遞迴的方式對切割後的兩個 list 再次進行切割。
4. 進行 merge

q_merge

一開始看到 head 為 list_head 時，感到疑問，因為要進行合併應該要為多的鏈結的 head ，因此觀看同學們的程式碼與 qtest 發現格式一開始要先轉換為 queue_contex_t 。

queue_context_t

趙韋霖 需要尋找如何讓線不要與節點重疊。

依照上面的 queue_context_t 的架構內容，知道使用合併前需要先使用 contain_of 進入各 q 取得每個 link list 的 head ，後續就使用常用 merge 方法。

q_ascend 和 q_descend

兩組方法相似，差異只為遞增或遞減，因此可以寫為同一個函式。
根據 Leetcode 給予的兩個 Hit ，知道在原有的題目上需要 Reverse 與儲存目前的最大值。
由於 Leetcode 給予的資料結構為單向鍊結，但在使環境下使用的是雙向環狀鍊結，因此可以直接使用 prev ，不需要進行反轉。