2020 第一週作業

--- title: 2020 第一週作業 tags: _核心設計 breaks: true --- # 2020q1 Homework1 (lab0) contributed by < `babysuse` > ## 作業描述 > 首先根據 CMU 的作業描述 - 如圖所示（pic） - 目標是一個儲存字串的 Singly Linked List - 並且要能區別出兩種特殊狀況 - NULL queue：Queue 為 NULL - empty queue：Queue 的 head field 為 NULL - 然後要實作出以下 functinos 和要求: - `q_new` - `q_free` - `q_insert_head` (LIFO discipline) - `q_insert_tail` (FIFO discipline) - `q_remove_head` - `q_size` - `q_reverse` (rearranging instead of re-allocating) <br> - 用 `malloc` 來配置空間儲存 linked list 中的 strings - 要求 `q_insert_tail` 以及 `q_size` 的複雜度為 $O(1)$ - 測試中將會超過 1,000,000 個 elements - \**其他要求參見 queue.c 和 queue.h 註解* \* - 成功編譯過後會產生 command line 測試程式 *qtest* - 也可以使用 /traces 中的各種測試指令 ```sh $ ./qtest -f traces/trace-eg.cmd ``` - 也有評分程式 ```sh $ ./driver.py ``` 或 ```sh $ make test ``` > 再根據本次作業的追加項目如下 - 修改 sorting 為 natural sort - 運用 Valgrind 排除 qtest 實作的記憶體錯誤 > 加分題 - 擴充 qtest 命令列功能 - 單行或多行編輯 - 歷史命令處理 - 命令自動補完 - 預設開啟 AddressSanitizer 同時滿足效能測試所需 - 指出現有程式的缺陷 ## 實作第一部份：CMU 作業要求（檔案中的 TODO 們） :::warning 程式的複雜度至少包含時間和空間的複雜度，行文應儘量明確聲明 :notes: jserv ::: - 首先是要讓 `q_insert_tail` 以及 `q_size` 的時間複雜度為 $O(1)$ - 就是很直觀的加上 `list_ele_t *tail` 以及 `size_t size` - 再來是處理 malloc 回傳 NULL 的狀況，有關 C 的 Error Handling - 首先 C 會將錯誤類別存入變數 errno （參見[總覽](http://www2.hs-fulda.de/~klingebiel/c-stdlib/sys.errno.h.htm)） - 可以使用 `void perror(const char *str)` 或是 `char *strerror(int errnum)` 取得錯誤訊息（以下等價） - ```perror("an error occurred");``` - ```printf("an error occurred: %s\n", strerror(errno));``` - 由於沒辦法取得其他使用到 heap 的 handler，因此沒辦法去釋放其他被使用的記憶體，所以我直接用 `exit(EXIT_FAILURE)` 退出程式？？？ > - 其餘就是 linked list 的實作，<s>從大一到現在已經做過無數次了，這裡就不再贅述</s>，附上 [github 連結](https://github.com/babysuse/lab0-c/blob/master/queue.c)。唯一不同點在於這次我儘量引入了 Linus 所謂的 taste，以及我在 [Clean Code](https://www.tenlong.com.tw/products/9789862017050) 中所理解到的 clean code。 > :::warning > 做了幾次不是關鍵，而是能否在其中獲得體悟，從細節做起，時時反思工程議題，是課程著重的要求 > :notes: jserv > :::