# 2020q3 Homework1 (lab0)

contributed by < `carlhutant` >
[TOC]
# 開發環境

$ uname -a
Linux carl-VirtualBox 5.4.0-47-generic #51~18.04.1-Ubuntu SMP Sat Sep 5 14:35:50 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0

# 程式撰寫

### 修改queue.h
加入 tail 與 size 使 q_insert_tail() 與 q_size() 複雜度為 O(1)

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size;
} queue_t;

### 實作q_new

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q) {
        q->head = NULL;
        q->tail = NULL;
        q->size = 0;
    }
    return q;
}

### 實作q_free

void q_free(queue_t *q)
{
    if (q) {
        list_ele_t *node_free;
        node_free = q->head;
        while (q->head) {
            q->head = q->head->next;
            free(node_free->value);
            free(node_free);
            node_free = q->head;
        }
        free(q);
    }
    return;
}

### 實作q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;
    newh->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, strlen(s));
    newh->value[strlen(s)] = '\0';
    newh->next = q->head;
    q->head = newh;
    if (q->tail == NULL)
        q->tail = newh;
    (q->size)++;
    return true;
}

### 實作q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;
    newh->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, strlen(s));
    newh->value[strlen(s)] = '\0';
    newh->next = NULL;
    if (q->tail) {
        q->tail->next = newh;
    }
    if (q->head == NULL)
        q->head = newh;
    q->tail = newh;
    (q->size)++;
    return true;
}

### 實作q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->head == NULL)
        return false;
    list_ele_t *node_free;
    node_free = q->head;
    q->head = q->head->next;
    if (q->tail == node_free)
        q->tail = q->tail->next;
    if (sp) {
        size_t l;
        if (bufsize > strlen(node_free->value)) {
            l = strlen(node_free->value);
        } else {
            l = bufsize - 1;
        }
        strncpy(sp, node_free->value, l);
        sp[l] = 0;
    }
    free(node_free->value);
    free(node_free);
    (q->size)--;
    return true;
}

### 實作q_size

{
    if (q == NULL)
        return 0;
    return q->size;
}

### 實作q_reverse

void q_reverse(queue_t *q)
{
    if (q == NULL || q->size < 2) {
        return;
    }
    list_ele_t **node = &(q->head);
    list_ele_t *cursor = NULL;
    q->tail = q->head;
    while (*node) {
        list_ele_t *next = (*node)->next;
        (*node)->next = cursor;
        cursor = *node;
        *node = next;
    }
    *node = cursor;
}

### 實作q_sort

void merge_sort(list_ele_t **q, int size)
{
    if (size < 2) {
        return;
    }
    list_ele_t *sub_q1 = *q;
    list_ele_t *sub_q2 = *q;
    list_ele_t **tmp = q;
    int size2 = size / 2;
    int size1 = size - size2;
    for (int i = 0; i < size1; i++) {
        tmp = &sub_q2->next;
        sub_q2 = sub_q2->next;
    }
    *tmp = NULL;
    tmp = q;
    *q = NULL;
    merge_sort(&sub_q1, size1);
    merge_sort(&sub_q2, size2);
    while (sub_q1 && sub_q2) {
        int cmp = strcmp(sub_q1->value, sub_q2->value);
        if (cmp >= 0) {
            *tmp = sub_q2;
            sub_q2 = sub_q2->next;
            tmp = &(*tmp)->next;
            if (cmp == 0) {
                *tmp = sub_q1;
                sub_q1 = sub_q1->next;
                tmp = &(*tmp)->next;
            }
        } else {
            *tmp = sub_q1;
            sub_q1 = sub_q1->next;
            tmp = &(*tmp)->next;
        }
        *tmp = NULL;
    }
    if (sub_q1) {
        *tmp = sub_q1;
    } else {
        *tmp = sub_q2;
    }
}
void q_sort(queue_t *q)
{
    if (q == NULL || q->size < 2) {
        return;
    }
    merge_sort(&q->head, q->size);
}

## todo ： merge sort 對少量資料成本過高，可試著改變資料型態與演算法

# 測試結果
通過了 trace16
因此 sort 的複雜度應該沒問題
但卡在 trace15
目前只能懷疑 code 不夠精簡 有多餘的行為導致最終仍然 Time limit exceeded
trace15 :

new
ih dolphin 1000000
it gerbil 1000000
size 1000
reverse
sort
size 1000