📄 sarray.hpp
字号:
// SArray.h: interface for the CSArray class.
// 模块名称：启程动态数组C++模板类
// 说明：本代码提供对动态数组的支持，在内存中程序将数据分块存放，
// 避免了大块内存的申请，同时也和普通的双向链表不同的是本代码提供
// 了对内部数据的快速索引，大大提高了数据访问速度。
// 本代码可以任意使用、修改、传播。
// 黄建雄 huangjianxiong@sina.com
// 2003-09-25
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_SARRAY_H__B1D40C22_2698_4202_921E_36D447EA4199__INCLUDED_)
#define AFX_SARRAY_H__B1D40C22_2698_4202_921E_36D447EA4199__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#ifndef ASSERT
#define ASSERT(a) void()
#endif
#ifndef BOOL
#define BOOL int
#endif
template<class T>
class CSArray
{
typedef struct _SARRAYNODE{
struct _SARRAYNODE * prenode; //前一节点
T * data; //存储实际数据数组的数据块的指针
struct _SARRAYNODE * nextnode; //后一节点
}SARRAYNODE;
public:
CSArray(int nGrowBy=5){
m_pCurNode=m_pHeadNode=m_pTailNode=NULL;
m_nCurIndex=-1;
m_nCount=0;
m_nGrowBy=nGrowBy;
}
virtual ~CSArray(){Free();}
//******************************************
// name:Add
// function:添加数据
// input: T newElement-新数据
// return: 数据索引号
// remark:
//******************************************
int Add(T newElement)
{
SARRAYNODE *temp=NULL;
int offset=0;
if(m_nGrowBy==0)//
return -1;
if(m_pHeadNode==NULL)
{
m_pHeadNode=new SARRAYNODE;
m_pHeadNode->prenode=m_pHeadNode->nextnode=NULL;
m_pHeadNode->data=new T[m_nGrowBy];
if(m_pHeadNode->data==NULL)
return -1;
*m_pHeadNode->data=newElement;
m_nCurIndex=0;
m_nCount++;
m_pCurNode=m_pTailNode=m_pHeadNode;
}
else
{
if(m_nCount%m_nGrowBy==0)
{
temp=new SARRAYNODE;
if(temp==NULL)
return 0;
temp->nextnode=NULL;
temp->prenode=m_pTailNode;
temp->data=new T[m_nGrowBy];
if(temp->data==NULL)
return 0;
*temp->data=newElement;
m_pTailNode->nextnode=temp;
m_pTailNode=temp;
m_pCurNode=temp;
}
else
{
*(m_pTailNode->data+m_nCount%m_nGrowBy)=newElement;
m_pCurNode=m_pTailNode;
}
m_nCount++;
m_nCurIndex=m_nCount-1;
}
return m_nCurIndex;
}
//******************************************
// name:AddBatch
// function:批量添加数据
// input: T *pElement-源数组指针
// int count-数组大小
// return: BOOL TRUE－成功；FALSE－失败
// remark:
//******************************************
BOOL AddBatch(T *pElement,int count)
{
for(int i=0;i<count;i++)
if(Add(pElement[i])==-1)
return FALSE;
return TRUE;
}
//******************************************
// name:Copy
// function:数据复制
// input: CSArray & src-源动态数组
// return:
// remark: 使用前请先确保两个对象有相同的数据类型
//******************************************
void Copy(CSArray &src )
{
T *pt;
RemoveAll();
int size=src.GetSize();
SetSize(size);
for(int i=0;i<m_nCount;i++)
{
pt=src.GetPtAt(i);
SetAt(*pt,i);
}
}
//******************************************
// name:GetAt
// function:获取数组指定位置的数据
// input: int index-指定位置
// return: T 数据
// remark:
//******************************************
T GetAt(int index){
int offset=0;
SARRAYNODE *temp=NULL;
ASSERT(index>=0&&index<m_nCount);
temp=GetDestSegEntry(index);
m_pCurNode=temp;
m_nCurIndex=index;
return ((T *)temp->data)[index%m_nGrowBy];
}
//******************************************
// name:GetPtAt
// function:获取数组指定位置的数据的指针
// input: int index-指定位置
// return: T 数据
// remark: 提供对内部数据的直接访问，小心使用!!
//******************************************
T *GetPtAt(int index){
int offset=0;
SARRAYNODE *temp=NULL;
ASSERT(index>=0&&index<m_nCount);
temp=GetDestSegEntry(index);
m_pCurNode=temp;
m_nCurIndex=index;
return ((T *)temp->data)+index%m_nGrowBy;
}
T operator[](int index){ return GetAt(index);}
//******************************************
// name:GetSize
// function:获取数组的数据容量
// input:
// return: int 数据容量
// remark:
//******************************************
int GetSize(){return m_nCount;}
//******************************************
// name:SetAt
// function:修改数组指定位置的数据
// input: T newElement-新数据
// int index-指定索引号
// return: BOOL TURE-成功；FALSE－失败
// remark:
//******************************************
BOOL SetAt(int index,T &newElement)
{
int offset=0;
SARRAYNODE *temp=NULL;
if(index<0||index>m_nCount-1)
return FALSE;
temp=GetDestSegEntry(index);
m_pCurNode=temp;
*(m_pCurNode->data+index%m_nGrowBy)=newElement;
m_nCurIndex=index;
return TRUE;
}
//******************************************
// name:InsertAt
// function:在数组指定位置插入一个新数据
// input: int index-指定索引号
// T newElement-待插入的数据
// return: BOOL TURE-成功；FALSE－失败
// remark: 本接口关系到大量数据的迁移，不推荐大量使用
// 算法还有待进一步优化
//******************************************
BOOL InsertAt(int index,T newElement){
if(index<0||index>m_nCount)
return FALSE;
else if(index==m_nCount)
return Add(newElement);
else
{
T t;
Add(newElement);//enlarge buffer by one space
for(int i=m_nCount-1;i>index;i--)
{
t=GetAt(i-1);
SetAt(t,i);
}
SetAt(newElement,i);
return TRUE;
}
}
//******************************************
// name:RemoveAt
// function:删除数组中指定索引号中包含的数据
// input: int index-指定索引号
// return: BOOL TURE-成功；FALSE－失败
// remark: 本接口关系到大量数据的迁移，不推荐大量使用
// 算法还有待进一步优化
//******************************************
BOOL RemoveAt(int index){
SARRAYNODE *temp=NULL;
T t;
if(index<0||index>m_nCount)
return FALSE;
for(int i=index;i<m_nCount-1;i++)
{
t=GetAt(i+1);
SetAt(t,i);
}
m_nCurIndex=0;
m_pCurNode=m_pHeadNode;
m_nCount--;
if(m_nCount%m_nGrowBy==0)
{
temp=m_pTailNode;
m_pTailNode=m_pTailNode->prenode;
if(temp->data)
delete []temp->data;
delete (temp);
if(m_pTailNode==NULL)
m_pHeadNode=m_pCurNode=NULL;
else
m_pTailNode->nextnode=NULL;
}
return TRUE;
}
//******************************************
// name:SetGrowBy()
// function:设置数据增长幅度
// input:
// return:
// remark: 在初始化时使用
//******************************************
void SetGrowBy(int nGrowBy)
{
m_nGrowBy=nGrowBy;
}
//******************************************
// name:RemoveAll()
// function:清空对象中的数据
// input:
// return: BOOL TURE-成功；FALSE－失败
// remark:
//******************************************
BOOL RemoveAll(){
if(m_pHeadNode==NULL)
return TRUE;
Free();
m_pCurNode=m_pHeadNode=m_pTailNode=NULL;
m_nCurIndex=-1;
m_nCount=0;
return TRUE;
}
//******************************************
// name:SetSize()
// function:设置数据的容量
// input: int size -数据的容量
// return: BOOL TURE-成功；FALSE－失败
// remark:只允许扩大容量
//******************************************
BOOL SetSize(int size){
SARRAYNODE *temp=NULL;
int oldsegs=0,newsegs=0;
if(m_nCount>=size)
return 0;
oldsegs=(m_nCount+m_nGrowBy-1)/m_nGrowBy;
newsegs=(size+m_nGrowBy-1)/m_nGrowBy;
for(int i=oldsegs;i<newsegs;i++)
{
temp=new SARRAYNODE;
if(temp==NULL)
return FALSE;
temp->prenode=m_pTailNode;
temp->nextnode=NULL;
temp->data=new T[m_nGrowBy];
if(temp->data==NULL)
return FALSE;
if(m_pHeadNode!=NULL)
{
m_pTailNode->nextnode=temp;
m_pTailNode=temp;
}
else
{
m_pCurNode=m_pHeadNode=m_pTailNode=temp;
}
}
m_nCount=size;
//黄建雄 2003-7-27 修复潜在错误
if(m_nCurIndex==-1) m_nCurIndex=0;
return TRUE;
}
protected:
//******************************************
// name:GetDestSegEntry()
// function:获取数据所在链表的节点指针
// input: int index -数据索引
// return: SARRAYNODE * -数据所在链表的节点指针
// remark:内部使用，
//******************************************
SARRAYNODE * GetDestSegEntry(int index)
{
SARRAYNODE * ret=NULL;
int i=0;
if(index<m_nCurIndex/m_nGrowBy*m_nGrowBy)// dest data is in before cur data segment
{
if(m_nCurIndex/m_nGrowBy<2*(index/m_nGrowBy))
//find the seg from head;
{
ret=m_pHeadNode;
for(i=0;i<index/m_nGrowBy;i++)
ret=ret->nextnode;
}
else //find the seg from cur seg;
{
ret=m_pCurNode;
for(i=m_nCurIndex/m_nGrowBy;i>index/m_nGrowBy;i--)
ret=ret->prenode;
}
}
else if(index<(m_nCurIndex/m_nGrowBy+1)*m_nGrowBy)//in cur data seg
{
ret=m_pCurNode;
}
else //after cur data seg;
{
if((m_nCount-1)/m_nGrowBy+m_nCurIndex/m_nGrowBy>2*(index/m_nGrowBy))
//find the seg from cur;
{
ret=m_pCurNode;
for(i=m_nCurIndex/m_nGrowBy;i<index/m_nGrowBy;i++)
ret=ret->nextnode;
}
else //find the seg form tail;
{
ret=m_pTailNode;
for(i=(m_nCount-1)/m_nGrowBy;i>index/m_nGrowBy;i--)
ret=ret->prenode;
}
}
return ret;
}
//******************************************
// name:Free()
// function:释放对象占用的空间，
// input:
// return:void
// remark:内部使用,外部要清空对象请使用RemoveAll()接口
//******************************************
virtual void Free()
{
SARRAYNODE *temp1,*temp2;
temp1=m_pHeadNode;
while(temp1!=NULL)
{
temp2=temp1->nextnode;
if(temp1->data!=NULL)
delete []temp1->data;
delete (temp1);
temp1=temp2;
}
}
private:
int m_nCount; //数组对象包括的数据数
int m_nCurIndex; //当前的索引号
int m_nGrowBy; //每次增长的尺寸
SARRAYNODE * m_pCurNode; //链表中当前节点的指针，在数据检索时确定从向个方向搜索
SARRAYNODE * m_pHeadNode; //头节点
SARRAYNODE * m_pTailNode; //尾结点
};
#endif // !defined(AFX_SARRAY_H__B1D40C22_2698_4202_921E_36D447EA4199__INCLUDED_)
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -