# 2024q1 Homework1 (lab0)
contributed by < `v0103` >
### Reviewed by `Vincent550102`
### Reviewd by `vax-r`
* 只完成部分 queue.c 之操作函式，而且也沒有進行任何改進
* github commit message 依舊過於簡短並且沒有完整表達 why v.s. how
1. `q_sort`、`q_ascend`、`q_descend`、`q_merge` 尚未實作
2. `q_reverseK` 可善用 `list_cut_position`、`list_splice_init` 等內建巨集，例如：
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_empty(head))
return;
struct list_head *li, *safe, *tmp = head;
LIST_HEAD(tmp_head);
int i = 0;
list_for_each_safe (li, safe, head) {
if (++i == k) {
list_cut_position(&tmp_head, tmp, li);
q_reverse(&tmp_head);
list_splice_init(&tmp_head, tmp);
tmp = safe->prev;
i = 0;
}
}
}
```
### Reviewed by `w96086123`
1. `q_insert_head` 中有提出必須檢查的條件，這時的排版應該要以編號來表示而不是直接使用換行來表達，這樣會讓人不知道這裡是在表達什麼意思。
2. 不需要把程式碼完整呈現出來。
### Reviewed by `vestata`
1. 若是在修改的地方附上 commit 連結可以加快查閱速度。
2. git commit message 不符合 [如何寫好 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/) 中的規範。
3. 開發紀錄中應減少使用第一人稱「我」，以便更清晰地傳達資訊。
## 開發環境
```shell
$ gcc --version
gcc (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): 6
On-line CPU(s) list: 0-5
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-9400F CPU @ 2.90GHz
CPU family: 6
Model: 158
Thread(s) per core: 1
Core(s) per socket: 6
Socket(s): 1
Stepping: 10
CPU max MHz: 4100.0000
CPU min MHz: 800.0000
BogoMIPS: 5799.77
```
## 針對佇列操作的程式實作
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
### `q_new`
這裡的 `if` 條件是為了確保前面的 `malloc` 函式能夠成功配置足夠大小的記憶體給 `new` 指標。若配置失敗， `malloc` 會返回 `NULL` ，因此在這種情況下，函式會直接回傳 `NULL` 。
初始化部分原本是以手動方式實作，後來發現在`list.h`中已經有適用的函式，因此決定直接使用該函式。這樣的做法有助於提高程式碼的重用性和可讀性，<s>避免重複造輪子</s>。
:::warning
閱讀 Wikipedia: [Reinventing the wheel](https://en.wikipedia.org/wiki/Reinventing_the_wheel)，思考前後文是否合理。
:::
```c
struct list_head *q_new()
{
struct list_head *new = malloc(sizeof(struct list_head));
if (!new)
return NULL;
INIT_LIST_HEAD(new);
return new;
}
```
### `q_free`
:::warning
不知道就說不知道，不要說「不太知道」，工程人員說話要精準。
:::
這題我也想使用 `list.h` 裡的函式或巨集，但是<s>不太知道</s> 怎麼使用，因此參考 [alanjian85](https://hackmd.io/@alanjian85/lab0-2023)。
因此這裡使用 `list.h` 的巨集 `list_for_each_entry_safe` ，走訪整個佇列，用 `safe` 來指向 `entry->next` ，不使用 `list_for_each_entry` 是因為執行 `q_release_element` 會將entry刪掉以致於執行 `entry->next` 會出錯，整個佇列會遺失，至於 `list_for_each_entry` 的參數list則是要看 `queue.h` 裡的 `element_t` 結構的命名。另外如果佇列是 NULL，則會在一開始就結束該函式。
```c
void q_free(struct list_head *head) {
if(!head)
return ;
element_t *entry, *safe;
list_for_each_entry_safe(entry, safe, head, list)
q_release_element(entry);
free(head);
}
```
:::danger
1. 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
2. 留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)及[詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)
3. 改進你的漢語表達
:::
### `q_insert_head`
:::danger
避免非必要的項目縮排 (即 `* `)，以清晰、明確，且流暢的漢語書寫。
:::
這裡有個要檢查的點
輸入的 list 是否為 `NULL`
`malloc` `new` 有沒有成功
`strdup` 函式本身會呼叫 `malloc` 因此也需要檢查是否成功
都沒問題才能將該 `new` 插入到 `list` 裡。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
new->value = strdup(s);
if (!new->value) {
free(new);
return false;
}
list_add(&new->list, head);
return true;
}
```
### `q_insert_tail`
和上述 `q_insert_head` 相似，僅需將 `list_add` 改成 `list_add_tail` 即可完成。
### `q_remove_head`
作業說明有提到，`remove` 和 `delete` 的差別，`remove` 不會將節點抹除，因此這裡只有使用 `list_del` 來 unlink，沒有使用 `free` 來釋放該節點的記憶體。兩個要注意的點是
* 檢查鏈結串列是否為 `empty`
* 為了確保在 `strncpy` 後 `sp` 有 null character 。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *tmp = list_first_entry(head, element_t, list);
list_del(head->next);
if (sp) {
strncpy(sp, tmp->value, bufsize);
sp[bufsize - 1] = '\0';
}
return tmp;
}
```
### `q_remove_tail`
和上述 `q_remove_head` 相似，僅需將 `list_first_entry` 改成 `list_last_entry` 即可完成。
### `q_delete_mid`
這裡我使用快慢指標，`fast` 每次走 2 步，`slow` 每次走 1 步，當 `fast` 走訪完整個 list，`slow` 則會在鏈結串列的中間。
我嘗試幾次後發現有兩個要注意的點
* `fast` 和 `slow` 一開始要從 `head->next` 出發才是正確的
* `fast` 指到 `head` 或 `head->prev` 都算是走訪完 list
找完中點後，由於 delete 是要將該節點記憶體釋放，所以除了用 `list_del` unlink 要再使用 `q_release_element` 釋放整個 element 的記憶體。
:::warning
改進漢語表達。
:::
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *fast = head->next;
struct list_head *slow = head->next;
for (; fast != head && fast != head->prev;
fast = fast->next->next, slow = slow->next) {
}
list_del(slow);
q_release_element(list_entry(slow, element_t, list));
return true;
}
```
:::warning
針對環狀雙向佇列，提出更快的方法。
:::
`TO DO : 針對環狀雙向佇列可以使用兩個指標，一個往next，一個往prev`
### `q_delete_dup`
這段程式碼的目標是移除重複項目。程式使用 `list_for_each_entry_safe` 來走訪整個 `list` ，並使用 `strcmp` 函數比較項目的值。如果發現重複的項目，它將刪除所有重複的項目，但保留最後一個。為了將最後一項也刪掉，我使用 `dup_last` 變數，來確保最後一個重複的項目會被刪除。
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head))
return false;
bool dup_last = false;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list)
if (&safe->list != head && !strcmp(entry->value, safe->value)) {
list_del(&entry->list);
q_release_element(entry);
dup_last = true;
} else if (dup_last) { // del dup last one
list_del(&entry->list);
q_release_element(entry);
dup_last = false;
}
return true;
}
```
### `q_swap`
由於 swap 只需要改變每個 element 的鏈結串列，~~不需要值~~ 不需要改變節點當中的數值，所以我這裡使用~~的是~~ `list_for_each_safe`，再使用 `list_del` 和 `list_add` 就可以將兩者 swap (下方解釋)，最後 `safe = node->next` 可以確保都是兩個為一組 swap。
```c
void q_swap(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *node, *safe;
list_for_each_safe (node, safe, head)
if (safe != head) {
list_del(node);
list_add(node, safe);
safe = node->next;
}
return;
```
後來看到 `list_move` 這個函式，剛好就是 `list_del` 和 `list_add` 的組合，在 `list.h` 裡可以看到他的敘述是 `Move a list node to the beginning of the list` 不過將輸入更改後便可以達到我要的功能 `將節點 node 移至節點 safe 後`。
```diff
list_for_each_safe (node, safe, head)
if (safe != head) {
- list_del(node);
- list_add(node, safe);
+ list_move(node, safe);
safe = node->next;
}
```
### `q_reverse`
reverse 跟 swap 一樣都只需要更改鏈結串列的指向，我一樣使用 `list_for_each_safe` 走訪每個節點，並將他們都`Move a list node to the beginning of the list`，這次是使用他真正的功能了，如此一來整個鏈結串列就被 reverse 了。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *node, *safe;
list_for_each_safe (node, safe, head)
list_move(node, head);
}
```
### `q_reverseK`
我這裡使用最土炮的方法，在 `q_reverse` 的基礎上加上兩個計數器，`count_turn` 用來確認後面是否還有完整的 k 組 element，`count_k` 則是用來數已被 reverse 的節點數，若達到 k 個則將重新計數，並改變後面節點要插入的位置。
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head))
return;
struct list_head *node, *safe, *start = head;
int count_k = 0, count_turn = 0;
int turn = q_size(head) / k;
list_for_each_safe (node, safe, head) {
list_move(node, start);
if (count_turn == turn) /*no complete k-group*/
return;
if (++count_k == k) { /*change start per kth node*/
start = safe->prev;
count_turn++;
count_k = 0;
}
}
}
```
:::warning
> [name=I-HSIN Cheng]
> 這裡是開發筆記不是教學頁面，不需要闡述每個函式的邏輯與做法，程式碼本身應該清楚到不需文字解釋即可理解，除非有任何特別之處，應該寫出可改進之處，另外說明文字的贅字太多且解說不清晰。
:::
Sign in with Wallet
Connect another wallet