2019q1 Homework1 (lab0)

contributted by < chengWei1123 >

開發環境

$ uname -a
Linux wei-X550JX 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

作業要求

實作以下 LIFO FIFO Queue 之功能

• q_new

  • Create empty queue.
  • Return NULL if could not allocate space.

• q_free

  • Free ALL storage used by queue.
  • No effect if q is NULL.

• q_insert_head

  • Attempt to insert element at head 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.

• q_insert_tail

  • 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.

• q_remove_head

  • Attempt to remove element from head of queue.
  • Return true if successful.
  • Return false if queue is NULL or empty.
  • If sp is non-NULL and an element is removed, copy the removed string to sp
    (up to a maximum of bufsize-1 characters, plus a null terminator.)
  • The space used by the list element and the string should be freed.

• q_size

  • Return number of elements in queue.
  • Return 0 if q is NULL or empty

• q_reverse

  • 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.

• 詳細說明 :

  • 作業說明
  • C Programming Lab

實作

queue structure

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

為了讓 q_insert_tail 和 q_size 能有題目要求的

$O(1)$ 時間複雜度，所以要增加 tail
和 size 兩個feild

「時間複雜度」和「時間」是兩件事，請改善用語，工程人員說話要精準明確

jserv

q_new

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL)
        return q;
    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) {
        q_remove_head(q, NULL, 0);
    }
    free(q);
}

直接使用 q_remove_head 直到 queue 變空

q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    /* What should you do if the q is NULL? */
    if (q == NULL)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;

    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->value = malloc((strlen(s) + 1) * sizeof(char));
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);

    if (q->size == 0)
        q->tail = newh;

    newh->next = q->head;
    q->head = newh;
    q->size++;
    return true;
}

strlen 回傳長度不包含 '\0'，所以第13行中 strlen 後面要加1
此外我發現我分不太清楚 strcpy 和 strdup 之間的差別
參考 strcpy vs strdup 後，我的理解是 strdup 是 malloc + strcpy，也因為 strdup 有 hidden malloc，所以使用完字串後 progammer 特別容易忘記 free 掉此空間

q_insert_tail

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 */
    if (q == NULL)
        return false;
    list_ele_t *newt;
    newt = malloc(sizeof(list_ele_t));
    if (newt == NULL)
        return false;
    newt->value = malloc((strlen(s) + 1) * sizeof(char));
    if (newt->value == NULL) {
        free(newt);
        return false;
    }
    strcpy(newt->value, s);
    if (q->size == 0) {
        q->head = newt;
    } else {
        q->tail->next = newt;
    }
    q->tail = newt;
    newt->next = NULL;
    q->size++;
    return true;
}

q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head)
        return false;
    if (sp) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size--;
    return true;
}

我原本以為是如果 buffer 放不下被刪除的資料，就直接不放，但後來發現我理解錯題意了

q_size

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

記得考慮 q 為 NULL 的狀況

q_reverse

void q_reverse(queue_t *q)
{
    if (!q || q->size < 2)
        return;

    list_ele_t *front = NULL;
    list_ele_t *mid = q->head;
    list_ele_t *rear;
    while (mid) {
        rear = mid->next;
        mid->next = front;
        front = mid;
        mid = rear;
    }
    q->tail = q->head;
    q->head = front;
}

程式最後一行，我原本寫 q->head = mid;
讓我 debug 很久，最後才發現執行完 while loop 後 mid pointer 指到的是 NULL

自動評分系統運作的原理

待補

qtest 的行為和裡頭的技巧

待補