klds.h

一个个人开发的rpg游戏＜亚特兰蒂斯传奇＞的源码

template<class T>
CLagQueueChild<T>::~CLagQueueChild()
{
	Clear();
}
template<class T>
CLagQueue<T>*CLagQueue<T>::ForeCreate()
{
	return new CLagQueueChild<T>();
}
template<class T>
bool CLagQueueChild<T>::EnQueue(const T &data,unsigned long dwPriority)
{
	if(!m_pHead)
	{
		m_pHead=new CLQNode<T>(data,dwPriority,NULL);
		if(!m_pHead)
			return false;
		m_nLength=1;
		return true;
	}
	CLQNode<T>*pNodeInsert=new CLQNode<T>(data,dwPriority,NULL);
	if(!pNodeInsert)
		return false;
	CLQNode<T>*pTemp=m_pHead;
	CLQNode<T>*pNode=m_pHead;
	while(pTemp)
	{
		if(pTemp->Priority <= dwPriority)
		{
			pNode=pTemp;
			pTemp=pTemp->next;
		}
		else
			break;
	}
	if(pTemp==m_pHead)
	{
		pNodeInsert->next=m_pHead;
		m_pHead=pNodeInsert;
		m_nLength++;
		return true;
	}
	m_nLength++;
	pTemp=pNode->next;
	pNode->next=pNodeInsert;
	pNodeInsert->next=pTemp;
	
	return true;
}
template<class T>
bool CLagQueueChild<T>::DeQueue(T & data)
{
	if(!m_pHead)
		return false;
	CLQNode<T>*pTemp=m_pHead;
	data=m_pHead->data;
	m_pHead=m_pHead->next;
	delete pTemp;
	m_nLength--;
	return true;
}
template<class T>
void CLagQueueChild<T>::Clear()
{
	CLQNode<T>*pTemp;
	while(m_pHead)
	{
		pTemp=m_pHead;
		m_pHead=m_pHead->next;
		delete pTemp;
	}
	m_nLength=0;
}
//////////////////////////////////////////////////////////////////////////////////////////////
template<class T>
class KGDStackChild:private KGDStack<T>
{
	template<class T>
	class KGDSNode
	{
	public:
		T data;
		KGDSNode<T>*next;
		KGDSNode(){next=NULL;}
		~KGDSNode(){}
	};
	
	unsigned long m_nLength;

	KGDSNode<T>*m_pTop;
	KGDSNode<T>*m_pBottom;
	
	bool Pop(T & data);
	bool Push(const T & data);
	bool GetTop(T & data);
	bool GetBottom(T & data);
	unsigned long GetLength() const;
	void Clear();

	bool InsertBottom(const T & data);
public:
	KGDStackChild();
	virtual ~KGDStackChild();
};

template<class T>
KGDStack<T>*KGDStack<T>::ForeCreate()
{
	return new KGDStackChild<T>();
}
template<class T>
unsigned long KGDStackChild<T>::GetLength() const
{
	return m_nLength;
}
template<class T>
void KGDStackChild<T>::Clear()
{
	KGDSNode<T>*pTemp=NULL;
	while(m_nLength)
	{
		m_nLength--;
		pTemp=m_pTop;
		m_pTop=m_pTop->next;
		delete pTemp;
	}
	m_pTop=NULL;
	m_pBottom=NULL;
}
template<class T>
bool KGDStackChild<T>::Push(const T & data)
{
	KGDSNode<T>*pTemp=new KGDSNode<T>();
	if(!pTemp)
		return false;
	pTemp->data=data;
	
	m_nLength++;
	if(!m_pBottom)
		m_pBottom=pTemp;
	pTemp->next=m_pTop;
	m_pTop=pTemp;

	return true;
}
template<class T>
bool KGDStackChild<T>::Pop(T & data)
{
	if(!m_pTop)
		return false;
	m_nLength--;

	KGDSNode<T>*pTemp=m_pTop;
	data=m_pTop->data;
	m_pTop=m_pTop->next;
	if(pTemp==m_pBottom)
		m_pBottom=NULL;
	delete pTemp;
	
	return true;
}
template<class T>
bool KGDStackChild<T>::GetTop(T & data)
{
	if(!m_pTop)
		return false;
	data=m_pTop->data;
	return true;
}
template<class T>
bool KGDStackChild<T>::GetBottom(T & data)
{
	if(!m_pBottom)
		return false;
	data=m_pBottom->data;
	return true;
}
template<class T>
bool KGDStackChild<T>::InsertBottom(const T & data)
{
	KGDSNode<T>*pTemp=new KGDSNode<T>();
	pTemp->data=data;
	if(!pTemp)
		return false;
	m_nLength++;

	if(!m_pBottom)
	{
		m_pBottom=pTemp;
		return true;
	}
	m_pBottom->next=pTemp;
	m_pBottom=m_pBottom->next;

	return true;
}
template<class T>
KGDStackChild<T>::KGDStackChild()
{
	m_pTop=NULL;
	m_pBottom=NULL;
	m_nLength=0;
}
template<class T>
KGDStackChild<T>::~KGDStackChild()
{
	Clear();
}
//////////////////////////////////////////////////////////////////////////////////////////////////
//图：组成结构：邻接表
//////////////////////////////////////////////////////////////////////////////////////////////////
template<class NodeType,class InfoType>
class CGraphChild
{
private:
	template<class NodeType,class InfoType>
	class CArcNode
	{
	public:
		int m_nAdjVex;													//弧指向的顶点标识
		CArcNode<NodeType,InfoType>*m_pNextArc;							//弧
		InfoType m_pArcInfo;											//弧信息

		CArcNode(){m_pNextArc=NULL;m_pArcInfo=NULL;}
		~CArcNode(){}
	};

	template<class NodeType,class InfoType>
	class CNode
	{
	public:
		NodeType m_data;												//节点数据（顶点数据）
		CArcNode<NodeType,InfoType>*m_pFirstArc;						//从本顶点出发的第一条弧
		CNode(){m_pFirstArc=NULL;}
	};
private:
	CNode<NodeType,InfoType>*m_pNode;									//节点的集合

	int *m_pVexArray;													//顶点标识的数组
	int m_nVexCount;													//当前顶点数量
	int m_nMaxVexCount;													//最大的顶点数量
	int m_nArcCount;													//弧的数量
 													
public:
	bool IsVexInGraph(int nVex,int &pos);								//顶点nVex是否存在于顶点标识数组中，如果存在，pos返回所在数组的位置

	bool AddVex(int nVex,NodeType data);								//加入一个顶点
	bool AddArc(int nVexFrom,int nVexTo,const InfoType& info);			//在顶点VexFrom和VexTo中加入一条弧
	bool DelVex(int nVex);												//删除顶点nVex同时删除与之关联的弧
	bool DelArc(int nVexFrom,int nVexTo);								//删除从nVexFrom到nVexTo的弧
	bool DelAllArcLinkWithVex(int nVex);								//删除与nVex相关联的弧
	void Release();														//释放整个图
	
	bool GetVexData(int nVex,NodeType&data);							//得到顶点nVex的信息
	bool GetArcInfo(int nVexFrom,int nVexTo,InfoType &info);			//得到从nVexFrom到nVexTo的弧的信息
	bool SetArcInfo(int nVexFrom,int nVexTo,const InfoType& info);		//设置从nVexFrom到nVexTo的弧的信息

	int GetArcCount() const;											//得到弧数量
	int GetVexCount() const;											//得到顶点数量


 
public:
 	CGraphChild();
	virtual ~CGraphChild();
};

template<class NodeType,class InfoType>
CGraphChild<NodeType,InfoType>::CGraphChild()
{
	m_pVexArray=NULL;
	m_nVexCount=0;
	m_nMaxVexCount=0;
	m_nArcCount=0;
	m_iType=NULL;
	m_pNode=NULL;
}

template<class NodeType,class InfoType>
CGraphChild<NodeType,InfoType>::~CGraphChild()
{
	Release();
}
template<class NodeType,class InfoType>
int CGraphChild<NodeType,InfoType>::GetArcCount() const
{
	return m_nArcCount;
}
template<class NodeType,class InfoType>
int CGraphChild<NodeType,InfoType>::GetVexCount() const
{
	return m_nVexCount;
}
template<class NodeType,class InfoType>
void CGraphChild<NodeType,InfoType>::Release()
{
	if(m_pVexArray)
	{
		delete [] m_pVexArray;
		m_pVexArray=NULL;
	}
	CArcNode<NodeType,InfoType>*pTemp=NULL;
	for(int i=0;i<m_nVexCount;i++)
	{
		pTemp=m_pNode[i].m_pFirstArc;
		while(pTemp)
		{
			pTemp=pTemp->m_pNextArc;
			delete m_pNode[i].m_pFirstArc;
			m_pNode[i].m_pFirstArc=pTemp;
		}
	}
	m_nVexCount=0;
	m_nMaxVexCount=0;
	m_nArcCount=0;
	m_iType=NULL;
}

template<class NodeType,class InfoType>
bool CGraphChild<NodeType,InfoType>::AddArc(int nVexFrom,int nVexTo,const InfoType& Info)
{
	int posFrom,posTo;
	if(!IsVexInGraph(nVexFrom,posFrom))
		return false;
	if(!IsVexInGraph(nVexTo,posTo))
		return false;
	CArcNode<NodeType,InfoType>*pTemp=m_pNode[posFrom].m_pFirstArc;
	CArcNode<NodeType,InfoType>*pTempFront=pTemp;
	
	while(pTemp)
	{
		if(pTemp->m_nAdjVex==nVexTo)
			return false;
		pTempFront=pTemp;
		pTemp=pTemp->m_pNextArc;
	}
	pTemp=new CArcNode<NodeType,InfoType>();
	if(!pTemp)
		return false;
	pTemp->m_pArcInfo=Info;
	pTemp->m_nAdjVex=nVexTo;
	pTemp->m_pNextArc=NULL;
	if(pTempFront)
		pTempFront->m_pNextArc=pTemp;
	else
		m_pNode[posFrom].m_pFirstArc=pTemp;

	m_nArcCount++;
	return true;
}
template<class NodeType,class InfoType>
bool CGraphChild<NodeType,InfoType>::SetArcInfo(int nVexFrom,int nVexTo,const InfoType& info)
{
	int posFrom,posTo;
	if(!IsVexInGraph(nVexFrom,posFrom))
		return false;
	if(!IsVexInGraph(nVexTo,posTo))
		return false;
	CArcNode<NodeType,InfoType>*pTemp=m_pNode[posFrom].m_pFirstArc;
	while(pTemp)
	{
		if(pTemp->m_nAdjVex==nVexTo)
		{
			pTemp->m_pArcInfo=info;
			return true;
		}
		pTemp=pTemp->m_pNextArc;
	}
	return false;
}
template<class NodeType,class InfoType>
bool CGraphChild<NodeType,InfoType>::GetArcInfo(int nVexFrom,int nVexTo,InfoType &info)
{
	int posFrom,posTo;
	if(!IsVexInGraph(nVexFrom,posFrom))
		return false;
	if(!IsVexInGraph(nVexTo,posTo))
		return false;
	CArcNode<NodeType,InfoType>*pTemp=m_pNode[posFrom].m_pFirstArc;
	while(pTemp)
	{
		if(pTemp->m_nAdjVex==nVexTo)
		{
			info=pTemp->m_pArcInfo;
			return true;
		}
		pTemp=pTemp->m_pNextArc;
	}
	return false;
}
template<class NodeType,class InfoType>
bool CGraphChild<NodeType,InfoType>::GetVexData(int nVex,NodeType&data)
{
	int iPos;
	if(!IsVexInGraph(nVex,iPos))
		return false;
	data=m_pNode[iPos].m_data;
	return true;
}
template<class NodeType,class InfoType>
bool CGraphChild<NodeType,InfoType>::DelAllArcLinkWithVex(int nVex)
{
	for(int i=0;i<m_nVexCount;i++)
	{
		DelArc(m_pVexArray[i],nVex);
		DelArc(nVex,m_pVexArray[i]);
	}
	return true;
}
template<class NodeType,class InfoType>
bool CGraphChild<NodeType,InfoType>::DelVex(int nVex)
{
	int iPos;
	if(!IsVexInGraph(nVex,iPos))
		return false;

	DelAllArcLinkWithVex(nVex);
 	
	m_nVexCount--;
	for(int i=iPos;i<m_nVexCount;i++)
	{
		m_pVexArray[i]=m_pVexArray[i+1];
		m_pNode[i]=m_pNode[i+1];
	}
	if(m_nMaxVexCount-m_nVexCount>16)
	{
		m_nMaxVexCount-=16;
		m_pNode=(CNode<NodeType,InfoType>*)realloc(m_pNode,sizeof(CNode<NodeType,InfoType>)*m_nMaxVexCount);
		m_pVexArray=(int*)realloc(m_pVexArray,sizeof(int)*m_nMaxVexCount);
	}
 	return true;
}
template<class NodeType,class InfoType>
bool CGraphChild<NodeType,InfoType>::DelArc(int nVexFrom,int nVexTo)
{
	int posFrom,posTo;
	if(!IsVexInGraph(nVexFrom,posFrom))
		return false;
	if(!IsVexInGraph(nVexTo,posTo))
		return false;
	CArcNode<NodeType,InfoType>*pTemp=m_pNode[posFrom].m_pFirstArc;
	CArcNode<NodeType,InfoType>*pTempFront=pTemp;
	
	if(pTemp)
	{
		if(pTemp->m_nAdjVex==nVexTo)
		{
			pTemp=pTemp->m_pNextArc;
			delete pTempFront;
			pTempFront=NULL;
			m_pNode[posFrom].m_pFirstArc=pTemp;
			m_nArcCount--;
			return true;
		}
		else
			pTemp=pTemp->m_pNextArc;
	}
	while(pTemp)
	{
		if(pTemp->m_nAdjVex==nVexTo)
		{
			pTempFront->m_pNextArc=pTemp->m_pNextArc;
			delete pTemp;
			pTemp=NULL;
			m_nArcCount--;
			return true;
		}
		else
		{
			pTempFront=pTemp;
			pTemp=pTemp->m_pNextArc;
		}
	}
	return false;
}
template<class NodeType,class InfoType>
bool CGraphChild<NodeType,InfoType>::IsVexInGraph(int nVex,int&pos)
{
	int low=0;
	int high=m_nVexCount-1;
	int mid;
	while(low<=high)
	{
		mid=(low+high)>>1;
		if(nVex==m_pVexArray[mid])
		{
			pos=mid;
			return true;
		}
		else if(nVex<m_pVexArray[mid])
		{
			high=mid-1;
		}
		else
			low=mid+1;
	}
	return false;
}
template<class NodeType,class InfoType>
bool CGraphChild<NodeType,InfoType>::AddVex(int nVex,NodeType data)
{
	for(int i=0;i<m_nVexCount;i++)
	{
		if(m_pVexArray[i]==nVex)
			return false;
		else if(m_pVexArray[i]>nVex)
		{
			break;
		}
	}
	m_nVexCount++;
	if(m_nVexCount>=m_nMaxVexCount)
	{
		m_nMaxVexCount+=16;
		int *pTemp=m_pVexArray;
		CNode<NodeType,InfoType>*pNodeTemp=m_pNode;
	
		m_pNode=(CNode<NodeType,InfoType>*)realloc(m_pNode,sizeof(CNode<NodeType,InfoType>)*m_nMaxVexCount);
		m_pVexArray=(int*)realloc(m_pVexArray,sizeof(int)*m_nMaxVexCount);
		if(!m_pVexArray || !m_pNode)
		{
			m_pVexArray=pTemp;
			m_pNode=pNodeTemp;
			return false;
		}	
	}
	for(int j=m_nVexCount-1;j>i;j--)
	{
		m_pVexArray[j]=m_pVexArray[j-1];
		m_pNode[j]=m_pNode[j-1];
	}
	m_pVexArray[i]=nVex;
	m_pNode[i].m_data=data;
	m_pNode[i].m_pFirstArc=NULL;


	return true;
}

#endif