---
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 中的各種測試指令

    $ ./qtest -f traces/trace-eg.cmd

- 也有評分程式

    $ ./driver.py

或

    $ 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
> :::