2020q1 Homework1 (lab0)

contributed by < chao0502 >

實驗環境

$ uname -a
Linux chao-Aspire-V5-591G 4.15.0-70-generic #79~16.04.1-Ubuntu SMP Tue Nov 12 14:01:10 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version 
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.12) 5.4.0 20160609

作業要求

詳細閱讀 C Programming Lab ，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。

​​​​編輯 queue.c & queue.h
​​​​q new: 新增一個 empty queue
​​​​q free: 將 queue 用到的空間都釋放掉
​​​​q insert head: 插入一個新的 node 在 queue 的head(LIFO)
​​​​q insert tail: 插入一個新的 node 在 queue 的head(FIFO)
​​​​q remove head: 將 queue 的 head 移除
​​​​q size: 回傳 queue 的長度
​​​​q sort: 將 queue 由小到大排序

作業說明中，已規範共筆書寫的慣例：中英文字元間以半形空白字元 區隔，請修正。

jserv

實作流程

1. 先從老師的 github 將所需檔案 fork 到自己的帳號
2. 使用 git clone 將檔案下載到本地端
   ​​​​$ git clone https://github.com/自己的帳號/自己的repository名稱
   

3. 嘗試 make，得到以下結果
   ​​​​$ make
   ​​​​CC	qtest.o
   ​​​​CC	report.o
   ​​​​CC	console.o
   ​​​​CC	harness.o
   ​​​​CC	queue.o
   ​​​​CC	random.o
   ​​​​CC	dudect/constant.o
   ​​​​CC	dudect/fixture.o
   ​​​​CC	dudect/ttest.o
   ​​​​LD	qtest
   

4. 開始修改作業程式碼

• queue.h
  由於要使 q_insert_tail 以及 q_size 可在O(1)時間複雜度完成
  因此在queue_t中新增兩個變數

    typedef struct {
        list_ele_t *head; /* Linked list of elements */
        list_ele_t *tail;
        int size;
    } queue_t;

• q_new
  當 malloc fail 時,會給予原本要賦予記憶體空間的變數 NULL 值
  因此在使用 queue_t *q 的 q 之前要先判斷它是否是 NULL

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

• q_free
  先用 if(q) 來確定 queue 是存在的,避免錯誤的使用
  之後再一一 free 掉 queue 中的 node

    void q_free(queue_t *q)
    {
        /* TODO: How about freeing the list elements and the strings? */
        /* Free queue structure */
        if (q) {
            whlie (q->head) {
                if (q->head->next) {
                    list_ele_t *tem;
                    tem = q->head;
                    free(q->head->value);
                    q->head = q->head->next;
                    free(tem);
                } else {
                    free(q->head->value);
                    free(q->head);
                }
            }
            free(q);
        }
    }

• q_insert_head
• q_insert_tail
• q_remove_head
• q_size
• q_reverse
• q_sort