C基礎之 list 庫奧義_ZenDei技術網路在線

list 是電腦軟體體系基石. 是數據結構開始和結束. 同樣也是 C 解決複雜問題的跳板. ...

前言 - 關於 list 思考

　　list 是最基礎的數據結構也是數據結構的基礎. 高級 C 代碼紐帶也是 list.

扯一點, 當你走進了 C 的殿堂, 那麼你和 list 增刪改查那就是一輩子丫 ~ 這裡不妨分享一下作者對於 list 認知經歷的幾個階段 (比心)
i) 原生鏈表

struct list {
    struct list * next;
    ...
}

鏈表結構和業務數據綁定在一起. 朴實無華麗, 重劍可破軍

ii) 萬能鏈表

struct list {
    struct list * next;
    void * node;
}

所有業務結點抽象為 void * 萬能指針. 瑕疵是存在 sizeof (void *) 記憶體浪費.

像一杯甜酒喝起來還挺爽, 只是熱量有點高.
iii) 內核鏈表

struct $list {
    struct $list * next;
};

#define $LIST_HEAD struct $list $node

$LIST_HEAD 巨集放在需要實現的鏈式結構的頭位置. 有點繼承味道, 例如下麵這樣

struct list {
    $LIST_HEAD;
    ...
}

住用利用隱含條件 &list = &(list.$node) => list->next = &(list.$node)->next.

鏈表結點首地址和業務結點首地址值想等. 在內核看挺常用的. 四兩撥千斤 ~ iv) 註冊鏈表

struct $list {
    struct $list * next;
};

#define $LIST struct $list $node;

typedef struct {
    struct $list * root; // 存儲鏈表的頭節點

    icmp_f fadd; // 鏈表中插入數據執行的方法
    icmp_f fget; // 鏈表中查找數據執行的方法
    node_f fdie; // 鏈表中刪除數據執行的方法
} * list_t;

//
// list_next - 獲取結點n的下一個結點.
// n        : 當前結點
//
#define list_next(n) ((void *)((struct $list *)(n))->next)

//
// list_create - 構建 list 對象
// fadd : 插入數據方法
// fget : 獲取數據方法
// return : 創建好的鏈表對象
//
#define list_create(fadd, fget) \
list_create_((icmp_f)fadd, (icmp_f)fget)

inline list_t list_create_(icmp_f fadd, icmp_f fget) {
    list_t list = malloc(sizeof *list);
    list->root = NULL;
    list->fadd = fadd;
    list->fget = fget;
    list->fdie = NULL;
    return list;
}

註冊行為定義如下

//
// icmp_f - 比較行為的類型
// : int add_cmp(const void * now, const void * node)
//
typedef int (* icmp_f)();

//
// node_f - 銷毀當前對象節點
// : void list_die(void * node);
//
typedef void (* node_f)(void * node);

當時產生這個想法是太迷戀基於函數註冊的方式. 希望一次註冊終身受用.

但在實戰中發現, C 很多時候只用到局部部分. 功能越強大, 考慮的越全面, 代碼寫起來就越難受. 等同於衣服太多, 搬家就會很麻煩. 領證還要房子車子票子, 這麼麻煩, 那結個 pi 呀. 必須要整改 :)
v) 取捨鏈表

struct list {
    struct list * next;
    ...
}

or

//
// list.h 通用的單鏈表庫
// void * list = NULL;
//
struct $list {
    struct $list * next;
};

#define $LIST struct $list $node;

簡單業務上使用第一個原生鏈表, 在特定場合(順序有要求)使用內核鏈表.

成熟在於取捨, 渣往往是抉擇的時候不定, 遇到的時候不剋制. 有感情那 OK, 有票子那 OK, else 自己玩毛 ~
　　說了這麼多沒用的, 希望讀者能夠理解作者關於鏈表結構的思考心路. 本文後續重點就是講解 $LIST ~

正文 - 介面設計

　　 list 首先從總體介面設計感受此中氣息

//
// list.h 通用的單鏈表庫
// void * list = NULL;
// 
struct $list {
    struct $list * next;
};

#define $LIST struct $list $node;

//
// list_next - 獲取結點n的下一個結點.
// n        : 當前結點
//
#define list_next(n) ((void *)((struct $list *)(n))->next)

//
// list_delete - 鏈表數據銷毀操作
// list     : 基礎的鏈表結構
// pist     : 指向基礎的鏈表結構
// fdie     : 鏈表中刪除數據執行的方法
// return   : void
//
#define list_delete(list, fdie)                                         \
list_delete_(&(list), (node_f)(fdie))
extern void list_delete_(void ** pist, node_f fdie);

//
// list_get - 匹配得到鏈表中指定值
// list     : 基礎的鏈表結構
// fget     : 鏈表中查找數據執行的方法
// left     : 待查找的結點內容 
// return   : 查找到的節點, NULL 表示沒有查到
//
#define list_get(list, fget, left)                                      \
list_get_((list), (icmp_f)(fget), (const void *)(intptr_t)(left))
extern void * list_get_(void * list, icmp_f fget, const void * left);

//
// list_pop - 匹配彈出鏈表中指定值
// list     : 基礎的鏈表結構
// pist     : 指向基礎的鏈表結構
// fget     : 鏈表中查找數據執行的方法
// left     : 待查找的結點內容 
// return   : 查找到的節點, NULL 表示沒有查到 
//
#define list_pop(list, fget, left)                                      \
list_pop_(&(list), (icmp_f)(fget), (const void *)(intptr_t)(left))
extern void * list_pop_(void ** pist, icmp_f fget, const void * left);

//
// list_add - 鏈表中添加數據, 從小到大 fadd(left, ) <= 0
// list     : 基礎的鏈表結構
// pist     : 指向基礎的鏈表結構
// fadd     : 插入數據方法
// left     : 待插入的鏈表結點
// return   : void
//
#define list_add(list, fadd, left)                                      \
list_add_(&(list), (icmp_f)(fadd), (void *)(intptr_t)(left))
extern void list_add_(void ** pist, icmp_f fadd, void * left);

大量用到一個巨集技巧

// list     : 基礎的鏈表結構
// pist     : 指向基礎的鏈表結構

#define list_delete(list, fdie)                                         \
list_delete_(&(list), (node_f)(fdie))

通過巨集將一維指針轉成二維指針來使用. 缺點是指針不可複製. 或者複製後不能再使用上一個指針.

(等同於破壞型智能指針)優勢在於瀟灑, 寧可 BUG 不斷, 也要帥氣到底 ~

介面實現部分

開頭從 delete 講起. C 可以沒有 create(alloc) , 但一定要有 delete(free). 來不及銷毀證據那就不用出去嗨了.

//
// list_delete - 鏈表數據銷毀操作
// pist     : 指向基礎的鏈表結構
// fdie     : 鏈表中刪除數據執行的方法
// return   : void
//
void 
list_delete_(void ** pist, node_f fdie) {
    if (pist && fdie) {
        // 詳細處理鏈表數據變化
        struct $list * head = *pist;
        while (head) {
            struct $list * next = head->next;
            fdie(head);
            head = next;
        }
        *pist = NULL;
    }
}

核心招式在於 *pist = NULL; 希望置空. (雖然沒有卵用, 因為指針可複製, 存在多個引用)

如果場景不允許複製的話, 可以一用.

對於後面幾個函數核心設計圍繞頭結點處理上, 如果處理的對象是頭結點, 需要重新設置.

//
// list_get - 匹配得到鏈表中指定值
// list     : 基礎的鏈表結構
// fget     : 鏈表中查找數據執行的方法
// left     : 待查找的結點內容 
// return   : 查找到的節點, NULL 表示沒有查到
//
void * 
list_get_(void * list, icmp_f fget, const void * left) {
    if (fget) {
        struct $list * head = list;
        while (head) {
            if (fget(left, head) == 0)
                return head;
            head = head->next;
        }
    }
    return NULL;
}

//
// list_pop - 匹配彈出鏈表中指定值
// pist     : 指向基礎的鏈表結構
// fget     : 鏈表中查找數據執行的方法
// left     : 待查找的結點內容 
// return   : 查找到的節點, NULL 表示沒有查到 
//
void * 
list_pop_(void ** pist, icmp_f fget, const void * left) {
    struct $list * head, * next;
    if (!pist || fget)
        return NULL;

    // 看是否是頭節點
    head = *pist;
    if (fget(left, head) == 0) {
        *pist = head->next;
        return head;
    }

    // 不是頭節點挨個處理
    while (!!(next = head->next)) {
        if (fget(left, next) == 0) {
            head->next = next->next;
            return next;
        }
        head = next;
    }

    return NULL;
}

//
// list_next - 獲取結點n的下一個結點.
// n        : 當前結點
//
#undef  list_next
#define list_next(n) ((struct $list *)(n))->next

//
// list_add - 鏈表中添加數據, 從小到大 fadd(left, ) <= 0
// pist     : 指向基礎的鏈表結構
// fadd     : 插入數據方法
// left     : 待插入的鏈表結點
// return   : void
//
void 
list_add_(void ** pist, icmp_f fadd, void * left) {
    struct $list * head;
    if (!pist || !fadd || !left)
        return;
    
    // 看是否是頭結點
    head = *pist;
    if (!head || fadd(left, head) <= 0) {
        list_next(left) = head;
        *pist = left;
        return;
    }

    // 不是頭節點, 挨個比對
    while (head->next) {
        if (fadd(left, head->next) <= 0)
            break;
        head = head->next;
    }

    // 添加最終的連接關係
    list_next(left) = head->next;
    head->next = left;
}

很多代碼強烈推薦自己多打幾遍. 這是實踐派絕招, 可以啥都不懂, 但會寫(有思考更好)應該也是及格吧.

其中 list_next 巨集設計思路也很灑脫. 對外暴露是讀操作, 對內是寫操作.

這裡不妨贈送個測試介面

//
// node_f - 銷毀當前對象節點
//  : void list_die(void * node); 
//
typedef void (* node_f)(void * node);

//
// list_each - 鏈表迴圈處理函數, 僅僅測試而已
// list     : 基礎的鏈表結構
// feach    : 處理每個結點行為函數
// return   : void
//
#define list_each(list, feach)                                          \
list_each_((list), (node_f)(feach))
extern void list_each_(void * list, node_f feach);

void 
list_each_(void * list, node_f feach) {    
    if (list && feach) {
        struct $list * head = list;
        while (head) {
            struct $list * next = head->next;
            feach(head);
            head = next;
        }
    }
}

list 使用 demo 可以參照這下麵的寫法

#define INT_NAME (64)

struct peoples {
    $LIST

    double age;
    char name[INT_NAME + 1];
};

// peoples_add : 預設年齡從小到大排序, 並且獲取
inline static int peoples_add(struct peoples * left, struct peoples * node) {
    return (int)(left->age - node->age);
}

// peoples_each : 單純的列印介面信息
inline static void peoples_each(struct peoples * node) {
    printf("age = %9.6lf, name = %s\n", node->age, node->name);
}

//
// list test demo
//
void list_test(void) {
    void * peops = NULL;

    // 這裡添加數據
    struct peoples peop[5];
    for (int i = 0; i < LEN(peop); ++i) {
        peop[i].age = rand() % 100 + rand() * 1.0 / rand();
        snprintf(peop[i].name, LEN(peop[i].name), "peop_%d", i);
        list_add(peops, peoples_add, peop + i);
    }

    // 這裡列印數據
    list_each(peops, peoples_each);
}

到這關於 list 瞭解的一切都傳入糖果中 : ) 更好例子, 基於 list 設計了重覆定時器例子

　　timer - https://github.com/wangzhione/structc/blob/master/structc/base/timer.c

(扯一點, 定時器有很多實現思路. 採用 list, heap, double list, array + list 都有, 看應用領域.) 能夠寫好 list,

算數據結構結業了吧. 想起朴實的大學數學老師說, 走出學校的時候還記得數學分析, 那數學系就算學合格了.

現在想起來有些心痛, 真實在. 對於大家都懂的需要多練習, 對於都不明白的需要多調研.

順勢而為, 伴傑遮天.

後記 - 有序展望

　　錯誤和成長是難免的歡迎指正 ~ :-

小雨中的回憶 - https://music.163.com/#/song?id=119664

:- >

C基礎 之 list 庫奧義

C基礎之 list 庫奧義