C 語言面向對象編程實戰：通用單鏈表完整實現

編輯：關於C語言

設計理念

本文展示如何用 C 語言模擬面向對象特性，實現一個類型無關、功能完備的單鏈表。核心思想：以 struct slist_node 作為基類節點，用戶自定義節點通過結構體嵌入繼承；通過函數指針實現多態操作（釋放、比較）；封裝所有操作於 struct single_list 中，構成「類」接口。

核心數據結構

節點基類與列表頭

struct slist_node {
    struct slist_node *next;
};

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 *, struct slist_node *);
    struct single_list *(*insert)(struct single_list *, int, struct slist_node *);
    struct single_list *(*replace)(struct single_list *, int, struct slist_node *);
    struct slist_node *(*find_by_key)(struct single_list *, void *);
    struct slist_node *(*first)(struct single_list *);
    struct slist_node *(*last)(struct single_list *);
    struct slist_node *(*at)(struct single_list *, int);
    struct slist_node *(*take_at)(struct single_list *, int);
    struct slist_node *(*take_by_key)(struct single_list *, void *);
    struct single_list *(*remove)(struct single_list *, struct slist_node *);
    struct single_list *(*remove_at)(struct single_list *, int);
    struct single_list *(*remove_by_key)(struct single_list *, void *);
    int (*length)(struct single_list *);
    void (*clear)(struct single_list *);
    void (*deletor)(struct single_list *);
};

構造函數

struct single_list *new_single_list(
    list_op_free_node op_free,
    list_op_key_hit_test op_cmp
) {
    struct single_list *list = malloc(sizeof(struct single_list));
    list->head = list->tail = NULL;
    list->size = 0;
    list->free_node = op_free;
    list->key_hit_test = op_cmp;
    // 綁定所有方法指針...
    list->add = _add_node;
    list->insert = _insert_node;
    // ... 其餘方法綁定
    return list;
}

關鍵算法實現

節點查找（按鍵值）

static struct slist_node *_find_by_key(struct single_list *list, void *key) {
    if (list->key_hit_test) {
        struct slist_node *p = list->head;
        while (p) {
            if (list->key_hit_test(p, key) == 0) return p;
            p = p->next;
        }
    }
    return NULL;
}

指定位置插入節點

static struct single_list *_insert_node(struct single_list *list, int pos, struct slist_node *node) {
    if (pos < list->size) {
        // 遍歷至插入位置
        struct slist_node *p = list->head, *prev = list->head;
        for (int i = 0; i < pos; i++) { prev = p; p = p->next; }
        // 頭插或中間插入
        if (p == list->head) {
            node->next = list->head;
            list->head = node;
        } else {
            prev->next = node;
            node->next = p;
        }
        if (node->next == NULL) list->tail = node;
        list->size++;
    } else {
        list->add(list, node); // 超出範圍則尾插
    }
    return list;
}

用戶自定義類型示例

定義整數節點與字符串節點，分別實現釋放與比較回調：

struct int_node {
    struct slist_node node; // 嵌入基類，實現繼承
    int id;
};

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

static void _int_child_free(struct slist_node *node) {
    free(node);
    printf("int node freed\n");
}