# 2020q3 Homework1 (lab0)
contributed by < `chi-ming5566` >
## 開發環境
```shell
$ uname -a
Linux yx 5.3.0-40-generic #32-Ubuntu SMP Fri Jan 31 20:24:34 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 9.2.1-9ubuntu2) 9.2.1 20191008
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```
## 作業要求
在 queue.c/queue.h 中完成以下實作
*新增 int size 這個新成員到 struct queue_t
*更改q_free、q_insert_head、q_insert_tail、q_remove_head、q_size、q_reverse、q_sort等函式
## 實作流程
### queue.h
* 新增int size 這個新成員到 struct queue_t
```cpp=
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
### queue.c
* q_free
*增加 變數 tmp 作為釋放用的節點
```cpp=
void q_free(queue_t *q)
{
if (!q)
return;
list_ele_t *tmp = q->head;
while (q->head) {
q->head = q->head->next;
tmp->next = NULL;
free(tmp->value);
free(tmp);
tmp = q->head;
}
free(q);
}
```
* q_insert_head
*將新變數 list_ele_t 放入 queue 的前端
*先判斷傳入的 q 是否為 NULL,是為了預防在分配memory後才發現 q 為 NULL,造成 memory leak
*在分配memory給新的變數後,判斷是否分配成功,若失敗,則將之前所分配的 newh 清除
*以 <string.h> 的 strncpy 複製 s,放入新變數的值
*使用 memset 將 newh->value 歸零
```cpp=
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (!newh) {
return false;
}
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
if (!newh->value) {
free(newh);
return false;
}
memset(newh->value, '\0', strlen(s) + 1);
strncpy(newh->value, s, strlen(s));
newh->next = q->head;
q->head = newh;
if (!q->rail) {
q->tail = q->head;
} else {
while (q->tail->next) {
q->tail = q->tail->next;
}
}
q->size += 1;
return true;
}
```
* q_insert_tail
*將新元素 (list_ele_t) 放入 queue 的尾端
```cpp=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
newt->value = malloc(sizeof(char) * strlen(s) + 1);
if (!newt->value) {
free(newt);
return false;
}
memset(newt->value, '\0', strlen(s) + 1);
strncpy(newt->value, s, strlen(s));
newt->next = NULL;
if (!q->tail) {
q->tail = q->head = newt;
} else {
q->tail->next = newt;
q->tail = newt;
}
q->size += 1;
return true;
}
```
* q_remove_head
```cpp=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head) {
return false;
}
if (sp) {
size_t realbufsize = (bufsize > strlen(q->head->value))
? strlen(q->head->value)
: bufsize - 1;
memset(sp, '\0', realbufsize + 1);
strncpy(sp, q->head->value, realbufsize);
}
list_ele_t *tmp;
tmp = q->head;
q->head = q->head->next;
tmp->next = NULL;
free(tmp->value);
free(tmp);
q->size -= 1;
return true;
}
```
* q_size
```cpp=
int q_size(queue_t *q)
{
return !q ? 0 : q->size;
}
```
* q_reverse
```cpp=
void q_reverse(queue_t *q)
{
if (!q || q->size < 2) {
return;
}
list_ele_t *tmp;
tmp = q->head->next;
q->tail->next = q->head;
while (tmp != q->tail) {
tmp = tmp->next;
q->head->next->next = q->tail->next;
q->tail->next = q->head->next;
q->head->next = tmp;
}
q->tail = q->head;
q->head = q->head->next;
q->tail->next = NULL;
}
```
* q_sort
*使用 Merge sort 排序
```cpp=
void merge(list_ele_t **head)
{
if (!(*head) || !((*head)->next))
return;
list_ele_t *l1 = (*head)->next;
list_ele_t *l2 = *head;
while (l1 && l1->next) {
l2 = l2->next;
l1 = l1->next->next;
}
l1 = l2->next;
l2->next = NULL;
l2 = *head;
merge(&l2);
merge(&l1);
*head = NULL;
list_ele_t **tmp = head;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) < 0) {
*tmp = l1;
l1 = l1->next;
} else {
*tmp = l2;
l2 = l2->next;
}
tmp = &((*tmp)->next);
}
*tmp = l1 ? l1 : l2;
}
```
*q_sort
```cpp=
void q_sort(queue_t *q)
{
if (!q || q->head == q->tail) {
return;
}
merge(&q->head);
while (q->tail->next) {
q->tail = q->tail->next;
}
}
```