# 2024q1 Homework1 (lab0)
contributed by < `will-in-nc` >
## 開發環境
```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: 36 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 5 5600X 6-Core Processor
CPU family: 25
Model: 33
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 0
CPU max MHz: 3701.0000
CPU min MHz: 0.0000
BogoMIPS: 7402.00
```
## 指定的佇列操作
### `q_insert_head`, `q_insert_tail`
:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::
<s>這兩個function的內容幾乎相同</s> ，只有最後是呼叫`list_add`或是`list_add_tail`的區別
:::warning
對應到數學公式，function 應翻譯為「函數」，後者就像是台「機器」，它能夠將集合 A 裡面的每個元素「唯一地」對應到集合 B 裡的一個元素。但在 C 語言一類的通用程式語言中，function 未必具備數學函數的意涵，也就是缺乏「唯一對應」的特性，例如對於 [time](https://man7.org/linux/man-pages/man2/time.2.html) 來說，給定同樣的輸入，卻會在不同時間點得到不同的結果，在 C 語言一類的通用程式語言中，甚至可省略傳回值，後者就不符合「函數」的行為。因此，當在通用的程式設計中，function 應翻譯為「函式」，表示「衍生自數學函數的常式 (routine)」。另外，對於更一般的描述，function 會指「功能」一類的意涵，應合適挑選譯詞。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *e_new = (element_t *) malloc(sizeof(element_t));
if (!e_new)
return false;
e_new->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
if (!e_new->value) {
free(e_new);
return false;
}
INIT_LIST_HEAD(&e_new->list);
snprintf(e_new->value, strlen(s) + 1, "%s", s);
list_add(&e_new->list, head);
return true;
}
```
### q_free
```c
/* Free all storage used by queue */
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *e, *next;
list_for_each_entry_safe (e, next, head, list) {
q_release_element(e);
}
free(head);
}
```
一開始我不斷遇到以下錯誤
```
ERROR: Corruption detected in block with address 0x7fffd9c7ce10 when attempting to free it
```
這個錯誤發生的原因是我在新增節點中的`value`時要求的記憶體大小和複製過去的字串大小不一致
### `q_remove_tail`, `q_remove_tail`
這兩個function的內容幾乎相同，只有目標是`head->next`或是`head->prev`的區別
```c
/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head)
return NULL;
if (list_empty(head))
return NULL;
struct list_head *target_list = head->next;
element_t *target_e = list_entry(target_list, element_t, list);
list_del_init(target_list);
if (sp != NULL)
snprintf(sp, bufsize, "%s", target_e->value);
return target_e;
}
```
### q_reverse
```c
/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
if (!head)
return;
if (list_empty(head))
return;
struct list_head *l_head = head->next;
while (l_head->next != head) {
list_move_tail(head->prev, l_head);
}
}
```
標記出原本佇列的第一個節點後，不斷地將佇列的最後一個節點移到開頭，直到原本的第一個節點成為最後一個節點
### `q_reverseK`
```c
/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head)
return;
if (list_empty(head))
return;
struct list_head *l_head = head->next;
int times = q_size(head) / k;
for (int j = 0; j < times; j++) {
struct list_head *prev = l_head->prev, *target = l_head->next;
for (int i = 1; i < k; i++) {
struct list_head *temp = target;
target = target->next;
list_move(temp, prev);
}
l_head = l_head->next;
}
}
```
### `q_swap`
```c
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head)
return;
if (list_empty(head))
return;
q_reverseK(head, 2);
}
```
`q_swap`可以直接<s>調用</s> 呼叫 `q_reverseK`來實作
### `q_sort`
```c
struct list_head *merge_sort(struct list_head *head,
struct list_head *tail,
int size,
bool descend)
{
if (size == 1)
return head;
struct list_head *mid = head;
int len = 0;
while (len < size / 2) {
mid = mid->next;
len++;
}
int len2 = size - len;
struct list_head *l1 = merge_sort(head, mid->prev, len, descend),
*l2 = merge_sort(mid, tail, len2, descend),
*prev = l1->prev, *lhead = prev;
element_t *e1 = list_entry(l1, element_t, list),
*e2 = list_entry(l2, element_t, list);
while (len > 0 && len2 > 0) {
struct list_head *target = NULL;
if ((strcmp(e1->value, e2->value) > 0) == descend) {
target = &e1->list;
l1 = l1->next;
e1 = list_entry(l1, element_t, list);
len--;
} else {
target = &e2->list;
l2 = l2->next;
e2 = list_entry(l2, element_t, list);
len2--;
}
list_move(target, lhead);
lhead = target;
}
return prev->next;
}
/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
if (!head)
return;
if (list_empty(head))
return;
merge_sort(head->next, head->prev, q_size(head), descend);
}
```
目前為止我還沒想出以迭代實作合併排序的方法，因此以遞迴的方式實作
### `q_ascend`, `q_descend`
```c
/* Remove every node which has a node with a strictly less value anywhere to
* the right side of it */
int q_ascend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head)
return 0;
int len = q_size(head);
if (len <= 1)
return len;
element_t *e = list_entry(head->prev, element_t, list);
struct list_head *next = e->list.prev;
while (next != head) {
element_t *e_next = list_entry(next, element_t, list);
if (strcmp(e->value, e_next->value) < 0) {
element_t *temp = e_next;
next = next->prev;
list_del_init(&temp->list);
q_release_element(temp);
len--;
} else {
e = e_next;
next = next->prev;
}
}
return len;
}
```
從佇列的尾端開始檢查節點是否符合升序或降序
### `q_merge`
```c
/* Merge all the queues into one sorted queue, which is in ascending/descending
* order */
int q_merge(struct list_head *head, bool descend)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head)
return 0;
if (q_size(head) <= 1)
return 0;
queue_contex_t *main_q = list_entry(head->next, queue_contex_t, chain);
queue_contex_t *q, *next;
int len = q_size(main_q->q);
list_for_each_entry_safe (q, next, head, chain) {
if (q != main_q) {
struct list_head *l1 = main_q->q->next, *l2 = q->q->next,
*prev = main_q->q, *lhead = prev;
int len1 = len, len2 = q_size(q->q);
len += len2;
list_splice_init(q->q, main_q->q);
element_t *e1 = list_entry(l1, element_t, list),
*e2 = list_entry(l2, element_t, list);
while (len1 > 0 && len2 > 0) {
struct list_head *target = NULL;
if ((strcmp(e1->value, e2->value) > 0) == descend) {
target = &e1->list;
l1 = l1->next;
e1 = list_entry(l1, element_t, list);
len1--;
} else {
target = &e2->list;
l2 = l2->next;
e2 = list_entry(l2, element_t, list);
len2--;
}
list_move(target, lhead);
lhead = target;
}
}
}
return len;
}
```
利用`q_sort`中合併的部分來實作
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
Sign in with Wallet
Connect another wallet