# 2020q1 Homework1 (lab0)
contributed by < `mistysya` >
題目出處: [lab0](https://hackmd.io/@sysprog/linux2020-lab0)
## 開發環境
```shell
$ lsb_release -a
Description: Ubuntu 18.04.4 LTS
$ gcc 7.4.0
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0
```
## queue.c 實作
### q_new()
建立一個新的空佇列 (empty queue)
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q == NULL) {
printf("ERROR::q_new()::Allocate memory to queue failed.\n");
return NULL;
}
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
### q_free()
清除該條佇列，釋放佇列占用的記憶體，同時要一併釋放佇列內元素占用的記憶體
不能僅單純釋放 queue 的元素，還需要釋放 queue 元素的字串占用的記憶體，因為當初插入 queue 時，有特別為字串 allocate memory ，這部分的記憶體並不會自動釋放。
```c=
void q_free(queue_t *q)
{
if (q == NULL)
return;
list_ele_t *tmp = q->head;
while (tmp) {
q->head = tmp->next;
free(tmp->value);
free(tmp);
tmp = q->head;
}
free(q);
}
```
### q_insert_head()
自佇列的開頭 (head) 插入新元素，同時需將字串 (string) 複製一份給新元素
**實作遇到問題 :**
* 在進行 make test 時，部分測試都會顯示執行 `q_free()` 之後仍有元素存在。
* 當初實作 function 時雖然有想到進行字串複製可能出現 allocate memory 失敗的情況 (14行)，做了錯誤訊息顯示以及結束 function 的處理。
但沒有考慮到在之前 (8行) 已經為新插入元素 allocate memory 成功，如果直接結束 function 會發生 **memory leak** 的情況。
因此補上 `free(newh)` 之後 (17行) 便解決該問題。
```c=
bool q_insert_head(queue_t *q, char *s)
{
if (q == NULL) {
printf("ERROR::q_insert_head()::Pointer to queue is NULL.\n");
return false;
}
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (newh == NULL) {
printf("ERROR::q_insert_head()::Allocate memory to newh failed.\n");
return false;
}
int length = strlen(s);
char *value = malloc(sizeof(char) * (length + 1));
if (value == NULL) {
printf("ERROR::q_insert_head()::Allocate memory to value failed.\n");
free(newh);
return false;
}
strncpy(value, s, length);
value[length] = '\0';
newh->next = q->head;
newh->value = value;
q->head = newh;
if (q->tail == NULL)
q->tail = newh;
q->size += 1;
return true;
}
```
### q_insert_tail()
自佇列的尾端 (tail) 插入新元素，同時需將字串 (string) 複製一份給新元素
為了達到在 $O(1)$ 時間複雜度內完成插入，額外新增一個指標來記錄 tail 的位置
```c=
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
**實作遇到問題 :**
* 問題同 `q_insert_head()` ，在進行 make test 時，部分測試都會顯示執行 `q_free()` 之後仍有元素存在。
以同樣的方式解決。
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if (q == NULL) {
printf("ERROR::q_insert_tail()::Pointer to queue is NULL.\n");
return false;
}
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (newh == NULL) {
printf("ERROR::q_insert_tail()::Allocate memory to newh failed.\n");
return false;
}
int length = strlen(s);
char *value = malloc(sizeof(char) * (length + 1));
if (value == NULL) {
printf("ERROR::q_insert_tail()::Allocate memory to value failed.\n");
free(newh);
return false;
}
strncpy(value, s, length);
value[length] = '\0';
newh->next = NULL;
newh->value = value;
if (q->tail) {
q->tail->next = newh;
} else {
q->head = newh;
}
q->tail = newh;
q->size += 1;
return true;
}
```
### q_remove_head()
自佇列的開頭 (head) 移除元素，同時將移除元素的字串內容複製到指定字串中
需要特別注意元素的字串長度是否超過指定的 buffer size，否則在執行 `strncpy` 時可能會出錯，同時也需要在字串尾部補上 `\0`，因為 `strncpy` 不會自動在目標字串補上空字元。
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q == NULL) {
printf("ERROR::q_remove_head()::Pointer to queue is NULL.\n");
return false;
}
if (q->head == NULL) {
printf("ERROR::q_remove_head()::Queue is empty.\n");
return false;
}
if (sp == NULL) {
printf("ERROR::q_remove_head()::Pointer to string is NULL.\n");
return false;
}
list_ele_t *tmp = q->head;
int length = strlen(tmp->value);
if (length < bufsize) {
strncpy(sp, tmp->value, length);
sp[length] = '\0';
} else {
strncpy(sp, tmp->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
if (q->tail == q->head)
q->tail = NULL;
q->head = q->head->next;
free(tmp->value);
free(tmp);
q->size -= 1;
return true;
}
```
### q_size()
回傳佇列中元素的數量
為了達到在 $O(1)$ 時間複雜度內完成插入，額外新增一個整數變數來記錄元素的數量
```c=
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
```c=
int q_size(queue_t *q)
{
if (q == NULL || q->head == NULL)
return 0;
return q->size;
}
```
### q_reverse()
在不額外配置或釋放任何元素的情況下，反向排序整條 queue
```c=
void q_reverse(queue_t *q)
{
if (q == NULL || q->head == NULL || q->head->next == NULL)
return;
q->tail = q->head;
list_ele_t *prevEle = NULL;
list_ele_t *nextEle = q->head->next;
while (nextEle) {
q->head->next = prevEle;
prevEle = q->head;
q->head = nextEle;
nextEle = nextEle->next;
}
q->head->next = prevEle;
}
```
### q_sort()
以遞增順序排序 queue 中的元素
**實作遇到問題 :**
* 使用 selection sort 或 insertion sort 都會出現超時的問題
* 改用 **merge sort** 解決超時問題，但部分測資會出現遞迴層數過多導致 **stack overflow** 的問題
* 遞迴層數過多造成的 stack overflow 問題，透過改用迭代的方式進行 merge sort 解決
```c=
int min(int x, int y)
{
return x < y ? x : y;
}
void q_sort(queue_t *q)
{
if (q == NULL)
return;
int length = q->size;
for (int width = 1; width < length; width *= 2) {
list_ele_t tmp_head;
list_ele_t *tmp = &tmp_head;
list_ele_t *l_node = q->head;
list_ele_t *r_node = q->head;
for (int start = 0; start < length; start += width * 2) {
int mid = min(start + width, length),
end = min(start + width * 2, length);
int ls = start;
int le = mid;
int rs = mid;
int re = end;
for (int i = 0; i < width; i++) {
if (r_node->next)
r_node = r_node->next;
else
break;
}
while (ls < le && rs < re) {
if (strnatcmp(l_node->value, r_node->value) < 0) {
tmp->next = l_node;
tmp = tmp->next;
l_node = l_node->next;
tmp->next = NULL;
ls += 1;
} else {
tmp->next = r_node;
tmp = tmp->next;
r_node = r_node->next;
tmp->next = NULL;
rs += 1;
}
}
while (ls < le) {
tmp->next = l_node;
tmp = tmp->next;
l_node = l_node->next;
tmp->next = NULL;
ls += 1;
}
while (rs < re) {
tmp->next = r_node;
tmp = tmp->next;
r_node = r_node->next;
tmp->next = NULL;
rs += 1;
}
l_node = r_node;
}
q->head = tmp_head.next;
}
}
```
Sign in with Wallet
Connect another wallet