# 2023q1 Homework1 (lab0)
contributed by < `oEric0929o` >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.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): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 167
Model name: 11th Gen Intel(R) Core(TM) i5-11400F @ 2.60GHz
Stepping: 1
CPU MHz: 2600.000
CPU max MHz: 4400.0000
CPU min MHz: 800.0000
BogoMIPS: 5184.00
```
## 開發過程
拿到這份作業的一開始可以說是毫無頭緒，自己嘗試閱讀資料後不知道要如何開始，直到詢問 [Thegoatistasty](https://hackmd.io/@pigwei/r1jWYNipi) 同學，他建議我依照測資順序一步一步完成，才慢慢開始有進度。撰寫程式的過程大多是先想辦法讀懂同學的程式碼，再自己寫出來，過程中有明顯感覺到自己有進步，最後有幾個函式靠自己查資料完成，很有成就感。能完成這份作業真的很感謝 [Thegoatistasty](https://hackmd.io/@pigwei/r1jWYNipi) 同學的幫忙，給了我方向也解答了我很多疑問。
### q_new
```c
/* Create an empty queue */
struct list_head *q_new()
{
struct list_head *p = malloc(sizeof(struct list_head));
if (!p)
return NULL;
INIT_LIST_HEAD(p);
return p;
}
```
### q_free
```c
/* Free all storage used by queue */
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *temp, *safe;
list_for_each_entry_safe (temp, safe, l, list) {
list_del(&temp->list);
free(temp->value);
free(temp);
}
free(l);
}
```
### q_insert_head
原本用 ``` strcpy ``` ，執行時報錯，參考[文件](https://security.web.cern.ch/recommendations/en/codetools/c.shtml)後改用 ```snprintf```
```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_node = (element_t *) malloc(sizeof(element_t));
if (!new_node)
return false;
new_node->value = (char *) malloc(strlen(s) + 1);
if (!new_node->value) {
free(new_node);
return false;
}
snprintf(new_node->value, strlen(s) + 1, "%s", s);
list_add(&new_node->list, head);
return true;
}
```
### q_insert_tail
將 ```q_insert_head``` 中的 ``` list_add ``` 改成 ```list_add_tail``` 即可
```c
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_node = (element_t *) malloc(sizeof(element_t));
if (!new_node)
return false;
new_node->value = (char *) malloc(strlen(s) + 1);
if (!new_node->value) {
free(new_node);
return false;
}
snprintf(new_node->value, strlen(s) + 1, "%s", s);
list_add_tail(&new_node->list, head);
return true;
}
```
### q_remove_head
一開始想了很久想不出 ```sp``` 的功能，仔細看了 ```queue.h``` 中的敘述才發現是用來儲存刪除節點的字串內容
```c
/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head) || !sp)
return NULL;
element_t *p = list_entry(head->next, element_t, list);
strncpy(sp, p->value, bufsize - 1);
sp[bufsize - 1] = '\0';
list_del(&p->list);
return p;
}
```
### q_remove_tail
```q_remove_head``` 刪除 ```head``` 的下一個節點，而因為是雙向鏈結串列，所以 ```q_remove_tail``` 只要改成刪除 ```head``` 的前一個節點即可
```c
/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head) || !sp)
return NULL;
element_t *p = list_entry(head->prev, element_t, list);
strncpy(sp, p->value, bufsize - 1);
sp[bufsize - 1] = '\0';
list_del(&p->list);
return p;
}
```
### q_size
```c
/* Return number of elements in queue */
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
### q_delete_mid
運用快慢指標找到中間的節點並刪除
```c
/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
struct list_head *fast, *slow;
fast = head->next->next;
slow = head->next;
while (fast != head && fast->next != head) {
fast = fast->next->next;
slow = slow->next;
}
list_del(slow);
element_t *del = list_entry(slow, element_t, list);
free(del->value);
free(del);
return true;
}
```
### q_delete_dup
參考 [GeeksforGeeks](https://www.geeksforgeeks.org/remove-duplicates-from-a-sorted-linked-list/) 的作法刪除多餘重複節點，再刪除每組重複節點的第一個節點
```c
/* Delete all nodes that have duplicate string */
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 *current = head->next;
element_t *cur_node, *next_node;
bool dup = false;
while (current->next != head) {
cur_node = list_entry(current, element_t, list);
next_node = list_entry(current->next, element_t, list);
if (strcmp(cur_node->value, next_node->value) == 0) {
dup = true;
list_del(&next_node->list);
q_release_element(next_node);
} else {
current = current->next;
if (dup == true) {
list_del(&cur_node->list);
q_release_element(cur_node);
dup = false;
}
}
}
if (dup) {
list_del(&cur_node->list);
q_release_element(cur_node);
}
return true;
}
```
### q_swap
利用 ```list_move``` 進行交換，將 ```p``` 放到 ```p->next``` 後方之後 ```p->next``` 剛好會是下一個要交換的節點
```c
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head)
return;
struct list_head *p;
for (p = head->next; p->next != head && p != head; p = p->next)
list_move(p, p->next);
}
```
### q_reverse
利用 ```list_move``` 依序將每個節點放到最前面，即完成反轉
```c
/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
if (!head)
return;
struct list_head *node, *safe;
list_for_each_safe (node, safe, head)
list_move(node, head);
}
```
### q_reverseK
利用 ```count``` 計數，當 ```count``` 到達 ```k``` 時用 `list_move` 做反轉，並移動 `temp` 來記錄下一次反轉的起始點
```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 || list_empty(head) || k <= 1)
return;
struct list_head *node, *safe, *temp = head;
int count = 0;
list_for_each_safe (node, safe, head) {
count++;
if (count == k) {
struct list_head *cur_node = temp->next,
*next_node = temp->next->next;
while (count != 0) {
list_move(cur_node, temp);
cur_node = next_node;
next_node = next_node->next;
count--;
}
temp = safe->prev;
}
}
}
```
### q_sort
採用 merge sort ，參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)中雙指標的方法實作 `merge_two_lists` ，再以遞迴的方式實作 merge sort ，排序前將頭尾切開，完成排序後再接起來
```c
/* Merge two sorted lists */
struct list_head *merge_two_lists(struct list_head *l1,
struct list_head *l2,
bool descend)
{
struct list_head *head = NULL;
struct list_head **ptr = &head;
for (; l1 && l2; ptr = &(*ptr)->next) {
element_t *a = list_entry(l1, element_t, list);
element_t *b = list_entry(l2, element_t, list);
if ((strcmp(a->value, b->value) <= 0 && !descend) ||
(strcmp(a->value, b->value) > 0 && descend)) {
*ptr = l1;
l1 = l1->next;
} else {
*ptr = l2;
l2 = l2->next;
}
}
*ptr = (struct list_head *) ((uintptr_t) l1 | (uintptr_t) l2);
return head;
}
/* Merge sort recursively */
struct list_head *merge_sort(struct list_head *head, bool descend)
{
if (!head || !head->next)
return head;
struct list_head *fast, *slow;
fast = slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
slow->prev->next = NULL;
struct list_head *l1 = merge_sort(head, descend);
struct list_head *l2 = merge_sort(slow, descend);
return merge_two_lists(l1, l2, descend);
}
/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
head->prev->next = NULL;
head->next = merge_sort(head->next, descend);
head->next->prev = head;
struct list_head *p = head;
while (p->next) {
p->next->prev = p;
p = p->next;
}
head->prev = p;
p->next = head;
}
```
### q_descend
以反序走訪，遇到較小的節點就刪除。架構和 `q_delete_dup` 很相似，將刪除的條件判斷從相等改為小於
```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 || list_empty(head))
return 0;
struct list_head *current = head->prev;
element_t *cur_node = NULL, *prev_node = NULL;
int len = 1;
while (current->prev != head) {
cur_node = list_entry(current, element_t, list);
prev_node = list_entry(current->prev, element_t, list);
if (strcmp(cur_node->value, prev_node->value) < 0) {
list_del(&prev_node->list);
q_release_element(prev_node);
} else {
len++;
current = current->prev;
}
}
return len;
}
```
### q_merge
一開始對 `queue_contex_t` 和 `list_head` 不夠了解，一直想不明白 `next` 代表的意義，查看 `queue.h` 才發現這裡的參數 `head` 和其他函式不同，是 header of chain ，所以 `head->next` 是會在 chain 之間移動而不是 list 。將 chain 中的每一條 list 接在一起再做排序即可完成 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 || list_empty(head))
return 0;
queue_contex_t *p = list_entry(head->next, queue_contex_t, chain);
if (list_is_singular(head))
return p->size;
struct list_head *node;
for (node = head->next->next; node != head; node = node->next) {
queue_contex_t *tmp = list_entry(node, queue_contex_t, chain);
list_splice_init(tmp->q, p->q);
}
q_sort(p->q, descend);
return p->size;
}
```
Sign in with Wallet
Connect another wallet