C 語言實作動態陣列 ListArray（二）：帶容量增量機制的優化版

編輯：關於C語言

優化動機

基礎版（方法一）每次新增/刪除都重新分配記憶體，頻繁操作下效能低下。本版引入 預設容量 與 擴容步長 機制，參考 std::vector / ArrayList 思想：空間換時間，減少 malloc/free 與 memcpy 次數。

完整標頭檔實作

#ifndef __LISTARRAY_H__
#define __LISTARRAY_H__

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

#define LISTDEFAULTSIZE 20   // 初始容量
#define LISTCHANGESIZE  10   // 每次擴容/縮容步長

typedef struct _List List;

struct _List {
    void **pListPointArray;                 // 元素指標陣列
    int Total;                              // 目前元素個數
    int ChangeSize;                         // 擴容步長
    int Size;                               // 目前分配容量
    void (*Add)(List *pList, void *pListPoint);
    void (*Remove)(List *pList, void *pListPoint);
    void (*Delete)(void *pList);
};

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

static void ListDelete(void *pList) {
    rt_free(((List *)pList)->pListPointArray);
    rt_free(pList);
}

static void ListAdd(List *pList, void *pListPoint) {
    void **tListPointArray;

    // 1. 容量不足時擴容
    if (pList->Size == pList->Total) {
        pList->Size += pList->ChangeSize;
        tListPointArray = rt_malloc(sizeof(int *) * pList->Size);
        memcpy(tListPointArray, pList->pListPointArray, sizeof(int *) * pList->Total);
        rt_free(pList->pListPointArray);
        pList->pListPointArray = tListPointArray;
    }

    // 2. 尾端插入
    pList->pListPointArray[pList->Total] = pListPoint;
    pList->Total++;
}

static void ListRemove(List *pList, void *pListPoint) {
    int pListIndex, tListIndex;
    void **tListPointArray;

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

    // 1. 原地移除：雙指標覆蓋法，O(n) 無額外分配
    for (pListIndex = 0, tListIndex = 0; pListIndex < pList->Total; pListIndex++) {
        if (pList->pListPointArray[pListIndex] != pListPoint) {
            pList->pListPointArray[tListIndex] = pList->pListPointArray[pListIndex];
            tListIndex++;
        }
    }
    pList->Total = tListIndex;

    // 2. 縮容判斷：剩餘元素遠小於容量時才縮容
    if (pList->Total <= (pList->Size - pList->ChangeSize)) {
        pList->Size -= pList->ChangeSize;
        tListPointArray = rt_malloc(sizeof(int *) * pList->Size);
        memcpy(tListPointArray, pList->pListPointArray, sizeof(int *) * pList->Total);
        rt_free(pList->pListPointArray);
        pList->pListPointArray = tListPointArray;
    }
}

static List *ListCreate(void) {
    List *pList = (List *)rt_malloc(sizeof(List));
    pList->Total = 0;
    pList->Size = LISTDEFAULTSIZE;
    pList->ChangeSize = LISTCHANGESIZE;
    pList->pListPointArray = rt_malloc(sizeof(int *) * LISTDEFAULTSIZE); // 修正：乘以指標大小
    pList->Add = ListAdd;
    pList->Remove = ListRemove;
    pList->Delete = ListDelete;
    return pList;
}

#endif

關鍵改進點解析

1. 結構體新增欄位

Size：目前已分配的總容量（槽位數）。
ChangeSize：每次擴容/縮容的步長（預設 10）。

2. 新增策略：按需擴容

只有當 Total == Size 時才觸發 realloc 邏輯（手動 malloc+memcpy+free）。
擴容後 Size += ChangeSize，後續多次 Add 直接使用預留空間，O(1) 尾端插入。

3. 移除策略：原地移除 + 延遲縮容

移除採用雙指標原地覆蓋，不再每次分配新記憶體，僅 Total--。
縮容條件：Total <= Size - ChangeSize，即剩餘元素較少時才釋放多餘空間，避免頻繁震盪。

4. 建構函數初始化

預分配 LISTDEFAULTSIZE（20）個指標槽位。
修正原碼潛在 Bug：rt_malloc(LISTDEFAULTSIZE) → rt_malloc(sizeof(int *) * LISTDEFAULTSIZE)。

效能對比

指標	方法一（基礎版）	方法二（優化版）
新增（均攤）	O(n) 每次分配	O(1) 均攤，僅擴容時 O(n)
移除（均攤）	O(n) 每次分配	O(n) 移動元素，縮容時額外 O(n)
記憶體碎片	高（頻繁 malloc/free）	低（大塊分配，較少釋放）
峰值記憶體	精確佔用	預留 `ChangeSize` 槽位