?? 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 + -