seqlist.cpp

创建顺序表： 输出顺序表：顺序输出各个元素； 插入顺序表：在指定位置处插入元素； 删除顺序表：根据删除指定位置的元素； 逆转顺序表：按逆序倒置所有的元素； 排序顺序表：按照升序排列所有元素；

// Seqlist.cpp: implementation of the Seqlist class.
//
//////////////////////////////////////////////////////////////////////
#include "Seqlist.h"
#include<stdlib.h>
#include<iostream>
using namespace std;
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
//构造函数，通过指定参数sz定义数组的长度
template<class T>
Seqlist<T>::Seqlist(int sz)
{
	if(sz>0)
	{
		maxSize=sz;
		last=-1;
		data=new T[maxSize];
		if(data==NULL)
		{
			cerr<<"存储分配错误"<<endl;
			exit(1);
		}
		
	}
}
//复制构造函数
template<class T>
Seqlist<T>::Seqlist(Seqlist<T>&L)
{
	maxSize=L.size();
	int last=L.length()-1;
	data=new T[maxSize];
	if(datd==NULL){cerr<<"存储分配错误！"<<endl;exit(1);}
	if(int i=i;i<=last+1;i++)
	{
		datd[i-1]=L.getData(i);
	}
}
//搜索x在表中位置，函数返回表项序号
template<class T>
int Seqlist<T>::Search(T& x)const
{
	for(int i=1;i<=last+1;i++)
	{
		if(data[i-1]==x)
		return i;
	}

	return 0;
}
 //定位第i个表项，函数返回表项序号
template<class T>
int Seqlist<T>::Locate(int i)const
{
	if(i>0 && i<=last+1)return i;
	else return 0;
}
template<class T>
 int Seqlist<T>::getData(int i)const
{   
	int x;
    if(i>0&&i<=last+1)
		x=data[i-1];
   return x;
}


//在第i个表项后插入x
template<class T>
bool Seqlist<T>::Insert(int i,T x)
{
	if(last==maxSize-1)return false;
	if(i<0||i>last+1)return false;
	for(int j=last;j>=i;j--)
		data[j+1]=data[j];
	data[i]=x;
	last++;
	return true;
}
//删除第i个表项
template<class T>
bool Seqlist<T>::Remove(int i,T& x)
{
	if(i<=0||i>last+1)return false;
	x=data[i-1];
	if(i==last+1);
		else
		{
			for(int j=i;j<=last;j++)
	                data[j-1]=data[j];
		}
	last--;
	return true;
}
//建立顺序表
template <class T>
void Seqlist<T>::input()
{
	cout<<"开始建立顺序表,请输入表中元素个数:";	
	cin>>last;
	while(last>maxSize-1)
	{
		cout<<"表元素个数输入有误,范围不能超过"<<maxSize-1<<":"<<endl;
		cout<<"开始建立顺序表,请输入表中元素个数:";
		cin>>last;
	}
	cout<<"请输入各个表项："<<endl;

	for(int i=0;i<=last-1;i++)
	{
		cin>>data[i];
		
	}

	
}
//输出顺序表
template<class T>
void Seqlist<T>::output()
{
	if(data==NULL)cout<<"空表"<<endl;
	else
	{
	
		for(int i=0;i<=last-1;i++)
			cout<<data[i]<<endl;
	}

}
//改变data数组空间大小
template <class T>
void Seqlist<T>::reSize(int newSize)
{
	if(newSize<=0)
	{cerr<<"无效的数组大小"<<endl;return;}
	if(newSize!=maxSize)
	{
		T*newArray=new T[newSize];
		if(newArray==NULL)
		{
			cerr<<"存储分配错误。"<<endl;exit(1);
		}
		int n=last+1;
		T*srcptr=data;
		T*destptr=newArray;
		while(n--){*destptr++=*srcptr++;}
		delete data;
		data=newArray;
		maxSize=newSize;
	}
}
template <class T>
void Seqlist<T>::integrate(Seqlist<T>&A,Seqlist<T>&B,int m,int n)
{
	maxSize=A.Size()+B.Size();
	data=new T[maxSize];
	int k=0,s=0;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			j=s;
			if(A.getData(i)>B.getData(j))
				data[k++]=B.getData(j);
			else j=n;
		}
		s=j;
		data[k++]=A.getData(i);
	}
	last=m+n-1;
}
//按从大到小的顺序排列
template <class T>
void Seqlist<T>::paixu()const
{
	int n=last,i,j;
	T temp;
	for(i=0;i<n-1;i++)
		for(j=i;j<n;j++)
			if(data[i]>data[j])
			{
				temp=data[j];
				data[j]=data[i];
				data[i]=temp;
			
			}
	cout<<"排序后，按从小到大的顺序输出为："<<endl;
	for(i=0;i<=last-1;i++)
	{cout<<"#"<<i+1<<":"<<data[i]<<" ";}
	cout<<endl;
}
//将顺序表的元素逆序 
template <class T>
void Seqlist<T>::reverse()const
{ 
	T temp;
    int i ,n;
	n=last;
	for(i=0;i<n/2;i++)
	{
		temp=data[i];
		data[i]=data[n-i-1];
		data[n-i-1]=temp;

	}
	cout<<"逆序后变为"<<endl;
	for(i=0;i<=last-1;i++)
	{cout<<"#"<<i+1<<":"<<data[i]<<" ";}
	cout<<endl;


}
//计算两集合的并集
template <class T>
void Seqlist<T>::Combine(Seqlist<T>&LA,Seqlist<T>&LB)
{
	int n=LA.length(),m=LB.length(),i,k,x;
	for(i=1;i<=m;i++)
	{
		x=LB.getData(i);
		k=LA.Search(x);
		if(k==0)
		{LA.Insert(n-1,x);n++;}
	}
} 
//计算两集合的交集
template <class T>
void Seqlist<T>::Inter(Seqlist<T>& LA,Seqlist<T>& LB)
{
	int n=LA.length(),m=LB.length(),i=1,k,x,a;

	while(i<=n)
	{
		x=LA.getData(i);
		k=LB.Search(x);
		if(k==0)
		{
			LA.Remove(i,a);
			n--;
		}
		else i++;
	}
}