您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言實現面向對象編程（五）：通用單鏈表的設計與實現

編輯：關於C

在前幾篇文章中，我們探討了如何在 C 語言中引入面向對象的特性，如封裝、繼承與多態。本文將運用這些技巧，實現一個通用的單鏈表數據結構，作為後續更複雜數據結構（如樹、鍵值鏈表）以及最終 HTTP 服務器的基礎。

設計目標

實現一個能存儲任意數據類型的單鏈表，支持增、刪、改、查、插入等基本操作。通過回調函數實現節點內存釋放與鍵值比較，達到類型無關性。

核心數據結構

首先定義基礎節點結構 slist_node，所有用戶自定義節點必須以此為首成員（模擬繼承）。鏈表管理結構 single_list 包含頭尾指針、大小統計，以及一組函數指針作為方法接口。

#ifndef SLIST_H
#define SLIST_H

#ifdef __cplusplus
extern "C" {
#endif

#define NODE_T(ptr, type) ((type*)ptr)

struct slist_node {
    struct slist_node *next;
};

typedef void (*list_op_free_node)(struct slist_node *node);
typedef int (*list_op_key_hit_test)(struct slist_node *node, void *key);

struct single_list {
    struct slist_node *head;
    struct slist_node *tail;
    int size;

    void (*free_node)(struct slist_node *node);
    int (*key_hit_test)(struct slist_node *node, void *key);

    struct single_list *(*add)(struct single_list *list, struct slist_node *node);
    struct single_list *(*insert)(struct single_list *list, int pos, struct slist_node *node);
    struct single_list *(*replace)(struct single_list *list, int pos, struct slist_node *node);
    struct slist_node *(*find_by_key)(struct single_list *, void *key);
    struct slist_node *(*first)(struct single_list *list);
    struct slist_node *(*last)(struct single_list *list);
    struct slist_node *(*at)(struct single_list *list, int pos);
    struct slist_node *(*take_at)(struct single_list *list, int pos);
    struct slist_node *(*take_by_key)(struct single_list *list, void *key);
    struct single_list *(*remove)(struct single_list *list, struct slist_node *node);
    struct single_list *(*remove_at)(struct single_list *list, int pos);
    struct single_list *(*remove_by_key)(struct single_list *list, void *key);
    int (*length)(struct single_list *list);
    void (*clear)(struct single_list *list);
    void (*deletor)(struct single_list *list);
};

struct single_list *new_single_list(list_op_free_node op_free, list_op_key_hit_test op_cmp);

#ifdef __cplusplus
}
#endif
#endif // SLIST_H

關鍵實現細節

節點添加 (_add_node)：維護 tail 指針實現 O(1) 尾部插入。
位置插入 (_insert_node)：遍歷至指定位置調整指針，超出範圍則轉為尾部添加。
節點替換 (_replace)：移除原位置節點並釋放，插入新節點。
鍵值查找 (_find_by_key)：遍歷鏈表調用用戶提供的 key_hit_test 回調。
內存管理：所有刪除操作均調用 free_node 回調，若未提供則默認 free()。

使用示例：整數鏈表測試

定義繼承自 slist_node 的 int_node，實現釋放回調與鍵值比較回調，展示創建、插入、查找、刪除、替換、取出等操作。

struct int_node {
    struct slist_node node;
    int id;
};

static void _int_child_free(struct slist_node *node) {
    free(node);
    // 僅首次釋放時打印提示
    static int flag = 0;
    if (!flag) { flag = 1; printf("int node free\n"); }
}

static int _int_slist_hittest(struct slist_node *node, void *key) {
    struct int_node *inode = NODE_T(node, struct int_node);
    return (inode->id == (int)key) ? 0 : 1;
}

void int_slist_test() {
    struct single_list *list = new_single_list(_int_child_free, _int_slist_hittest);
    // ... 添加 100 個節點，奇數尾插，偶數插入位置 1
    // 驗證首尾節點、遍歷輸出、鍵值查找、位置刪除、節點替換、鍵值刪除、取出節點等操作
    list->deletor(list); // 銷毀鏈表及所有節點
}