# 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 配置所需記憶體，接著用 <s>macro</s> `INIT_LIST_HEAD` 初始化 list_head

:::warning
`INIT_LIST_HEAD` 不是巨集。
:::

:::danger
說好的進度呢？
> 會慢慢把寫好的進度補上 🙏
:::

### `q_free`

:::danger
- [ ] traverse (動詞) 和 traversal (名詞)

根據 Dictionary.com 的[解釋](https://www.dictionary.com/browse/traverse
): (作為及物動詞和不及物動詞都有類似的意思，以下列出作為及物動詞的寓意)
* 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](https://en.wikipedia.org/wiki/Ludwig_Boltzmann)) 於統計力學領域 (statistical mechanics) 提出的概念，其一廣為人知的結果是：在經過長時間後，時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色，在隨機分析領域亦然。

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

$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

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

:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(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。

:::danger
改進你的漢語表達。
> fixed
:::

### `q_swap`

### `q_reverse`

### `q_reverseK`

### `q_sort`

### `q_ascend、q_descend`

### `q_merge`

:::danger
commit [add implement to all function without merge.](https://github.com/cseslowpoke/lab0-c/commit/c3b785e7d6fb4349f8fc80c3f3a63ab2c11945dc) 不符合作業規範，請詳閱教材並修正 git commit message。

用 `git rebase -i` 修正。
> commit [1b3237](https://github.com/cseslowpoke/lab0-c/commit/1b3237d1cfc5d176c2853a7ef1189a0c8e6821e9)
> 根據 [如何寫一個 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/#rules05) 中提到的，好的 commit messages 需要遵守七個規則，
>
> 當你宣稱改進後，要列出 git commit SHA-1 的超連結，並檢討之前哪裡沒做好。
:::

## 遇到的一些問題

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

:::warning
`git rebase` 到最新的 `lab0-c`
:::