2024q1 Homework1 (lab0)

contributed by < cseslowpoke >

開發環境

$ gcc --version
gcc (GCC) 13.2.1 20231205 (Red Hat 13.2.1-6)
Copyright (C) 2023 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.

$ lscpu
Architecture:           aarch64
  CPU op-mode(s):       64-bit
  Byte Order:           Little Endian
CPU(s):                 8
  On-line CPU(s) list:  0-7
Vendor ID:              Apple
  Model name:           Icestorm-M1
    Model:              1
    Thread(s) per core: 1
    Core(s) per socket: 4
    Socket(s):          1
    Stepping:           0x1
    Frequency boost:    enabled
    CPU(s) scaling MHz: 83%
    CPU max MHz:        2064.0000
    CPU min MHz:        600.0000
    BogoMIPS:           48.00

指定的佇列操作

`q_new`

先 malloc 配置所需記憶體，接著用 ~~macro~~ INIT_LIST_HEAD 初始化 list_head

INIT_LIST_HEAD 不是巨集。

說好的進度呢？

會慢慢把寫好的進度補上 🙏

`q_free`

traverse (動詞) 和 traversal (名詞)

根據 Dictionary.com 的解釋: (作為及物動詞和不及物動詞都有類似的意思，以下列出作為及物動詞的寓意)

to pass or move over, along, or through.
to go to and fro over or along.

其實這意思很好懂，就像我們「走過」/「穿越」校園一般，於是 traverse a linked list 就會是「(用某種手段) 存取多個鏈結串列的節點」，但這裡卻沒有必要「所有」的範圍：英語的 "move over/through" 用於某個區域時，根本沒有這樣的隱含意義。如果將 traverse 翻譯為「遍歷」，就會導致「超譯」，也就是跳脫「直譯」和「意譯」。

當我們回頭看 "traverse" 所在的技術描述內容，例如 "traverse every node"，若翻譯為「遍歷每個節點」，那麼既然都「遍」(意即「全面」、「到處」)，又何來「每個」節點呢？於是，合理的翻譯應改為「逐一走訪每個節點」 —— 差異在哪？在 "traverse every node" 的應用場景中，可能是我們嘗試在鏈結串列尋找特定的節點內含的資料，一旦找到就停止，或者我們要偵測給定的鏈結串列是否包含環狀 (circular) 結構，並沒有真的要「遍」(到處/全面)「歷」(意即「經過」) 每個節點。在我們的用語中，要區分「意圖」(intention) 和「實際作用」(reaction)，濫用「遍歷」會使得語意不清，從而難以推測英語原文的訴求。

還有個更重要的原因是，「遍歷」這詞已在理工領域存在，且廣泛使用，即「遍歷理論」(Ergodic theory)，後者是研究具有不變測度 (invariant measure) 的動力系統及其相關問題的一個數學分支。遍歷理論研究遍歷變換，由試圖證明統計物理中的遍歷假設 (Ergodic hypothesis) 演進而來。

在統計學中，若單一個物理系統在不同時間內重複相同的實驗 (如丟擲一枚硬幣)，其取樣數據所得的統計結果 (如硬幣出現正面的機率) 和極多個完全相同的物理系統的系集 (如丟極多個相同的硬幣) 在同時作相同的實驗取樣數據的統計結果假設為相同時，此種假設即稱為「遍歷性假設」或「遍歷假設」。基於這個假設，對時間平均的統計方式及結果，便可由對系集的平均及統計方式得到。在一般物理系統中，尤其在統計力學範圖中，均採用此遍歷性假設為基本的假設。在流體力學中對亂流的實驗分析，亦是採用此假設。

遍歷 (Ergodic) 源於以下二個希臘詞：

ergon (對應英語的 work)
odos (對應英語的 path 或 way)

最初這是由奧地利物理學家波茲曼 (Ludwig Boltzmann) 於統計力學領域 (statistical mechanics) 提出的概念，其一廣為人知的結果是：在經過長時間後，時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色，在隨機分析領域亦然。

因此，若貿然將 traverse 翻譯為「遍歷」，一來語意不清，二來增加和理工多項領域專業人員的溝通成本，實在得不償失。

\to

資訊科技詞彙翻譯

用 list_for_each_entry_safe 逐一走訪鏈結串列的每個節點，在走訪的過程用 q_release_element 將走訪到的節點使用的記憶體釋放掉。

避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。

`q_insert_head、q_insert_tail`

配置記憶體空間並將輸入通過 strncpy 複製到節點上，接著使用 list_add 將節點插入到開頭， q_insert_tail 的過程也類似，只是將 list_add 改成 list_add_tail。

`q_remove_head、q_remove_tail`

用 list_first_entry、list_last_entry 獲取完整的節點，將節點的資訊使用 strncpy 複製到傳入的指標 sp，接著使用 list_del 將 list 斷開，並將節點回傳。

`q_delete_mid`

使用快慢指標的概念，慢指標向前一步時，快指標向前兩步，這樣快指標回到 head 時，慢指標就會在 list 的中間，接下來就用 list_del，將指標指向的 list 斷開，再用 list_entry 取得完整節點、q_release_element 將節點使用的記憶體釋放。

`q_delete_dup`

使用 list_for_each_entry_safe 來逐一走訪鏈結串列中的每一個節點。在這個過程中，利用 strcmp 函數來比較當前節點 (entry) 與下一個安全節點 (safe) 的值。

如果 strcmp 返回 0（表示 entry 與 safe 的值相等），則釋放當前節點（entry），並將一個標誌（flag）設為 1。

當 strcmp 返回一個非 0 值（即 entry 與 safe 的值不相等）時，檢查標誌（flag）。如果標誌為 1，則釋放當前節點（entry），並將標誌（flag）重置為 0。

改進你的漢語表達。

fixed

`q_swap`

`q_reverse`

`q_reverseK`

`q_sort`

`q_ascend、q_descend`

`q_merge`

commit add implement to all function without merge. 不符合作業規範，請詳閱教材並修正 git commit message。

用 git rebase -i 修正。

commit 1b3237
根據如何寫一個 Git Commit Message 中提到的，好的 commit messages 需要遵守七個規則，

當你宣稱改進後，要列出 git commit SHA-1 的超連結，並檢討之前哪裡沒做好。

遇到的一些問題

~~1. cppcheck 版本過新導致靜態分析時會需要去修改到非作業的程式碼，例：queue.h。 :::success 解決方式：將 cppcheck 的版本降到其他同學使用的 2.9 :::~~

git rebase 到最新的 lab0-c