# 2019q1 Homework1(lab0) contributed by < `110805` > ## 實驗環境 ```shell $ 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` ```clike 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。 ```clike 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)。 ```clike 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 失敗的情形時會無法處理。 ```clike 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 的尾端。 ```clike 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 的問題產生。 ```clike 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 後才能算出。 ```clike 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 ， 並讓三個指標往下個節點前進。 ```clike 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: 新增資料、刪除資料、反轉](http://alrightchiu.github.io/SecondRound/linked-list-xin-zeng-zi-liao-shan-chu-zi-liao-fan-zhuan.html)