# 2019q1 Homework1 (lab0) contributed by < `TWPLrh` > ## 系統環境 ``` Linux shihruhung-pc 4.18.0-15-generic #16-Ubuntu SMP Thu Feb 7 10:56:39 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux gcc (Ubuntu 8.2.0-7ubuntu1) 8.2.0 ``` ## 作業要求 完成 Queue 程式碼 - `struct queue_t` - 增加tail和size已達到O(1)。 ```cpp=1 typedef struct { list_ele_t *head; /* Linked list of elements */ list_ele_t *tail; int size; } queue_t; ``` - `q_new` - 新建 Queue ``` cpp=1 queue_t *q_new() { queue_t *q = malloc(sizeof(queue_t)); if (!q) return NULL; q->size = 0; q->head = q->tail = NULL; return q; } ``` 照著註解去做，如果沒分配到的話要return NULL，如果成功，就必須設定初始值之後回傳。 - `q_free` - 釋放 Queue ```cpp=1 void q_free(queue_t *q) { if (!q) return; list_ele_t *prev; while (q->head) { prev = q->head; q->head = q->head->next; if (prev->value) free(prev->value); free(prev); } free(q); } ``` 當q->head不是null，就將q->head移到next，並將prev的value和prev釋放。 - `q_insert_head` - 插入 Queue ```cpp=1 bool q_insert_head(queue_t *q, char *s) { if (!q) return false; list_ele_t *newh; newh = malloc(sizeof(list_ele_t)); if (!newh) return false; newh->value = malloc(strlen(s) + 1); if (!newh->value) { free(newh); return false; } newh->value = strcpy(newh->value, s); q->size += 1; if (q->size == 1) { q->head = q->tail = newh; q->head->next = NULL; } else { newh->next = q->head; q->head = newh; } return true; } ``` 這裡的重點我認為是在`Size=1`時如果不將newh->next設成`null`，在`make test`時就會說錯誤，這也讓我意識到，C在`malloc`後並不會將所有初值都弄好，需要用`memset`去清空或是每個property依次去設定。 - `q_insert_tail` - 插入 Queue 尾端 ```cpp=1 bool q_insert_tail(queue_t *q, char *s) { if (!q) return false; list_ele_t *newh; newh = malloc(sizeof(list_ele_t)); if (!newh) return false; newh->value = malloc(strlen(s) + 1); if (!newh->value) { free(newh); return false; } newh->value = strcpy(newh->value, s); q->size += 1; newh->next = NULL; if (q->size == 1) q->head = q->tail = newh; else { q->tail->next = newh; q->tail = newh; } return true; } ``` 和`q_insert_head`差不多，不一樣的地方在`line 20`之後，`q->tail->next`一定是`null`所以可以不用包在`if`裡面，`else`的話則先把`q->tail->next`設爲`newh`，再把`q->tail`設爲`newh`這是和`q_insert_head`不同的地方。 - `q_remove_head` - 移除 Queue Head ```cpp=1 bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { /* You need to fix up this code. */ if (!q || !q->head || q->size == 0) return false; if (sp) { strncpy(sp, q->head->value, bufsize - 1); sp[bufsize - 1] = '\0'; } list_ele_t *next = q->head->next; q->size -= 1; if (q->head->value) free(q->head->value); free(q->head); if (q->size == 0) q->head = q->tail = NULL; else q->head = next; return true; } ``` 照著註解要求，先把會false的情況寫在前面，之後就代表這個Queue是可以被`remove_head`，再確認sp是否`non-null`，如果是，就複製過去，並把bufsize-1設成`'\0'`，再做一些property的修改即可。 - `q_size` - 回傳 Queue Size ```cpp=1 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; } ``` 直接回傳Queue的size，如果null，回傳0 - `q_reverse` - 前後翻轉 Queue 的順序 ```cpp=1 void q_reverse(queue_t *q) { /* You need to write the code for this function */ if (q && q->size != 0) { q->tail = q->head; list_ele_t *prev = NULL, *next; while (q->head) { next = prev; prev = q->head; q->head = q->head->next; prev->next = next; } q->head = prev; } } ``` 翻轉就只是簡單的改變list方向而已，方法如code所示，先把`q->tail`設爲`q->head` ，`loop`裡面就是將list前後串接改變，第一次是`null`，最後因為`q->head`已經指到不知道什麼地方，所以把他指回`prev` ## 自動評分系統 `Usage : make test` #### Tracing 過程 - `makefile` -> `qtest.c` -> `script/driver.py` -> `traces/` #### makefile - `makefile` 中有 `test`，當在terminal輸入 `make test`時即會呼叫`test`下的`scripts/driver.py`來協助評分和輸出。 ```=0 test: qtest scripts/driver.py scripts/driver.py ``` #### qtest.c - `qtest.c` 的 `console_init()`，把測試的function都加入且綁定到cmd上，綁定的function都有各種條件來測試記憶體是否釋放以及邏輯是否造成運行上的錯誤。錯誤會呼叫`report()`來印出那裡有錯及錯誤類別。 ```cpp=0 static void console_init(){...} ``` #### script/driver.py - `script/driver.py` 有 `class Tracer` 目的在執行15種trace方法，當每個方法都run過之後會印出總分。執行每一種執行方法都會呼叫`trace\`目錄下的`*.cmd`，並利用`subprocess.call()`執行`qtest`下的測試函式。 #### traces/ - `trace/` 下的檔案都是執行測試的腳本，對應的就是`qtest.c`下`console_init()`所加入cmd的函式。