# 2022q1 Homework1 (lab0)
contributed by < `qwer312132` >
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.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): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 142
Model name: Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz
Stepping: 12
CPU MHz: 2100.000
CPU max MHz: 4200.0000
CPU min MHz: 400.0000
BogoMIPS: 4199.88
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-7
```
## [作業要求](https://hackmd.io/@sysprog/2022-lab0)
* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點;
* `q_release_element`: 釋放特定節點的記憶體空間;
* `q_size`: 計算目前佇列的節點總量;
* `q_delete_mid`: 移走佇列中間的節點，詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
* `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
* `q_swap`: 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
* `q_sort`: 以==遞增順序==來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;
## queue.c 實作
:::danger
不要只張貼程式碼，需要解說並闡述後續的改進。
:notes: jserv
:::
### q_new
增加新節點
```c
struct list_head *q_new()
{
struct list_head *q = (struct list_head *) malloc(sizeof(struct list_head));
if (q) {
INIT_LIST_HEAD(q);
return q;
}
return NULL;
}
```
### q_free
釋放list使用到的記憶體
原本沒有想到要判斷 l 是否是 NULL ，在 check 時一直 segmentation fault
後來到 qtest 中才發現 quit 也會做ㄧ次 free
```c
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *li = l->next;
while (li != l) {
struct list_head *temp = li;
li = li->next;
element_t *e = container_of(temp, element_t, list);
q_release_element(e);
}
free(l);
}
```
### q_insert_head
在 list 前新增節點
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *e = (element_t *) malloc(sizeof(element_t));
if (!e)
return false;
e->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
if (!e->value) {
free(e);
return false;
}
strncpy(e->value, s, strlen(s));
list_add(&e->list, head);
e->value[strlen(s)] = '\0';
return true;
}
```
### q_insert_tail
在 list 後新增節點
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *e = (element_t *) malloc(sizeof(element_t));
if (!e)
return false;
e->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
if (!e->value) {
free(e);
return false;
}
strncpy(e->value, s, strlen(s));
list_add_tail(&e->list, head);
e->value[strlen(s)] = '\0';
return true;
}
```
### q_remove_head
在 list 頭刪除節點
好像還有些 bug ，會造成 segmentation fault
目前猜測是我沒仔細看 qtest
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!list_empty(head)) {
struct list_head *h = head->next;
element_t *e = container_of(h, element_t, list);
strncpy(sp, e->value, bufsize - 1);
list_del(h);
sp[bufsize - 1] = '\0';
return e;
}
return NULL;
}
```
### q_remove_tail
在 list 尾刪除節點
目前問題如同 q_remove_head
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!list_empty(head)) {
struct list_head *t = head->prev;
element_t *e = container_of(t, element_t, list);
strncpy(sp, e->value, bufsize - 1);
list_del(t);
sp[bufsize - 1] = '\0';
return e;
}
return NULL;
}
```
### q_size
計算 list 有多少節點
參考自[lab0](https://hackmd.io/@sysprog/2020-lab0)
```c
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
bool q_delete_mid(struct list_head *head)
{
if (!head)
return NULL;
struct list_head *temp1 = head->next;
struct list_head *temp2 = head->prev;
while (temp1 != temp2 && temp1->next != temp2) {
temp1 = temp1->next;
temp2 = temp2->prev;
}
list_del(temp1);
free(temp1);
return true;
}
```
### q_delete_dup
刪除重複元素的節點
```c
bool q_delete_dup(struct list_head *head)
{
if (!head)
return NULL;
struct list_head *temphead = head->next;
while (temphead != head) {
bool flag = 0;
element_t *tempheadElement = container_of(temphead, element_t, list);
struct list_head *temp = temphead->next;
while (temp != head) {
element_t *tempElement = container_of(temp, element_t, list);
if (strcmp(tempElement->value, tempheadElement->value) == 0) {
flag = 1;
list_del(temp);
temp = temp->next;
free(tempElement);
} else {
break;
}
}
temphead = temphead->next;
if (flag) {
list_del(temphead->prev);
free(tempheadElement);
}
}
return true;
}
```
:::warning
試著縮減上述程式碼，撰寫更精簡有效的實作
:notes: jserv
:::
### q_swap
交換相鄰的節點
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head) || list_is_singular(head))
return;
else {
struct list_head *temp1, *temp2, *temp3;
temp1 = head->next;
temp2 = temp1->next;
temp3 = head;
while (1) {
temp1->next = temp2->next;
temp1->prev = temp2;
temp2->next = temp1;
temp2->prev = temp3;
temp3->next = temp2;
if (temp1->next != head && temp1->next->next != head) {
temp3 = temp1;
temp1 = temp1->next;
temp2 = temp1->next;
} else {
break;
}
}
}
}
```
### q_reverse
翻轉整個 list
```c
void swap_two_node(struct list_head **node1, struct list_head **node2)
{
struct list_head *temp;
temp = *node1;
*node1 = *node2;
*node2 = temp;
}
void q_reverse(struct list_head *head)
{
struct list_head *temp = head;
swap_two_node(&temp->next, &temp->prev);
list_for_each (temp, head) {
swap_two_node(&temp->next, &temp->prev);
}
}
```
### q_sort
按升序排列
參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/YA7RMqd6RE2UL8OmmjU9PQ)
雖然寫過mergesort，不過第一次對 linked list 做排序，一直寫錯
```c
struct list_head *merge(struct list_head *l, struct list_head *r)
{
struct list_head *head = NULL;
struct list_head **indirect = &head;
while (l && r) {
element_t *elementl = container_of(l, element_t, list);
element_t *elementr = container_of(r, element_t, list);
if (strcmp(elementl->value, elementr->value) < 0) {
*indirect = l;
l = l->next;
} else {
*indirect = r;
r = r->next;
}
indirect = &(*indirect)->next;
}
*indirect = (struct list_head *) ((uintptr_t) l | (uintptr_t) r);
return head;
}
struct list_head *mergesort(struct list_head *l, struct list_head *r)
{
struct list_head *tortoise = l;
struct list_head *hare = l;
if (l == r) {
l->next = NULL;
return l;
} else if (l->next == r) {
element_t *left = container_of(l, element_t, list);
element_t *right = container_of(r, element_t, list);
if (strcmp(left->value, right->value) > 0) {
l->next = NULL;
r->next = l;
return r;
} else {
r->next = NULL;
return l;
}
}
while (hare->next != NULL && hare->next->next != NULL && hare->next != r &&
hare->next->next != r) {
hare = hare->next->next;
tortoise = tortoise->next;
}
struct list_head *list1, *list2;
struct list_head *temp = tortoise->next;
list1 = mergesort(l, tortoise);
list2 = mergesort(temp, r);
return merge(list1, list2);
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
head->prev->next = NULL;
head->next = mergesort(head->next, head->prev);
struct list_head *node = head;
while (node->next) {
node->next->prev = node;
node = node->next;
}
node->next = head;
head->prev = node;
}
```
目前完成了 queue.c 的部份，不過應該還會修改，大部分的程式碼都是沒想清楚就寫的，應該可以再簡潔一些
Sign in with Wallet
Connect another wallet