---
title: 2025q1 Homework1 (lab0)
---
# 2025q1 Homework1 (lab0)
contributed by < [`duckcone`](https://github.com/duckcone) >
### Reviewed by `HeatCrab`
> 只要 `next != head` 就判斷 `current` 節點的字串是否與 `next` 節點的字串相同，若是相同就將 `next = next->next`。
這裡的 while 迴圈，可以使用 `list.h` 中的 `list_for_each_safe` 來取代，增加可讀性。
簡單實作如下：
```diff
+ struct list_head *safe;
- while (next != head) {
+ list_for_each_safe(next, safe, head) {
const element_t *next_element = list_entry(next, element_t, list);
if (strcmp(current_element->value, next_element->value) == 0) {
- next = next->next;
+ break;
- } else {
- break;
}
+ if (next == head) break;
}
```
> 設定 `dup_head->prev->next = next; next->prev = dup_head->prev` 來將重複的節點斷開連接。
可以使用 `list.h` 中的 `list_cut_position` 來簡化。
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
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.
$ uname -a
Linux oslab 6.8.0-54-generic #56-Ubuntu SMP PREEMPT_DYNAMIC Sat Feb 8 00:37:57 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 48 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 7800X3D 8-Core Processor
CPU family: 25
Model: 97
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 2
```
## 指定的佇列操作
### q_new()
建立一個空佇列。利用 `malloc()` 配置一塊記憶體，並且利用函式 `INIT_LIST_HEAD();` 對佇列進行初始化。
在測試中發現原先程式碼並未考慮 `malloc` 失敗的問題，因此加入了判斷 `malloc` 是否成功的程式碼。
```diff
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
+ if (!head)
+ return NULL;
INIT_LIST_HEAD(head);
return head;
```
### q_free()
釋放佇列的空間。利用 `list_for_each_entry_safe()` 走訪每個包含 `list_head` 結構體的每個節點，並且利用 `qrelease_element()` 釋放節點。
### q_insert_head()
新增一個節點在佇列的起始位置。透過呼叫 `create_new_element()
` 函式來新增新的 `element_t`，最後透過 `list_add()` 函式將節點新增在佇列的開頭位置。
**create_new_element() 的實作細節**
1. 在進行 `element_t *new_element = malloc(sizeof(element_t))` 之後須判斷是否成功，若 `malloc()` 失敗則釋放其記憶體並傳 `NULL`。
2. 透過 `strdup()` 將參數 `s` duplicate 一份，並且將節點的 `value` 指向其位址。
#### 如果 `*s` 是 NULL pointer 呢？
參考 [2024 年系統軟體系列課程討論區](https://www.facebook.com/groups/system.software2024/permalink/1556863905091502/?mibextid=oMANbw) 社團中的這篇貼文所提到的問題，發現自己的程式碼無法確認使用者在新增節點時所輸入的字串為何，因此在 `q_insert_head()` 以及 `q_insert_tail()` 中新增了判斷字串的程式碼，透過 `if(!s || !*s)` 來確保指標 `s` 所指向的位址非 `NULL`或字串非 `NULL` 。
```diff=
bool q_insert_head(struct list_head *head, char *s)
{
- if (!head)
+ if (!head || !s || !*s)
return false;
element_t *new_element = create_new_element(s);
if (!new_element)
return false;
list_add(&new_element->list, head);
return true;
}
```
### q_insert_tail()
與 `q_insert_head()` 的實作方式相同，透過呼叫 `element_new()` 函式來新增新的節點，並透過 `list_add_tail()` 將節點新增在佇列的尾端。
### q_remove_head()
原先的想法是先取得佇列開頭的節點位址，並且調整 `prev` 以及 `next` 所指向的位址。但是在進行 `$ make test` 後，發現在進行 `Test of insert_head and remove_head` 測試時會有以下錯誤訊息：
```shell
ERROR: Attempted to free unallocated block. Address = 0x558a5a52e278
ERROR: Attempted to free unallocated or corrupted block. Address = 0x558a5a52e278
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
```
在閱讀 `queue.h` 檔案時不夠仔細，忽略了以下針對 `q_remove_head()` 的說明：
> If sp is non-NULL and an element is removed, copy the removed string to `*sp` (up to a maximum of bufsize-1 characters, plus a null terminator.)
因此針對此函式進行修正。
```diff
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
- if (!head)
+ if (!head || list_empty(head))
+ return NULL;
+
+ element_t *head_element = list_first_entry(head, element_t, list);
+ if (!head_element)
return NULL;
- element_t *head_element = container_of(head, element_t, list);
- head->next->prev = head->prev;
- head->prev->next = head->next;
+ if (!sp)
+ return head_element;
+ memset(sp, '\0', bufsize);
+ strncpy(sp, head_element->value, bufsize);
+ list_del(&head_element->list);
return head_element;
}
```
### q_remove_tail()
與 `q_remove_head()` 的實作方式相同，唯一的差別在於利用 `list_last_entry()` 尋找佇列的最後一個節點。
### q_size()
利用 `list_for_each()` 逐一走訪每個節點來計算佇列中的節點數量。
### q_delete_dup()
實作上分為兩個步驟
1. 尋找重複的節點
2. 刪除重複的節點
#### 尋找重複的節點
1. 利用 `list_for_each(current, next, head)` 來逐一走訪每個節點，並且同時擁有當前節點 `current` 以及下個節點 `next` 的位址。
2. 只要 `next != head` 就判斷 `current` 節點的字串是否與 `next` 節點的字串相同，若是相同就將 `next = next->next`。
3. 一旦 `next == head` 或者 `current` 節點的字串與 `next` 節點的字串不同，便會跳出尋找重複節點的迴圈。這時從 `current` 到 `next->prev` 節點的字串內容都是相同的。
#### 刪除重複的節點
1. 設定 `dup_head = current` 表示所有重複節點的起始節點。
2. 設定 `dup_head->prev->next = next; next->prev = dup_head->prev` 來將重複的節點斷開連接。
3. 利用 `temp` 節點作為 `dup_head` 的下一個節點。並在刪除 `dup_head` 所指向的節點之後將 `dup_head = temp` 。反覆執行此操作直到 `dup_head == next` 即可將所有重複的節點刪除。
4. `list_for_each_safe()` 會在每一次迭代將 `current = next` 。
### q_swap()
參考自 [2025-02-25 問答簡記 HerryChaing](https://hackmd.io/l4--gpsZQBiEI5LKS1lDvg?view#HenryChaing) 的實作方式。
初始化 `current` 為 `head->next` 。當 `current` 以及 `current->next` 都不等於 `head` 節點時，利用 `list_move` 將 `current` 與 `current->next` 的節點互換，並且繼續走訪佇列。
查看 `list_move()` 的實作可以發現該函式呼叫 `list_add(node, head)` ，在 `list_add()` 中之所以是將 `node` 加入至 `head->next->prev` 是因為在佇列的 `head` 本身只有提供尋找佇列開頭的功能，並且並無嵌入在 `element_t` 的結構中，因此需要透過 `head->next` 才是佇列中的第一個節點。
透過 `list_move(node, head)` 的特性，正好可以將，`node` 與 `head` 的位置互換。
### q_reverse()
利用 `list_for_each_safe()` 逐一走訪每一個節點，並且將 `current` 節點的 `next` 與 `prev` 所指向的位址互換。由於 `list_for_each_safe()` 的中止條件為 `node == head` ，因此迴圈結束後需要再將 `head` 節點的 `next` 以及 `prev` 所指向的位址互換。
### q_reverseK()
當以下四種情況時不須進行節點反轉
1. `head` 為 `NULL` 時
2. `head` 所指向的佇列為空佇列時
3. `head` 所指向的佇列只有一個節點時
4. 反轉的節點數量 `k` 為 0 時
首先利用 `list_for_each_safe(current, safe, head)` 逐一走訪每個節點，並且利用計數器 `counter` 來計算走訪的節點數量，當 `counter >= k` 時便進行反轉：
1. 利用 `list_move_tail(current->prev, safe)` 將 `current` 的前一個節點移動至 `safe` 節點之前
2. 將 `counter` 值減 1
3. k 個元素只需要做 k - 1 次的交換即可完成反轉，因此完成反轉時 `counter` 的值為 1
4. 將 `counter` 歸 0
### q_delete_mid()
透過兩個指標 `head_ptr` 以及 `tail_ptr` 對 `head` 的 `prev` 以及 `next` 方向逐一走訪，當兩個指標相等(節點數量為奇數)，或是 `head_ptr->next` 等於 `tail_ptr` (節點數量為偶數) 時，即中間節點的位置。
Sign in with Wallet
Connect another wallet