seqlist.h

数据结构课程设计中顺序表的实现用C++编写的

/////////////////////////////////////////////////////////////
//Function:用模板定义顺序表类,同时定义顺序表类的相关成员函数
//Program:seqlist.h
/////////////////////////////////////////////////////////////
#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>
#include <string.h>

const defaultSize=100;//顺序表的缺省大小为100

const print_one_record=-1;
const print_all_record=-2;

template <class Type> class SeqList
{
public:
	SeqList(int MaxSize=defaultSize);//构造函数
	~SeqList();//析构函数
	int Length() const;//计算表长度
	int Find(Type &) const;//查找或定位元素位置,返回其位置
	int IsIn(Type &);//判定x是否在表中
	int Insert(Type &);//将新数据插入到顺序表的尾部
	int Insert(Type &,int);//将新数据插入到顺序表的任意位置
	int Remove(Type &);//删除指定的数据元素
	int Remove(int);//删除指定位置的数据元素
	int Update(Type&);//更新某个数据元素
	int Update(Type&,int);//更新指定位置的数据元素
	int Next(Type &);//找后继
	int Prior(Type &);//找前驱
	int IsEmpty();//判空
	int IsFull();//判满
	void print(int) const;//输出顺序表的元素或特定的某个元素
	int Total(Type&);//统计	
	Type Get(int i);//取出位置i的数据元素

	int SaveToFile();//保存数据
	int ReadFromFile();//读取数据
private:
	Type *data;//存放顺序表的动态数组
	int MaxSize;//顺序表的最大可空纳空间
	int last;//顺序表当前已存表项的最后位置号
};

template <class Type> SeqList<Type>::SeqList(int sz)
{
//构造函数，通过指定参数sz定义动态数组的大小
	if(sz>0)
	{
		MaxSize=sz;last=-1;
		data=new Type[MaxSize];
	}
}

template <class Type> SeqList<Type>::~SeqList()
{
	//析构函数的定义
	delete []data;
}
template <class Type> int SeqList<Type>::Total(Type &x)
{
	int count=0;
	for(int i=0;i<=last;i++)
	{
		if(data[i]==x){count++;}
	}
	return count;
}
template <class Type> int SeqList<Type>::Find(Type &x) const
{
	//定位：找x在表中的位置，若查找成功，返回数据元素的位置；否则返回-1
	int i=0;
	while(i<=last&&(data[i]!=x))i++;
	if(i>last) return -1;
	else return i;
}

template <class Type> int SeqList<Type>::Length() const
{
	//返回表中实际存放数据元素的个数
	return last+1;
}

template <class Type> int SeqList<Type>::IsFull()
{
	//判定顺序表是否已满
	return last==MaxSize-1;
}

template <class Type> int SeqList<Type>::IsEmpty()
{
	//判定顺序表是否为空
	return last==-1;
}

template <class Type> Type SeqList<Type>::Get(int i)
{
	//取出位置i的数据元素值
	return i<0||i>last?NULL:data[i];
}

template <class Type> void SeqList<Type>::print(int disp_start) const
{
	//输出表中数据元素，或某个指定数据元素,其参数有两种可能
	//当disp_start=print_all(常量,定义为-2)
	if(disp_start==print_all_record)
	{
		int i;
		for(i=0;i<=last;i++)
		{
			cout<<setw(4)<<i+1;
			cout<<data[i]<<endl;
		}
		cout<<endl;
	}
	else
	{
		cout<<data[disp_start]<<endl;
		cout<<endl;
	}
}

template <class Type> int SeqList<Type>::IsIn(Type &x)
{
	//判断x是否在表中
	int i=0,found=0;
	while(i<=last&&!found)
	{
		if(data[i]!=x)i++;
		else found=1;
	}
	return found;
}

template <class Type> int SeqList<Type>::Insert(Type &x)
{
	//若顺序表有剩余空间，就在表的尾部插入新数据元素
	if(last<MaxSize-1)
	{
		last++;
		data[last]=x;
		cout<<endl;
		cout<<"已将数据插入到顺序表的尾部!"<<endl;
		cout<<endl;
		return 1;
	}
	else
	{
		cout<<endl;
		cout<<"无可用空间存放数据!"<<endl;
		cout<<endl;
		return 0;
	}
}

template <class Type> int SeqList<Type>::Insert(Type &x,int i)
{
	//若输入的位置合乎要求且顺序表有剩余空间，在顺序表的指定位置插入新数据元素
	if(i<0||i>last+1||last==MaxSize-1)
	{
		cout<<endl;
		cout<<"顺序表的最后一个元素的位置为:"<<last<<endl;
		cout<<"输入的插入位置不符合要求或顺序表无剩余空间!"<<endl;
		cout<<endl;
		return 0;
	}
	else
	{
		last++;
		for(int j=last;j>i;j--)data[j]=data[j-1];
		data[i]=x;
		cout<<endl;
		cout<<"已将数据插入到"<<i<<"位置"<<endl;
		cout<<endl;
		return 1;
	}
}

template <class Type> int SeqList<Type>::Remove(Type &x)
{
	//根据学生的姓名删除指定的数据元素
	int i=Find(x);
	if(i>=0)
	{
		last--;
		for(int j=i;j<=last;j++)data[j]=data[j+1];
		cout<<endl;
		cout<<"已将指定的元素删除了!!!"<<endl;
		cout<<endl;
		return 1;
	}
	return 0;
}

template <class Type> int SeqList<Type>::Remove(int i)
{
	//根据位置号删除指定位置的数据元素
	if(i>=0&&i<=last)
	{
		last--;
		for(int j=i;j<=last;j++)data[j]=data[j+1];
		return 1;
	}
	else
	{
		cout<<endl;
		cout<<"输入的删除位置不正确!"<<endl;
		cout<<endl;
		return 0;
	}
}

template <class Type> int SeqList<Type>::Update(Type &x)
{
	//根据学生的姓名，更新相应数据元素的数据
//	cout<<x.getName()<<endl;
	int i=Find(x);
	if(i>=0)
	{
		data[i].set_score(x.getscore());
		cout<<endl;
		cout<<"将指定的元素更新了!!!"<<endl;
		cout<<endl;
		return 1;
	}
	return 0;
}

template <class Type> int SeqList<Type>::Update(Type& x,int pos)
{
	//更新顺序表指定位置的数据元素数据

	if(pos>=0&&pos<=last)
	{
		data[pos].set_score(x.getscore());
		cout<<endl;
		cout<<"已将指定位置的元素更新了!!!"<<endl;
		cout<<endl;
		return 1;
	}
	else
	{
		cout<<endl;
		cout<<"注意:指定位置无数据可供更新!!!"<<endl;
		cout<<endl;
		return 0;
	}
}


template <class Type> int SeqList<Type>::Next(Type &x)
{
	//找x的后继
	int i=Find(x);
	if(i>=0&&i<last)return i+1;
	else return -1;
}

template <class Type> int SeqList<Type>::Prior(Type &x)
{
	//找x的前驱
	int i=Find(x);
	if(i>0&&i<=last)return i-1;
	else return -1;
}

template <class Type> int SeqList<Type>::SaveToFile()
{
	ofstream outp("student.txt");
	int i;
	for(i=0;i<last;i++)
		outp<<data[i]<<endl;
	outp<<data[i];//最后一条记录单独写，以免行数多1
	return 0;
}

template <class Type> int SeqList<Type>::ReadFromFile()
{
	ifstream infile;
	infile.open("student.txt");

	int j=last+1;
	while(infile)
	{
		infile>>data[j];
		j++;
	}
	last=j-2;//注意:last!=j-1
	return 0;
}