---
tags: linux2020
---
# 2020q3 Homework1 (lab0)
contributed by < `kevin30292` >
code [GitHub](https://github.com/kevin30292/lab0-c)
## function 功能
queue.c 僅提供介面但尚未有完整程式實作，需要補完並逐步精進，包含以下：
1. q_new: 建立新的「空」佇列;
2. q_free: 釋放佇列所佔用的記憶體;
3. q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
4. q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
5. q_remove_head: 在佇列開頭 (head) 移除 (remove) 給定的元素。
6. q_size: 計算佇列中的元素數量。
7. q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
8. q_sort: 「進階電腦系統理論與實作」課程所新增，以遞增順序來排序鏈結串列的元素，可參閱 Linked List Sort 得知實作手法
## 開發紀錄
### `q_size`
由於要在 O(1) 的常數時間內執行完成，所以也不可能走訪整個鏈結串列，以取得佇列的容積。
新增 size 值紀錄 queue 的大小，又提示
>Return 0 if q is NULL or empty
```clike=
int q_size(queue_t *q)
{
return (q == NULL) ? 0 q->size
}
```
### `new_q`
>TODO: What if malloc returned NULL?
`malloc` 回傳 NULL 可能為記憶體不足，因此失敗。
加入檢查機制：
```c=
if(q == NULL){
printf("Error! Allocation was failed. \n");
return 1;
}
```
### `q_free`
需逐一 `free` 所有queue中的值及字串
```c=
void q_free(queue_t *q)
{
if (q != NULL) {
list_ele_t *next;
while (q->head != NULL) {
next = q->head->next;
free(q->head->value);
free(q->head);
q->head = next;
}
free(q);
}
}
```
### `q_insert_head`
第19行需要 `free(newh)` 因為第10行的 `malloc` 失敗，但第6行的malloc是有成功的
```c=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if (q != NULL) {
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (newh != NULL) {
int length;
length = strlen(s);
newh->value = malloc(length * sizeof(char));
if (newh->value != NULL) {
memcpy(newh->value, s, length);
newh->next = q->head;
q->head = newh;
q->size++;
return true;
}
else {
free(newh);
return false
}
}
else {
return false;
}
}
else {
return false;
}
}
```
### `q_insert_tail`
* 要在 O(1) 的常數時間內執行完成
>不能從 `head` 慢慢找 tail
>
加入 `tail` 性質
`queue.h` 加入：
```c=
list_ele_t *tail;
```
需修改 code 以維護此參數
`new_q` 加入：
```c=
q->tail = NULL; // Add for the q_insert_tail
```
`q_insert_head` 加入：
```c=
if (q->size == 0) {
q->tail = newh;
}
```
12-16行，避免 `head` 缺失情況
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if (q != NULL) {
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (newt != NULL) {
int length;
length = strlen(s) + 1;
newt->value = malloc(length * sizeof(char));
if (newt->value != NULL) {
memcpy(newt->value, s, length);
if (q->size == 0) {
q->head = newt;
} else {
q->tail->next = newt;
}
q->tail = newt;
newt->next = NULL;
q->size++;
return true;
} else {
free(newt);
return false;
}
} else {
return false;
}
} else {
return false;
}
}
```
### Debug
測試時發現==亂碼==及 ==Segmentation fault==
```shell
q = [gerbil▒▒▒ bear▒▒▒ dolphin▒▒▒]
cmd> # Now at the tail
cmd> it meerkat
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
make: *** [Makefile:51: check] Aborted (core dumped)
```
Segmentation fault 部分，檢查發現 `new_q` 沒有：
1. initialize `q->size`
2. 檢查 `q` 是否為 NULL
改寫 `q_new`
```c=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q == NULL) {
printf("Error! Allocation was failed. \n");
return q;
} else {
q->head = NULL;
q->tail = NULL; // Add for the q_insert_tail
q->size = 0;
return q;
}
}
```
亂碼部分，檢查發現 `q_insert_head` length 值錯誤
```c=
length = strlen(s);
```
改為：
```c=
length = strlen(s) + 1;
```
### `q_reverse`
用兩個 pointer 紀錄，過程中的 `head` 及 `tail` 命名為 `tmph` 及 `tmpt`
從舊 `head` 開始反轉，`head->next` 指回 `head` 以此類推。
維持 `q->head` 指向尚未反轉的佇列的首項
```c=
void q_reverse(queue_t *q)
{
if (q != NULL && q->size > 1) {
list_ele_t *tmph, *tmpt;
tmpt = q->head;
tmph = q->head->next;
q->tail = q->head;
while (q->head->next != NULL) {
q->head = tmph->next;
tmph->next = tmpt;
tmpt = tmph;
tmph = q->head;
}
q->head->next = tmpt;
q->tail->next = NULL;
}
}
```
圖解：
1. 初始 ==tmpt== 及 ==tmph==
```graphviz
digraph linkedlist {
rankdir=LR
node [shape=record]
a [label="{ <data> 1 | <ref> }", width=1]
b [label="{ <data> 2 | <ref> }", width=1]
c [label="{ <data> 3 | <ref> }", width=1]
head [shape=box, width=0.5, color=blue]
tail [shape=box, width=0.5, color=black]
tmph [shape=box, width=0.5, color=red]
tmpt [shape=box, width=0.5, color=red]
a:ref:a -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]
tail -> c
head -> a
tmpt -> a
tmph -> b
}
```
2. `tail` 移至 `head`
```graphviz
digraph linkedlist {
rankdir=LR
node [shape=record]
a [label="{ <data> 1 | <ref> }", width=1]
b [label="{ <data> 2 | <ref> }", width=1]
c [label="{ <data> 3 | <ref> }", width=1]
head [shape=box, width=0.5, color=blue]
tail [shape=box, width=0.5, color=black]
tmph [shape=box, width=0.5, color=red]
tmpt [shape=box, width=0.5, color=red]
a:ref:a -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]
tail -> a
head -> a
tmpt -> a
tmph -> b
}
```
3. while 迴圈
```graphviz
digraph linkedlist {
rankdir=LR
node [shape=record]
a [label="{ <data> 1 | <ref> }", width=1]
b [label="{ <data> 2 | <ref> }", width=1]
c [label="{ <data> 3 | <ref> }", width=1]
head [shape=box, width=0.5, color=blue]
tail [shape=box, width=0.5, color=black]
tmph [shape=box, width=0.5, color=red]
tmpt [shape=box, width=0.5, color=red]
a:ref:a -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]
b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]
tail -> a
head -> c
tmpt -> a
tmph -> b
}
```
```graphviz
digraph linkedlist {
rankdir=LR
node [shape=record]
a [label="{ <data> 1 | <ref> }", width=1]
b [label="{ <data> 2 | <ref> }", width=1]
c [label="{ <data> 3 | <ref> }", width=1]
head [shape=box, width=0.5, color=blue]
tail [shape=box, width=0.5, color=black]
tmph [shape=box, width=0.5, color=red]
tmpt [shape=box, width=0.5, color=red]
a:ref:a -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]
b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]
tail -> a
head -> c
tmpt -> b
tmph -> c
}
```
4. while 迴圈結束 `head->next` 為 ==NULL==
```graphviz
digraph linkedlist {
rankdir=LR
node [shape=record]
a [label="{ <data> 1 | <ref> }", width=1]
b [label="{ <data> 2 | <ref> }", width=1]
c [label="{ <data> 3 | <ref> }", width=1]
head [shape=box, width=0.5, color=blue]
tail [shape=box, width=0.5, color=black]
tmph [shape=box, width=0.5, color=red]
tmpt [shape=box, width=0.5, color=red]
b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]
c:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]
tail -> a
head -> c
tmpt -> b
tmph -> c
}
```
### `q_sort`
```c=
queue_t* merge_list(queue_t *l1, queue_t *l2)
{
if (!l1) return l2;
if (!l2) return l1;
if( l1->value < l2->value) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l2->next, l1);
return l2;
}
}
queue_t* merge_sort(list_ele_t *l)
{
if (!q || !q->next) return q;
list_ele_t* fast;
list_ele_t* slow;
fast = q->head->next;
slow = q->head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t* l1 = merge_sort(q);
list_ele_t* l2 = merge_sort(q2);
return merge_list(l1,l2);
}
void q_sort(queue_t *q)
{
if (q && q->size > 0) {
merge_sort(q);
return;
} else {
printf("Something going wrong!!");
return;
}
}
```
卡在merge_sort()，不知道應該用什麼型態的 input ，考慮到 recursive 呼叫。
參考前人實作：[ZhuMon](https://hackmd.io/@ZhuMon/lab0-c)，採用 pointer to pointer 的方式，即可不用考慮回傳 type 的問題。
```c=
void merge_sort(list_ele_t **head)
{
if(!(*head) || !((*head)->next)) return;
list_ele_t* fast;
list_ele_t* slow;
fast = (*head)->next;
slow = *head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = NULL;
slow = *head;
merge_sort(&fast);
merge_sort((&slow));
list_ele_t **tmp = head;
*head = NULL;
while (fast && slow) {
if (strcmp(fast->value, slow->value) < 0) {
*tmp = fast;
fast = fast->next;
} else {
*tmp = slow;
slow = slow->next;
}
tmp = &(*tmp)->next;
}
*tmp = fast ? fast : slow;
}
void q_sort(queue_t *q)
{
if (!q || q->size == 1) {
return;
} else if (q && q->size > 1) {
merge_sort(&q->head);
return;
} else {
return;
}
}
```
發現 sorting 在包含大寫的時候會不正常:
Sign in with Wallet
Connect another wallet