seqlist.h

图的常用算法

#ifndef SEQUENTIAL_LIST
#define SEQUENTIAL_LIST

#include <iostream.h>
#include <iomanip.h>
#include <assert.h>

template <class T>
class SeqList
{
	protected:
		T *dataList;
		int maxListSize;
		int currPos;

	public:
		SeqList(int size=50);
		SeqList(const SeqList<T> & list);
		~SeqList();

		T & operator[](int index);
		int Length() const;

		int Find(const T & item) const;
		void Insert(const T & item);
		void Delete(const T & item);

		int IsEmpty() const;
		int IsFull() const;

		void Print()const;

		friend ostream & operator
			<<(ostream & os,const SeqList<T> & list);

};

template <class T>
SeqList<T>::SeqList(int size)
{
	assert(size>0);

	maxListSize=size;
	dataList=new T[maxListSize];
	assert(dataList!=NULL);
	currPos=-1;

}

template <class T>
SeqList<T>::SeqList(const SeqList<T> & list)
{
	assert(!list.IsEmpty());

	maxListSize=list.maxListSize;
	currPos=list.currPos;
	dataList=new T[maxListSize];

	for(int i=0;i<maxListSize;i++)
		dataList[i]=list.dataList[i];

}

template <class T>
SeqList<T>::~SeqList()
{
	delete []dataList;
	
	maxListSize=0;
	currPos=-1;
}

template <class T>
int SeqList<T>::Length() const
{
	return currPos+1;
}

template <class T>
int SeqList<T>::Find(const T &item)const
{
	for(int i=0;i<=currPos;i++)
		if(dataList[i]==item)
			return i;

		return -1;

}

template <class T>
int SeqList<T>::IsEmpty()const
{
	return currPos==-1;
}

template <class T>
int SeqList<T>::IsFull()const
{
	return currPos==maxListSize;
}

template <class T>
T & SeqList<T>::operator[](int index)
{
	assert(index >=0&&index<=currPos);
	return dataList[index];
}

template <class T>
void SeqList<T>::Insert(const T & item)
{
	if(IsFull())
	{
		cout<<"SeqList is Full!"<<endl;
		return;
	}
	currPos++;
	dataList[currPos]=item;
}

template <class T>
void SeqList<T>::Delete(const T & item)
{
	int i;
	if(i=Find(item)!=-1)
	{
		for(int j=i;j<currPos;j++)
			dataList[j]=dataList[j+1];

		currPos--;
	}
}

template <class T>
void SeqList<T>::Print() const
{
	for(int i=0;i<=currPos;i++)
	{
		if(i%10==0&&i!=0)
			cout<<endl;
		cout<<setw(5)<<dataList[i];
	}
}

template <class T>
ostream & operator<<(ostream & os,const SeqList<T> & list)
{
	list.Print();
	return os;
}

#endif