contributed by < Chialiang86
>
實作 queue
的介面設計(包含 queue.h
及 queue.c
),搭配 GNU/Linux 開發環境,及學習 Git 進行版本控制,同時也整合 Valgrind 動態程式分析工具,作精準的記憶體分析和除錯。
此外,也要求程式開發要養成良好的 coding style ,檢查程式碼和 C/C++ 原始程式碼的風格是否一致,並透過 Cppcheck 進行靜態程式碼檢查。
queue.c 僅提供介面 (interface) 但尚未有完整程式實作,需要由學員補完並逐步精進,包含以下:
q_new
: 建立新的「空」佇列;q_free
: 釋放佇列所佔用的記憶體;q_insert_head
: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);q_insert_tail
: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);q_remove_head
: 在佇列開頭 (head) 移去 (remove) 給定的元素。q_size
: 計算佇列中的元素數量。q_reverse
: 以反向順序重新排列鏈結串列,該函式不該配置或釋放任何鏈結串列元素,換言之,它只能重排已經存在的元素;q_sort
: 以遞增順序來排序鏈結串列的元素q_sort
分析 recursive v.s. non-recursive recursive 版本的差異tail
來指向 queue_t
的最後一個元素size
來紀錄 queue_t
中 linked list 所包含的元素個數NULL
list_ele_t
元素的細節(包含 pointer 的記憶體配置、記憶體配置失敗的處理)隱藏起來。q_insert_head
及 q_insert_tail
的程式碼專注處理插入新元素的細節。true
false
當佇列為 NULL
或 記憶體配置失敗。true
。NULL
當佇列為 NULL
或 記憶體配置失敗。q->tail
來操作,不需從 q->head
來走訪整個 queue 到末端再進行插入,故時間複雜度從 O(n) 變成 O(1)。while
來走訪整個 queue 來逐步釋放記憶體。sp != NULL
則要將 queue 前端 bufsize - 1
個字元複製到 sp
中,並在 sp
的末端加入空字元 \0
。q
或 q->head
為 NULL
會回傳 false
,其他狀況皆回傳 true
。q_remove_head
的參數 (parameter) 這樣設計是為了要確保 queue 前端的元素所指向的字串和參數中的 sp
所指向的字串一致才會進行刪除,但經過研究 make test
和 ./qtest
執行的狀況,發現測資不會故意將錯誤的字串刪除,例如 queue->head->value
所指向的字串為 "dog"
,測資不會故意刪除 "cat"
或其他非 "dog"
的字串。queue->head->value
複製給 sp
的字串經過檢查,發現和預期的字串不一致代表是 queue 在操作的過程中有誤(如 reverse 或 sort 的結果不如預期等)。q
或 q->head
為 NULL
則回傳 0
; 否則回傳 q->size
。q->size
始終記錄著 queue 裡面的元素個數,因此在 queue 非空時直接回傳即可,時間複雜度為 O(1) 。strcasecmp
函數來進行字串比對,將字串進行遞增排序。int strcasecmp(const char *s1, const char *s2);
strcasecmp is not in the C or C++ standard. It's defined by POSIX.1-2001 and 4.4BSD.
The strcasecmp() function shall compare, while ignoring differences in case, the string pointed to by s1 to the string pointed to by s2. The strncasecmp() function shall compare, while ignoring differences in case, not more than n bytes from the string pointed to by s1 to the string pointed to by s2.
In the POSIX locale, strcasecmp() and strncasecmp() shall behave as if the strings had been converted to lowercase and then a byte comparison performed. The results are unspecified in other locales.
Upon completion, strcasecmp() shall return an integer greater than, equal to, or less than 0, if the string pointed to by s1 is, ignoring case, greater than, equal to, or less than the string pointed to by s2, respectively.
Upon successful completion, strncasecmp() shall return an integer greater than, equal to, or less than 0, if the possibly null-terminated array pointed to by s1 is, ignoring case, greater than, equal to, or less than the possibly null-terminated array pointed to by s2, respectively.
s1
較大回傳大於零的值、反之小於零, s1
, s2
一樣大則回傳 0 。s1
長度為 n1
、字串 s2
長度為 n2
較 n1
長,若 s2
的前 n1
個 byte 都和 s1
一樣,則此時 s2
會被判定比 s1
大。still reachable
)ls
可以找到輸出檔 massif.out.PID(PID 會在執行後給定)