2021q1 Homework1 (quiz1)

contributed by < ChenBoSyun >

tags: `linux2021`

Outline

2021q1 Homework1 (quiz1)
- Outline
- 程式碼分析

程式碼分析

linked list struct

既然已經 typedef node_t 為何不用 node_t *next，有其他考量或是單純 coding style

typedef struct __node {                   
    int value;
    struct __node *next;
} node_t;

list_add_node_t

這段程式碼是將 node_t 插入 list 的頭，並且把 list 重新指向 node_t

static inline void list_add_node_t(node_t **list, node_t *node_t) {
    node_t->next = *list;
    *list = node_t;
}

下圖為進入 list_add_node_t 時的狀態，C 語言 pass by value 會配置一段記憶體空間，將傳入參數的值複製到所配置的記憶體

下圖為 node_t->next = *list; 後的狀態，若傳入參數是

下圖為 *list = node_t; 後的狀態，這邊的動作是移動 list 的指標到 node，因此傳入的型態是 list 指標的指標，這樣才會確實的將 node address 指派給 list 的指標

[延伸思考]
若傳入的參數是 list 的指標

static inline void list_add_node_t(node_t *list, node_t *node_t) {
    node_t->next = list;
    *list = *node_t;
}

下圖是執行 list_add_node_t 後的結果

list_concat

list concat 從部分程式碼與涵式名稱可以推測，其功能是將鏈結串列 right 接在鏈結串列 left 後面
實際上， left 是用來紀錄 node_t.next 的記憶體位址，node_t.next 的型態是 node_t * ，因此 left 的型態才會是 node_t **

此外基於 pass by value 的機制，引數 left 本身的值沒有改變，還是指向 list 的開頭





static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        left = &((*left)->next);
    *left = right;
}

#1 static inline void list_concat(node_t **left, node_t *right)

下圖是進入 list_concat 後的示意圖

#3 left = &((*left)->next);

每次迴圈，都會指派下一個 node_t.next 的記憶體位址給 left

#2 while (*left)

迴圈結束條件是 *left == NULL，迴圈結束時 left 的值是最後一個 node_t.next 的記憶體位址，如下圖

#4 *left = right;

quicksort

參考 quicksort wiki
quicksort 使用 Divide and conquer 的策略
實作分為三個步驟

從數列中選定一個基準 (pivot)
將數列分成兩個子數列，分別是比 pivot 大的數列，和比 pivot 小的數列
遞迴執行 1,2 步驟

void quicksort(node_t **list)
{
    if (!*list)
        return;

    node_t *pivot = *list;
    int value = pivot->value;
    node_t *p = pivot->next;
    pivot->next = NULL;

    node_t *left = NULL, *right = NULL;
    while (p) {
        node_t *n = p;
        p = p->next;
        list_add_node_t(n->value > value ? AAA : BBB, n);
    }

    quicksort(&left);
    quicksort(&right);

    node_t *result = NULL;
    list_concat(&result, left);
    CCC;
    *list = result;
}

遞迴程式需要設定結束的條件，否則會陷入無窮遞迴
quicksort 在實作上會重複將數列切成左右兩個子數列，直到子數列小到不能再分割，也就是 NULL

#1 if (!*list)
#2     return;

這段程式碼是將 list 的開頭當作 pivot，並且 pivot->next = NULL
代表 pivot 是只有一個元素的 linked list，這是為了確保 list_concat 的正確性

node_t *pivot = *list;
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;

linked list 的分割比起 array 還要單純，只要走訪一遍linked list，將 value 比 pivot 小的加到left ，大的加到 right

node_t *left = NULL, *right = NULL;
while (p) {
    node_t *n = p;
    p = p->next;
    list_add_node_t(n->value > value ? &right : &left, n);
}

遞迴過程，分別對 left 跟 right 排序

quicksort(&left);
quicksort(&right);

在對 left, right 都排序過後，只要將 left, pivot, right 接在一起就好

node_t *result = NULL;
list_concat(&result, left);
list_concat(&result, pivot); list_concat(&result, right);
*list = result;