线性表的顺序储存结构

交通大学《算法与数据结构》课程实验报告班级：计算机科学与技术2014级2班实验项目名称：线性表的次序储藏结构实验项目性质：实验所属课程：算法与数据结构实验室(中心)：B01407指导教师：鲁云平实验达成时间：2016年3月21日教师评阅建议：署名：年代日实验成绩：一、实验目的1、实现线性表的次序储存结构2、熟习C++程序的基本结构，掌握程序中的头文件、实现文件和主文件之间的互相关系及各自的作用3、熟习次序表的基本操作方式,掌握次序表有关操作的详细实现二、实验容及要求对次序储存的线性表进行一些基本操作。主要包含：（1）插入：操作方式为在指定元素前插入、在指定元素以后插入、在指定地点达成插入（2）删除：操作方式可分为删除指定元素、删除指定地点的元素等，试试实现逻辑删除操作。（3）显示数据（4）查找：查问指定的元素（可依据某个数据成员达成查问操作）（5）定位操作：定位指定元素的序号（6）更新：改正指定元素的数据（7）数据文件的读写操作等。其余操作可依据详细需要自行增补。要求线性表采纳类的定义,数据对象的种类自行定义。三、实验设施及软件VC6.0四、设计方案㈠题目线性表的次序储存结构㈡设计的主要思路1、新建SeqList.h头文件，定义SeqList模板类2、设计类数据成员，包含：T*data（用于寄存数组）、intmaxSize（最大可容表项的项数）、intlast（目前已存表项的最后地点）3、设计类成员函数，主要包含：intsearch(T&x)const;//搜寻x在表中地点，函数返回表项序号intLocate(inti)const;//定位第i个表项，函数返回表项序号boolgetData(inti,T&x)const;//去第i个表项的值voidsetData(inti,T&x)//用x改正第i个表项的值boolInsert(inti,T&x);//插入x在第i个表项以后boolRemove(inti,T&x);//删除第i个表项，经过x返回表项的值boolIsEmpty( );//判表空否，空则返回true；不然返回falseboolIsFull( );//判表满否，满则返回true；不然返回falsevoidinput( );//输入voidoutput( );//输出voidofile( );/储存在文件中voidifile( );//读取文件并显示㈢主要功能1、成立新表2、对表进行插入（指定元素前、后以及指定地点插入）、删除（指定元素删除及指定地点删除）、改正等操作3、显示目前操作表的所有容4、储存在文件中5、从文件中读取表五、主要代码SeqList.h中的主要代码：1、类成员申明部分：protected:T*data;

//寄存数组intmaxSize;

//最大可容纳表项的项数intlast;

//目前已存表项的最后地点（从0开始）voidreSize(intnewSize);

//改变

data数组空间大小public:SeqList(intsz=defaultSize);SeqList(SeqList<T>&L);

//结构函数//复制结构函数~SeqList( ){delete[]data;}intSize( )const{returnmaxSize;}

//析构函数//计算表最大可容纳表项个数intLength( )const{returnlast+1;}intsearch(T&x)const;

//计算表长度//搜寻x在表中位置，函数返回表项序号intLocate(inti)const;

//定位第

i个表项，函数返回表项序号boolgetData(inti,T&x)const//去第i个表项的值{if(i>0&&i<=last+1){x=data[i-1];returntrue;}elsereturnfalse;}voidsetData(inti,T&x)//用x改正第i个表项的值{if(i>0&&i<=last+1)data[i-1]=x;}boolInsert(inti,T&x);

//插入

x在第

i个表项之后boolRemove(inti,T&x);

//删除第

i个表项，经过x返回表项的值boolIsEmpty( ){return(last==-1)?true:false;}true；不然返回falseboolIsFull( ){return(last==maxSize-1)?true:false;}

//判表空否，空则返回//判表满否，满则返回true；不然返回

falsevoidinput( );voidoutput( );SeqList<T>operator=(SeqList<T>&L);

//输入//输出//表整体赋值voidofile( );voidifile( );

//储存在文件中//读取文件并显示2、部分红员函数//搜寻函数：在表中次序搜寻与给定值项是第几个元素

x般配的表项，找到则函数返回该表//不然函数返回0，表示搜寻失败template<classT>intSeqList<T>::search(T&x)const{for(inti=0;i<=last;i++)if(data[i]==x)returni+1;

//次序搜寻return0;

//搜寻失败}//定位函数：template<classT>intSeqList<T>::Locate(inti)const{if(i>=i&&i<=last+1)returni;elsereturn0;}//插入函数//将新元素x插入到表中第i（i>=0&&i<=last+1）个表项以后，函数返回插入成功的信息，若//插入成功，则返回true；不然返回false.i=0是虚构的，其实是插入的第1个元素地点template<classT>boolSeqList<T>::Insert(inti,T&x){if(last==maxSize-1)returnfalse;if(i<0||i>last+1)returnfalse;for(intj=last;j>=i;j--)

//表满，不可以插入//参数i不合理，不可以插入//挨次后移，空出第i号地点data[j+1]=data[j];data[i]=x;last++;

//插入//最后地点+1returntrue;

//插入成功}//删除函数//从表中删除第i个表项，经过应用型参数x返回删除的元素值，函数//返回删除成功的信息，如删除成功则返回true，不然返回falsetemplate<classT>boolSeqList<T>::Remove(inti,T&x){if(last==-1)returnfalse;if(i<1||i>last+1)returnfalse;x=data[i-1];for(intj=i;j<=last;j++)data[j-1]=data[j];last--;returntrue;}//输入函数//从标准输入逐一数据输入，成立次序表template<classT>voidSeqList<T>::input( ){cout<<"开始成立次序表，请输入表中的元素个数:";while(1){cin>>last;if(last<=maxSize-1)break;cout<<"表元素个数有误，围不可以超出"<<maxSize<<":";}for(inti=0;i<last;i++){cout<<"#"<<i+1<<":";cin>>data[i];}}//输出函数template<classT>voidSeqList<T>::output( ){cout<<"次序表目前元素最后的地点为："<<last<<endl;for(inti=0;i<last;i++)cout<<"#"<<i+1<<":"<<data[i]<<endl;}//储存在文件中template<classT>voidSeqList<T>::ofile( ){ofstreamf1("Test1.txt",ios::out);if(!f1){cout<<"储存文件失败！"<<endl;exit(1);}for(inti=1;i<last+1;i++)f1.write((char*)&data[i-1],sizeof(data[i-1]));cout<<"储存成功！"<<endl;f1.close( );}//读取文件并打印出文件容template<classT>voidSeqList<T>::ifile( ){ifstreamf2("Test1.txt",ios::binary);if(!f2){cout<<"翻开文件失败！"<<endl;exit(1);}cout<<"文件容以下："<<endl;for(inti=1;!f2.eof( );i++){f2.read((char*)&data[i-1],sizeof(data[i-1]));}for(intj=1;j<i-1;j++)cout<<"#"<<j<<":"<<data[j-1]<<endl;f2.close( );}㈡测试主函数1、插入功能，对不一样地点的插入经过改正函数Insert(inti,x)第一形参实现,地点可经过成员函数search(x)确立case3:{//指定元素后插入intx,y;cout<<"请输入指定元素:";cin>>x;cout<<"请输入要插入的元素:";cin>>y;Seq.Insert(Seq.search(x),y);break;}case4:{//指定地点插入inti,x;cout<<"请输入插入的地点:";cin>>i;cout<<"请输入要插入的元素:";cin>>x;Seq.Insert(i,x);break;}case5:{//按容删除指定元素inti,x;cout<<"请输入要删除的元素容:";cin>>x;i=Seq.search(x);//指定元素地点if(Seq.Remove(i,x))cout<<"删除成功！"<<endl;elsecout<<"删除失败！"<<endl;break;}2、删除功能，指定序号删除直接调用Remove(i,x)即可实现，指定表项的容删除可经过search(x)函数返回获得该表项的序号，再经过Remove(i,x)实现case5:{//按容删除指定元素inti,x;cout<<"请输入要删除的元素容:";cin>>x;i=Seq.search(x);//指定元素地点if(Seq.Remove(i,x))cout<<"删除成功！"<<endl;elsecout<<"删除失败！"<<endl;break;}case6:{//按地点删除指定元素inti,x;cout<<"请输入要删除的元素序号:";cin>>i;if(Seq.Remove(i,x))cout<<"删除成功，删除的元素是:"<<x<<endl;elsecout<<"删除失败！"<<endl;break;}3、显示功能，直接调用成员函数output( )即可实现。4、查找功能，指定序号的查找经过成员函数getData(i,x)，此中的应用型形参能够返回该序号表项的值；指定表项查找经过成员函数search(x)即可实现case8:{//查找指定序号的元素inti,x;cout<<"请输入要查找元素的序号:";cin>>i;if(Seq.getData(i,x))cout<<"第"<<i<<"个元素的值是:"<<x<<endl;elsecout<<"查找失败！"<<endl;break;}case9:{//查找指定容的元素intx;cout<<"请输入要查找元素的容:";cin>>x;if(Seq.search(x))cout<<x<<"在"<<Seq.search(x)<<"位！"<<endl;elsecout<<"查找失败！"<<endl;break;}5、改正功能，调用成员函数setData(i,x)即可实现case10:{//改正指定地点元素的数据inti,x,y;cout<<"请输入要改正元素的序号:";cin>>i;cout<<"请输入要代替的元素数据:";cin>>x;Seq.setData(i,x);Seq.getData(i,y);//用y判断改正成功与否if(y==x)cout<<"改正成功！"<<endl;elsecout<<"改正失败！"<<endl;break;}6、储存与读取文件，调用成员函数ofile( )与ifile( )即可case11:{//储存在文件中Seq.ofile( );break;}case12:{//读取储存的文件Seq.ifile( );break;}六、测试结果及说明1、新建表及显示功能设置值：sz=5，#1=7，#2=4，#3=1，#4=5，#5=62、插入功能在指定元素前插入指定元素x=4，插入值y=3在指定元素后插入，指定元素x=5，插入值2，结果如左图在指定地点插入，地点i=4，插入值9，结果如右图3、删除功能按容删除，指定删除x=1，结果如左图按次号删除，指定序号i=2，结果如右图4、查找功能查找指定序号的元素，指定序