一步步演算法：通用資料結構設計——以函式指標實現型別抽象

編輯：關於C語言

C 語言無模板、無虛函式，若要寫出像 C++ STL 容器一樣支援任意型別的通用資料結構，核心技術是 void* 指標 + 函式指標。本文以循環佇列為例，示範如何將比較、列印、查找等型別相關操作抽象為回調函式，實現真正的型別無關容器。

通用佇列結構定義


typedef struct Queue {
    int front, rear;        // 隊頭、隊尾索引
    int capacity, size;     // 容量、當前元素數
    void **data;            // 元素指標陣列（void* 陣列）
    
    // 型別相關操作回調
    int (*compare)(const void*, const void*);  // 比較：<0, =0, >0
    void (*print)(const void*);                // 列印單一元素
    void* (*find_key)(const void*, const void*); // 查找：回傳匹配元素指標
    void (*free_elem)(void*);                  // 釋放元素記憶體（可選）
} Queue;

佇列建立與銷毀


Queue* queue_create(int capacity,
                    int (*cmp)(const void*, const void*),
                    void (*prn)(const void*),
                    void* (*fnd)(const void*, const void*),
                    void (*fre)(void*)) {
    if (capacity <= 0) return NULL;
    Queue *q = (Queue*)malloc(sizeof(Queue));
    if (!q) return NULL;
    q->data = (void**)malloc(capacity * sizeof(void*));
    if (!q->data) { free(q); return NULL; }
    
    q->front = q->rear = q->size = 0;
    q->capacity = capacity;
    q->compare = cmp;
    q->print = prn;
    q->find_key = fnd;
    q->free_elem = fre;
    return q;
}

void queue_destroy(Queue *q) {
    if (!q) return;
    if (q->free_elem) {
        for (int i = 0; i < q->size; i++) {
            int idx = (q->front + i) % q->capacity;
            q->free_elem(q->data[idx]);
        }
    }
    free(q->data);
    free(q);
}

核心操作實作

入隊


int queue_push(Queue *q, void *elem) {
    if (!q || q->size == q->capacity) return -1;  // 滿
    q->data[q->rear] = elem;
    q->rear = (q->rear + 1) % q->capacity;
    q->size++;
    return 0;
}

出隊


void* queue_pop(Queue *q) {
    if (!q || q->size == 0) return NULL;
    void *elem = q->data[q->front];
    q->front = (q->front + 1) % q->capacity;
    q->size--;
    return elem;  // 呼叫端負責釋放（除非佇列擁有所有權）
}

遍歷列印（原文改良版）


void queue_print(const Queue *q) {
    if (!q || q->size == 0 || !q->print) return;
    for (int i = 0; i < q->size; i++) {
        int idx = (q->front + i) % q->capacity;
        q->print(q->data[idx]);
    }
    putchar('\n');
}

查找元素


void* queue_find(const Queue *q, const void *key) {
    if (!q || !q->find_key) return NULL;
    for (int i = 0; i < q->size; i++) {
        int idx = (q->front + i) % q->capacity;
        void *found = q->find_key(q->data[idx], key);
        if (found) return found;
    }
    return NULL;
}

型別特化範例：整數佇列


int int_cmp(const void *a, const void *b) {
    int ia = *(const int*)a, ib = *(const int*)b;
    return (ia > ib) - (ia < ib);
}

void int_print(const void *a) {
    printf("%d ", *(const int*)a);
}

void* int_find(const void *elem, const void *key) {
    return (*(const int*)elem == *(const int*)key) ? (void*)elem : NULL;
}

void int_free(void *elem) { free(elem); }

// 使用示範
int main() {
    Queue *q = queue_create(10, int_cmp, int_print, int_find, int_free);
    
    for (int i = 1; i <= 5; i++) {
        int *val = (int*)malloc(sizeof(int));
        *val = i * 10;
        queue_push(q, val);
    }
    
    queue_print(q);  // 輸出: 10 20 30 40 50
    
    int key = 30;
    int *found = (int*)queue_find(q, &key);
    if (found) printf("找到: %d\n", *found);
    
    queue_destroy(q);
    return 0;
}