2019q1 Homework1(lab0)

contributed by < 110805 >

實驗環境

$ uname -a
Linux bang-HP-Spectre-x360-Convertible-13-w0XX 4.15.0-45-generic #48~16.04.1-Ubuntu SMP Tue Jan 29 18:03:48 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0

作業要求

本次作業是圍繞在實作 queue 上，且此 queue 是能夠支援 LIFO 及 FIFO 的。

題目要求以下 function 的實作：

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 中元素的順序，且此 function 不能 allocate 或是 free 掉任何元素

特別要求：

關於每個 function 的特別要求可參照 queue.c 及 queue.h 中的 comments
q_insert_tail() 及 q_size() 這兩個 function 之 time complexity 必須是
$O (1)$

實作

queue.h

struct queue_t
為了能夠讓 q_insert_tail() 及 q_size() 這兩個 function 能夠在

O (1)

的時間完成，在 struct queue_t 中增加以下兩個 field： list_ele_t *tail int size

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

queue.c

q_new()
建立一個空的 queue ，若無法 allocate 出指定大小的空間，則回傳 NULL。

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if(q){
      q->head = NULL;
      q->tail = NULL;
      q->size = 0;
    }
    return q;
}

q_free()
利用 q->head 為起點，並透過 next 沿著 queue 去 free elements ，在 free 掉該 element 之前，要記得先 free 掉該 element 之 value (value is a string)。

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    if(!q)
      return;

    list_ele_t *current;
    current=q->head;
    while (current){
      list_ele_t *temp;
      temp=current;
      current=current->next;
      free(temp->value);
      free(temp);
    }
    free(q);
    return;
}

q_insert_head()
在前端插入一個元素。題目要求在 copy 之前必須先 allocate space to string ，更重要的是要檢查 malloc 是否有成功，否則在 trace-11 中出現 malloc 失敗的情形時會無法處理。

bool q_insert_head(queue_t *q, char *s)
{
    /* What should you do if the q is NULL? */
    if (!q)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    /* Don't forget to allocate space for the string and copy it */
    newh->value = malloc(strlen(s) + 1);
    /* What if either call to malloc returns NULL? */
    if (!newh->value) {
        free(newh);
        return false;
    }
    memcpy(newh->value, s, strlen(s) + 1);
    newh->next = q->head;
    q->head = newh;
    q->size++;
    if (q->size == 1)
        q->tail = q->head;
    return true;
}

q_insert_tail()
插入一個元素到尾端。透過新增的 field tail，要插入一個元素到 queue 的尾端就不用從 head 開始走過整個 queue ，而是可以像 insert head 一樣直接將元素插入 queue 的尾端。

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

q_remove_head()
移除 queue 的前端元素，且在移除前須先將 string 的內容複製到 sp 中。此處採用 strncpy 是為了防止 buffer overflow 的問題產生。

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

q_size()
回傳 queue 中的元素個數。透過新增的 field 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()
利用三個指標來實作 reverse function ，每次進入迴圈就會將 cur->next 指向前個 node ，並讓三個指標往下個節點前進。

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (!q || q->size <= 1)
        return;
    list_ele_t *pre, *cur, *suc;
    pre = NULL;
    cur = q->head;
    suc = cur->next;
    while (suc) {
        cur->next = pre;
        pre = cur;
        cur = suc;
        suc = suc->next;
    }
    cur->next = pre;
    q->tail = q->head;
    q->head = cur;
}

解釋自動評分系統運作的原理

提及 qtest 的行為和裡頭的技巧

參考資料

Linked List: 新增資料、刪除資料、反轉