2019q1 Homework1 (lab0)

contributed by < st9540808 >

實驗環境

$ uname -a
Linux DESKTOP-GPGA00G 4.4.0-17763-Microsoft #253-Microsoft Mon Dec 31 17:49:00 PST 2018 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 8.1.0-1ubuntu3~16.04.york0) 8.1.0

作業要求

修改 queue.h queue.c 來實作一個支援 FIFO 和 LIFO 的 queue

q_new() : 建立一個空的 queue
q_free() : 釋放 queue 的所有記憶體資源
q_insert_head() : 在 queue 的頭插入一個元素 (LIFO)
q insert tail() : 在 queue 的尾插入一個元素 (FIFO)
q_remove_head() : 在 queue 的頭移除一個元素
q_size() : 回傳 queue 的元素個數
q_reverse() : 反轉 queue 中元素的順序，必須是 in-place，不能呼叫 malloc() 和 free()

Note:

value 必須使用動態分配
q_insert_tail() 和 q_size() 的時間複雜度必須是
$O (1)$

實作

`struct queue_t`

queue_t 裡新增兩個 field : tail 和 size 以達成

O (1)

的時間複雜度。

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    size_t size;
    /*
    You will need to add more fields to this structure
    to efficiently implement q_size and q_insert_tail
    */
} queue_t;

`q_new()`

建立一個空的 queue，同時也需要檢查 malloc 是否成功。

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (!q)
        return 0;

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

`q_free()`

釋放傳入 queue 所有元素的記憶體資源，value 因為是動態分配的所以也必須同時釋放。

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    list_ele_t *curr, *temp;

    if (!q)
        return;

    curr = q->head;
    while (curr) {
        temp = curr;
        curr = curr->next;
        free(temp->value);
        free(temp);
    }

    free(q);
}

`q_insert_head()`

在 queue 的頭插入一個元素，這裡也要檢查 malloc 是否成功。但在用 qtest 在評分時 trace-11-malloc 一直回傳 Attempt to free NULL，這部分一直沒辦法拿分，事實上根據 cppreference.com 對 free() 的描述:

If ptr is a null pointer, the function does nothing.

一般在實作如果傳入 NULL 是沒問題的，這裡 q_insert_head() 的實作因應這項評分而修改。

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    char *new_value;

    /* What should you do if the q is NULL? */
    if (!q)
        return false;

    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    new_value = strdup(s);
    if (!new_value) {
        free(newh);
        return false;
    }

    newh->value = new_value;
    newh->next = q->head;
    q->head = newh;
    if (q->size == 0)
        q->tail = newh;
    q->size++;

    return true;
}

`q_insert_tail()`

在 queue 的尾插入一個元素，需要區別 queue 的大小是 0 或大於 0 兩種情況。

bool q_insert_tail(queue_t *q, char *s)
{
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    list_ele_t *newh;
    char *new_value;

    if (!q)
        return false;

    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    new_value = strdup(s);
    if (!new_value) {
        free(newh);
        return false;
    }

    newh->value = new_value;
    newh->next = NULL;
    if (q->size == 0) {
        q->head = newh;
        q->tail = newh;
    } else {
        q->tail->next = newh;
        q->tail = newh;
    }
    q->size++;

    return true;
}

`q_remove_head`

從 queue 的頭移除一個元素，並且複製 bufsize - 1 個字元到 sp ，最後一個字元必須是空字元。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    list_ele_t *elem;

    if (!q || !q->head)
        return false;

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

    free(elem->value);
    free(elem);
    q->size--;
    return true;
}

`q_size()`

回傳 queue 的大小。

int q_size(queue_t *q)
{
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    if (!q)
        return 0;
    return q->size;
}

`q_reverse()`

反轉一個 queue ，一開始需要檢查 queue 是否為 NULL 且有 2 個以上個元素，再利用三個指標 prev curr next 來走訪 queue ，避免因為方向對調後存取不到剩餘的元素。
參考 : Linked List: 新增資料、刪除資料、反轉

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    list_ele_t *prev, *curr, *next;

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

    prev = NULL;
    curr = q->head;
    next = q->head->next;

    while (next) {
        curr->next = prev;
        prev = curr;
        curr = next;
        next = next->next;
    }

    curr->next = prev;
    q->tail = q->head;
    q->head = curr;
}