C語言實現動態指標陣列：完整庫代碼與設計詳解

編輯：關於C語言

動態指標陣列實現原理

核心思想：預分配固定容量陣列，容量不足時以 1.5 倍增長策略 realloc 擴容；元素減少達閾值時縮容至 1.5 倍當前大小。平衡記憶體效率與擴容頻率。

核心資料結構

struct DynamicArray {
    void **m_ppData;           // 指標陣列基址
    cp_int32 m_nAllocSize;     // 已分配容量
    cp_int32 m_nSize;          // 當前元素數
    DataDestroyFunc m_fDestroy; // 元素銷毀回調
    DataCmpFunc m_fCmp;        // 比較回調
    DataVisitFunc m_fVisit;    // 遍歷回調
};
typedef struct DynamicArray DyArray;

主要介面

DyArrayCreate：建立初始容量 10 的陣列
DyArrayAppend/Prepend/Insert：尾部/頭部/指定位置插入
DyArrayDelete/DeleteEx：單個/範圍刪除
DyArrayGetByIndex/GetFirst/GetLast：隨機/首/尾訪問
DyArraySetByIndex：修改指定位置
DyArrayFind：自定義比較查找
DyArrayForEach：遍歷訪問
DyArrayExpand/Shrink：手動擴縮容
DyArrayDestroy/Clear/Reset：銷毀/清空（含縮容選項）

關鍵實現細節

擴容策略：1.5 倍增長

cp_bool DyArrayExpand(DyArray *pArr, cp_int32 nNeed) {
    if ((pArr->m_nSize + nNeed) > pArr->m_nAllocSize) {
        cp_int32 allocSize = pArr->m_nAllocSize + (pArr->m_nAllocSize >> 1); // 1.5x
        void **data = (void **)realloc(pArr->m_ppData, sizeof(void *) * allocSize);
        if (data) {
            memset(data + pArr->m_nAllocSize, 0, (allocSize - pArr->m_nAllocSize) * sizeof(void *));
            pArr->m_ppData = data;
            pArr->m_nAllocSize = allocSize;
        }
    }
    return (pArr->m_nSize + nNeed) <= pArr->m_nAllocSize;
}

插入操作：後移元素騰出空位

cp_bool DyArrayInsert(DyArray *pArr, cp_int32 nIndex, void *pData) {
    if (!pArr) return CP_FALSE;
    cp_int32 nCursor = (nIndex < pArr->m_nSize) ? nIndex : pArr->m_nSize;
    if (DyArrayExpand(pArr, 1)) {
        for (cp_int32 i = pArr->m_nSize; i > nCursor; --i)
            pArr->m_ppData[i] = pArr->m_ppData[i - 1];
        pArr->m_ppData[nCursor] = pData;
        pArr->m_nSize++;
        return CP_TRUE;
    }
    return CP_FALSE;
}

刪除操作：前移元素填補空洞 + 自動縮容

cp_bool DyArrayDelete(DyArray *pArr, cp_int32 nIndex) {
    if (!pArr || nIndex < 0 || nIndex >= pArr->m_nSize) return CP_FALSE;
    if (pArr->m_fDestroy) pArr->m_fDestroy(pArr->m_ppData[nIndex]);
    for (cp_int32 i = nIndex; i + 1 < pArr->m_nSize; ++i)
        pArr->m_ppData[i] = pArr->m_ppData[i + 1];
    pArr->m_ppData[--pArr->m_nSize] = NULL;
    DyArrayShrink(pArr);  // 檢查是否需縮容
    return CP_TRUE;
}

縮容策略：使用率 < 2/3 且超過最小容量

cp_bool DyArrayShrink(DyArray *pArr) {
    if (!pArr) return CP_FALSE;
    if (pArr->m_nSize < (pArr->m_nAllocSize >> 1) && pArr->m_nAllocSize > MIN_PRE_ALLOCATE_SIZE) {
        cp_int32 nAllocSize = pArr->m_nSize + (pArr->m_nSize >> 1);
        void **pData = (void **)realloc(pArr->m_ppData, sizeof(void *) * nAllocSize);
        if (pData) {
            memset(pData + pArr->m_nSize, 0, (nAllocSize - pArr->m_nSize) * sizeof(void *));
            pArr->m_ppData = pData;
            pArr->m_nAllocSize = nAllocSize;
        }
    }
    return CP_TRUE;
}

回調機制：泛型編程關鍵

DataDestroyFunc：元素銷毀，釋放元素內部資源
DataCmpFunc：自定義比較，支援 Find
DataVisitFunc：遍歷處理，支援 ForEach

此設計實現了「容器與元素類型解耦」，是 C 語言模擬泛型的經典模式。

完整代碼結構

代碼分為 dyArray.h（介面）與 dyArray.c（實現），包含完整錯誤檢查、記憶體安全防護、邊界條件處理。適用於 iOS/macOS 平台，易移植至其他 C 環境。

使用範例

void destroy_int(void *p) { free(p); }

DyArray *arr = DyArrayCreate(destroy_int);
for (int i = 0; i < 100; ++i) {
    int *val = malloc(sizeof(int));
    *val = i;
    DyArrayAppend(arr, val);
}
DyArrayForEach(arr, [](void *p) { printf("%d ", *(int *)p); });
DyArrayDestroy(arr);