2019q1 Homework1 (lab0)

contributed by < shihyuuuuuuu >

題目要求

預期目標

• 英文閱讀
• C 語言程式設計基礎
• 學習使用 Git 與 GitHub
• 學習效能分析
• 研究自動測試機制

作業概述

本作業的目的主要是複習與練習 C 語言的基本技巧，包括以下幾項：

• Explicit memory management, as required in C.(記憶體管理)
• Creating and manipulating pointer-based data structures.(操作指標相關的資料結構)
• Working with strings.(字串操作練習)
• Enhancing the performance of key operations by storing redundant information in data structures.(透過在結構中儲存一些額外資料來加速一些操作的效能)
• Implementing robust code that operates correctly with invalid arguments, including NULL pointers.(學著處理非法輸入的參數，使程式不致於出錯)

實作內容

實作一個queue，並且可以支援 last-in, first-out(LIFO) 和 first-in, first-out(FIFO)，
使用 singly-linked list 來完成。
要完成以下各函式：

• q_new: 產生一個新的、空的 queue 。
• q_free: 釋放一個 queue 使用的空間。
• q_insert_head: 從 queue 的 head 插入一個新元素 ( LIFO )。
• q_insert_tail: 從 queue 的 tail 插入一個新元素 ( FIFO )。
• q_remove_head: 從 queue 的 head 移除一個元素。
• q_size: 計算 queue 中的元素個數。
• q_reverse: 反轉 queue 。(不能配置獲釋放任何元素)

開發環境

$ uname -a
Linux DESKTOP-CNBJG9V 4.4.0-17134-Microsoft #523-Microsoft Mon Dec 31 17:49:00 PST 2018 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

實作過程

q_new

初始化 queue 的記憶體空間與變數，並回傳指向該 queue 的指標。
當 malloc 失敗時，回傳 NULL 。

/*
  Create empty queue.
  Return NULL if could not allocate space.
*/
queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* If malloc return Null, return NULL. */
    if (!q)
        return NULL;
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

q_free

從 queue 的 head 到 tail 依序釋放每個 element 的記憶體空間。
除了釋放每個list_ele_t的空間外，也要記得釋放其所存的字串空間。

/* Free all storage used by queue */
void q_free(queue_t *q)
{
    if (!q)
        return;
    if (!(q->head)) {
        free(q);
        return;
    }

    list_ele_t *next_p;
    list_ele_t *next_next_p;
    next_p = q->head;

    /* Free the queue elements one by on from head to tail. */
    while (next_p) {
        next_next_p = next_p->next;
        free(next_p->value);
        free(next_p);
        next_p = next_next_p;
    }
    free(q);
}

q_insert_head

從 queue 的起始位置插入新的 element。
需特別注意無法配置空間或 queue 為 NULL 的情形。

/*
  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.
 */
bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* If queue is Null or fail to malloc, return false. */
    if (!q) {
        return false;
    }
    if (!(newh = malloc(sizeof(list_ele_t)))) {
        return false;
    }
    /* Allocate space for the string and copy it. */
    if (!(newh->value = malloc(sizeof(char) * (strlen(s) + 1)))) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);

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

q_insert_tail

從 queue 的最末位置插入新的 element。
需特別注意無法配置空間或 queue 為 NULL 的情形。

遇到的問題：一開始沒有把最尾端的指標設為NULL，導致測試程式找不到尾端。
原本認為 C 語言的指標如果沒有初始化 default 是 NULL ，因此沒有特別初始化。
後來在這份裡面看到："To initialize a pointer to null or to assign the null value to an existing pointer, a null pointer constant (NULL, or any other integer constant with the value zero) may be used. static initialization also initializes pointers to their null values."

/*
  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.
 */
bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newt;

    if (!q) {
        return false;
    }
    if (!(newt = malloc(sizeof(list_ele_t)))) {
        return false;
    }
    /* Allocate space for the string and copy it. */
    if (!(newt->value = malloc(sizeof(char) * (strlen(s) + 1)))) {
        free(newt);
        return false;
    }
    strcpy(newt->value, s);
    newt->next = NULL;
    q->size++;
    q->tail->next = newt;
    q->tail = newt;
    return true;
}

q_remove_head

移除 queue 的第一個 element ，並將q->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.)
*/
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    list_ele_t *remove_ele;

    /* If queue is NULL or queue is empty, return false. */
    if (!q || !q_size(q)) {
        return false;
    }

    remove_ele = q->head;
    if (sp) {
        strncpy(sp, remove_ele->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    q->size--;
    q->head = q->head->next;
    free(remove_ele->value);
    free(remove_ele);
    return true;
}

q_size

透過 queue 的其中一個變數 size 來存放當前 queue 的元素個數。

/*
  Return number of elements in queue.
  Return 0 if q is NULL or empty
 */
int q_size(queue_t *q)
{
    if (!q)
        return 0;
    return q->size;
}

q_reverse

透過一個一個將 element 的指標反轉，來實現整個 queue 的反轉，
並且不需配置或釋放任何空間

/*
  Reverse elements in queue
  No effect if q is NULL or empty
 */
void q_reverse(queue_t *q)
{
    if (!q || q_size(q) == 0 || q_size(q) == 1)
        return;
    
    list_ele_t *prev;
    list_ele_t *node;
    list_ele_t *next;

    prev = q->head;
    node = prev->next;
    q->tail = prev;
    prev->next = NULL;
    /* Iterate the list. If reach the last node, let q->head point to it. */
    while (node) {
        next = node->next;
        node->next = prev;
        prev = node;
        node = next;
    }
    q->head = prev;
}

上面程式碼有修改過, 下為原本的程式碼。
主要修改為重新命名冗餘的變數名 ，以及將不必要的 if 去掉。

    list_ele_t *prev;
    list_ele_t *next;
    list_ele_t *next_next;

    q->tail = q->head;
    prev = q->head;
    next = q->head->next;
    q->head->next = NULL;
    while (1) {
        next_next = next->next;
        next->next = prev;
        prev = next;
        next = next_next;
        if (next == NULL) {
            q->head = prev;
            break;
        }
    }

自動評分系統運作的原理

qtest 的行為與技巧