2025q1 Homework1 (lab0)

contributed by < JUSTUSVMOS >

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [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:          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) i7-9700K CPU @ 3.60GHz
    CPU family:           6
    Model:                158
    Thread(s) per core:   1
    Core(s) per socket:   8
    Socket(s):            1
    Stepping:             13
    BogoMIPS:             7200.01

Linux Kernal 風格鏈結串列

在 Linux kernel 中，鏈結串列的基本元件是 struct list_head。其定義通常如下：

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

• 雙向鏈結串列：list_head 包含兩個指標，分別指向前一個及後一個節點，形成一個雙向鏈結串列。
• 循環鏈結串列：設計上，鏈結串列通常是循環的，這表示鏈結串列頭的 prev 指向最後一個節點，而最後一個節點的 next 指向鏈結串列頭。這種設計可以簡化插入與刪除操作時對邊界情形的處理。

為了靈活運用鏈結串列，Linux kernel 採用「嵌入式」設計，只需在自訂型別中加入一個 struct list_head 成員，即可將該型別放入鏈結串列。：

element_t：
通過嵌入 struct list_head 成員，使得每個 element_t 可以成為一個節點，串聯成一個循環雙向鏈結串列，便於管理隊列中的各個元素。

typedef struct {
    int data;
    struct list_head list;
} element_t;

queue_contex_t：
包含一個指向實際鏈結串列（由 element_t 節點組成）的 q 指標，以及一個 chain 成員用於將多個隊列上下文連成一個雙向鏈結串列，另外還有記錄隊列大小及唯一標識的成員。

typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

• q 是一個指向 struct list_head 的指標，指向該隊列的頭節點。這個鏈結串列頭管理著由 element_t 組成的節點列表。
• chain 是一個 struct list_head 變數，用於將多個 queue_contex_t 結構串聯在一起。
  這樣可以形成一個雙向鏈結串列，使得各個隊列上下文可以被集中管理。
• size 用於記錄該隊列中的元素數量。
• id 用於唯一標識該隊列。