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

通用資料結構 C 實作：以函式指標實現型別無關的循環隊列

編輯：關於C

動機：為什麼需要「通用」資料結構？

C 語言無模板、無泛型。要寫一份能存 `int`、`float`、`struct Person*` 等**任意型別**的隊列，核心手段是：

資料欄位用 `void**`（指標陣列），存儲**元素位址**而非元素本身

這正是 C++ STL、`glib`、Linux 核心 `list_head` 等通用容器的設計精髓。

通用隊列結構體定義


typedef struct _QUEUE {
    int start;          // 隊頭索引
    int end;            // 隊尾索引（下一個插入位置）
    int length;         // 容量（陣列大小）
    int count;          // 當前元素數
    void **head;        // 指標陣列：void* head[length]

    // 型別操作函式指標（使用者必須提供）
    int   (*compare)(const void *, const void *); // 比較：<0,=0,>0
    void  (*print)(const void *);                 // 列印單元素
    void *(*find)(const void *, const void *);    // 查找：回傳找到的元素指標或 NULL
    void  (*destroy)(void *);                     // 銷毀元素（可選）
    void *(*copy)(const void *);                  // 深拷貝（可選）
} QUEUE;

建立與銷毀


QUEUE *queue_create(int length,
                    int (*cmp)(const void*, const void*),
                    void (*prn)(const void*),
                    void *(*fnd)(const void*, const void*),
                    void (*dst)(void*),
                    void *(*cpy)(const void*)) {
    if (length <= 0) return NULL;
    QUEUE *q = malloc(sizeof(QUEUE));
    if (!q) return NULL;
    q->head = calloc(length, sizeof(void*)); // 零初始化
    if (!q->head) { free(q); return NULL; }

    q->start = q->end = q->count = 0;
    q->length = length;
    q->compare = cmp; q->print = prn; q->find = fnd;
    q->destroy = dst; q->copy = cpy;
    return q;
}

void queue_destroy(QUEUE *q) {
    if (!q) return;
    if (q->destroy) {
        for (int i = 0, idx = q->start; i < q->count; i++, idx = (idx+1)%q->length)
            q->destroy(q->head[idx]);
    }
    free(q->head);
    free(q);
}

核心操作：入隊、出隊、遍歷列印

入隊


int queue_push(QUEUE *q, void *elem) {
    if (!q || q->count == q->length) return -1; // 滿
    void *stored = q->copy ? q->copy(elem) : elem; // 深拷貝或直接存指標
    q->head[q->end] = stored;
    q->end = (q->end + 1) % q->length;
    q->count++;
    return 0;
}

出隊


void *queue_pop(QUEUE *q) {
    if (!q || q->count == 0) return NULL;
    void *elem = q->head[q->start];
    q->head[q->start] = NULL; // 避免野指標
    q->start = (q->start + 1) % q->length;
    q->count--;
    return elem; // 呼叫端負責 destroy（若 queue 不持有所有權）
}

遍歷列印（原文範例修正版）


void queue_print(const QUEUE *q) {
    if (!q || q->count == 0) return;
    int idx = q->start;
    for (int i = 0; i < q->count; i++) {
        q->print(q->head[idx]);
        idx = (idx + 1) % q->length;
    }
    printf("\n");
}

**關鍵**：用模算術 `(idx+1)%length` 實現環狀遍歷，無需像原文那樣計算 `end` 虛擬位置。

型別操作函式實作範例：int 型別


// 比較：供查找/排序用
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);
}

// 查找：在隊列中尋找等於 target 的元素
void *int_find(const void *elem, const void *target) {
    return int_cmp(elem, target) == 0 ? (void*)elem : NULL;
}

// 銷毀：若 queue 持有所有權且元素為 malloc 記憶體
void int_destroy(void *a) { free(a); }

// 深拷貝：入隊時複製一份
void *int_copy(const void *a) {
    int *p = malloc(sizeof(int));
    if (p) *p = *(const int*)a;
    return p;
}

使用範例：存儲 int


int main() {
    QUEUE *q = queue_create(10, int_cmp, int_print, int_find, int_destroy, int_copy);
    int vals[] = {10, 20, 30, 40, 50};
    for (int i = 0; i < 5; i++) queue_push(q, &vals[i]); // 傳遞區域變數地址，copy 會複製
    queue_print(q); // 10 20 30 40 50

    int target = 30;
    void *found = NULL;
    for (int i = 0, idx = q->start; i < q->count && !found; i++, idx = (idx+1)%q->length)
        found = q->find(q->head[idx], &target);
    if (found) printf("Found: %d\n", *(int*)found);

    queue_destroy(q); // 釋放 copy 出來的記憶體
    return 0;
}

進階主題：compare 與 find 的協作

原文提到 `compare`、`find` 兩子函數待探索。實際上：

`compare`：通用比較介面，可用於**排序**（`qsort`）、**二分查找**、**去重**等
`find`：特定於容器的查找邏輯（如鏈表遍歷、雜湊表查找），內部常呼叫 `compare`

設計建議：`find` 參數為 `(const void *container_elem, const void *user_target)`，回傳找到的容器內元素指標或 `NULL`。

避坑指南

陷阱	後果	對策
直接存區域變數指標不拷貝	出作用域成野指標	必須提供 `copy`，入隊時深拷貝
`destroy` 與 `copy` 不匹配	雙重釋放或洩漏	約定：`copy` 分配 → `destroy` 釋放；若無 `copy` 則不 `destroy`
函式指標簽名不一致	編譯警告/未定義行為	統一用 `const void*` 參數，內部強轉
隊列滿/空邊界條件錯誤	資料覆蓋或讀取垃圾值	`count` 為唯一真相來源，`start==end` 表示空/滿靠 `count` 區分
多執行緒無鎖	競態條件	外部加鎖或用無鎖環形緩衝區

擴展方向

動態擴容：`count==length` 時 `realloc` 陣列並調整 `start/end`
雙端隊列：加 `push_front`/`pop_back`，`start` 可向前移動
優先隊列：內部改用堆，`compare` 決定優先級
迭代器介面：提供 `queue_iter_next` 抽象遍歷細節

總結

通用資料結構的核心是**資料與操作分離**：容器只管「指標的存放與索引」，「元素的語意」完全委託給使用者提供的函式指標。這篇文章以循環隊列為例，示範了 `void**` + 函式指標的經典 C 語言泛型編程範式。掌握此模式，即可構建出類似 C++ STL `vector`/`list`/`queue` 的型別安全、高複用 C 組件庫。