2020q1 Homework1 (lab0)

contributed by < BWbwchen >

開發環境

$ uname -a
Linux bw-pc 4.19.102-1-MANJARO #1 SMP Wed Feb 5 19:48:44 UTC 2020 x86_64 GNU/Linux
$ gcc --version
gcc (GCC) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.

作業要求

• q_new: 建立新的「空」佇列;
• q_free: 釋放佇列所佔用的記憶體;
• q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
• q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
• q_remove_head: 在佇列開頭 (head) 移除 (remove) 給定的元素。
• q_size: 計算佇列中的元素數量。
• q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
• q_sort: 以遞增順序來排序鏈結串列的元素

實作

Structure

• 為了要讓q_insert_tail 和 q_size 可以為
  $O(1)$ ，因此加入新的 struct member 來隨時紀錄 tail 和 size

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
} queue_t;

q_new

• malloc 一個新的記憶體空間，但須注意 malloc 有沒有失敗，並做初始化

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));

    if (q == NULL)
        return NULL;

    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

q_free

• 單純的從 head 一路 free 到結尾，但須注意 value 也是經由 malloc 取得的，因此也要 free

void q_free(queue_t *q)
{
    if (q == NULL)
        return;

    while (q->head) {
        list_ele_t *tmp = q->head;
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
    }

    free(q);
}

q_insert_head

• 需注意如果原先的 queue 是空的情況，還有在 malloc value 失敗時，要記得把原本的 newh 還回去

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((strlen(s) + 1) * sizeof(char));
    if (newh->value == NULL) {
        free(newh);
        return false;
    }

    strncpy(newh->value, s, strlen(s));
    newh->value[strlen(s)] = '\0';

    if (q->head == NULL) {
        q->tail = newh;
    }

    newh->next = q->head;
    q->head = newh;
    q->size++;


    return true;
}

q_insert_tail

• 需要注意 queue 為空的狀況，要記得更新 queue 的資料

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL)
        return false;

    list_ele_t *tmp;
    tmp = malloc(sizeof(list_ele_t));
    if (tmp == NULL)
        return false;

    tmp->next = NULL;
    tmp->value = malloc((strlen(s) + 1) * sizeof(char));
    if (tmp->value == NULL && strlen(s) != 0) {
        free(tmp);
        return false;
    }

    strncpy(tmp->value, s, strlen(s));
    tmp->value[strlen(s)] = '\0';

    if (q->tail == NULL) {
        q->head = tmp;
    } else {
        q->tail->next = tmp;
    }

    q->tail = tmp;
    q->size++;

    return true;
}

q_remove_head

• 需要注意如果 queue 的長度為 1 的狀況。也要記得刪除的 node 需要把 value free 掉

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->head == NULL)
        return false;

    if (sp != NULL) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    if (q->head->next == NULL) {
        free(q->head->value);
        free(q->head);
        q->head = NULL;
        q->tail = NULL;
        q->size = 0;
        return true;
    }

    list_ele_t *tmp;
    tmp = q->head;
    q->head = q->head->next;
    q->size--;

    free(tmp->value);
    free(tmp);
    return true;
}

q_size

int q_size(queue_t *q)
{
    return !q ? 0 : q->size;
}

q_reverse

• 因為 list_ele_t 只記住 next 的資料，因此需要一個 pointer 來記住下一個 element ，才能順利將 next 的資料更新。

void q_reverse(queue_t *q)
{
    if (q == NULL || q->head == NULL || q->size == 1)
        return;

    list_ele_t *pre = NULL, *now = q->head, *after = q->head->next;
    q->tail = q->head;

    while (after) {
        now->next = pre;
        pre = now;
        now = after;
        after = after->next;
    }

    now->next = pre;
    q->head = now;
}

q_sort

• 我採用 merge sort 的方式
• 如果採用測驗 1 的方式去切 list 的話，複雜度沒辦法壓下來，因此要找到 list 區段的中心才能將複雜度壓到
  $O(nlogn)$

list_ele_t *merge_sort(list_ele_t *start)
{
    if (start == NULL || start->next == NULL)
        return start;

    list_ele_t *mid;
    mid = get_mid(start);
    list_ele_t *right = mid->next;
    mid->next = NULL;

    return merge_list(merge_sort(start), merge_sort(right));
}

• get_mid()
• 用兩個走訪速率為 1 ： 2 的 pointer 去走訪到中間點

list_ele_t *get_mid(list_ele_t *start)
{
    if (start == NULL)
        return start;

    list_ele_t *slow = start, *fast = start;

    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

• merge_list
• 這邊我就直接採用測驗題的方式去做 merge

list_ele_t *merge_list(list_ele_t *left, list_ele_t *right)
{
    // Merge
    list_ele_t *start = NULL;
    for (list_ele_t *merge = NULL; left || right;) {
        if (!right || (left && strcmp(left->value, right->value) < 0)) {
            if (!merge) {
                start = merge = left;
            } else {
                merge->next = left;
                merge = merge->next;
            }
            left = left->next;
        } else {
            if (!merge) {
                start = merge = right;
            } else {
                merge->next = right;
                merge = merge->next;
            }
            right = right->next;
        }
    }
    return start;
}