# 2025q1 Homework1 (lab0)
contributed by < [`EJ7289`](https://github.com/EJ7289) >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
``` shell
$ 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
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 142
Model name: Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz
Stepping: 9
CPU(s) scaling MHz: 14%
CPU max MHz: 3500.0000
CPU min MHz: 400.0000
BogoMIPS: 5799.77
Virtualization: VT-x
L1d cache: 64 KiB (2 instances)
L1i cache: 64 KiB (2 instances)
L2 cache: 512 KiB (2 instances)
L3 cache: 4 MiB (1 instance)
NUMA node0 CPU(s): 0-3
```
## 針對佇列操作的程式碼實作
### q_new
在 C 語言中， `malloc` 用來分配指定大小的記憶體空間，並且回傳指標，配置的空間尚未初始化。
> ***C99 [7.20.3.3] The malloc function**
> `#include <stdlib.h>`
> `void * malloc(size_t size);`
> **Description**
> The **malloc** function allocates space for an object whose size is specified by **size** and whose value is indeterminate.
> **Return**
> The **malloc** function returns either a null pointer or a pointer to the allocated space.*
若記憶體配置失敗，須回傳空指標，但是 C 語言中的空指標用 NULL 表示。
補充：C++11 中的空指標用 nullptr 表示。
``` c
struct list_head *q_new(){
struct list_head *h = (struct list_head *)malloc(sizeof(struct list_head));
if (!h) {
return NULL;
}
h->next = h;
h->prev = h;
return h;
}
```
### q_free
注意事項：
- list_head 為**雙向循環鏈結串列**， head 一直指向 next 也不會是 NULL
- 釋放記憶體，須將 elem 以及 elem->value 的記憶體都釋放
- ==為什麼不能不能只釋放 elem 就好？==
- ==為什麼另外釋放 elem->value 不釋放 elem->list ？==
- 最後也需要將 head 釋放
以下程式會陷入無窮迴圈：
``` c
void q_free(struct list_head *head)
{
while(head) {
struct list_head *next = head->next;
free(head);
head = next;
}
}
```
> 放 github 的程式
`free` 函數的引數為指標。
> ***C99 [7.20.3.2] The free function**
> `#include <stdlib.h>`
> `void free(void *ptr);`*
### q_insert_head/q_insert_tail
- [ ] 原本的程式1：
``` c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *newq = malloc(sizeof(element_t));
if (!newq) { return false; }
newq->value = s;
newq->list.next = head;
newq->list.prev = head->prev;
return true;
}
```
以上程式的問題有：
1. 若 s 是**區域變數**，會在離開函數時被釋放，導致外界無法取得。
2. 該佇列為**雙向循環**鏈結串列，因此需要原本的鏈結串列指向新建的。
修改方法：
1. 為了讓外界能讀取 s 的值，使用 `strdup()` 複製字串。 `strdup()` 會用 malloc 獲得新的字串，並且可用 free 釋放字串。
2. 雙向循環的鏈結串列在新增節點時，需要打斷2條鏈和新增4條鏈。被打斷的鏈會使用到，因此需要注意新增4條鏈的順序。
- [ ] 改寫為程式2：
``` c
bool q_insert_tail(struct list_head *head, char *s)
{
// Create a new queue
element_t *newq = malloc(sizeof(element_t));
if (!newq) {
return false;
}
// Duplicate s in global memory and storage in new queue
newq->value = strdup(s);
if (!newq->value) {
free(newq);
return false;
}
// Insert s at the tail of queue
newq->list.next = head;
newq->list.prev = head->prev;
head->prev->next = &newq->list;
head->prev = &newq->list;
return true;
}
```
- [ ] 程式3：使用 API 簡化程式
> 放 github 的程式
### q_remove_head/q_remove_tail
在 queue.h 說明：
1. `q_remove_head(struct list_head *head, char *sp, size_t bufsize)`
- head: header of queue
- sp: 插入要移除的字串
- bufsize: 字串 *sp 可以容納的做大空間
原本程式碼：
``` c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)) {
return NULL;
}
// find the element of node
element_t *h = list_entry(head, element_t, list);
sp = h->value;
list_del_init(head);
return h;
}
```
以上程式的問題有：
1. head 為 dummy 而不是起始 node，真正的起始 node 為 head->next
- 改為 `list_entry(head->next, element_t, list)`
- 改為 `list_del_init(head->next)`
2. `sp = h->value` 無法回傳字串 <font color="#0000FF">- h 為區域變數</font>
- 若用 `*sp = *h->value` 只能回傳一個字元，無法回傳字串
- 使用 `strncpy` 複製 sp ==如果不複製為怎樣？==
:::spoiler **char 的使用**
- `char` **只能**作為字元，例如 `char a = 'a'` ==char的字元宣告必須用**單引號**==
- `char` **不能**作為字串的宣告，例如 ~~`char a = "good"`~~
- `char *` 則作為字串的指標宣告
- `char *a = "a"` ==char的指標宣告必須用**雙引號**==
- `char *b = "good"`
``` c
char *a = "a";
char *b = "banana";
printf("%c\n", a); // error
printf("%c\n", *a); // correct, a
printf("%c\n", b); // error
printf("%c\n", *b); // correct, b
printf("%s\n", b); // correct, banana
printf("%s\n", *b); // error
```
:::
- [ ] 程式2:
``` c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head)) {
return NULL;
}
// find the element of node
element_t *h = list_entry(head, element_t, list);
if (sp) {
sp = strncpy()
}
sp = h->value;
list_del_init(head);
return h;
}
```
### q_size
解題思維：
1. 利用 count 在迴圈內計算
2. head 為 dummy 並非直接指向第一個節點
> insert github's commit
### q_delete_mid
解題思維：
1. 排除 head 為 NULL 或 empty 的情況
2. 用快慢指標找到鏈結串列的中間點
3. 移除鏈結串列的中間點 (利用 `list_del()`)
5. 釋放中間點 (須同時釋放 `elem` 和 `elem->value`)
> insert github's commit
### q_delete_dup
目的：將**相鄰**且**相同**的數值刪除
<!-- 情境分析：
| prev | curr | next | step 1 | step 2 |
| ---- | ---- | ---- | ------ | ------ |
| 0 | 1 | 2 | | |
| 1 | 1 | 2 |
| 0 | 1 | 1 |
| 1 | 1 | 1 | -->
解法：
1. 比較 curr 與 next 是否相同
2. 若相同，將布林變數改成 true ；若不相同，將布林變數改成 false
3. 布林變數為 false （不動作）；布林變數為 true 和布林變數為 true 變成 false （刪除前一個數值 prev ）
- [ ] 原本程式 1
``` c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head))
return false;
struct list_head *curr = head->next;
struct list_head *next = curr->next;
bool del = false;
while(curr!=head) {
element_t *elem = list_entry(curr, element_t, list);
element_t *safe = list_entry(next, element_t, list);
if (elem->value == safe->value) {
del = true;
list_for_each_entry_safe(elem, safe, head, list);
free(elem->value);
free(elem);
} else if ((elem->value != safe->value) && (del == true)) {
del = false;
list_for_each_entry_safe(elem, safe, head, list);
free(elem->value);
free(elem);
}
curr = next;
next = next->next;
}
return true;
}
```
程式 1 存在的問題：
1. elem->value 指向的是 **value 的地址**，因此要用 `strcmp()`
2. `list_for_each_entry_safe()` 的使用方式不正確
在 `list.h` 中說明`list_for_each_entry_safe()` 可用來代替一個 for 迴圈。
``` c
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, typeof(*entry), member), \
safe = list_entry(entry->member.next, typeof(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, typeof(*entry), member))
```
最基本的定義方式`#define MACRO value` => `#define MAX 1000`
3. 須使用 `list_del()` 將指定數值從鏈結串列中移除
4. 需要初始化 `entry=NULL` 和 `safe=NULL`
- [ ] 程式 2
> github code
### q_swap
利用 XOR 操作 swap 的行為，不適用在 `struct` 和 `char*` ，因此該題不適用。
``` c
XORswap(int *a, int *b) {
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
```
因此，需要另外存取的空間 tmp 。
解題方法：不改 node ，指改變 `*value` 。（如下方程式所示）
``` c
for (; curr != head && curr->next != head;
curr = curr->next->next, next = curr->next) {
char *tmp = list_entry(curr, element_t, list)->value;
list_entry(curr, element_t, list)->value = list_entry(next, element_t, list)->value;
list_entry(next, element_t, list)->value = tmp;
}
```
> github code
### q_reverse
解題方法：
1. `curr->next = prev` 的概念
但該題目是雙向循環鏈結串列，用該方法修改連接的串列會更複雜一些。
=> 方法修改為頭尾互換（如圖所示）
=> 不改變 node 指改變 `*value`
``` mermaid
flowchart LR
id0(0) <--> id1(1) <--> id2(2) <--> id3(3) <--> id4(4) <--> id5(5)
```
``` mermaid
flowchart LR
id0(5) <--> id1(1) <--> id2(2) <--> id3(3) <--> id4(4) <--> id5(0)
style id0 color:#f00;
style id5 color:#f00;
```
``` mermaid
flowchart LR
id0(5) <--> id1(4) <--> id2(2) <--> id3(3) <--> id4(1) <--> id5(0)
style id1 color:#f00;
style id4 color:#f00;
```
### q_reverseK
解題方法：
1. 判斷是否能切成 K
2. K 個切成一個小 queue
> github code
在 **C99 [6.8.5.3]** 中，解釋到 for 迴圈的使用如下，
`for ( init-clause ; condition ; iteration-expression ) statement`
其中：
- init-clause：變數初始化（可為變數宣告或運算式）
- condition：循環條件（當條件為 false（0）時停止迴圈）
- iteration-expression：每次迴圈執行完後的運算式
- statement：迴圈主體
範例：
``` c
for (int a=0, b=0; a<3, b<3; a++, b++, printf("a = %d\n", a)) {
printf("b = %d\n\n", b);
}
```
輸出：
``` c
b = 0
a = 1
b = 1
a = 2
b = 2
a = 3
```
### q_sort
- [ ] 原程式
``` c
struct list_head *qsort_split(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head))
return head;
struct list_head *base = head->next;
struct list_head *curr = head->next->next;
struct list_head *left;
struct list_head *right;
INIT_LIST_HEAD(left);
INIT_LIST_HEAD(right);
for (; curr != head; curr = curr->next) {
if (strcmp(list_entry(base, element_t, list)->value,
list_entry(curr, element_t, list)->value) >= 0) {
list_add_tail(curr, left);
} else {
list_add_tail(curr, right);
}
}
if (descend == true) {
struct list_head *tmp = left;
left = right;
right = tmp;
}
list_add_tail(base, left);
list_splice(qsort_split(left, descend), qsort_split(right, descend));
return left;
}
```
==想建立一個新的 dummy 為什麼不能這樣寫？==
``` c
struct list_head *dummy;
INIT_LIST_HEAD(dummy);
```
``` c
struct list_head *dummy = NULL;
INIT_LIST_HEAD(dummy);
```
為什麼必須這樣寫？
``` c
struct list_head dummy;
INIT_LIST_HEAD(&dummy);
```
### q_ascend / q_descend
> github code
### q_merge
- 使用 `queue_context_t` 取出各個 queue
- 輸出 merge queue 時，需要以 `head` 作為 head ？
## 參考資料
1. C 語言動態記憶體的配置：https://blog.gtwang.org/programming/c-memory-functions-malloc-free/#google_vignette
2.
Sign in with Wallet
Connect another wallet