qlist.h

编写一个STL中的CString类

#ifndef QLIST_H
#define QLIST_H

#include <iostream.h>
#define NULL 0

template <class T>
class QList;

// 链表节点类定义
template <class T>
class QListNode
{
	friend QList<T>;
private:
	T data;
	QListNode<T>* link;
};

// 链表定义
template <class T>
class QList 
{
public:
	QList(){ first=NULL;};
	~QList();
public:
	QList<T>& Append(const T& x);
	int GetLength() const;
	void Output() const;	
	bool Search(const T& x,int& nPos);
	bool Insert(int nPos,const T& x);
	T At(int nPos);
	void Remove(int& nPos);
	void Remove(const T& x);
	void RemoveAll();
	T& operator[](int nPos);
	void Sort();
private:
	QListNode<T>* first;
};

// 链表析构
template <class T>
QList<T>::~QList()
{
	RemoveAll();
};

// 清空链表
template <class T>
void QList<T>::RemoveAll()
{
	QListNode<T>* nextNode;
	
	while(first)
	{
		nextNode=first->link;
		delete first;
		first=nextNode;
	};
};

// 向链表尾部加上一个元素
template <class T>
QList<T>& QList<T>::Append(const T& x)
{
	QListNode<T>* newNode=new QListNode<T>;
	newNode->data=x;

	// 当首节点不为空时
	if(first!=NULL)
	{
		QListNode<T>* tmpNode=first;
		
		while(tmpNode->link!=NULL)
		{
			tmpNode=tmpNode->link;
		}		
		
		tmpNode->link=newNode;
		newNode->link=NULL;
	}

	// 当首节点为空时
	if(first==NULL)
	{
		first=newNode;
		first->link=NULL;
	}

	return *this;
};

// 输出链表
template <class T>
void QList<T>::Output() const
{
	QListNode<T>* current;
	for(current=first;current;current=current->link)
	{
		cout<<current->data<<" ";
	}

	cout<<endl;
};

// 得到链表长度
template <class T>
int QList<T>::GetLength() const
{
	int nLen=0;
	QListNode<T>* current;
	for(current=first;current;current=current->link)
	{
		nLen++;
	}

	return nLen;
};

// 在链表中寻找值为x的节点
template <class T>
bool QList<T>::Search(const T& x,int& nPos) 
{
	nPos=0;

	QListNode<T>* current;
	for(current=first;current;current=current->link)
	{
		if(current->data==x)
		{
			return true;
		}
		nPos++;
	}
	
	return false;
};

// 在nPos处插入x
template <class T>
bool QList<T>::Insert(int nPos,const T& x)
{
	if(nPos<0 || nPos>GetLength()) return false;

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

	QListNode<T>* p;

	if(nPos==0)
	{
		newNode->link=first;
		first=newNode;	
	}
	else if(nPos==GetLength())
	{
		p=first;

		while(p->link!=NULL)
		{
			p=p->link;
		}

		newNode->link=NULL;
		p->link=newNode;
	}
	else
	{
		p=first;
		nPos--;

		while(nPos>0)
		{
			p=p->link;
			nPos--;
		}

		newNode->link=p->link->link;
		p->link=newNode;
	}

	return true;
}

// 删除一个节点
template <class T>
void QList<T>::Remove(int& nPos) 
{
	if(nPos<0 || nPos>GetLength()-1) return;

	QListNode<T>* p=first;

	if(nPos==0)
	{
		p=first->link;
		delete first;
		first=p;		
	}
	else
	{
		QListNode<T>* current=first;		
		nPos--;

		while(nPos>0)
		{
			current=current->link;
			nPos--;
		}

		if(current->link->link==NULL)
		{
			delete current->link;
			current->link=NULL;
		}
		else
		{
			p=current->link->link;
			delete current->link;
			current->link=p;
		}
	}	
};

// 删除一批值为x的节点
template <class T>
void QList<T>::Remove(const T& x)
{
	int nPos;
	while(Search(x,nPos))
	{
		Remove(nPos);
	}
};

// 得到位于nPos的节点
template <class T>
T QList<T>::At(int nPos)
{
	QListNode<T>* p=first;

	while(nPos>0)
	{
		nPos--;
		p=p->link;
	}
	
	return p->data;
};

// 重载[]操作符,得到位于nPos的节点的引用
template <class T>
T& QList<T>::operator[](int nPos)
{
	QListNode<T>* p=first;
	
	while(nPos>0)
	{
		nPos--;
		p=p->link;
	}
	
	return p->data;
};

// 链表排序
template <class T>
void QList<T>::Sort()
{
	int i,j;
	int nLen=GetLength();

	T& c=operator[5];


	
/*	for(j=1;j<nLen;j++)
	{
		for(i=0;i<nLen-j;i++)
		{
			if(this[i] = this[i+1] )
			{
				T tmp;
				tmp=this[i+1];
				this[i+1]=this[i];
				this[i]=tmp;
			}
		}
	}*/
};

#endif