2024q1 Homework1 (lab0)

contributed by < alianlbj23 >

Reviewed by allenliao666

• Git commit 都有依照修改項目撰寫對應的commit，而且沒有把多個函式修改全記錄在同一次 coomit 中，也有撰寫修改的原因及方法等等，方便日後追蹤，很值得我學習。
• 建議在 q_reverse 的部分增加從 do-while 迴圈修改為 while 的理由。
• q_swap 可以使用間接指標使程式碼更優雅簡潔。

Reviewed by brian049

• commit message 描述清楚明瞭。

開發環境

$ neofetch --stdout
OS: Kubuntu 22.04.4 LTS x86_64 
Host: Modern 15 A5M REV:1.0 
Kernel: 6.5.0-21-generic 
Uptime: 14 mins 
Packages: 3004 (dpkg), 12 (snap) 
Shell: zsh 5.8.1 
Resolution: 1920x1080, 2560x1440 
DE: Plasma 5.24.7 
WM: KWin 
Theme: [Plasma], Breeze [GTK2/3] 
Icons: [Plasma], breeze-dark [GTK2/3] 
Terminal: konsole 
Terminal Font: MesloLGS NF 14 
CPU: AMD Ryzen 7 5700U with Radeon Graphics (16) @ 4.372GHz 
GPU: AMD ATI 04:00.0 Lucienne 
Memory: 3590MiB / 15338MiB

指定佇列的操作

q_new

建立一個名為 struct list_head 的結構體，並使用 list.h 內的 INIT_LIST_HEAD 初始化成雙向鏈結串列

q_free

使用 list.h 內的 list_for_each_entry_safe 走訪每個節點，需要注意釋放完傳入的鏈結串列底下的節點後，頭節點也要被刪除。

q_insert_head和q_insert_tail

使用 list.h 內的 list_add 和 list_add_tail 函式，可以將新的節點分別插入於鏈結串列的頭部和尾部。

這邊使用strdup 而非 strcpy 的原因在於 strdup 可自動計算字串長度，並分配足夠的記憶體複製儲存的字串，從而避免了 strcpy 在使用時可能導致緩衝區溢出的問題。

    new_node->value = strdup(s);

q_size

逐一走訪節點以求得指定鏈結串列的長度

q_reverse

考慮到使用 while 並以 current != head 作為條件，一開始將 current = head 會有矛盾，因此使用 do-while 讓它先做過一遍在判斷就能解決矛盾的問題。

    do {
        temp = current->next;
        current->next = current->prev;
        current->prev = temp;
        current = temp;
    } while (current != head);

為了確保在 while 循環的開始也能正確處理而沒有矛盾，因此修改成以下程式碼

-    do {
-        temp = current->next;
-        current->prev = temp;
-        current->next = current->prev;
-        current = temp;
-    } while (current != head);
+    if (!head || list_empty(head))
+        return;
+    struct list_head *current = head, *next = NULL;
+    while (next != head) {
+        next = current->next;
+        current->next = current->prev;
+        current->prev = next;
+        current = next;
+    }

每次的循環會修改 next 指向目前節點的下一個指標，藉此判斷是否走完了全部的節點。

q_swap

對於現行節點 current 和其下一個節點 next，通過修改它們的 prev 和 next 指標來進行交換。接著更新 current 和 next 指向下一對相鄰節點，以便進行下一輪的交換。

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

參考了 ChenFuhuangKye 內的程式碼，發現他使用了 list_move 大幅簡化了程式碼，觀察 list_move 的敘述

list_move(struct list_head *node, struct list_head *head)

這個函式的設計允許我們將一個節點移動到另一個特定位置，特別是移動到鏈結串列的開頭。list_move 的實現依賴於兩個基本操作：list_del 和 list_add 。

功能說明

這個函式的主要功能是將一個節點從它當前的位置移動到一個新的位置，這個新位置是作為 head 節點之後的第一個元素。

實做 細節

對照 Dictionary.com 對 implement 一詞的解釋:

• to fulfill; perform; carry out:
• to put into effect according to or by means of a definite plan or procedure.
• Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
• to fill out or supplement

「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。

$\to$ 資訊科技詞彙翻譯

• list_del
  • 指定節點將從鏈結串列中移除。通過讓該節點的前後節點互相連接，並跳過該結點達成，因此指定節點不會被刪除。
• list_add
  • 接著將 list_del 刪除的節點新增至 head 的開頭。

操作過程

1. 初始狀態
   假設有一個鏈結串列為以下所示， node 指向1， head 指向2

2. 執行 list_del 節點 node 會被跳過，而 node 前後節點互相連接

3. 執行 list_add
   節點 node 會新增至 head 之後，因此最終的鏈結串列變成

使用 Graphviz 予以視覺化，並嵌入到 HackMD 筆記中

-    struct list_head *current = head->next, *next = current->next;
-    while (current != head && next != head) {
-        current->prev->next = next;
-        next->prev = current->prev;
-        current->next = next->next;
-        next->next->prev = current;
-        current->prev = next;
-        next->next = current;
+    struct list_head *current = head->next;
+    while (current != head && current->next != head) {
+        list_move(current, current->next);
         current = current->next;
-        next = current->next;
     }

HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」