# 2020q3 Homework1 (lab0)
contributed by <`tigger12613`>
## 系統環境
```shell
windows10 2004
virtualbox 6.0.14
ubuntu 20.04
```
## 作業要求
[2020q3(lab0)](https://hackmd.io/@sysprog/2020-lab0)
## 實作
### queue_t
`tail` 指向 queue 的最後一個 element
`size` 紀錄 queue 的大小
```cpp
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
### q_new
新增並初始化一個 queue
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q) {
return q;
}
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
### q_free
從頭開始一個一個刪除 element 以及 element 裡的 value
time complexity = O(n)
```cpp
void q_free(queue_t *q)
{
if (!q) {
return;
}
while (q->head != NULL) {
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
### q_insert_head
新增一個 element 並且放入 value ， 把 element 放到queue的第一個位置
time complexity = O(1)
* 重點
* 所有 pointer 都要自己寫入 NULL ， c pointer 並沒有 default value
* 如果第二個 malloc 失敗，要記得 free 第一個 allocated space
* strncpy 並不一定會加上 \0 要手動加
```cpp
bool q_insert_head(queue_t *q, char *s)
{
if (!q) {
return false;
}
list_ele_t *newh = NULL;
newh = malloc(sizeof(list_ele_t));
if (!newh) {
return false;
}
newh->value = NULL;
newh->next = NULL;
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s));
newh->value[strlen(s)] = '\0';
newh->next = q->head;
if (!q->head) {
q->head = newh;
q->tail = newh;
} else {
q->head = newh;
}
q->size++;
return true;
}
```
### q_insert_tail
與 q_insert_head 類似，只是放在尾端
time complexity = O(1)
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newh = NULL;
if (!q) {
return false;
}
newh = malloc(sizeof(list_ele_t));
if (!newh) {
return false;
}
newh->value = NULL;
newh->next = NULL;
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s));
newh->value[strlen(s)] = '\0';
if (!q->tail) {
q->head = newh;
q->tail = newh;
} else {
q->tail->next = newh;
q->tail = newh;
}
q->size++;
return true;
}
```
### q_remove_head
刪除 head 指向的 element ， head 指向下一個 element
time complexity = O(1)
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head) {
return false;
}
if (sp && q->head->value) {
if (strlen(q->head->value) > bufsize - 1) {
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
} else {
strncpy(sp, q->head->value, strlen(q->head->value));
sp[strlen(q->head->value)] = '\0';
}
}
if (q->head == q->tail) {
free(q->head->value);
free(q->head);
q->head = NULL;
q->tail = NULL;
} else {
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
q->size--;
return true;
}
```
### q_size
回傳 queue 的長度，如果沒有 queue return 0
因為有紀錄 size ，所以 time complexity = O(1)
```cpp
int q_size(queue_t *q)
{
if (!q) {
return 0;
}
return q->size;
}
```
### q_reverse
反轉 queue
time complexity = O(n)
space complexity = O(1)
```cpp
void q_reverse(queue_t *q)
{
if (!q || !q->head || q->size <= 1) {
return;
} else {
q->tail = q->head;
list_ele_t *left = NULL;
list_ele_t *right;
while (q->head) {
right = q->head->next;
q->head->next = left;
left = q->head;
q->head = right;
}
q->head = left;
}
}
```
### q_sort
我選擇使用 merge sort
經過 merge sort 之後 tail 會跑掉，要重新找到 tail
time complexity = O(nlogn)
space complexity = O(1)
```cpp
void q_sort(queue_t *q)
{
if (!q || !q->head) {
return;
}
q->head = merge_sort(q->head);
while (q->tail->next) {
q->tail = q->tail->next;
}
}
```
### merge_sort
參考[Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)
```cpp
list_ele_t *merge_sort(list_ele_t *head)
{
if (!head || !head->next) {
return head;
}
list_ele_t *slow = head;
list_ele_t *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *left = merge_sort(head);
list_ele_t *right = merge_sort(fast);
return merge(left, right);
}
list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
list_ele_t *head = NULL;
list_ele_t *tail = NULL;
while (left && right) {
if (strcmp(left->value, right->value) <= 0) {
if (!head) {
head = left;
tail = left;
} else {
tail->next = left;
tail = tail->next;
}
left = left->next;
} else {
if (!head) {
head = right;
tail = right;
} else {
tail->next = right;
tail = tail->next;
}
right = right->next;
}
}
if (left) {
tail->next = left;
}
if (right) {
tail->next = right;
}
return head;
}
```
Sign in with Wallet
Connect another wallet