contributed by < LindaTing0106
>
此函式目的在於找到串列的尾端,故在 *left
和 (*left)->next
不等於 null 的情況下,
left
應該要等於 &(*left)->next
,也就是 *left
下一個節點的地址。
此函式是在計算整個串列的長度,所以 while
中只需要判斷 *left
當下的節點是否為 null ,如有指向節點,則可以持續往下一個節點,並計算長度。
則 left
= &(*left)->next
。
此處 CCCC
填入 p->next
,因為此函式需要去遍歷串列的每個節點,並根據他們大於或是小於 pivot 的值,決定應該插入 right
或是 left
。
原本想法是因為 begin 和 end 儲存一段串列的頭與尾,像是前面的
所以 DDDD
= list_tail(left)
, EEEE
= list_tail(right)
。
後來發現是傳進去的型態問題, node_t *list_tail(node_t **left)
傳入的型態應該為 pointer of pointer of node_t ,故將答案改為 DDDD
= list_tail(&left)
, EEEE
= list_tail(&right)
。
上述的快速排序法是使用非遞迴的方式實作。
還沒進入迴圈之前, begin[0]
和 end[0]
分別會指向串列的頭與尾。
先選定 4 作為 pivot ,並且將 pivot 從串列移除,之後開始比較 pivot 與串列各個節點之間的大小,將小於 pivot 的節點 list_add
進 left
,大於 pivot 的節點 list_add
進 right
。
排列好大小後,利用 begin[i]
和 end[i]
指標指向串列的頭跟尾。
begin[i]
和 end[i]
指向的是比 pivot 小的串列, begin[i+2]
和 end[i+2]
指向的是比 pivot 大的串列, begin[i+1]
和 end[i+1]
則指向 pivot 。
由於 i += 2;
所以先從上一回合比 pivot 大的串列開始執行上述動作。
將 7 當作 pivot 所以在比大小的時候, 將節點 5list_add
進 left
,而right
只能指向 NULL 。
再下一回合 i = 4
時,因為 begin[4]
和 end[4]
都指向 NULL ,所以進到else中,並且 i--
,來到 i = 3
,由於 begin[3]
和 end[3]
都指向節點 7,故將 7 list_add
進 result
,且 i--
, i = 2
時也是相同操作,將 5 list_add
進 result
。重複以上步驟,最終 result
則會為一個遞增串列,以上及為程式碼的運作原理。
從上述程式碼可以看出他永遠都是選擇第一個節點作為 pivot ,但當最差情況發生時的時間複雜度會來到 O(n²) ,像是 [1, 2, 3, 4, 5]
則每次選到的 pivot 都為最左邊的數字,如此 left
都為 NULL 而 right
為除了 pivot 以外的節點。如此每次選擇 pivot 後,都要遍歷剩下的節點,那麼就可以使用 Median of Medians Algorithm 的方法去規避最差情況發生。
在程式碼中引入 list.h 函式,並將 node_t 改為串列連接。
將程式碼內部用到 node_t 的函式,都改寫為 list_head 的型態。
由於改為 list_head 的型態,故可以將 list_tail 的函式刪除,直接使用 list->prev 的方式表示最尾端的端點,故也將 end 移除。但因為要保存每次分治的串列,故這裡的 begin 需要配置 list_head 的空間。
此外將原本很多單純用 = 賦予值的部分,改為運用 list_splice_init
、 list_move
。
AAAA
填入 &head
,則可以透過指標的指標進行編寫。
當此處的priv不為 NULL ,則會將型態轉為整數的指標,使用*取值後再加 1 。初步認為這裡應是對應到最後算出比較次數的計算。
在比較完兩個節點的大小後,使用 *tail
將較小的節點連接到 head ,而後應該要將 tail
指向此節點的 next ,讓下次比較大小時,較小的節點可以繼續接在 *tail
處,也就是讓尾端的 next 可以放入下一個節點的地址。
故 BBBB
應該填入 &(*tail->next)
, 但因為要填入最精簡的程式碼,故寫成 &a->next
。
而 CCCC
只是換成在如果節點 b 比 a 的值小的情況,所以可以直接填入 &b->next
。
從此段程式碼來看, list
最終會指向 NULL ,而需要補上 DDDD
和 EEEE
才能使整個串列變成雙向環狀鏈結串列,所以需要將 list
的前一個節點,也就是 tail
的下一個節點變為 head
,並且 head
的上一個節點也應該要為 tail
。故 DDDD
填入 tail->next
,而 EEEE
為 head->prev
。
在這段程式碼中我們可以觀察到 stk_size
此變數,一開始是設為 0 ,而在後面找 run 的迴圈裡,此變數也會更著增加,從這裡我們可以判斷 stk_size
是表示著切了幾個 run 的個數,並且在各個合併的函示中, stk_size
的數量也會減少。
而在 build_prev_link(head, head, stk0);
此函式中,我們可以得知是在將最後合併出來,只剩下一個 run 的串列修正為雙向環狀鏈結串列,故 FFFF
填入 1。
在上述程式碼內,並無設定 minrun 的部分,假設被傳入 find_run
的 list 。
因為 5 > 4 的關係想辦法讓這段 run 反轉。
最後回傳回主程式遞增的 run ( 稱 run1 ) ,以及另一個還沒被排序過的串列。
tp
會將排序過的 run 的 head
串接在一起,經過剛剛的 find_run
,現在 run 的數量等於 1 ,接著進入 merge_collapse
,但因為 run==1 ,所以直接跳出。
再跑一次迴圈後,剛剛剩下來沒有被排序的串列,經過 find_run
的處理後, result.head
的指針會指向處理好的 run ,在這裡程式是用 result.head->prev
指向 run1 。
之後再次進到 merge_collapse 函式,根據是否滿足上面提到的原則,來決定要不要進行合併。
明顯可以發現上述程式碼中並沒有包含 minrun 的實作,故應將 minrun 加入程式的實作。 minrun 的大小為,將總資料長度轉為二進位後的前 6 位數字,若 6 位數字後不為 0 ,則加 1。
這段重建二元樹的程式碼,是先從 TreeNode *buildTree
開始,首先程式會先創一個空的 hash table ,並且利用 void node_add
將 inorder
的節點放入 hash table 中,其中節點資訊包含了數值和位置。
之後在 TreeNode *dfs
中,會利用指標 *tn
去存取目前在前序中最前面的節點的數值,當作此子樹的頭,以及利用這個數值在 int find
中找尋其在中序裡的位置。
其中 tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder, in_low, idx - 1, in_heads, size);
,會持續遞迴出左子樹的函式。 pre_low + 1
做為下輪的 int pre_low
是因為第一個已經被當作頭了,所以 pre_low
就往前一格。 pre_low + (idx - in_low)
做為下輪的 int pre_high
,則是利用 idx - in_low
可以算出左子樹有的節點數量,所以用 pre_low + 左子樹有的節點數量
,得出後面 pre_low + (idx - in_low)
格的節點都是左子樹的節點。 idx - 1
做為下輪的 int in_high
是因為在中序中,頭左邊的所有節點都是左子樹的節點。
而 tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder, idx + 1, in_high, in_heads, size);
, pre_high - (in_high - idx - 1)
做為下輪的 int pre_low
是因為 (in_high - idx - 1)
可以得出在前序中右子樹的尾到右子樹的頭中間的節點數量,故用 pre_high
減去,可得右子樹的頭的節點的位置。 idx + 1
做為下輪的 int in_low
,則是因為在中序中頭的右側即全為右子樹節點。
LRU Cache
是將一種快取的實做方式,當有新資料進來時,將快取中最後一次被存取的部分給替代掉。
需要寫一般串列和 hash table 的串列,來去串接節點是因為可以利用 hash table 提升我們在取值時的速度,如果只有一般串列,那我們必須遍歷 count
個節點找尋我們要的節點。而需要一般串列是因為我們這樣才有哪個節點是最後被使用的紀錄。
LRUCache *lRUCacheCreate(int capacity)
會根據其容量大小來為其配置記憶體大小。
void lRUCacheFree(LRUCache *obj)
利用傳入的指標,將其指向的快取給刪除,程式裡面用到 list_entry
函式,來取得快取中的串列的物件,再將其各個刪除。應該也可以使用 hlist_del
將 hash table 中串列的節點移除。
int lRUCacheGet(LRUCache *obj, int key)
程式碼中會先遍歷對應的 hash table 中的串列,如果有找到對應的值,則將 dlist 中該節點,搬去串列的最前方,並回傳該值,如果找不到,則回傳 -1
。
void lRUCachePut(LRUCache *obj, int key, int value)
是希望將給定的值放入快取中,首先會利用 key 求出 hash 值,再利用 hash 值來檢查是否此 key 值已經使用過了。
這段程式碼相當為將 &cache->node move 至 &obj->hhead[hash] ,既然都有 list_move 了,也可以實作出 hlist_move 。
find_nth_bit
在指定的記憶體空間找出第 N 個設定的位元。
__ffs(unsigned long word)
是用來找一段 long 中,最高的位元是哪一位,程式碼當中用了多個判斷式。
其中原理為,當 word & 0xf 為 0 則表示在 4 位元內 word 的值都為 0 ,故 word 必大於 ,以此類推。
find_nth_bit
的程式碼運作原理為,先比較要找的數字有無超過限制的 size
,並檢查 size
的設置是否符合規範, GENMASK(h, l)
是將 h
到 l
間的位元變為 1 , 故 val
為 addr
h
到 l
間的值,如果 val
有值,則利用 fns
找到為 1 的最高位元並回傳。