# 2020q3 Homework1 (lab0)
contributed by < [`OliveLake`](https://github.com/OliveLake/lab0-c.git) >

### [lab0題目描述](https://hackmd.io/@sysprog/2020-lab0)

## 環境
### Kernel

uname -srv
#Darwin Kernel Version 19.6.0
#因為macOS載ubuntu磁碟分區有問題，暫時用原系統，會盡快解決，很抱歉

### Compiler

gcc --version
# Apple clang version 11.0.3 (clang-1103.0.32.29) 

## Requirement
- q_new:建立一個新且空的queue
- q_free:釋放整個:queue 的記憶體
- q_insert_head:在 head 插入元素(LIFO)
- q_insert_tail:在 tail 插入元素(FIFO)
- q_remove_head:從 head 移除特定元素
- q_size:回傳目前queue 的大小(元素數量)
- q_reverse:反向排列queue且不能增減元素
- q_sort:將元素遞增排列

## Data type
### Linked list elements

typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;

### Queue structure
- 為了實作q_insert_tail函數並維持$O(1)$的時間複雜度，加入指向queue尾端的指標，就不用從頭到尾執行，否則時間複雜度是$O(N)$

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

## q_new
Requirements:
* Create empty queue.
* Return NULL if could not allocate space.

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

- 如果分配記憶體錯誤malloc()會回傳NULL，若是成功要到記憶體，則回傳位址
## q_free
Requirements:
* Free all storage used by queue

queue_t *q_new()
{
    if (!q)    return;
    list_ele_t *target = q->head;
    while (target) {
        q->head = target;
        target = target->next;
        free(q->head->value);
        free(q->head);
    }
    free(q);
}

- 走訪每個節點，先釋放元素內的字串和值，再釋放整個structure
## q_insert_head
Requirements:

* Attempt to insert element at head of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Arguments points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    if (!q)
        return false;
    newh = malloc(sizeof(list_ele_t));
    if (!newh) {
        free(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));

    if (!q->head) {
        q->head = q->tail = newh;
        newh->next = NULL;
    } else {
        newh->next = q->head;
        q->head = newh;
    }
    q->size++;
    return true;
}

- strlen 回傳的字串沒有包含 NUL character 的長度, 所以在配置空間的時候必須要加1
- 不要用strcpy，因為可能改動到其他記憶體

## q_insert_tail
Requirements:
* Attempt to insert element at tail of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *new;  
    newh = malloc(sizeof(list_ele_t));   
    if (!new)
        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 = NULL;
    if (!q->tail) {
        q->tail = q->head = newh;
    } else {
        q->tail->next = newh;
        q->tail = newh;
    }  
    q->size += 1;
    return true;
}

- 和q_insert_head類似
## q_size
Requirements:
* Return number of elements in queue.
* Return 0 if q is NULL or empty

if (!q)
        return false;
    return q->size;

* 要維持$O(1)$的複雜度
* 檢查傳入的 queue 是否為 NULL，若否則直接回傳 size
## q_reverse
Requirements:
* Reverse elements in queue
* No effect if q is NULL or empty
* This function should not allocate or free any list elements
* (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
* It should rearrange the existing ones.

if (!q || q->size == 0)
        return;

    list_ele_t *prev_ele = NULL;
    list_ele_t *temp_ele = q->head;
    q->tail = q->head;
    while (temp_ele) {
        temp_ele = temp_ele->next;
        q->head->next = prev_ele;
        prev_ele = q->head;
        q->head = temp_ele;
    }
    q->head = prev_ele;

* 參考[amikai](https://hackmd.io/@yLOCW3p8QquG_IWn4gMSfw/rkyPtw_YQ?type=view)學長姐的方式，把每個元素的next指向前一個，再改動head和tail，不要動到元素中的資料
## merge_sort

list_ele_t *p1, *p2;
    p1 = *head;
    p2 = (*head)->next;
    while (p1 && p1->next) {
        p1 = p1->next;
        p2 = p2->next->next;
    }
    p1 = p2->next;
    p2->next = NULL;
    p2 = *head;

    merge_sort(&p1);
    merge_sort(&p2);

    *head = NULL;
    list_ele_t **tmp = head;
    while (p1 && p2) {
        if (strcmp(p1->value, p2->value) < 0) {
            *tmp = p1;
            p1 = p1->next;
        } else {
            *tmp = p2;
            p2 = p2->next;
        }
        tmp = &((*tmp)->next);
    }
    return;
}

* 從頭開始找中間點，注意在把小數列併入大數列前要先排序好小數列，才可以在數列比較的時候直接比較head就好

## q_sort

    merge_sort(&q->head);

    while (q->tail->next)
        q->tail = q->tail->next;

    return;