seqlist.cpp

一个关于数据结构链表的小程序

#include<iostream.h>

//LinearList----------------------------------------------
template <class T>
class LinearList
{
	public:
		virtual bool Insert(int i,T x)=0;
		virtual bool Delete(const T &x)=0;
		virtual void Reverse()=0;
		virtual void Output(ostream& out)const=0;
	protected:
		int n;
};

//SeqList----------------------------------------------
template <class T>
class SeqList:public LinearList<T>
{
	public:
		SeqList(int mSize);
		~SeqList() {delete []elements;}
		bool Insert(int i,T x);           //将X插入下标为i的元素后面
		void Reverse();                   //将顺序表逆置
		bool Delete(const T &x);          //删除表中所有元素值为X的元素
		void Output(ostream& out)const;   //输出所有元素
	private:
		int maxLength;
		T *elements;
};

template<class T>
SeqList<T>::SeqList(int mSize)
{
	maxLength=mSize;
	elements=new T[maxLength];
	n=0;
}

//在表中下标为i的元素ai之后插入x。若i=-1,则x插在第一个元素a0前。若插入成功，则返回true，否则返回false
template <class T>
bool SeqList<T>::Insert(int i,T x)
{
	if (i<-1||i>n-1) {
		cout<<"Out of Bounds"<<endl;
		return false;
	}
	if (n==maxLength){                 //上溢出检查
		cout<<"OverFlow"<<endl;
		return false;
	}
	for (int j=n-1;j>i;j--)
		elements[j+1]=elements[j];     //从后往前逐个后移元素
	elements[i+1]=x;                    //将x插入下标为i的元素后面
	n++;
	return true;
} 

template <class T>
void SeqList<T>::Reverse()            //将顺序表逆置
{
    T temp;
	if(n>1)
		for(int i=0;i<n/2;i++)
		{
			temp=elements[i];
			elements[i]=elements[n-i-1];
            elements[n-i-1]=temp;
		}
}

template <class T>
bool SeqList<T>::Delete(const T &x)  //删除表中所有元素值为X的元素
{
	int i,j;
	bool flag=false;
	for (i=0;i<n;i++)   //搜索值为x的元素
		if (elements[i]==x){
				for (j=i+1;j<n;j++)   //从前往后逐个前移元素
					elements[j-1]=elements[j];
				i--;
				n--;
				flag=true;
		}
	if (!flag) cout<<"Not found!"<<endl;
	return flag;
}

template <class T>
void SeqList<T>::Output(ostream& out)const 
{
	for(int i=0;i<n;i++)
		out<<elements[i]<<' ';
	out<<endl;
}


//main----------------------------------------------
const int mSize=100;
void main()
{
	SeqList<int> Seq(mSize);
	//构成线性表：0 1 2 3 4 5 6 7 8 9
	for(int i=0;i<10;i++)
		Seq.Insert(i-1,i);
	Seq.Output(cout);
	//插入9
    cout<<"Insert 9:"<<endl;
	Seq.Insert(1,9);
	Seq.Output(cout);

	//逆置
	cout<<"Reverse:"<<endl;
    Seq.Reverse();
    Seq.Output(cout);
    
	//删除 9
	cout<<"Delete 9:"<<endl;
	Seq.Delete(9);
	Seq.Output(cout);
}