---
tags: linux2023
---
# 2023q1 Homework1 (lab0)
contributed by < `Thegoatistasty` >
:::danger
注意書寫規範：中英文間用一個半形空白字元區隔。
:notes: jserv
:::
:::success
謝謝老師，有進行修改了
:::
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.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): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 13
CPU max MHz: 4500.0000
CPU min MHz: 800.0000
BogoMIPS: 5199.98
```
## 開發過程
### q_new
```c
struct list_head *q_new()
{
struct list_head *head = (struct list_head*) malloc(sizeof(*head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
### q_free
```c
void q_free(struct list_head *l) {
if(!l)
return;
element_t *save, *temp;
list_for_each_entry_safe(temp, save, l, list)
q_release_element(temp);
free(l);
}
```
### q_insert_{head,tail}
這邊曾經遇到的問題是沒有預留 `'/0'` 位置給 value，導致出現
```
ERROR: Corruption detected in block with address 0x55a707abb980 when attempting to free it
```
目前還沒找到是哪裡產生這樣的訊息，不過解決方法就是在 malloc 時多加一個 byte 的空間
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new = (element_t*) malloc(sizeof(element_t));
if (!new)
return false;
char *value = (char*) malloc(strlen(s) * sizeof(char) + 1);//+1 for '/0'
if(!value)
return false;
strcpy(value, s);
new->value = value;
list_add(&new->list, head);
return true;
}
```
```c
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *new = (element_t*) malloc(sizeof(*new));
if (!new)
return false;
char *value = (char*) malloc(strlen(s) * sizeof(char) + 1);
if(!value)
return false;
strcpy(value, s);
new->value = value;
list_add_tail(&new->list, head);
return true;
}
```
### q_remove_head、q_remove_tail
遇到的問題類似，以q_remove_head為例
:::warning
查詢教育部辭典「[蠻](https://dict.revised.moe.edu.tw/dictView.jsp?ID=1235)」，改進你的漢語書寫。
:notes: jserv
:::
:::success
收到！
:::
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if(!head)
return NULL;
sp = (char*) malloc(bufsize * sizeof(char*));
if(!sp)
return NULL;
element_t* first_entry = list_first_entry(head, element_t, list);
strncpy(sp, first_entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
list_del(head->next);
return first_entry;
}
```
原本這麼寫，但會跑出
> ERROR: Failed to store removed value
後來發現sp已經malloc過了(q_test.c裡do_remove的remove)，再malloc一次會在測試時找不到原本的位置，所以將malloc刪掉就好了
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if(!head)
return NULL;
if(!sp)
return NULL;
element_t* last_entry = list_last_entry(head, element_t, list);
strncpy(sp, last_entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
list_del(head->next);
return last_entry;
}
```
```c
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *new = (element_t*) malloc(sizeof(*new));
if (!new)
return false;
char *value = (char*) malloc(strlen(s) * sizeof(char) + 1);
if(!value)
return false;
strcpy(value, s);
new->value = value;
list_add_tail(&new->list, head);
return true;
}
```
### q_swap
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
for(struct list_head* node = head->next; node->next != head; node = node->next){
list_del(node);
list_add(node, node->next);
}
}
```
### q_delete_mid
利用老師上課提到的『指標一快一慢』的方法（Hare & Tortoise Algorithm）
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
// Hare & Tortoise Algorithm
struct list_head *fast, *slow;
fast = slow = head->next;
do{
fast = fast->next;
if(fast == head)
break;
slow = slow->next;
fast = fast->next;
}while(fast != head);
list_del(slow);
return true;
}
```
### q_sort
> 參考 [npes87184's blog](https://npes87184.github.io/2015-09-12-linkedListSort/)的作法，再以自己的方法實作
為了實作 merge sort，我加入了兩個函式:
* `struct list_head *merge_two_lists` : 用來合併二個鏈結串列
* `struct list_head *merge_sort` : merge sort 的遞迴式
merge_two_lists 原本是這麼做的
```c
struct list_head *merge_two_lists(struct list_head *list1, struct list_head *list2)
struct list_head *temp = (struct list_head *)malloc(sizeof(temp));
if(!temp)
return list1;
struct list_head *save = temp;
while(list1 && list2){
element_t *v1 = list_entry(list1, element_t, list);
element_t *v2 = list_entry(list2, element_t, list);
if(strcmp(v1->value, v2->value) >= 0){
temp->next = list1;
list1->prev = temp;
temp = list1 = list1->next;
}
else{
temp->next = list2;
list2->prev = temp;
temp = list2 = list2->next;
}
}
if(!list1){
temp->next = list2;
list2->prev = temp;
}
if(!list2){
temp->next = list1;
list1->prev = temp;
}
free(temp);
return save->next;
```
但當我 make test 時會顯示
> FATAL ERROR: Calls to malloc disallowed
發現它不讓我使用 malloc，思來想去找不到好方法，於是尋找是否有人用類似的方法。結果找到 [@seasonwang](https://hackmd.io/@seasonwang/B1B0lVqpo#q_sort) 和我參考的是同一個部落格，而且是用 indirect pointer 的方式，於是我將他的基礎上改進程式碼（減少一個 indirect pointer ），並改為
:::warning
請查詢英文字典，理解 "optimize" 和 "improve" 的差異。
注意 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:notes: jserv
:::
```c
struct list_head *merge_two_lists(struct list_head *list1, struct list_head *list2)
{
struct list_head *temp = NULL;
struct list_head **indirect = &temp;
struct list_head *last = NULL;
while (list1 && list2) {
element_t *v1 = list_entry(list1, element_t, list);
element_t *v2 = list_entry(list2, element_t, list);
if (strcmp(v1->value, v2->value) <= 0) {
list1->prev = *indirect;
*indirect = list1;
list1 = list1->next;
} else {
list2->prev = *indirect;
*indirect = list2;
list2 = list2->next;
}
last = *indirect;
indirect = &((*indirect)->next);
}
if (!list1) {
last->next = list2;
list2->prev = last;
}
if (!list2) {
last->next = list1;
list1->prev = last;
}
return temp;
}
```
然後是遞迴的 merge sort
```c
struct list_head *merge_sort(struct list_head *head)
{
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;
slow->prev = NULL;
struct list_head *list1 = merge_sort(head);
struct list_head *list2 = merge_sort(slow);
return merge_two_lists(list1, list2);
}
```
再來是作業的 q_sort，當時忘記重新連結頭跟尾，debug 了很久
```c
/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
if(list_empty(head))
return;
// break the list circle
head->prev->next = NULL;
head->prev = NULL;
// merge sort
head->next = merge_sort(head->next);
// reconnect
head->next->prev = head;
struct list_head *t = head;
while (t->next != NULL) {
t->next->prev = t;
t = t->next;
}
head->prev = t;
t->next = head;
}
```
### q_merge
我第一眼看到這個函式時，蠻疑惑為什麼會需要 merge多個 list，因為之前操作都是只有一個 list 的情形。於是閱讀了 ```qtest.c``` 的 ```do_merge``` 和 ```do_new``` 才發現一直以來操作的其實是 ```current->q```。
而在 ```do_merge``` 呼叫 ```q_merge``` 時會傳入 ```&chain.head```，並接收 merge 完後 list 的長度。所以要存取所有的 list 的話，需要用到 ```queue_context_t``` 這個 struct。
```c
int q_merge(struct list_head *head)
{
if(!head || list_empty(head))
return 0;
queue_contex_t *headchain = list_entry(head->next, queue_contex_t, chain);
if(list_is_singular(headchain->q))
return headchain->size;
for(struct list_head *h = head->next->next; h != head; h = h->next){
queue_contex_t *qctx = list_entry(h, queue_contex_t, chain);
headchain->size += qctx->size;
list_splice_tail_init(qctx->q, headchain->q);
}
q_sort(headchain->q);
return headchain->size;
// https://leetcode.com/problems/merge-k-sorted-lists/
}
```
### q_descend
[2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/)
:::warning
改以 Graphviz 製圖
:notes: jserv
:::
最直觀的解法應該是從頭開始逐一節點檢查，但是這樣時間複雜度會是 $O(n^{2})$。我觀察之後發現可以由最後一個 node 往前 traverse，遇到 value 比較小的直接 delete 掉，如此時間複雜度就變為 $O(n)$
```c
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
if (list_is_singular(head))
return 1;
int len = 1;
element_t *t = list_entry(head->prev, element_t, list);
char *v = t->value;
struct list_head *h, *safe;
for(h = head->prev->prev, safe = h->prev; h != head; h = safe, safe = h->prev){
t = list_entry(h, element_t, list);
if(strcmp(v, t->value) > 0){
list_del(h);
q_release_element(list_entry(h, element_t, list));
}
else{
v = t->value;
len++;
}
}
return len;
}
```
### q_reverse、q_reverseK
二者非常類似，我都是將 traverse 到的點用 ```list_move``` 移到head後面，比較不同的是 q_reverseK 需要額外用一個 counter 計數以及 head 的位置要調整而已
```c
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);
}
```
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_is_singular(head))
return;
struct list_head *node, *safe, *start;
start = head;
int counter = 0;
list_for_each_safe(node, safe, head){
counter++;
if(counter == k){
struct list_head *temp, *temp_safe;
for(temp = start->next, temp_safe = temp->next; temp != safe; temp = temp_safe, temp_safe = temp->next)
list_move(temp, start);
counter = 0;
start = safe->prev;
}
}
}
```
目前95/100
Sign in with Wallet
Connect another wallet