C 語言泛型編程與抽象數據類型 (ADT) 實戰：以 Set 為例的完整設計與實現

抽象數據類型 (ADT) 核心思想

• 封裝：隱藏具體實現 (數組/鏈表/樹/哈希)，僅暴露操作接口。
• 信息隱藏：用戶代碼依賴接口，不依賴結構體佈局，實現可隨時替換。
• 泛型：用 void* 承載任意類型元素，配合函數指針實現類型相關操作 (比較、複製、銷毀)。

ADT 設計三層架構

+------------------+
|   Client Code    |  僅包含 .h，調用 API
+------------------+
        │
        ▼
+------------------+
|  Interface (.h)  |  不完整類型聲明、操作函數聲明
|  typedef struct  |
|  Set *Set;       |
+------------------+
        │
        ▼
+------------------+
| Implementation   |  完整結構體定義、內存管理、算法邏輯
|  (.c)            |
+------------------+

完整 Set ADT 設計

1. 公共接口: set.h

#ifndef SET_H
#define SET_H

typedef struct Set *Set;           // 不完整類型，隱藏實現
typedef struct Object *Object;     // 泛型元素句柄

/* 集合操作 */
Set    set_new(void);              // 創建空集合
void   set_delete(Set s);          // 銷毀集合 (含元素)
int    set_add(Set s, Object o);   // 添加，返回 1:成功 0:已存在 -1:錯誤
int    set_remove(Set s, Object o); // 移除，返回 1:成功 0:不存在
int    set_contains(Set s, Object o); // 查詢
int    set_size(Set s);            // 元素個數

/* 迭代器 (只讀) */
typedef struct SetIter *SetIter;
SetIter set_iter_new(Set s);
Object set_iter_next(SetIter it);
void   set_iter_delete(SetIter it);

/* 類型相關操作表 (由具體元素類型實現) */
typedef struct TypeDesc {
    int (*compare)(const Object a, const Object b); // <0, =0, >0
    Object (*copy)(Object o);       // 深拷貝
    void   (*destroy)(Object o);    // 釋放資源
    // 可選：hash, print 等
} TypeDesc;

/* 帶類型描述符的創建 (支持多種元素類型共存) */
Set set_new_typed(const TypeDesc *desc);

#endif

2. 具體元素類型: int_type.c (整數元素示例)

#include "set.h"
#include 
#include 

/* 整數對象內部表示 */
typedef struct IntObj { int val; } IntObj;

static int int_compare(const Object a, const Object b) {
    return ((IntObj *)a)->val - ((IntObj *)b)->val;
}
static Object int_copy(Object o) {
    IntObj *n = malloc(sizeof(IntObj));
    *n = *(IntObj *)o;
    return n;
}
static void int_destroy(Object o) { free(o); }

const TypeDesc TYPE_INT = { int_compare, int_copy, int_destroy };

/* 便利構造函數 */
Object Int_new(int v) {
    IntObj *o = malloc(sizeof(IntObj));
    o->val = v;
    return o;
}
int Int_get(Object o) { return ((IntObj *)o)->val; }

3. 集合實現: set_array.c (有序數組實現，適合小規模/教學)

#include "set.h"
#include 
#include 

struct Set {
    const TypeDesc *desc;
    Object *elems;   // 動態數組
    int size;
    int capacity;
};

Set set_new_typed(const TypeDesc *desc) {
    Set s = malloc(sizeof(*s));
    s->desc = desc;
    s->capacity = 4;
    s->size = 0;
    s->elems = malloc(s->capacity * sizeof(Object));
    return s;
}

void set_delete(Set s) {
    for (int i = 0; i < s->size; ++i)
        s->desc->destroy(s->elems[i]);
    free(s->elems);
    free(s);
}

static int find_index(Set s, Object o) {
    int lo = 0, hi = s->size - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        int cmp = s->desc->compare(o, s->elems[mid]);
        if (cmp == 0) return mid;
        if (cmp < 0) hi = mid - 1;
        else lo = mid + 1;
    }
    return ~lo; // 未找到，返回按位取反的插入位置
}

int set_add(Set s, Object o) {
    int idx = find_index(s, o);
    if (idx >= 0) return 0; // 已存在
    idx = ~idx; // 插入位置
    if (s->size == s->capacity) {
        s->capacity *= 2;
        s->elems = realloc(s->elems, s->capacity * sizeof(Object));
    }
    memmove(&s->elems[idx+1], &s->elems[idx], (s->size - idx) * sizeof(Object));
    s->elems[idx] = s->desc->copy(o);
    s->size++;
    return 1;
}

int set_contains(Set s, Object o) {
    return find_index(s, o) >= 0;
}

/* 迭代器實現略 */

4. 客戶端使用示例: main.c

#include "set.h"
#include "int_type.h" // 包含 TYPE_INT 與 Int_new
#include 

int main() {
    Set s = set_new_typed(&TYPE_INT);
    set_add(s, Int_new(5));
    set_add(s, Int_new(2));
    set_add(s, Int_new(8));
    set_add(s, Int_new(2)); // 重複，忽略

    printf("Size: %d\n", set_size(s)); // 3
    printf("Contains 5: %d\n", set_contains(s, Int_new(5))); // 1

    // 迭代輸出 (有序)
    SetIter it = set_iter_new(s);
    Object o;
    while ((o = set_iter_next(it)) != NULL)
        printf("%d ", Int_get(o));
    putchar('\n'); // 2 5 8
    set_iter_delete(it);

    set_delete(s);
    return 0;
}

內存管理策略

進階：哈希表實現 (O(1) 平均)

struct HashSet {
    const TypeDesc *desc;
    Object **buckets; // 指針數組
    int bucket_count;
    int size;
    // 需在 TypeDesc 增加 hash 函數
    unsigned (*hash)(Object o);
};

// 插入: idx = hash(o) % bucket_count; 線性探測/鏈表解決衝突
// 擴容: size/bucket_count > LOAD_FACTOR (0.75) 時 rehash

總結：C 語言 ADT 設計原則清單

1. 不完整類型：typedef struct Foo *Foo; 隱藏結構體定義。
2. void* 泛型：容器存儲 void* (或 Object 別名)。
3. 類型描述符：struct TypeDesc { compare, copy, destroy, hash... } 封裝類型相關操作。
4. 所有權語義明確：文檔標註誰負責 free，API 命名體現 (create/destroy, add/remove, retain/release)。
5. 錯誤處理：返回 int 狀態碼或 NULL，配合 errno 或錯誤碼枚舉。
6. 迭代器抽象：提供只讀迭代器，隱藏遍歷細節。
7. 編譯防火牆：.h 僅含聲明，.c 含定義，修改實現不觸發客戶端重編譯 (大項目關鍵)。

這種設計模式是 C 語言大型項目 (如 Linux 內核 kobject、Glib GObject、Redis 數據結構) 的基石，掌握它意味著從「寫代碼」進化為「設計系統」。