基本原理：事先准备好一个固定长度的数组。
假设长度不够的时候。realloc一块区域。
另外：在数组元素降低的情况下。须要缩减数组长度。
主要接口：
cp_bool DyArrayAppend(DyArray* pArr, void* pData)//加数据到数组末尾 cp_bool DyArrayExpand(DyArray* pArr, cp_int32 nNeed)//扩展数组 cp_bool DyArrayDelete(DyArray* pArr, cp_int32 nIndex)//删除元素by index cp_bool DyArrayShrink(DyArray* pArr)//缩减数组
源码例如以下：（iOS平台的c实现）
//
// dyArray.h
// dataStruct
//
// Created by hherima on 14-7-28.
// Copyright (c) 2014年 . All rights reserved.
//
#ifndef dataStruct_dyArray_h
#define dataStruct_dyArray_h
#include <stdlib.h>
enum
{
CP_FALSE = 0,
CP_TRUE = !CP_FALSE
};
typedef unsigned char cp_bool;
typedef signed int cp_int32;
typedef void (*DataDestroyFunc)(void *);
typedef cp_bool (*DataCmpFunc)(void *,void *);
typedef void (*DataVisitFunc)(void *);
#define F_MALLOC_TYPE(s) (s*)f_malloc(sizeof(s))
#define FREEFUN free
#define MIN_PRE_ALLOCATE_SIZE 10 //The initial size of the dynamic array.
#define MEMSETFUN memset
#define REALLOCFUN realloc
#define MALLOCFUN malloc
struct DynamicArray
{
void **m_ppData; //the address of the allocated array.
cp_int32 m_nAllocSize; //the allocated array size.
cp_int32 m_nSize; //the used size of the array.
DataDestroyFunc m_fDestroy; //the callback function to destroy one data.
DataCmpFunc m_fCmp; //the callback function to compare one data.
DataVisitFunc m_fVisit; //the callback function to visit each data.
};
typedef struct DynamicArray DyArray;
DyArray* DyArrayCreate(DataDestroyFunc pDataDestroy);
cp_bool DyArrayInsert(DyArray* pArr, cp_int32 nIndex, void* pData);
cp_bool DyArrayPrepend(DyArray* pArr, void* pData);
cp_bool DyArrayAppend(DyArray* pArr, void* pData);
cp_bool DyArrayDelete(DyArray* pArr, cp_int32 nIndex);
cp_bool DyArrayDeleteEx(DyArray* pArr, cp_int32 nBegin,cp_int32 nEnd);
cp_bool DyArrayGetByIndex(DyArray* pArr, cp_int32 nIndex, void** ppData);
cp_bool DyArrayGetFirst(DyArray* pArr,void** ppData);
cp_bool DyArrayGetLast(DyArray* pArr,void** ppData);
cp_bool DyArraySetByIndex(DyArray* pArr, cp_int32 nIndex, void* pData);
cp_int32 DyArrayLength(DyArray* pArr);
cp_int32 DyArrayFind(DyArray* pArr, DataCmpFunc pCmp,void *pData);
cp_bool DyArrayForEach(DyArray* pArr, DataVisitFunc pVisit);
void DyArrayDestroy(DyArray* pArr);
void DyArrayDestroyCustom(DyArray* pArr,DataDestroyFunc pDataDestroy);
void DyArrayReset(DyArray* pArr);//shrink
void DyArrayClear(DyArray* pArr);//not shrink
void DyArrayResetCustom(DyArray* pArr,DataDestroyFunc pDataDestroy);
void DyArrayClearCustom(DyArray* pArr,DataDestroyFunc pDataDestroy);//not shrink
#endif
CP_TRUE : CP_FALSE; } /************************************************************************************************** 【函数名】: DyArrayGetLast 【描写叙述】: 获取数组最后一个元素 【參数】: pArr: the array's address. ppData: out parameter, to record the element's pointer. 【返回值】: true or false. ***************************************************************************************************/ cp_bool DyArrayGetLast(DyArray* pArr,void** ppData) { return DyArrayGetByIndex(pArr,pArr->m_nSize-1,ppData) ? CP_TRUE : CP_FALSE; } /************************************************************************************************** 【函数名】:DyArraySetByIndex 【描写叙述】: 设置数组元素by index 【參数】: pArr: the array's address. nIndex: the element's position. pData: the element's pointer. 【返回值】: true or false. ***************************************************************************************************/ cp_bool DyArraySetByIndex(DyArray* pArr, cp_int32 nIndex, void* pData) { //if the input parameter is invalid, return. if(!pArr || nIndex < 0) { return CP_FALSE; } pArr->m_ppData[nIndex] = pData;//find the related position and set its value. return CP_TRUE; } /************************************************************************************************** 【函数名】: DyArrayLength 【描写叙述】:获取数组的长度 【參数】: pArr: the array's address. 【返回值】: 数组长度. ***************************************************************************************************/ cp_int32 DyArrayLength(DyArray* pArr) { return pArr ? pArr->m_nSize : -1; } /************************************************************************************************** 【函数名】: DyArrayFind 【描写叙述】:查找数组中的指定元素 【參数】: pArr: the array's address. pCmp: the callback function to compare the data. pData: the search destination in the array. 【返回值】:假设成功返回位置，否则返回-1 ***************************************************************************************************/ cp_int32 DyArrayFind(DyArray* pArr, DataCmpFunc pCmp,void *pData) { cp_int32 i; //if the input parameter is invalid, return. if(!pArr) { return -1; } //visit each one to find the right one. for(i=0; i<pArr->m_nSize;i++) { if(pCmp) { if(pCmp(pArr->m_ppData[i],pData) == CP_TRUE) { return i; } }else { //if NO compare funciton, just compare the address. if(pArr->m_ppData[i] == pData) { return i; } } } return -1; } /************************************************************************************************** 【函数名】: DyArrayForEach 【描写叙述】:遍历数组 【參数】: pArr: the array's address. pVisit: the callback function to visit the data. 【返回值】:假设成功返回true，否则false ***************************************************************************************************/ cp_bool DyArrayForEach(DyArray* pArr, DataVisitFunc pVisit) { cp_int32 i; //if the input parameter is invalid, return. if(!pArr || !pVisit) { return CP_FALSE; } //visit each one with the visit function. for(i=0; i<pArr->m_nSize;i++) { pVisit(pArr->m_ppData[i]); } return CP_TRUE; } /************************************************************************************************** 【函数名】: DyArrayDestroy 【描写叙述】:销毁整个数组 【參数】: pArr: the array's address. 【返回值】:NA ***************************************************************************************************/ void DyArrayDestroy(DyArray* pArr) { cp_int32 i; //if the input parameter is invalid, return. if(!pArr) { return; } //Using destroy function to destroy each element's memory. if(pArr->m_fDestroy) { for(i=0; i<pArr->m_nSize; i++) { pArr->m_fDestroy(pArr->m_ppData[i]); } } //free the array. FREEFUN(pArr->m_ppData); pArr->m_ppData = NULL; FREEFUN(pArr); pArr = NULL; } /************************************************************************************************** 【函数名】: DyArrayDestroyCustom 【描写叙述】:使用用户函数。小围数组 【參数】: pArr: the array's address. pDataDestroy: user's destroy function. 【返回值】:NA ***************************************************************************************************/ void DyArrayDestroyCustom(DyArray* pArr,DataDestroyFunc pDataDestroy) { cp_int32 i; //if the input parameter is invalid, return. if(!pArr) { return; } //Using destroy function to destroy each element's memory. if(pDataDestroy) { for(i=0; i<pArr->m_nSize;i++) { pDataDestroy(pArr->m_ppData[i]); } } //free the array. FREEFUN(pArr->m_ppData); pArr->m_ppData = NULL; FREEFUN(pArr); } /************************************************************************************************** 【函数名】: DyArrayExpand 【描写叙述】:扩展数组 【參数】: pArr: the array's address. nNeed: the needed new size. 【返回值】:假设成功返回ture否则返回false ***************************************************************************************************/ cp_bool DyArrayExpand(DyArray* pArr, cp_int32 nNeed) { cp_int32 allocSize = 0; void** data = NULL; //if the input parameter is invalid, return. if(!pArr) { return CP_FALSE; } //if need, expand to 1.5 times of the original size. if((pArr->m_nSize + nNeed) > pArr->m_nAllocSize) { allocSize = pArr->m_nAllocSize + (pArr->m_nAllocSize>>1); data = (void**)REALLOCFUN(pArr->m_ppData, sizeof(void*) * allocSize); if(data != NULL) { //clear the expanded space of the new memory. MEMSETFUN(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_TRUE : CP_FALSE; } /************************************************************************************************** 【函数名】: DyArrayInsert 【描写叙述】:插入数组by index 【參数】: pArr: the array's address. nIndex: the position in the array to insert new data. pData: the data to be inserted. 【返回值】:假设成功返回true否则false ***************************************************************************************************/ cp_bool DyArrayInsert(DyArray* pArr, cp_int32 nIndex, void* pData) { cp_bool bRet = CP_FALSE; cp_int32 nCursor = nIndex; cp_int32 i; //if the input parameter is invalid, return. if(!pArr) { return CP_FALSE; } //get the right cursor. nCursor = nCursor < pArr->m_nSize ? nCursor : pArr->m_nSize; if(DyArrayExpand(pArr, 1) == CP_TRUE) { //move all the elements after the cursor to the next positon. for(i = pArr->m_nSize; i > nCursor; i--) { pArr->m_ppData[i] = pArr->m_ppData[i-1]; } //set the cursor's value. pArr->m_ppData[nCursor] = pData; pArr->m_nSize++; bRet = CP_TRUE; } return bRet; } /************************************************************************************************** 【函数名】: DyArrayPrepend 【描写叙述】:在数组開始加入一个数据 【參数】: pArr: the array's address. pData: the data to be added. 【返回值】:假设成功返回ture，否则false ***************************************************************************************************/ cp_bool DyArrayPrepend(DyArray* pArr, void* pData) { return DyArrayInsert(pArr,0,pData) ? CP_TRUE:CP_FALSE; } /************************************************************************************************** 【函数名】: DyArrayAppend 【描写叙述】:加入数据到数组末尾 【參数】: pArr: the array's address. pData: the data to be added. 【返回值】:假设成功返回true。否则false ***************************************************************************************************/ cp_bool DyArrayAppend(DyArray* pArr, void* pData) { return DyArrayInsert(pArr,pArr->m_nSize,pData) ?
CP_TRUE:CP_FALSE; } /************************************************************************************************** 【函数名】: DyArrayShrink 【描写叙述】:缩减数组 【參数】: pArr: the array's address. 【返回值】:ture 或者false ***************************************************************************************************/ cp_bool DyArrayShrink(DyArray* pArr) { cp_int32 nAllocSize = 0; void** pData = NULL; //if the input 【參数】 is invalid, return. if(!pArr) { return CP_FALSE; } //if need, shrink the array to 1.5 times of elements number. if((pArr->m_nSize < (pArr->m_nAllocSize >> 1)) && (pArr->m_nAllocSize > MIN_PRE_ALLOCATE_SIZE)) { nAllocSize = pArr->m_nSize + (pArr->m_nSize >> 1); pData = (void**)REALLOCFUN(pArr->m_ppData, sizeof(void*) * nAllocSize); if(pData != NULL) { //clear memory of the unused space of new memory. MEMSETFUN(pData+pArr->m_nSize,0,(nAllocSize-pArr->m_nSize)*sizeof(void*)); pArr->m_ppData = pData; pArr->m_nAllocSize = nAllocSize; } } return CP_TRUE; } /************************************************************************************************** 【函数名】: DyArrayDelete 【描写叙述】:删除元素by index 【參数】: pArr: the array's address. nIndex: the position in the array to delete useless data. 【返回值】:ture 或者false ***************************************************************************************************/ cp_bool DyArrayDelete(DyArray* pArr, cp_int32 nIndex) { cp_int32 i; //if the input parameter is invalid, return. if(!pArr) { return CP_FALSE; } //destroy the element with destroy function. if(pArr->m_fDestroy) { pArr->m_fDestroy(pArr->m_ppData[nIndex]); } //move the elements after 'nIndex' to the previous one. for(i = nIndex; (i+1) < pArr->m_nSize; i++) { pArr->m_ppData[i] = pArr->m_ppData[i+1]; } //set the last one to null. pArr->m_ppData[i] = NULL; pArr->m_nSize--; //if need ,shrink the size. DyArrayShrink(pArr); return CP_TRUE; } /************************************************************************************************** 【函数名】: DyArrayDeleteEx 【描写叙述】:删除元素by index （扩展） 【參数】: pArr: the array's address. nIndex: the position in the array to delete useless data. nEdn: 【返回值】:ture 或者false ***************************************************************************************************/ cp_bool DyArrayDeleteEx(DyArray* pArr, cp_int32 nBegin,cp_int32 nEnd) { cp_int32 i,nLen = 0; //if the input parameter is invalid, return. //if(!pArr && nBegin>nEnd && nBegin<0 && nBegin>=pArr->m_nSize && nEnd<0 && nEnd>=pArr->m_nSize) if(!pArr) { return CP_FALSE; } //destroy the element with destroy function. if(pArr->m_fDestroy) { for(i=nBegin; i<=nEnd; i++) { pArr->m_fDestroy(pArr->m_ppData[i]); } } //move the elements after 'nIndex' to the previous one. nLen = nEnd - nBegin + 1; for(i = nBegin; (i+nLen) < pArr->m_nSize; i++) { pArr->m_ppData[i] = pArr->m_ppData[i+nLen]; } //set the last one to null. //pArr->m_ppData[i] = NULL; pArr->m_nSize -= nLen; //if need ,shrink the size. DyArrayShrink(pArr); return CP_TRUE; } /************************************************************************************************** 【函数名】: DyArrayReset 【描写叙述】:清除数组数据，缩减数组到原始大小 【參数】: pArr: the array's address. 【返回值】: none. ***************************************************************************************************/ void DyArrayReset(DyArray* pArr) { cp_int32 i; void** pData = NULL; //if the input parameter is invalid, return. if(!pArr) { return; } //reset all the elements with destroy function. if(pArr->m_fDestroy) { for(i=0; i<pArr->m_nSize;i++) { pArr->m_fDestroy(pArr->m_ppData[i]); } } pArr->m_nSize = 0; //if need, shrink the size. if(pArr->m_nAllocSize > MIN_PRE_ALLOCATE_SIZE) { pData = (void**)REALLOCFUN(pArr->m_ppData, sizeof(void*) * MIN_PRE_ALLOCATE_SIZE); if(pData != NULL) { pArr->m_ppData = pData; pArr->m_nAllocSize = MIN_PRE_ALLOCATE_SIZE; } if(pArr->m_ppData) { MEMSETFUN(pArr->m_ppData,0,sizeof(void*)*pArr->m_nAllocSize); } } } /************************************************************************************************** 【函数名】: DyArrayClear 【描写叙述】:清除数组数据。不缩减数组到原始大小 【參数】: pArr: the array's address. 【返回值】:NA ***************************************************************************************************/ void DyArrayClear(DyArray* pArr) { cp_int32 i; void** pData = NULL; //if the input parameter is invalid, return. if(!pArr) { return; } //reset all the elements with destroy function. if(pArr->m_fDestroy) { for(i=0; i<pArr->m_nSize;i++) { pArr->m_fDestroy(pArr->m_ppData[i]); } } pArr->m_nSize = 0; } /************************************************************************************************** 【函数名】: DyArrayResetCustom 【描写叙述】:清除数组使用用户函数，缩减数组到原始大小 【參数】: pArr: the array's address. pDataDestroy: user's destroy function. 【返回值】:NA ***************************************************************************************************/ void DyArrayResetCustom(DyArray* pArr,DataDestroyFunc pDataDestroy) { cp_int32 i; void** pData = NULL; //if the input parameter is invalid, return. if(!pArr) { return; } //reset all the elements with destroy function. if(pDataDestroy) { for(i=0; i<pArr->m_nSize;i++) { pDataDestroy(pArr->m_ppData[i]); } } pArr->m_nSize = 0; //if need, shrink the size. if(pArr->m_nAllocSize > MIN_PRE_ALLOCATE_SIZE) { pData = (void**)REALLOCFUN(pArr->m_ppData, sizeof(void*) * MIN_PRE_ALLOCATE_SIZE); if(pData != NULL) { pArr->m_ppData = pData; pArr->m_nAllocSize = MIN_PRE_ALLOCATE_SIZE; } if(pArr->m_ppData) { MEMSETFUN(pArr->m_ppData,0,sizeof(void*)*pArr->m_nAllocSize); } } } /************************************************************************************************** 【函数名】: DyArrayClearCustom 【描写叙述】:清除数组使用用户函数，不缩减数组到原始大小 【參数】: pArr: the array's address. pDataDestroy: user's destroy function. 【返回值】:NA ***************************************************************************************************/ void DyArrayClearCustom(DyArray* pArr,DataDestroyFunc pDataDestroy) { cp_int32 i; void** pData = NULL; //if the input parameter is invalid, return. if(!pArr) { return; } //reset all the elements with destroy function. if(pDataDestroy) { for(i=0; i<pArr->m_nSize;i++) { pDataDestroy(pArr->m_ppData[i]); } } pArr->m_nSize = 0; }
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5130708.html，如需转载请自行联系原作者
