sysprog2018
contributed by <goho302jo03
>
請持續更新進度!!
–課程助教
請補上你的實驗環境
課程助教
以上這段程式碼可以分成兩個區塊來看
head
這個指標指向了queue最開始的位置,在實作 insert_head 以及 move_head 的時候可以有 O(1) 的時間複雜度。
tail
在實作 insert_tail 的時候遇到一個限制是必須在時間複雜度為 O(1) 的情況下完成,因此在 queue struct 裡面新增了這個指標指向了 queue 的最尾端,而在 queue 是空的時, head 跟 tail 都會是NULL。
size
在實作 q_size 時,也是有個限制是必須在時間複雜度 O(1) 下完成,因此加了一個 size 的變數,初始值為 0,會在每次插入節點時 +1,並在刪除節點時 -1,在呼叫 q_size() 時,若 queue 不是 NULL 的話就回傳 size 這個變數的值,因此能在常數時間內完成。
一開始先試著 alloc 大小為 queue_t 的記憶體,如果 alloc 失敗的話就直接回傳 NULL 表示無法成功創建 queue。如果 alloc 成功的話,因為這個 queue 還是空的,所以就將 queue 的 tail 以及 head 設為 NULL,並將 size 的值設為 0。
首先先檢查傳入的 q 是否為 NULL,如果是的話就不做任何事。必須依序將每個 node 所分配到的空間 free 掉,一直到每個 node 都成功 free 後,最後再 free(q)。
首先檢查 q 是否為 NULL,是的話就直接 return false,接著宣告一個型態為 list_ele_t 的 node 並且嘗試 alloc 一段記憶體位址給它,如果失敗的話也是 return false,接著利用 strdup() 這個函式宣告一段記憶體位址給這個 node 的 value,strdup() 成功的話會回傳一個地址,失敗的話則回傳 NULL,若回傳值為 NULL 則先 free 先前 alloc 給 node 的記憶體,再 return false。
strdup:會自動 alloc 記憶體給目的的指標,並且把要複製的內容複製到該指標中
strcpy:目的指標必須是一個已經分配記憶體的位址
一開始檢查 queue 是否為 NULL,是的話就回傳 0,不是的話就回傳 queue 的 size,如此一來可以達到 O(1) 的時間複雜度。
首先檢查 queue 是否為 NULL,是的話就不做任何事。接著參考 linklist reverse 實作,唯一需要注意的就是 head 以及 tail 兩個指標必須對調。
queue 的實作到目前為止在 make test
下,拿到了 63 分,除了需要用到 q_remove_head 的 trace 外,其他的 trace 都可以順利通過。
首先檢查 q 是否為 NULL,以及 q_size 是否為 0,這兩種情況下都沒辦法順利的 remove head,因此直接 return false。接著計算在有限的 bufsize 中可以存下多少個 char,宣告一個 tmp 來暫時存放要 remove 掉的那個 node,並且重新 assign head 的位址、size - 1。
接著因為 bufsize 的限制,因此這裡使用了 memcpy 來指定要分配的 memory 大小為何,並將 sp 的最後一個字元設為 null terminator。存取完 value 後就 free 掉 tmp,並且檢查剩餘的 queue size,是否為 0,是的話就把 tail 指向的位址也清空。
在完成了 remove head 的實作後,測試分數成功來到 100/100