线性表的顺序储存结构

1、-作者xxxx-日期xxxx线性表的顺序储存结构【精品文档】重庆交通大学算法与数据结构课程实验报告班 级：计算机科学与技术2014级2班实验项目名称： 线性表的顺序储存结构 实验项目性质： 实验所属课程： 算法与数据结构 实验室(中心)： B01407 指 导 教 师 ： 鲁云平 实验完成时间： 2016 年 3 月 21 日【精品文档】教师评阅意见： 签名： 年 月 日实验成绩：1、 实验目的1、实现线性表的顺序存储结构2、熟悉C+程序的基本结构，掌握程序中的头文件、实现文件和主文件之间的相互关系及各自的作用3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验内容及要求对顺序

2、存储的线性表进行一些基本操作。主要包括：（1）插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入（2）删除：操作方式可分为删除指定元素、删除指定位置的元素等，尝试实现逻辑删除操作。（3）显示数据（4）查找：查询指定的元素（可根据某个数据成员完成查询操作）（5）定位操作：定位指定元素的序号（6）更新：修改指定元素的数据（7）数据文件的读写操作等。其它操作可根据具体需要自行补充。要求线性表采用类的定义,数据对象的类型自行定义。三、实验设备及软件四、设计方案 题目线性表的顺序存储结构 设计的主要思路1、 新建SeqList.h头文件，定义SeqList模板类2、 设计类数据成员

3、，包括：T *data（用于存放数组）、int maxSize（最大可容表项的项数）、int last（当前已存表项的最后位置） 3、 设计类成员函数，主要包括：int search(T& x)const;/搜索x在表中位置，函数返回表项序号int Locate(int i)const;/定位第i个表项，函数返回表项序号bool getData(int i,T& x)const;/去第i个表项的值void setData(int i,T& x)/用x修改第i个表项的值bool Insert(int i,T& x);/插入x在第i个表项之后bool Remove(

4、int i,T& x);/删除第i个表项，通过x返回表项的值bool IsEmpty();/判表空否，空则返回true；否则返回falsebool IsFull();/判表满否，满则返回true；否则返回falsevoid input();/输入void output();/输出void ofile();/存储在文件中void ifile();/读取文件并显示 主要功能1、 建立新表2、 对表进行插入（指定元素前、后以及指定位置插入）、删除（指定元素删除及指定位置删除）、修改等操作3、 显示当前操作表的全部内容4、 存储在文件中5、 从文件中读取表五、主要代码SeqList.h中的主要

5、代码：1、 类成员声明部分：protected:T *data;/存放数组int maxSize;/最大可容纳表项的项数int last;/当前已存表项的最后位置（从0开始）void reSize(int newSize);/改变data数组空间大小public:SeqList(int sz = defaultSize);/构造函数SeqList(SeqList<T>& L);/复制构造函数SeqList()delete data;/析构函数int Size()constreturn maxSize;/计算表最大可容纳表项个数int Length()constreturn

6、last+1;/计算表长度int search(T& x)const;/搜索x在表中位置，函数返回表项序号int Locate(int i)const; /定位第i个表项，函数返回表项序号bool getData(int i,T& x)const/去第i个表项的值if(i>0&&i<=last+1)x=datai-1;return true;else return false;void setData(int i,T& x)/用x修改第i个表项的值if(i>0&&i<=last+1) datai-1=x;bool

7、Insert(int i,T& x);/插入x在第i个表项之后bool Remove(int i,T& x);/删除第i个表项，通过x返回表项的值bool IsEmpty()return (last = -1)?true:false;/判表空否，空则返回true；否则返回falsebool IsFull()return (last = maxSize-1)?true:false;/判表满否，满则返回true；否则返回falsevoid input();/输入void output();/输出SeqList<T>operator=(SeqList<T>&a

8、mp; L);/表整体赋值void ofile();/存储在文件中void ifile();/读取文件并显示 2、 部分成员函数/搜索函数：在表中顺序搜索与给定值x匹配的表项，找到则函数返回该表项是第几个元素/否则函数返回0，表示搜索失败template<class T>int SeqList<T>:search(T& x)constfor(int i = 0;i <= last; i+)if(datai = x) return i+1;/顺序搜索return 0;/搜索失败/定位函数：template<class T>int SeqList&

9、lt;T>:Locate(int i)constif(i >= i&&i <= last+1) return i ;else return 0;/插入函数/将新元素x插入到表中第i（i>=0&&i<=last+1）个表项之后，函数返回插入成功的信息，若/插入成功，则返回true；否则返回false.i=0是虚拟的，实际上是插入的第1个元素位置template<class T>bool SeqList<T>:Insert(int i,T& x)if(last = maxSize-1) return fa

10、lse;/表满，不能插入if(i<0 | i>last+1) return false;/参数i不合理，不能插入for(int j = last ;j >=i;j-)/依次后移，空出第i号位置dataj+1 = dataj;datai = x;/插入last+;/最后位置+1return true;/插入成功/删除函数/从表中删除第i个表项，通过应用型参数x返回删除的元素值，函数/返回删除成功的信息，如删除成功则返回true，否则返回falsetemplate<class T>bool SeqList<T>:Remove(int i,T& x)

11、if(last = -1 )return false;if(i<1 | i>last+1)return false;x = datai-1;for(int j = i;j <= last;j+)dataj-1 = dataj;last-;return true;/输入函数/从标准输入逐个数据输入，建立顺序表template<class T>void SeqList<T>:input()cout<<"开始建立顺序表，请输入表中的元素个数:"while(1)cin>>last;if(last<=maxSiz

12、e-1) break;cout<<"表元素个数有误，范围不能超过"<<maxSize<<":"for(int i = 0;i < last;i+)cout<<"#"<<i+1<<":"cin>>datai;/输出函数template<class T>void SeqList<T>:output()cout<<"顺序表当前元素最后的位置为："<<last<

13、<endl;for(int i = 0;i < last;i+)cout<<"#"<<i+1<<":"<<datai<<endl;/存储在文件中template<class T>void SeqList<T>:ofile()ofstream f1("Test1.txt",ios:out);if(!f1)cout<<"存储文件失败！"<<endl;exit(1);for(int i = 1;i &l

14、t; last+1;i+)f1.write(char*) &datai-1,sizeof(datai-1);cout<<"存储成功！"<<endl;f1.close();/读取文件并打印出文件内容template<class T>void SeqList<T>:ifile()ifstream f2("Test1.txt",ios:binary);if(!f2)cout<<"打开文件失败！"<<endl;exit(1);cout<<"文

15、件内容如下："<<endl;for(int i = 1;!f2.eof();i+)f2.read(char*)&datai-1,sizeof(datai-1);for(int j = 1;j < i-1;j+)cout<<"#"<<j<<":"<<dataj-1<<endl;f2.close(); 测试主函数1、插入功能，对不同位置的插入通过修改函数Insert(int i,x)第一形参实现,位置可通过成员函数search(x)确定case 3:/指定元素后插

16、入int x,y;cout<<"请输入指定元素:"cin>>x;cout<<"请输入要插入的元素:"cin>>y;Seq.Insert(Seq.search(x),y);break; case 4:/指定位置插入int i,x;cout<<"请输入插入的位置:"cin>>i;cout<<"请输入要插入的元素:"cin>>x;Seq.Insert(i,x);break; case 5:/按内容删除指定元素int i,x;c

17、out<<"请输入要删除的元素内容:"cin>>x;i = Seq.search(x);/指定元素位置if(Seq.Remove(i,x) cout<<"删除成功！"<<endl;else cout<<"删除失败！"<<endl;break; 2、删除功能，指定序号删除直接调用Remove(i,x)即可实现，指定表项的内容删除可通过search(x)函数返回得到该表项的序号，再通过Remove(i,x)实现case 5:/按内容删除指定元素int i,x;cout

18、<<"请输入要删除的元素内容:"cin>>x;i = Seq.search(x);/指定元素位置if(Seq.Remove(i,x) cout<<"删除成功！"<<endl;else cout<<"删除失败！"<<endl;break; case 6:/按位置删除指定元素int i,x;cout<<"请输入要删除的元素序号:"cin>>i;if(Seq.Remove(i,x) cout<<"删除成功

19、，删除的元素是:"<<x<<endl;else cout<<"删除失败！"<<endl;break; 3、显示功能，直接调用成员函数output()即可实现。4、查找功能，指定序号的查找通过成员函数getData(i,x)，其中的应用型形参可以返回该序号表项的值；指定表项查找通过成员函数search(x)即可实现case 8:/查找指定序号的元素int i,x;cout<<"请输入要查找元素的序号:"cin>>i;if(Seq.getData(i,x) cout<&l

20、t;"第"<<i<<"个元素的值 是:"<<x<<endl;else cout<<"查找失败！"<<endl;break; case 9:/查找指定内容的元素int x;cout<<"请输入要查找元素的内容:"cin>>x;if(Seq.search(x) cout<<x<<"在 "<<Seq.search(x)<<" 位！ "<<endl;else cout<<"查找失败！"<<endl;break; 5、修改功能，调用成员函数setData(i,x)即可实现case 10:/修改指定位置元素的数据int i,x,y;cout<<"请输入要修改元素的序号:"cin>>i;cout<<"请输入要替代的元素数据:"cin>>x;Seq.setData(i,x);Seq.getData(i,y);/用y判定