contributed by < asas1asas200 >
jim12312321
q_size
的成本。list_del_init
會更加安全,尤其當該移除節點還要再次運用時。觀察 man malloc
中的 RETURN VALUE
裡面提到:
所以在一般情況下可以用 malloc()
的傳回值是否為 0
來判斷是否成功申請記憶體。
參照 The Linux Kernel API 中的用法,核心中的 list API 使用了 dummy node 的方式實作,所以第一個 head 節點宣告成 struct list_head
型態即可,一開始寫成了 element_t
多用了一些空間:
對於 free 操作特別需要注意的為 list_for_each_entry_safe
,根據註解的說明,在遍歷時若有刪除操作要使用此帶有 safe 後綴的巨集,將其展開後會發現其多了一個 safe 成員用來暫存 next
的位址,便可以放心移除當前疊代的元素。
因為整個操作包含了一些物件的資源申請與釋放,所以採用 goto + label 的方式實作,不過對於現階段的程式碼而言也僅僅是一兩行的差別。
字串複製的部份原本使用 strcpy
,後來被 cppcheck 提醒這一系列的函數( strcpy
、 strcat
、 strcmp
)都有著未檢查 buffer 的潛在問題: Common vulnerabilities guide for C programmers#strcpy 。
為了避免重複的程式碼,所以將 entry 移動到最後一個元素後呼叫 q_insert_head
,不確定這樣的寫法是否比較好。
此處根據描述實作了頭尾的移除,並且將其 value 根據要求複製給 sp 。
複雜度為 的長度計算,不過個人認為可以用 head 來存放長度資訊,用 的空間來換取原本需要 的時間是相當划算的。
疊代每個元素,並將上一個元素標記為 last
,如果 last
和當前的元素值一樣的話將 dup_flag
標記為 true
,並且刪除當前元素繼續下一次的疊代。
而當前元素若和 last
不一樣且 dup_flag
為 true
的話代表 last
是 重複的元素 ,並且已經是當前 list 中沒有一樣的了,所以從 list 中清除 last
並設定 dup_flag
為 false
繼續疊代。
而 dup_flag
的意義即是 last
是否為 重複的元素 。
跟 q_delete_dup 的做法類似,在每次疊代中一次刪除,一次插入,達成 swap 的效果,這題限制不能改變 value 稍微想了一下。
這邊不像 swap 的時候有特別說不能改 value ,所以只要交換 q_size / 2 次就可以 reverse 了,具體操作如下:
最一開始的情形
這時候 LR 做交換,注意到這邊交換的是他們的 value 而非真正在 linked-list 上做交換,所以 left 和 right 不會變:
然後將 left 往 next 的方向前進並將 right 往 prev 的方向:
再進行一次交換:
對於每個長度為 n 的 list ,只要交換 次即可得到反轉後的結果。
因為限制了 malloc()
的使用,所以使用 VLA 並將 list 當成 array 來實作 merge sort ,但此方法不是很好所以不多做說明。
改良紀錄 commit 59650e0 。
一開始因為不想去動到 list 元素的排列,想嘗試只更改 value 指向來完成排序,奈何 linked-list 無法隨機訪問,所以有其困難,在實作 swap 的時候突然發現 list_add
和 list_add_tail
可以用在此處便回來改良程式:
實作採用的是 merge sort 演算法,為了方便畫圖及簡潔的畫面所以下面流程皆用 Singly-Linked List 表達,考慮一般情況:
其中 L 、 R 、 M 分別代表左界、右界以及中間。
根據 merge sort 的規則,這時候分別對 、 做排序,會得到如下結果,用一樣的顏色代表該連續區塊保證已排序(後面會用到):
這時候設定兩個疊代用的指標分別指向 L 和 M :
比對 l_iter
和 r_iter
的值,這邊因為 1 < 3 所以將 1 先從 list 中移除再插進 3 的前面:
然後移動 r_iter
到原本的右邊,以這邊來說就是 2 的位址:
再做一次一樣的操作後會變成下圖:
此時 r_iter
會指向最右邊的下一個,這時候代表操作完成,看起來雖然只有把右半部做移動而已, l_iter
完全沒有移動,但是實際上他們早就是已排序的,所以到此就結束了,不用像陣列的時候做多餘的複製和寫入。
從這個案例可以看出其中一個邊界條件就是 r_iter != r->next
。
接下來看一個最簡單的例子:
在這個例子中,很明顯 l_iter
會一直往右跑,直到找到 3 ,也就是 r_iter
的位址,所以另一個邊界條件即為 l_iter != r_iter
。
在實作上只有一個要特別注意的地方:
傳入 merge_sort()
的 l
、 r
和在裡面計算的 mid
會因為移動元素的關係所以改變位址,目前的解決辦法是設定 l_safe
和 r_safe
在有需要的時候重新定位。