C 語言實作動態陣列 ListArray（一）：基礎版每次增減重新分配

專案背景

C 語言標準庫缺乏動態陣列容器，許多專案需自行實作。本文介紹一個模仿 VC++ CList / CArray 風格的 ListArray 實作，採用結構體封裝資料與操作函數指標，實現面向物件風格。第一版採用最直觀的策略：每次新增或刪除元素都重新分配記憶體、複製資料、釋放舊記憶體。

完整標頭檔實作

#ifndef __LISTARRAY_H__
#define __LISTARRAY_H__

#include "rtthread.h"
#include "finsh.h"

// 前向宣告
typedef struct _ListArray ListArray;

struct _ListArray {
    void **pListPointArray;                    // 元素指標陣列
    int Total;                                 // 目前元素個數
    void (*Add)(ListArray *pList, void *pListPoint);    // 新增
    void (*Remove)(ListArray *pList, void *pListPoint); // 移除
    void (*Delete)(void *pList);                // 析構
};

// ---------- 內部靜態函數 ----------

// 析構：先釋放指標陣列，再釋結構體本身
static void ListDelete(void *pList) {
    if (((ListArray *)pList)->pListPointArray != RT_NULL) {
        rt_free(((ListArray *)pList)->pListPointArray);
    }
    rt_free(pList);
}

// 新增：重新分配 +1 空間，複製舊資料，檢查重複，尾端插入
static void ListAdd(ListArray *pList, void *pListPoint) {
    void **tListPointArray = rt_malloc(sizeof(int *) * (pList->Total + 1));
    int pListIndex;

    for (pListIndex = 0; pListIndex < pList->Total; pListIndex++) {
        if (pList->pListPointArray[pListIndex] == pListPoint) {
            rt_free(tListPointArray); // 重複元素，釋放新記憶體並返回
            return;
        }
        tListPointArray[pListIndex] = pList->pListPointArray[pListIndex];
    }

    tListPointArray[pList->Total] = pListPoint;
    pList->Total += 1;

    if (pList->pListPointArray != RT_NULL) rt_free(pList->pListPointArray);
    pList->pListPointArray = tListPointArray;
}

// 移除：重新分配 -1 空間，跳過目標元素複製其餘，縮減總數
static void ListRemove(ListArray *pList, void *pListPoint) {
    int pListIndex, tListIndex;
    void **tListPointArray;
    void **FreePointArray;
    void **SavePointArray;

    if (pList->Total == 0) return;

    tListPointArray = rt_malloc(sizeof(int) * (pList->Total - 1));
    FreePointArray = tListPointArray;
    SavePointArray = pList->pListPointArray;

    for (pListIndex = 0, tListIndex = 0; pListIndex < pList->Total; pListIndex++) {
        if (pList->pListPointArray[pListIndex] == pListPoint) {
            FreePointArray = pList->pListPointArray; // 標記舊陣列待釋放
            SavePointArray = tListPointArray;        // 標記新陣列待保留
            continue;
        }
        if (tListIndex < (pList->Total - 1)) {
            tListPointArray[tListIndex] = pList->pListPointArray[pListIndex];
            tListIndex++;
        }
    }

    pList->Total = (SavePointArray == tListPointArray) ? pList->Total - 1 : pList->Total;
    if (FreePointArray != RT_NULL) rt_free(FreePointArray);
    pList->pListPointArray = SavePointArray;
}

// 建構函數：初始化結構體並綁定操作函數
static ListArray *ListCreate(void) {
    ListArray *pList = (ListArray *)rt_malloc(sizeof(ListArray));
    pList->Total = 0;
    pList->pListPointArray = RT_NULL;
    pList->Add = ListAdd;
    pList->Remove = ListRemove;
    pList->Delete = ListDelete;
    return pList;
}

#endif

核心設計解析

1. 結構體封裝與函數指標多態

ListArray 結構體包含：

• 資料成員：void **pListPointArray（指標陣列）、int Total（計數）。
• 操作成員：三個函數指標 Add、Remove、Delete，實現「方法」綁定。

使用時：list->Add(list, ptr);，模擬 list.Add(ptr)。

2. RT-Thread 記憶體管理

程式碼依賴 RT-Thread 核心的 rt_malloc/rt_free 而非標準 malloc/free，適用於嵌入式環境。若移植至標準 C 環境，只需替換為標準庫函數並處理 NULL 判斷。

3. 新增邏輯（ListAdd）

1. 分配 Total + 1 大小的新陣列。
2. 遍歷舊陣列複製指標，同時檢查重複（指標比較）。
3. 尾端插入新指標，更新 Total。
4. 釋放舊陣列，指向新陣列。

4. 移除邏輯（ListRemove）

1. 分配 Total - 1 大小的新陣列。
2. 雙指標遍歷：pListIndex 讀舊陣列，tListIndex 寫新陣列，遇到目標指標則跳過不複製。
3. 透過 FreePointArray/SavePointArray 雙指標技巧決定最終保留哪塊記憶體。
4. 更新 Total，釋放被淘汰記憶體。

效能特性與適用場景

優點： 實作簡單、記憶體佔用精確（無預留空間）。
缺點： 頻繁增刪時大量分配/釋放記憶體，產生碎片與效能開銷。

總結與下一步

此版本適合元素數量較少、增刪頻率低的場景。下一版（方法二）將引入 容量與增量機制，減少記憶體重分配次數，大幅提升高頻操作效能。