contributed by <hsiehong
>
進階電腦系統理論與實作
實做queue.c以下功能
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
: 「進階電腦系統理論與實作」課程所新增,以遞增順序來排序鏈結串列的元素,可參閱 Linked List Sort 得知實作手法;q_new
NULL
pointerq_free
q_insert_head
若 queue is NULL
, 無法新增,回傳 NULL
, 若 queue is empty , 更新 q->head
, q->tail
, q->size
newh->value
要注意是新增 strlen(s) + 1
的大小,要保留 \0
的空間
依據 CERN Common vulnerabilities guide for C programmers 建議而移除 strcpy 等不安全的函式 , 這裡使用strncpy()
line20 原本是要處理 q->size == 0 的情況,後來覺得讀性不是很好,所以改成下面
不懂 line 15,為什麼不是 free(newh->value)
, 測資會過不了
q_insert_tail
q_insert_head
,換湯不換藥q_remove_head
q->size
- 1*sp
q_size
q_reverse
NULL
或 empty 不用動作q_sort
依據上面程式碼第一次跑完的成績,有排序的部份都沒過
--- TOTAL 71/100
改成 merge sort,也是參考上篇文章作法
ZhuMo
同學的,使用到 pointer to pointerq->tail
--- TOTAL 94/100
執行 make valgrind
結果:--- TOTAL 94/100
問題在 test06
錯誤訊息如下
truncated strings
,直覺告訴我是 remove head 的部份出問題了,回去看了一次程式碼如下,還有 spec ,發現是字串結尾沒有忘記加上 null terminator
修改如下
test06過了,但換 test09 錯誤如下
原來沒注意到 sp
也有可能是 NULL
,判斷條件補上
這樣就沒問題了
$ valgrind --tool=massif ./qtest
利用第 16 筆測資來做範例,測試腳本如下
memory heap consumption
的使用量是隨著 item 的數目升高的,並且可以看到每次 free 完 queue 記憶體幾乎都會被釋放,但有個問題是第一次釋放完跟第二次釋放完 queue 記憶體並不是回到相同的狀態,這部份還不知道怎麼回事。而程式結束時 memory heap consumption
也隨著歸零