contributed by < stanleyuan
>
作業說明有特別提到程式碼一致性的重要,要求使用 clang format 來檢查程式法風格,老師有說一句話滿重要的「工程師是會溝通的」。最近也是滿有感的,常常是今天的我看不懂昨天的我的程式碼,明天的我可能也是看不懂今天的我的程式碼。推薦 vim-autoformat 可以一鍵使用系統中的 formatting program。另外還有 syntastic 除了語法檢查之外,也可以使用系統中的 coding style program 來檢查 coding style。
完成以下的 oprations:
q new: Create a new, empty queue.
q free: Free all storage used by a queue.
q insert head: Attempt to insert a new element at the head of the queue (LIFO discipline).
q insert tail: Attempt to insert a new element at the tail of the queue (FIFO discipline).
q remove head: Attempt to remove the element at the head of the queue.
q size: Compute the number of elements in the queue
另外也要求:
q_insert_tail and q_size require that implementations operate in time O(1).
由於題目要求 q_insert_tail and q_size 的 時間複雜度都是 O(1),勢必在 queue_t 中要紀錄 tail node 的位置還有 queue 的大小。需要加上一個 tail 的 pointer 還有整數 size。
新 queue_t:
舊 q_new:
可以看到註解寫到要考慮如果 malloc return NULL,哪些情況下 malloc 會 return NULL呢?
RETURN VALUE
The malloc() and calloc() functions return a pointer to the allocated memory, which is suitably aligned for any built-in type. On error, these functions return NULL. NULL may also be returned by a successful call to malloc() with a size of zero, or by a successful call to calloc() with nmemb or size equal to zero.
有錯誤或是 size 為零的時候便會回傳NULL,所以將程式修改為:
因為已經在 queue_t 裡加上 tail 和 size,也要記得初始化。
舊 q_insert_head:
在這裡有 3 種情況要考慮:
會變成:
q->size 要記得加 1
舊 q_remove_head:
要判斷有沒有 q, q->head, sp
但一直出錯,後來才發現忘記了q->tail,如果是移除掉最後一個 node 的話:
要記得 free 該 node 的 value 還有 node,q->size 要減一。
舊的 q_size
因為在初始化、新增、刪除都有對 q-?size 做紀錄,如果 q 存在的話,只需回傳 q->size:
舊的 q_insert_tail:
這邊要注意的是要求 O(1),所以要從 q->tail 下手
test 過了,但發現我在處理 q->tail 的時候好像怪怪的,如果一開始沒有 nodes,q->tail 就會等於 NULL,那 q->tail->next = tmp
會指到哪裡?
但 test 過了(?
最後我改成:
才有正確的檢查兩種 cases,測試也過了。
利用 counter 先紀錄 head node,將 head 往前後再把 counter 所指到的 node free 掉。
這個比較複雜,要將所有 node 的 next pointer 轉向,例如:
會變成:
想法是要用兩個 pointer 來紀錄連續兩個 node 並且變更指標所指向的 node:
knowThyself
linux
c
linkList
w1