contributed by < nickyanggg
>
linux2020
依照作業說明完成 queue.c & queue.h 二個檔案,主要功能如下:
q_new
建立新的 empty queueq_free
釋放 queue 所用到的空間q_insert_head
插入新的 element 至 queue 的開頭q_insert_tail
插入新的 element 至 queue 的尾端q_remove_head
刪除 queue 的開頭的 elementq_size
計算 queue 中的 element 數量q_reverse
將 queue 中的 element 依反向順序排列q_sort
將queue 中的 element 依遞增順序排列由於 q_insert_tail
、q_size
皆要求複雜度 ,因此將 queue_t
修改如下:
如此,當實作 q_insert_tail
、q_size
時,可以不用重頭 traverse 一遍,前者可以直接利用 tail
去做串接,而後者則是可以直接回傳 size
的值。
q_new
q_free
q_insert_head
value
失敗時,要回頭去 free 前面 malloc 給新進 element 的空間。head
、tail
、size
。q_insert_tail
q_insert_head
的注意事項。q_remove_head
size
是否為 0。sp
存在,copy 欲刪的 element 的 value 進去,記得在最後面補上結束字元 '\0'
,詳情請參考 strncpy。head
、tail
、size
。q_size
q_reverse
size <= 1
的狀況。curr
、prev
、temp
來把 queue 中所有的 elements 逆向接起來。head
、tail
的值調換。q_sort
size <= 1
的狀況。merge_sort
。tail
的值。merge_sort
merge_sort
left
都 assign 成 head
,而 right
則是 head->next
的話,也就是左半段的 queue 只有一個 element,而右半段的 queue 則是剩下的所有 element,這樣子的複雜度仍為 ,因此下面會介紹將 left
、right
平均分配的方式。left
、right
前者每次跳一個 element,後者每次跳二個 element,當 right 到 queue 的尾端時,left
所指向的 element 剛好位於 queue 的中間,接著再將 right
assign 成 left->next
( 也就是右邊半段的頭 ),再把 left->next
assign 成 NULL
( 也就是斷開成二個 queue ),最後再把 left
assign 成 head
即可,此時 left
、right
各代表著左半段的 head
以及右半段的 head
。merge
來把二段已經 sort 好的 queue 給 merge 起來。merge
merge
的時候,不可利用遞迴的方式,不然會發生 stack overflow
導致 segmentation fault
。利用 make test
觀看結果