# 2019q3 Homework2 (lab0)
contributed by < `YenHengLin` >
>作業系統:Ubuntu 18.04 LTS
>作業系統類型：64 位元
## [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 作業要求
### 回想 string 儲存方式
* c 語言儲存 string的方式 是用 char 去儲存的，如果要存長度為 $n$ 的 string 就必須要用 $n+1$ 個 char 去儲存。
* 儲存的方式為前面 $n$ 個 char 為典型的 ASCII =='== 型式(例: **'A'**)，而最後一個 char 則設成 `\0` (null terminator)

### 修改 queue_t structure
* 為了更好的做到 FIFO 操作，增加了 `list_ele_t *tail`
* 題目要求 $O(1)$ 時間算出 queue_t 裡的 element 個數，所以增加 `int size` 紀錄增加的 element
* code

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;

### 修改 q_new
* 設 `q->tail = NULL`讓 q_new 在 FIFO 的情況下也能判斷 queue_t 是 empty queue
* 設 `q->size = 0`，因為 empty queue 跟 NULL queue 一樣，size 都為 0
* 多寫一行程式碼判斷 malloc 失敗的情況，避免 malloc 失敗，程式卻還要求 q->head 存在
* code

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

### 完成 q_free
* 如果只 free(q) 的話，則會有好幾個物件遺失掉指著他的指標，而使得這些物件散落在記憶體空間裡，如果程式沒有完整的回收機制的話，程式會認為這些遺失的記憶是還有用處的，而不去動用他，久了造成電腦明明還有很多剩餘空間，可是記憶體卻滿了的現象
* 為了避免 memory leak，我們必須將 q->head 指向的東西一個個 free 掉，透過 head 移動來實現
* code

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    if (q == NULL) {
        return;
    }
    list_ele_t *temp;
    while (q->head != NULL) {
        temp = q->head;
        q->head = q->head->next;
        free(temp->value);
        free(temp);
    }
    free(q);
}

* 另外透過 valgrind 去檢驗是否有 memory leak
`$valgrind ./qtest`

cmd>new
cmd>new
q = []
cmd>it 1
cmd>it 1
q = [1]
cmd>it 2
cmd>it 2
q = [1 2]
cmd>free
cmd>free
q = NULL
cmd>quit
cmd>quit
Freeing queue

發現並無 memory leak,代表我們的 q_free 確實把不用的記憶體還給系統
### 完成 q_insert_head
* 如果 q 為 NULL 就代表 q 還沒被 new 出來，這時插入是錯的
* q 如果不為 NULL 就要判斷之後的 malloc 是否都成功，如果不成功就要回傳 NULL，而 value 為 NULL 的處理比較特別，由於 value 為 NULL 時,newh 這個變數已經有空間佔據了，必須要 free 掉他才能回傳 false，避免造成 memory leak
* value 的空間大小跟 s 一樣大，而每個 char 的值則使用 c 語言內建的函式 **strcpy**
* 由於是 LIFO 的形式，所以我們將新創的物件，插在 head 前面
* 插完後增加 q->size 的值，方便 q_size 的計算
* 為了讓操作順序為 ih 先在 it 會使得 it 操作不知道要將物件插在哪裡,所以寫入 q->tail,紀錄 it 操作插入的地方
* code

ool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    if (q == NULL) {
        return false;
    }
    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->head == NULL) {
        q->tail = newh;
    }

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

### 完成 q_insert_tail
* 前面的新增的方式跟 q_insert_head 一樣
* 插入的方式由於要實現 FIFO，所以我們要接在 head 之後，用 tail 去紀錄尾巴在哪裡，而 tail 儲存的方式隨著 queue 是否為空而給變
* 第一次插入時 queue 為空的，所以要將 head 指向第一個新建出來的物件，之後 head 指標就不動了，只改動 tail 指標
* 加完物件後，一樣要將 `q->size++` 以記錄現在有幾個 element 在 queue 裡面
* code

bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    if (q == NULL) {
        return false;
    }
    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->head == NULL) {
        q->head = newh;
        q->tail = newh;
    } else {
        q->tail->next = newh;
        q->tail = newh;
    }
    q->tail->next = NULL;
    q->size++;
    return true;

    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
}

### q_remove_head
* 判斷是否為 NULL queue 或是為 empty queue，如果是，那就不能移除 head
* 判斷移除的字串是否大於 bufsize，大於時比較麻煩，由於移除的字串空間超出了 sp 所配置的空間，所以要使用 strncpy 來指定要 copy 多少個字元
* **strcpy** 從 src 複製 n 個指定的字串到 dest 字串，有可能複製的這 n 個字串都無 `\0` (null terminator)，所以必須要在最後的位子，也就是 `sp[bufsize-1]` 設成 `\0`
* code

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (q == NULL || q->head == NULL) {
        return false;
    }
    if (sp != NULL) {
        // because sp could have string not match the sp size,so use strlen

        if (bufsize < strlen(q->head->value) + 1) {
            strncpy(sp, q->head->value, bufsize);
            sp[bufsize - 1] = 0;
        } else {
            strcpy(sp, q->head->value);
        }
    }
    list_ele_t *temp = q->head;
    q->head = q->head->next;
    free(temp->value);
    free(temp);
    --q->size;
    return true;
}

### 修改 q_size
* 判斷 q 是否為空如果為空就回傳 0
* 如果不為空就回傳 q->size
* code

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 == NULL) {
        return 0;
    }
    return q->size;
}

### 完成 q_reverse
* [參考資料](http://alrightchiu.github.io/SecondRound/linked-list-xin-zeng-zi-liao-shan-chu-zi-liao-fan-zhuan.html)
* 翻轉 linklist 指標要注意一點，修改指標 next 指向前面時，指向後面的鏈結就會跟著消失了，所以我們必須要使用 preceding 去記錄 next 目前指向誰，記錄下來後才能對 next 做更改，將他更改為我們用 prev 記錄下來的上一個物件
* 範例圖示
* 另外需要注要 q->tail 的指標要從尾巴指向開頭，所以要在還沒 reverse 前，先將 q->tail 指向 q->head

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (q == NULL || q->head == NULL) {
        return;
    }
    q->tail = q->head;
    list_ele_t *prev = NULL;
    list_ele_t *curr = q->head;
    list_ele_t *preceding = q->head->next;
    while (preceding != NULL) {
        curr->next = prev;
        prev = curr;
        curr = preceding;
        preceding = preceding->next;
    }
    curr->next = prev;
    q->head = curr;
}