介绍一个模板动态数组
作者/黄建雄
本代码提供对动态数组的支持,在内存中程序将数据分块存放,避免了大块内存的申请。同时,与普通的双向链表不同,本代码提供了对内部数据的快速索引,大大提高了数据访问速度。本代码提供C、C++两个版本,可以任意使用、修改、传播。
下面是动态数组结构示意图:
图一
数据结构:
本模块核心是一个对双向链表的扩展,它通过一个可以指向任意数据类型的指针(在C语言版中是一个void
*,在C++中是一个模板)实现了对任意数据类型的处理。链表中的节点中的data域是真正存放数组中数据的缓冲区的指针,该缓冲区的大小(必须是一个正整数)一个需要在程序开始时根据实际需要设定,例如目标数据量在0到100个左右,可以将它设成10等(设太小在添加数据时需要频繁为数据分配空间,太大容易造成内存的浪费),这个时候如果数据量在51到60之间,链表中将包含6个数据节点。
数据接口:(以C++语言版为例)
//******************************************
// name:Add
// function:添加数据
// input:T newElement-新数据
// return: 数据索引号
// remark:
//******************************************
int Add(T newElement).
//******************************************
// name:AddBatch
// function:批量添加数据
// input:T *pElement-源数组指针
// int count-数组大小
// return: BOOLTRUE-成功;FALSE-失败
// remark:
//******************************************
BOOL AddBatch(T *pElement,int count).
//******************************************
// name:Copy
// function:数据复制
// input:CSArray & src-源动态数组
// return:
// remark: 使用前请先确保两个对象有相同的数据类型
//******************************************
void Copy(CSArray &src ).
//******************************************
// name:GetAt
// function:获取数组指定位置的数据
// input:int index-指定位置
// return: T 数据
// remark:
//******************************************
T GetAt(int index).
//******************************************
// name:GetPtAt
// function:获取数组指定位置的数据的指针
// input:int index-指定位置
// return: T 数据
// remark: 提供对内部数据的直接访问,小心使用!!
//******************************************
T *GetPtAt(int index).
//******************************************
// name:GetSize
// function:获取数组的数据容量
// input:
// return: int 数据容量
// remark:
//******************************************
int GetSize().
//******************************************
// name:SetAt
// function:修改数组指定位置的数据
// input:T newElement-新数据
// int index-指定索引号
// return: BOOL TURE-成功;FALSE-失败
// remark:
//******************************************
BOOL SetAt(int index,T &newElement).
//******************************************
// name:InsertAt
// function:在数组指定位置插入一个新数据
// input:int index-指定索引号
// T newElement-待插入的数据
// return: BOOL TURE-成功;FALSE-失败
// remark: 本接口关系到大量数据的迁移,不推荐大量使用
// 算法还有待进一步优化
//******************************************
BOOL InsertAt(int index,T newElement).
//******************************************
// name:RemoveAt
// function:删除数组中指定索引号中包含的数据
// input:int index-指定索引号
// return: BOOL TURE-成功;FALSE-失败
// remark: 本接口关系到大量数据的迁移,不推荐大量使用
// 算法还有待进一步优化
//******************************************
BOOL RemoveAt(int index)
//******************************************
// name:RemoveAll()
// function:清空对象中的数据
// input:
// return: BOOL TURE-成功;FALSE-失败
// remark:
//******************************************
BOOL RemoveAll().
//******************************************
// name:SetSize()
// function:设置数据的容量
// input:int size -数据的容量
// return: BOOL TURE-成功;FALSE-失败
// remark:只允许扩大容量
//******************************************
BOOL SetSize(int size)
代码下载
1、 C语言版(模拟C++的模板及面向对象方法):fteb_array.zip
2、 C++语言版:sarray.zip