2021q1 Homework1 (quiz1)

contributed by < Shanola >

第一周題目
GitHub程式碼

測驗 1

程式碼

考慮單向 linked list 結構，已知無 circular，嘗試以遞增順序進行 Quick sort，以下為有進行新增或修改的程式碼片段

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

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 ? &right/*AAA*/ : &left/*BBB*/, n);
    }

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

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

node_t *list_make_node_t(node_t *list, int value)
{
    node_t *n = malloc(1 * sizeof(node_t));
    if (!n) {
        assert(n && "malloc error");
        return NULL;
    }
    n->value = value;
    n->next = NULL;
	n->prev = NULL;
    if (!list) {
        return n;
    } else {
        node_t *tmp = list;
        while (tmp->next) {
            tmp = (tmp->next);
        }
        tmp->next = n;
		n->prev = tmp;
        return list;
    }
}

void list_free(node_t **list)
{
    if (!(*list)->next) {
        free(*list);
    } else {
        list_free(&((*list)->next));
    }
}

程式碼解析

首先 list_add_node_t 是一個沒有回傳值 (void) 且在編譯時被展開到呼叫位置 (static inline) 的函式，具有一個指向 node_t 指標的指標 list，及指向 node_t 的指標 node 兩個參數，負責將節點加到 list 前方：

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

再來 list_concat 負責將兩個 list 連接起來：

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

在這個遞迴式的 quicksort 函式中，會先以 list 中的第一個節點當作 pivot，將所有比 pivot 小的值連接到 left list 上，而比較大的則會接到 right list 上，然後再對這兩個 list 遞迴做 quick sort，最後再將 left, pivot, right 連接起來。

Random 問題

long int random(void) 是屬於 stdlib.h 標準函式庫中的函式，該函式根據 seed 去 table 找大小為 31 的 long int 的序列的其中一個值來回傳，但這個 seed 若沒有被指定時會自動餵入 1，也因此使得 random 每次回傳的亂數看似是固定的。

有一個常見的解決方法是使用 void srandom(unsigned int seed) 來填入 seed，填入的 seed 可以用一個隨時變化的值(譬如時間），如此一來 random 回傳的值所屬的序列便會隨時間變換，每次回傳的值的序列也不一樣。

Optimized q-sort

將 __node 結構多一個指標以指向前一個節點：

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

有改寫過後的函式變成：
list_make_node_t

node_t *list_make_node_t(node_t *list, int value)
{
    node_t *n = malloc(1 * sizeof(node_t));
    if (!n) {
        assert(n && "malloc error");
		return NULL;
    }
    n->value = value;
    n->next = NULL;
	n->prev = NULL;
    if (!list) {
        return n;
    } else {
        node_t *tmp = list;
        while (tmp->next) {
            tmp = (tmp->next);
        }
        tmp->next = n;
		n->prev = tmp;
        return list;
    }
}

tags: linux2021