2020q1 Homework1 (lab0)

contributed by < mistysya >

題目出處: lab0

開發環境

$ lsb_release -a
Description: Ubuntu 18.04.4 LTS
$ gcc 7.4.0
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0

queue.c 實作

q_new()

建立一個新的空佇列 (empty queue)

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q == NULL) {
        printf("ERROR::q_new()::Allocate memory to queue failed.\n");
        return NULL;
    }
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

q_free()

清除該條佇列，釋放佇列占用的記憶體，同時要一併釋放佇列內元素占用的記憶體

不能僅單純釋放 queue 的元素，還需要釋放 queue 元素的字串占用的記憶體，因為當初插入 queue 時，有特別為字串 allocate memory ，這部分的記憶體並不會自動釋放。

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

q_insert_head()

自佇列的開頭 (head) 插入新元素，同時需將字串 (string) 複製一份給新元素

實作遇到問題 :

• 在進行 make test 時，部分測試都會顯示執行 q_free() 之後仍有元素存在。

  • 當初實作 function 時雖然有想到進行字串複製可能出現 allocate memory 失敗的情況 (14行)，做了錯誤訊息顯示以及結束 function 的處理。

    但沒有考慮到在之前 (8行) 已經為新插入元素 allocate memory 成功，如果直接結束 function 會發生 memory leak 的情況。

    因此補上 free(newh) 之後 (17行) 便解決該問題。

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL) {
        printf("ERROR::q_insert_head()::Pointer to queue is NULL.\n");
        return false;
    }
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        printf("ERROR::q_insert_head()::Allocate memory to newh failed.\n");
        return false;
    }
    int length = strlen(s);
    char *value = malloc(sizeof(char) * (length + 1));
    if (value == NULL) {
        printf("ERROR::q_insert_head()::Allocate memory to value failed.\n");
        free(newh);
        return false;
    }
    strncpy(value, s, length);
    value[length] = '\0';

    newh->next = q->head;
    newh->value = value;
    q->head = newh;
    if (q->tail == NULL)
        q->tail = newh;
    q->size += 1;
    return true;
}

q_insert_tail()

自佇列的尾端 (tail) 插入新元素，同時需將字串 (string) 複製一份給新元素

為了達到在

$O(1)$ 時間複雜度內完成插入，額外新增一個指標來記錄 tail 的位置

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

實作遇到問題 :

• 問題同 q_insert_head() ，在進行 make test 時，部分測試都會顯示執行 q_free() 之後仍有元素存在。

  以同樣的方式解決。

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL) {
        printf("ERROR::q_insert_tail()::Pointer to queue is NULL.\n");
        return false;
    }
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        printf("ERROR::q_insert_tail()::Allocate memory to newh failed.\n");
        return false;
    }
    int length = strlen(s);
    char *value = malloc(sizeof(char) * (length + 1));
    if (value == NULL) {
        printf("ERROR::q_insert_tail()::Allocate memory to value failed.\n");
        free(newh);
        return false;
    }
    strncpy(value, s, length);
    value[length] = '\0';

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

q_remove_head()

自佇列的開頭 (head) 移除元素，同時將移除元素的字串內容複製到指定字串中

需要特別注意元素的字串長度是否超過指定的 buffer size，否則在執行 strncpy 時可能會出錯，同時也需要在字串尾部補上 \0，因為 strncpy 不會自動在目標字串補上空字元。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL) {
        printf("ERROR::q_remove_head()::Pointer to queue is NULL.\n");
        return false;
    }
    if (q->head == NULL) {
        printf("ERROR::q_remove_head()::Queue is empty.\n");
        return false;
    }
    if (sp == NULL) {
        printf("ERROR::q_remove_head()::Pointer to string is NULL.\n");
        return false;
    }
    list_ele_t *tmp = q->head;
    int length = strlen(tmp->value);
    if (length < bufsize) {
        strncpy(sp, tmp->value, length);
        sp[length] = '\0';
    } else {
        strncpy(sp, tmp->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    if (q->tail == q->head)
        q->tail = NULL;
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size -= 1;
    return true;
}

q_size()

回傳佇列中元素的數量

為了達到在

$O(1)$ 時間複雜度內完成插入，額外新增一個整數變數來記錄元素的數量

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

int q_size(queue_t *q)
{
    if (q == NULL || q->head == NULL)
        return 0;
    return q->size;
}

q_reverse()

在不額外配置或釋放任何元素的情況下，反向排序整條 queue

void q_reverse(queue_t *q)
{
    if (q == NULL || q->head == NULL || q->head->next == NULL)
        return;
    q->tail = q->head;
    list_ele_t *prevEle = NULL;
    list_ele_t *nextEle = q->head->next;
    while (nextEle) {
        q->head->next = prevEle;
        prevEle = q->head;
        q->head = nextEle;
        nextEle = nextEle->next;
    }
    q->head->next = prevEle;
}

q_sort()

以遞增順序排序 queue 中的元素

實作遇到問題 :

• 使用 selection sort 或 insertion sort 都會出現超時的問題
  • 改用 merge sort 解決超時問題，但部分測資會出現遞迴層數過多導致 stack overflow 的問題
• 遞迴層數過多造成的 stack overflow 問題，透過改用迭代的方式進行 merge sort 解決

int min(int x, int y)
{
    return x < y ? x : y;
}

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

    int length = q->size;
    for (int width = 1; width < length; width *= 2) {
        list_ele_t tmp_head;
        list_ele_t *tmp = &tmp_head;
        list_ele_t *l_node = q->head;
        list_ele_t *r_node = q->head;
        for (int start = 0; start < length; start += width * 2) {
            int mid = min(start + width, length),
                end = min(start + width * 2, length);
            int ls = start;
            int le = mid;
            int rs = mid;
            int re = end;
            for (int i = 0; i < width; i++) {
                if (r_node->next)
                    r_node = r_node->next;
                else
                    break;
            }
            while (ls < le && rs < re) {
                if (strnatcmp(l_node->value, r_node->value) < 0) {
                    tmp->next = l_node;
                    tmp = tmp->next;
                    l_node = l_node->next;
                    tmp->next = NULL;
                    ls += 1;
                } else {
                    tmp->next = r_node;
                    tmp = tmp->next;
                    r_node = r_node->next;
                    tmp->next = NULL;
                    rs += 1;
                }
            }
            while (ls < le) {
                tmp->next = l_node;
                tmp = tmp->next;
                l_node = l_node->next;
                tmp->next = NULL;
                ls += 1;
            }
            while (rs < re) {
                tmp->next = r_node;
                tmp = tmp->next;
                r_node = r_node->next;
                tmp->next = NULL;
                rs += 1;
            }
            l_node = r_node;
        }
        q->head = tmp_head.next;
    }
}