# 2025q1 Homework2 (quiz1+2)
>contributed by <[ginsengAttack](https://github.com/ginsengAttack)>

## 第 1 周測驗題
### list_insert_before函式
要將新的節點插入選定節點的前方，用間接指標讓我們可以不用額外的指標紀錄前一個節點。

輸入的參數中， l 指向 list_t 的資料結構，而 list_t 中又存放 list_item 的起始位置，所以我們要從 l 中拿到串列的開頭。

l->head 會是串列的開頭，但是 p 是間接指標，我們要用 p 指向（指向開頭的指標），所以 AAAA = &l->head 。

然後我們要插入的地方是 before 的前面，所以迴圈當然是找到 before 的位置，讓 p 指向的值為 before 這個指標，所以 BBBB = before 。

最後是走訪每一個節點的操作，所以指向 next 即可，但 p 是間接指標，我們應該取 *p 來獲得它所指向的指標，接著透過 -> 來獲得指標所指向空間當中的 next 指標，然後把這個指標的位置給 p ，也就是 CCCC ＝ &(*p)->next 。

然後我們把 *p 設為 item 就是把 before 前一個節點的 next 設置成 item 再把 item 的下一個串接上 before 就完成插入操作了。

### 延伸問題:
merge sort 中 merge 的部份

void merge(struct ListNode** list1,struct ListNode* list2)
{
    while (*list1 != NULL && list2 != NULL) {
        if ((*list1)->val > list2->val) {
            struct ListNode *tmp = *list1;
            struct ListNode *insert = list2;
            list2 = list2->next;
            *list1 = insert;
            insert->next = tmp;
            list1 = &(*list1)->next;
        } else
            list1 = &(*list1)->next;
    } 
    if (list2 != NULL) 
        *list1 = list2;
}

用間接指標的概念完成將第二個串列依大小嵌入第一個串列，完成 merge。

### 管理樹狀結構的記憶體空間
#### remove_free_tree
這是一個管理記憶體空間的結構，要移除選定的空間（拿來使用），除了透過 find_free_tree 來找到相應的記憶體空間外，還必須維持樹狀結構的型態，所以透過中序找前一個節點的方式尋找替代者。

如果選定節點就是左子節點，那就直接換上來就好，因為那意味著左子樹只有一個節點，但是如果是在左子樹較下面的節點，我們就需要遞迴的呼叫 remove_free_tree 來找尋替代節點的替代節點。

然後除了沒有子節點跟只有一個子節點的情況外，我們最後還要把目標的左右指標設置為 NULL ，以避免 dangling references 。
#### in-order
中序是 左子樹->中->右子樹，一個節點中序的前一個節點有兩種可能：
1. 在左子樹
2. 在父節點

如果在父節點，意謂左子樹為 NULL ，這題程式碼已經先偵測左右是否為 NULL 所以不會是這種情況，前一個節點一定在左子樹

if ((*node_ptr)->l && (*node_ptr)->r)

而且會是在左子樹的中序表示法中最後的一個，所以會是左子樹的最右邊節點。

走到左子樹後，往右子節點走訪，直到找到盡頭，也就是右子節點為 NULL 者。

所以 EEEE = (*pred_ptr)->r ，而 FFFF 則是用來往右走訪的操作，所以是 pred_ptr=pred_ptr->r 。

### 非遞迴快速排序法
普通的遞迴算法是選定一個 pivot 然後透過左右指標將大於或小於的數字做交換，最終選定 pivot 的位置，達成初步將數列分割為小於跟大於 pivot 的兩段。

非遞迴的方式明顯不太一樣，小於 pivot 的值會存入 left 的串列，反之則存入 right 的串列，之後我們會得到3個串列，left、pivot跟 right。

先對 right 進行排序，放進 result，再放入 pivot 最後是排序好的 left 。

#### 程式碼分析
CCCC 很明顯是走訪每一個節點的操作，紀錄當前的指標後，走到下一個位置，所以是 p->next 。

這邊我有一個疑問， list_add 操作據我所知應該是加到給定節點的後面，那這樣不是一直把新的值加到 left 跟 right 的最前面嘛？

然後根據題意， end[i] 紀錄 left 的結尾，所以我認為是 list_tail(left) ， end[i+1]邏輯相同。

每次會把三種串列分別存入i、i+1、i+2，接著i+=2，所以會優先處理 right ，把 right 切成三等份之後，會把 right 切出的新 left 存回原本的位置，在繼續處理新 right ，最終直到某一次的串列只有一個節點的時候，我們就可以把值放進 result 了，因為這段處理完成，我們可以將 i-- 處理前面的串列。

#### 應用到核心風格
這裡算是除了作業第一次接觸到核心風格的程式碼，最特別的是將鍊結串列嵌入到結構當中，而不是直接拿指標指向下一個結構：

typedef struct __node {
    long value;
    struct list_head list;
} node_t;

實做 rebuild_list_link 應該是指將雙向指標串連上，把每一個節點的 prev 串到前一個節點，然後最後處理 head 讓它形成一個環狀，所以 GGGG 應為 head->prev=prev ，因為迴圈會讓 prev 停在最後一格。

然後程式主體部份，少了一個 end 陣列，直接用給定輔助函式獲取結尾，然後邏輯基本上沒有太大的不同，主要就是將鍊結串列嵌入結構體的方式會無法直接取得結構體中的值，所以要用一個函式來獲取值。

list_entry 函式就是 contain_of ，可以透過給定的指標、結構體名稱、指標指向結構體中成員的名稱，來計算 offset ，進而獲取結構體的起始位置，也就是結構體的指標，進而讀取結構體中其他成員的值。

所以 HHHH 也就是獲取 pivot 的存值，應該填入 list_entry(pivot,node_t,list)->value ，就可以得到值。

然後i+1是 left，+2 是 right ，L->next = result 的操作就是將 L 加入到最前面，每次都做這個操作，可以保證後來者一定放在更前面，程式碼又是從最大的串列，也就是 right 開始處理，所以保證遞增。

但是這邊看起來處理指標的部份比較粗糙，所以才會有額外的函式保證雙向鍊結串列。

## 第 2 周測驗題
延續上周的快速排序法，但是以能夠進行穩定排序的方式實做。

首先 pivot 一樣要獲得第一個元素，使用新的巨集 list_first_entry 完成，效果應該等價於list_entry(head->next,listitem, list) ，然後對照上周的題目，我們會將取出的節點針對整個串列進行移除 (remove) 操作，list_del 巨集會幫我們把前後指標處理好，然後把移除節點的前後指標也設置為 NULL 。

然後一樣透過以 pivot 值的大小將串列分割，這邊使用了 list_for_each_entry 系列的巨集，小的理所當然放入 less ，大的則放入 greater 。

這邊應該是排序穩定的關鍵，list_move_tail會將給定節點塞到最後，所以最終排序結果也會依照穩定的順序。補充，看到延伸問題剛好問這邊的問題，如果使用 list_move 就會將新的值加到最前面，也就是 head 的後面，這樣假設有兩個相同的數字，後面的那個就會因為位置被放到更前面。

左右兩邊各自進行遞迴。

pivot 為單一節點，使用 list_add ，即可加入 head 的後方，這裡注意， pivot 宣告的型別是 listitem，所以它並不是串列，沒有額外的 head。

而 list_less 和 list_greater，則各自是一整個串列，要用 list_splice 系列的巨集來處理，less 就加在 head 後面，greater 加在 head 前面，這樣就不用管 pivot 自然而然會排好序列。

### 延伸問題:
#### random_shuffle_array
lab0 要求實做的 Fisher-Yates Shuffle ，是從最大的位數開始，每次往下隨機選擇一人交換位置。

但這段程式在做的事情不一樣，它並沒有把位置交換，而是有一端被索引值替換了？暫時還沒有看懂這段的意思。

### 整數的開平方根運算
#### clz2 取 leading zero
程式的邏輯很簡單，它會將數字分為高位跟低位，如果高位全部為零，那就要從低位算出前導0的數量，反之則看高位。

c 是用來判定進行了幾次遞迴呼叫，因為每次輸入的位元長度不同，切出 upper 跟 lower 的大小也不同，初始輸入是32 bits 所以切一半要位移16，接下來是8，然後4最後2。

16bits 的 0xffff 能夠把左邊 16bits 取出，接下來要取 8bits 所以 0xffff 要右移 8bits，然後要取 4bits，所以再移 4bits，最後移動 2bits ，因為每次都是獨立的位移不會累加，所以最後 c=3 的時候要位移14。

magic 有四個值，所以索引最多只能找到0-3的數字，當 c=3 的時候，x才會是 4bits ，然後 upper、lower 各自才會是 2bits 數字，所以 jjjj 為 3。

然後 magic 用作最後查表直接回傳0的數量，當 upper 為非零值，那代表 x 的 leading zero 由其決定，有01xx、10xx、11xx，三種可能，由此可知，對應 magic[11] 的數值應該回傳0代表有0個0。

反之，upper 為零值，則透過 lower 決定0的數量，但是我們也要加入 upper 的0，而這種情況 upper 一定是00，所以 KKKK 為2。

考量到 lower 有可能出現 00，所以 HHHH 為2，這樣就可以回傳正確0的數量。

#### 實作
這段程式碼有點難，所以我的理解可能有（很多）錯漏的地方，姑妄聽之。

他的概念有點類似從1開始建構 root ，最終求取一個 root 的平方能夠剛好小於 x，但是當然不是使用$2^2-> 3^2-> 4^2$，慢慢求解，用的方法會比較巧妙。

假設輸入的 x 是25，那它會先算出遮罩m=16，然後因為25>16所以確定 x 一定包含16在內，最終根的結果就可以加入4。

能夠達到這點是因為 y 每次右移1，m 則右移2，m/4 會導致迴圈進行3輪，最開始加入 y 的16會在最後被位移到第二位，也就是4。

所以從最高位數開始，決定 x能否減掉10000，其實是在決定 root 第2位是否為1，這也是 m 為什每次移兩位的原因。

然後下一輪，就是透過100來判斷第1位數字是否為1。

這邊有另一個關鍵，它透過判斷 `if(9<=20)` ，來確定我們無法將第1位數字設置為1，這樣可能很難理解，為什是判斷20跟9？重點在於"交叉項"。

拆解這邊的邏輯，我們判斷第1位數字是否為1，其實就是判斷 root 能否是6，所以這邊的判斷可以等價為： `if(25<=36)`。

36為$6^2$ 又等於 $(4+2)^2$ ，我們將其拆開，可以寫成$4^2+2*2*4+2^2$，但是我們已經在x扣掉$4^2$了，所以我們要比較的是x剩餘的值是否可以滿足"交叉項＋新選入的數字(m)"。

因為m每次除以4，比對的數字會從一開始選定的m開始遞減，根據上述的邏輯，就是依序比對：
$m^2->(m+m/2)^2->(m+m/4)^2$
可以見得，每次交叉項都剛好除二，符合y除以2的設定。

直觀的講，就是當我確認4也就是100小於根號x的時候，我就要判斷6也就是110是否也小於，以此來得知第二個 bits 是否為1。

透過將第1個 bits 設置成1後的增加和x的剩餘比對，這時y是交叉項$2*4*2$ m是$2^2$，然後之所以最終答案直接加m而不是根號m是因為最終會右移到正確位置。

> 上面的部份我想了蠻久的，如果有錯誤拜託指正一下。

#### 延伸問題：
參考另外一個題目的思路：
$m/n$向上取整為$(m+n-1)/n$，如果m本身可以整除n的話，那加上n-1的餘數會是n-1，不會因為加上這個數字讓商數有改變，但如果餘數至少為1，那商就會加一，就算是餘數的最大值，n-1，也不足以讓商數+2。

所以我要讓 root 向上取整，也只需要加上一個數字，讓剛好可以取平方根不至於多取一個，又讓不能剛好的多取一個就好。

再結合之前交叉項的概念：
$4^2$跟$5^2$的差距，就是$2*4*1+1$，加上$2*4*1$就可以讓平方根加一。

但是這樣要在重新執行一次程式，所以應該有更好的辦法，之後再想。

### 雜湊
雜湊的結構體比較特別，連接每一個 node 的鍊結串列不會指向前一個 node，而是前一個 node 的 next。

之前提到雙向鍊結串列可以提昇走訪的效率，但是雜湊不太追求這個，更不會有需要直接存取最後一個節點的時候，所以採用這種結構。

這邊的鍊結串列是用來處理雜湊的碰撞問題，把碰撞的 node 放在同一個串列下，每次都會是走訪每個點查找。

所以一開始會透過雜湊值，找到相應串列的起始位置，然後進行走訪取值。

加入值的時候，會加入在第一個（也沒辦法加在最後一個），然後原本的第一個（如果存在），要指向新加入節點的 next 。

#### 延伸問題：