---
# System prepended metadata

title: 2020q3 Homework1 (lab0)

---

# 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;
}
```