klds.h

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

/************************************************************************************************
	文件名：klds.h
	模板链栈，模板链队列，模板有向图
	创建于2003-5-10 
	作者:吴振华(kylinx)(中国科大01级11系)
	E-mail:[e-mail]
	最后修改于2003-5-10
*************************************************************************************************/
#ifndef KL_DATA_STRUCTURE_H_
#define KL_DATA_STRUCTURE_H_
#include<windows.h>
template<class T>
class KGDQueue
{
public:
	virtual bool DeQueue(T & data)=0;											//出队
	virtual bool EnQueue(const T & data)=0;										//入队
	virtual bool GetHead(T & data)=0;											//得到队头的数据（并不从队列中删除）
	virtual bool GetTail(T & data)=0;											//得到队尾的数据（并不从队列中删除）
	virtual unsigned long GetLength() const=0;									//得到队列长度
	virtual void Clear()=0;														//清空队列

	virtual bool InsertHead(const T & data)=0;									//在头部插入（非正式入队,即插队）
	
	static KGDQueue<T>* ForeCreate();
};
template<class T>
class CPriorityQueue
{
public:
	virtual bool EnQueue(const T & data,unsigned long dwPriority)=0;
	virtual bool DeQueue(T & data)=0;
	virtual unsigned long GetLength() const=0;
	virtual void Clear()=0;

	static CPriorityQueue<T>* ForeCreate();
};
template<class T>
class CLagQueue
{
public:
	virtual bool EnQueue(const T & data,unsigned long dwPriority)=0;
	virtual bool DeQueue(T & data)=0;
	virtual unsigned long GetLength() const=0;
	virtual void Clear()=0;

	static CLagQueue<T>* ForeCreate();
};
template<class T>
class KGDList
{
public:
	virtual BOOL Insert(const T & data,int ID)=0;
	virtual BOOL Delete(int ID)=0;
	virtual BOOL GetHead(T & data)=0;
	virtual BOOL GetAndMovePointToNext(T & data)=0;
	virtual BOOL FindData(int id,T & data)=0;
	virtual BOOL ResetToHead()=0;
	virtual DWORD GetCurAddress()=0;
	virtual void SetCurAddress(DWORD dwAddr)=0;
	virtual unsigned long GetCount() const=0;
	virtual void Clear()=0;

	static KGDList<T>* ForeCreate();
};
template<class T>
class KGDStack
{
public:
	virtual bool Push(const T & data)=0;										//入栈
	virtual bool Pop(T & data)=0;												//出栈
	virtual bool GetTop(T & data)=0;											//得到栈顶数据
	virtual bool GetBottom(T & data)=0;											//得到栈低数据
	virtual unsigned long GetLength() const=0;									//得到栈的深度
	virtual void Clear()=0;														//清空栈
	
	virtual bool InsertBottom(const T & data)=0;								//从栈底插入

	static KGDStack<T>* ForeCreate();
};

//KGDQueue的子类
template<class T>
class KGDQueueChild:private KGDQueue<T>
{
	template<class T>
	class KGDQNode
	{
	public:
		T data;
		KGDQNode<T>*next;
		KGDQNode(){next=NULL;}
		~KGDQNode(){}
	};
	
	unsigned long m_nLength;

	KGDQNode<T>*m_pTop;
	KGDQNode<T>*m_pBottom;
	
	bool DeQueue(T & data);
	bool EnQueue(const T & data);
	bool GetHead(T & data);
	bool GetTail(T & data);
	unsigned long GetLength()const;
	void Clear();

	bool InsertHead(const T & data);
public:
	KGDQueueChild();
	virtual ~KGDQueueChild();
};
template<class T>
unsigned long KGDQueueChild<T>::GetLength() const
{
	return m_nLength;
}
template<class T>
void KGDQueueChild<T>::Clear()
{
	KGDQNode<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 KGDQueueChild<T>::InsertHead(const T & data)
{
	KGDQNode<T>*pTemp=new KGDQNode<T>();
	pTemp->data=data;

	m_nLength++;
	if(!m_pTop)
	{
		m_pTop=pTemp;
		return true;
	}
	pTemp->next=m_pTop;
	m_pTop=pTemp;
	return true;
}
template<class T>
bool KGDQueueChild<T>::GetHead(T & data)
{
	if(!m_pTop)
		return false;
	data=m_pTop->data;
	return true;
}
template<class T>
bool KGDQueueChild<T>::GetTail(T & data)
{
	if(!m_pBottom)
		return false;
	data=m_pBottom->data;
	return true;
}
template<class T>
bool KGDQueueChild<T>::EnQueue(const T & data)
{
	KGDQNode<T>*pTemp=new KGDQNode<T>();
	pTemp->data=data;

	if(!pTemp)
		return false;
	m_nLength++;
	if(!m_pTop)
	{
		m_pTop=pTemp;
		m_pBottom=pTemp;
		return true;
	}
	m_pBottom->next=pTemp;
	m_pBottom=m_pBottom->next;
	return true;
}
template<class T>
bool KGDQueueChild<T>::DeQueue(T & data)
{
	if(!m_pTop)
		return false;
	m_nLength--;
	data=m_pTop->data;

	KGDQNode<T>*pTemp=m_pTop;
	m_pTop=m_pTop->next;
	if(pTemp==m_pBottom)
		m_pBottom=NULL;
	delete pTemp;
	
	return true;
}
template<class T>
KGDQueueChild<T>::KGDQueueChild()
{
	m_pTop=NULL;
	m_pBottom=NULL;
	m_nLength=0;
}
template<class T>
KGDQueueChild<T>::~KGDQueueChild()
{
	Clear();
}
template<class T>
KGDQueue<T>*KGDQueue<T>::ForeCreate()
{
	return new KGDQueueChild<T>();
}
//////////////////////////////////////////////////////////////////////////////////////////////
template<class T>
class KGDListChild:private KGDList<T>
{
	template<class T>
	class KGDListNode
	{
	public:
		int nID;
		T data;
		KGDListNode<T>*pNext;

		KGDListNode(int id,const T & tdata,KGDListNode<T>*next=NULL)
		{
			nID=id;
			this->data=tdata;
			pNext=next;
		}
		~KGDListNode(){}
	};

	KGDListNode<T>	*m_pHead;
	KGDListNode<T>	*m_pTail;
	KGDListNode<T>	*m_pCur;
	unsigned long m_dwNodeCount;

	virtual BOOL Insert(const T & data,int ID);
	virtual BOOL Delete(int ID);
	virtual BOOL GetHead(T & data);
	virtual BOOL GetAndMovePointToNext(T & data);
	virtual BOOL FindData(int id,T & data);
	virtual BOOL ResetToHead();
	virtual DWORD GetCurAddress();
	virtual void SetCurAddress(DWORD dwAddr);
	virtual unsigned long GetCount() const {return m_dwNodeCount;}
	virtual void Clear();
public:
	KGDListChild();
	virtual ~KGDListChild();
};
template<class T>
KGDList<T>*KGDList<T>::ForeCreate()
{
	return new KGDListChild<T>();
}
template<class T>
DWORD KGDListChild<T>::GetCurAddress() 
{
	return (DWORD)m_pCur;
}
template<class T>
void KGDListChild<T>::SetCurAddress(DWORD dwAddr) 
{
	m_pCur=(KGDListNode<T>*)dwAddr;
}
template<class T>
KGDListChild<T>::KGDListChild()
{
	m_pHead=NULL;
	m_pCur=NULL;
	m_pTail=NULL;
	m_dwNodeCount=0;
}
template<class T>
KGDListChild<T>::~KGDListChild()
{
	Clear();
}
template<class T>
void KGDListChild<T>::Clear()
{
	KGDListNode<T>*pTemp;
	while(m_pHead)
	{
		pTemp=m_pHead;
		m_pHead=m_pHead->pNext;
		delete pTemp;
	}
	m_pTail=NULL;
	m_dwNodeCount=0;
	m_pCur=NULL;
}
template<class T>
BOOL KGDListChild<T>::FindData(int id,T & data)
{
	KGDListNode<T>*pTemp=m_pHead;
	while(pTemp)
	{
		if(pTemp->nID==id)
		{
			data=pTemp->data;
			return true;
		}
		pTemp=pTemp->pNext;
	}
	return false;
}
template<class T>
BOOL KGDListChild<T>::GetHead(T & data)
{
	if(!m_pHead)
		return false;
	data=m_pHead->data;
	return true;
}
template<class T>
BOOL KGDListChild<T>::GetAndMovePointToNext(T & data)
{
	if(m_pCur)
	{
		data=m_pCur->data;
		m_pCur=m_pCur->pNext;
		return true;
	}
	return false;
}
template<class T>
BOOL KGDListChild<T>::ResetToHead()
{
	m_pCur=m_pHead;
	return true;
}
template<class T>
BOOL KGDListChild<T>::Insert(const T & data,int ID)
{
	KGDListNode<T>*pNodeInsert=new KGDListNode<T>(ID,data,NULL);
	if(!pNodeInsert)
		return false;
	
	m_dwNodeCount++;

	if(!m_pHead)
	{
		m_pHead=pNodeInsert;
		m_pTail=pNodeInsert;
		return true;
	}
	if(!m_pHead->pNext)
	{
		m_pHead->pNext=pNodeInsert;
		m_pTail=m_pHead->pNext;
		return true;
	}
	m_pTail->pNext=pNodeInsert;
	m_pTail=m_pTail->pNext;

	return true;
}
template<class T>
BOOL KGDListChild<T>::Delete(int ID)
{
	if(m_pHead)
	{
		if(m_pHead->nID==ID)
		{
			if(m_pTail==m_pHead)
			{
				m_pTail=m_pHead->pNext;
			}
			KGDListNode<T>*pTemp=m_pHead;
			m_pHead=m_pHead->pNext;
			delete pTemp;

			m_dwNodeCount--;
			return true;
		}
	}
	KGDListNode<T>*pTemp=m_pHead->pNext;
	KGDListNode<T>*pNodePrev=m_pHead;
	
	while(pTemp)
	{
		if(pTemp->nID==ID)
		{
			 if(pTemp==m_pTail)
			 {
				 m_pTail=pNodePrev;
			 }
			 pNodePrev->pNext=pTemp->pNext;
			 delete pTemp;
		
			 m_dwNodeCount--;
			 return true;
		}
		pNodePrev=pTemp;
		pTemp=pTemp->pNext;
	}
	return false;
}
//////////////////////////////////////////////////////////////////////////////////////////////
template<class T>
class CPriorityQueueChild:private CPriorityQueue<T>
{
	template<class T>
	class CPQNode
	{
	public:
		T data;
		unsigned long Priority;
		CPQNode<T>*next;
		CPQNode<T>(T dt,unsigned long Prior,CPQNode<T>*next){data=dt;Priority=Prior;this->next=next;}
		CPQNode(){next=NULL;}
		~CPQNode(){}
	};
	CPQNode<T>*m_pHead;
	unsigned long m_nLength;
	virtual bool EnQueue(const T & data,unsigned long dwPriority);
	virtual bool DeQueue(T & data);
	virtual unsigned long GetLength() const {return m_nLength;}
	virtual void Clear();
public:
	CPriorityQueueChild();
	virtual ~CPriorityQueueChild();
};
template<class T>
CPriorityQueueChild<T>::CPriorityQueueChild()
{
	m_pHead=NULL;
	m_nLength=0;
}
template<class T>
CPriorityQueueChild<T>::~CPriorityQueueChild()
{
	Clear();
}
template<class T>
CPriorityQueue<T>*CPriorityQueue<T>::ForeCreate()
{
	return new CPriorityQueueChild<T>();
}
template<class T>
bool CPriorityQueueChild<T>::EnQueue(const T &data,unsigned long dwPriority)
{
	if(!m_pHead)
	{
		m_pHead=new CPQNode<T>(data,dwPriority,NULL);
		if(!m_pHead)
			return false;
		m_nLength=1;
		return true;
	}
	CPQNode<T>*pNodeInsert=new CPQNode<T>(data,dwPriority,NULL);
	if(!pNodeInsert)
		return false;
	CPQNode<T>*pTemp=m_pHead;
	CPQNode<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 CPriorityQueueChild<T>::DeQueue(T & data)
{
	if(!m_pHead)
		return false;
	CPQNode<T>*pTemp=m_pHead;
	data=m_pHead->data;
	m_pHead=m_pHead->next;
	delete pTemp;
	m_nLength--;
	return true;
}
template<class T>
void CPriorityQueueChild<T>::Clear()
{
	CPQNode<T>*pTemp;
	while(m_pHead)
	{
		pTemp=m_pHead;
		m_pHead=m_pHead->next;
		delete pTemp;
	}
	m_nLength=0;
}
//////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////
template<class T>
class CLagQueueChild:private CLagQueue<T>
{
	template<class T>
	class CLQNode
	{
	public:
		T data;
		unsigned long Priority;
		CLQNode<T>*next;
		CLQNode<T>(T dt,unsigned long Prior,CLQNode<T>*next){data=dt;Priority=Prior;this->next=next;}
		CLQNode(){next=NULL;}
		~CLQNode(){}
	};
	CLQNode<T>*m_pHead;
	unsigned long m_nLength;
	virtual bool EnQueue(const T & data,unsigned long dwPriority);
	virtual bool DeQueue(T & data);
	virtual unsigned long GetLength() const {return m_nLength;}
	virtual void Clear();
public:
	CLagQueueChild();
	virtual ~CLagQueueChild();
};
template<class T>
CLagQueueChild<T>::CLagQueueChild()
{
	m_pHead=NULL;
	m_nLength=0;
}