qdlist.h

编写一个STL中的CString类

/******************************************************************
* 文件名:QDList.h
* 文件说明:双向链表类
* 版本:1.00
* 修改履历:junglesong 创建于2004年8月22日
******************************************************************/
#ifndef QDLIST_H
#define QDLIST_H

template <class T>
class QDList;

/*---双向链表节点类---*/
template <class T>
class QDListNode
{
	friend QDList<T>;
private:
	T data;
	QDListNode<T> *left,*right;
};

/*---双向链表类---*/
#include <iostream.h>
#define NULL 0

template <class T>
class QDList
{
public:
	QDList();
	~QDList();
	void RemoveAll();
	void Append(const T& newData);
	void OutputList(ostream& out) const;
	bool RemoveAt(int nPos);
	int	 GetLength() const;
	bool Search(const T& x,int& nPos);
	void Insert(int nPos,const T& x);
private:
	QDListNode<T>* LeftEnd;
	QDListNode<T>* RightEnd;
	int m_nLength;
};

/*---双向链表类::构造函数---*/
template <class T>
QDList<T>::QDList()
{
	LeftEnd=RightEnd=NULL;
	m_nLength=0;
}

/*---双向链表类::析构函数---*/
template <class T>
QDList<T>::~QDList()
{
	RemoveAll();	
}

/*---双向链表类::清空链表---*/
template <class T>
void QDList<T>::RemoveAll()
{
	QDListNode<T>* curr=LeftEnd;
	QDListNode<T>* next;

	while(curr!=RightEnd)
	{
		next=curr->right;
		delete curr;		
		curr=next;
	}

	if(RightEnd) delete RightEnd;

	LeftEnd=RightEnd=NULL;
	m_nLength=0;
};

/*---双向链表类::在链表尾部添加一个节点---*/
template <class T>
void QDList<T>::Append(const T& newData)
{
	QDListNode<T>* newNode=new QDListNode<T>;
	newNode->data=newData;
	newNode->right=NULL;

	if(LeftEnd)
	{
		newNode->left=RightEnd;
		RightEnd->right=newNode;
		RightEnd=newNode;
	}
	else
	{
		LeftEnd=RightEnd=newNode;
		newNode->left=newNode->right=NULL;
		LeftEnd=newNode;
	}

	m_nLength++;
}

/*---双向链表类::输出链表---*/
template <class T>
void QDList<T>::OutputList(ostream& out) const
{
	if(!LeftEnd || m_nLength==0)
	{
		out<<"Empty List!";
		return;
	}

	for(QDListNode<T>* curr=LeftEnd;curr!=RightEnd;curr=curr->right)
	{
		out<<curr->data<<"\t";
	}

	out<<RightEnd->data<<"\t";
}

/*---双向链表类::删除一个链表节点---*/
template <class T>
bool QDList<T>::RemoveAt(int nPos)
{
	if(m_nLength==0) 
	{
		LeftEnd=RightEnd=NULL;
		return false;
	}

	QDListNode<T>* curr;
	QDListNode<T>* next;

	if(nPos<=0)
	{
		curr=LeftEnd;
		next=curr->right;
		delete curr;
		LeftEnd=next;
	}
	else if(nPos>=m_nLength)
	{
		curr=RightEnd;
		next=curr->left;
		delete curr;
		RightEnd=next;
	}
	else
	{
		curr=LeftEnd;
		while(nPos)
		{
			curr=curr->right;
			nPos--;
		}

		next=curr->right;
		curr->left->right=next;
		next->left=curr->left;

		delete curr;
	}
	
	m_nLength--;
	return true;
};

/*---双向链表类::得到链表长度---*/
template <class T>
int	 QDList<T>::GetLength() const
{
	return m_nLength;
};

/*---双向链表类::在链表中查找一个元素---*/
template <class T>
bool QDList<T>::Search(const T& x,int& nPos) 
{
	QDListNode<T>* curr=LeftEnd;
	nPos=-1;
	
	while(curr)
	{
		nPos++;
		if(curr->data==x)
		{
			return true;
		}
		curr=curr->right;
	}
	
	nPos=-1;
	return false;	
};

/*---双向链表类::在nPos处插入x---*/
template <class T>
void QDList<T>::Insert(int nPos,const T& x)
{
	if(m_nLength==0)
	{
		Append(x);
		return;
	}

	QDListNode<T>* newNode=new QDListNode<T>;
	newNode->data=x;

	if(nPos<=0)
	{
		newNode->right=LeftEnd;
		newNode->left=newNode;
		LeftEnd=newNode;
	}
	else if(nPos>=m_nLength)
	{
		newNode->left=RightEnd;
		RightEnd->right=newNode;
		RightEnd=newNode;
	}
	else
	{
		QDListNode<T>* curr=LeftEnd;
		
		while(nPos>1)
		{
			nPos--;
			curr=curr->right;
		}

		QDListNode<T>* next=curr->right;
		newNode->left=curr;
		curr->right=newNode;
		newNode->right=next;
		next->left=newNode;
	}	

	m_nLength++;
};



#endif