2019q1 Homework1 (lab0)

contributed by < yicheng11 >

開發環境

$ uname -a
Linux c44044064-Thinkpad 4.18.0-15-generic #16~18.04.1-Ubuntu SMP Thu Feb 7 14:06:04 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

作業要求

• 實做FIFO及LIFO queue，滿足以下功能

  • q_new：建立一個新的空 queue

  • q_free：把 queue 整個清除掉

  • q_insert_head：在 queue 的 head 新增新的元素

  • q_insert_tail：在 queue 的 tail 新增新的元素

  • q_remove_head：移除在 queue 的 head 的元素

  • q_size：計算 queue 中有多少元素

  • q_reverse：把 queue 反轉

    其中 q_insert_tail 與 q_size 的時間複雜度要求為

    $O(1)$

• 解釋自動評分系統運作原理還有提及 qtest 的行為和裡頭的技巧

實作

queue_t

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

為了使 q_size 與 q_insert_tail 的時間複雜度為

$O(1)$，利用 size 紀錄 queue 的大小，還有使用一指標指向 queue 的尾端

q_new

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 失敗的情況

q_free

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

循序 free value 再 free list_ele_t，時間複雜度是

$O(n)$

q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newh = malloc(sizeof(list_ele_t));

    if (!newh)
        return false;

    int len = strlen(s) + 1;
    char *ptr = malloc(len * sizeof(char));
    if (!ptr) {
        free(newh);
        return false;
    }
    memset(ptr, 0, len);
    strncpy(ptr, s, len - 1);
    newh->value = ptr;
    newh->next = q->head;
    if (q->head) {

        q->head = newh;
    } else {
        q->head = q->tail = newh;
    }
    q->size++;
    return true;
}

這邊使用 strncpy() 取代 strcpy() 防止 buffer overflow

q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newt = malloc(sizeof(list_ele_t));
    if (!newt)
        return false;
    int len = strlen(s) + 1;
    char *ptr = malloc(len * sizeof(char));
    if (!ptr) {
        free(newt);
        return false;
    }
    memset(ptr, 0, len);
    strncpy(ptr, s, len - 1);
    newt->value = ptr;
    newt->next = NULL;
    if (q->head) {
        q->tail->next = newt;
        q->tail = newt;
    } else {
        q->tail = q->head = newt;
    }
    q->size++;
    return true;
}

q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (!q || !q->size)
        return false;
    list_ele_t *tmp = q->head;
    if (sp) {
        memset(sp, '\0', bufsize);
        strncpy(sp, tmp->value, bufsize - 1);
    }
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size--;
    return true;
}

q_size

int q_size(queue_t *q)
{
    if (!q || !q->size)
        return 0;
    else
        return q->size;
}

因為在 queue_t 有以 size 紀錄 queue 的大小，所以可以直接回傳，時間複雜度是

$O(1)$

q_reverse

void q_reverse(queue_t *q)
{
    list_ele_t *r, *s;
    if (!q || !q->size)
        return;
    r = q->head->next;
    q->tail = q->head;
    q->head->next = NULL;
    for (; r != NULL; q->head = r, r = s) {
        s = r->next;
        r->next = q->head;
    }
}

把 queue 裡面的元素反轉

自動評分系統