线性表的顺序储存结构

1、算法与数据结构级：计算机科学与技术 2014线性表的顺序储存结构实验完成时间:2016年月实验所属课程:算法与数据结构实验室（中心）:B01407指导教师：鲁云教师评阅意见：签名：年 月曰实验成绩：一、实验目的1、实现线性表的顺序存储结构2、熟悉C+程序的基本结构，掌握程序中的头文件、实现文件和主文件之间的相互关系及各自的作用3、熟悉顺序表的基本操作方式，掌握顺序表相关操作的具体实现二、实验内容及要求对顺序存储的线性表进行一些基本操作。主要包括:(1 )插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入(2 )删除：操作方式可分为删除指定元素、删除指定位置的元素等，尝试实

2、现逻辑删除操作。(3 )显示数据(4 )查找：查询指定的元素(可根据某个数据成员完成查询操作)(5) 定位操作：定位指定元素的序号(6) 更新：修改指定元素的数据(7) 数据文件的读写操作等。其它操作可根据具体需要自行补充。要求线性表采用类的定义，数据对象的类型自行定义。三、实验设备及软件VC6.0四、设计方案题目线性表的顺序存储结构设计的主要思路1、新建SeqList.h头文件，定义SeqList模板类2、 设计类数据成员，包括：T *data (用于存放数组)、in t maxSize(最大可容表项的项数)、int last (当前已存表项的最后位置)搜索x在表中位置，函数返回表项序号 定

3、位第i个表项，函数返回表项序号去第i个表项的值3、设计类成员函数，主要包括：int search(T & x)co nst;/int Locate(i nt i)c on st;/用x修改第i个表项的值插入x在第i个表项之后/删除第i个表项，通过x返回表项的值bool getData(i nt i,T& x)c on st;/void setData(i nt i,T& x)/bool In sert(i nt i,T& x);/bool Remove(i nt i,T & x);bool IsEmpty();/ 判表空否，空则返回true ;否则返回falsebool IsFullO;/判表

4、满否，满则返回true ;否则返回falsevoid input();/ 输入void out put();/ 输出void ofile();/存储在文件中void ifile();/读取文件并显示主要功能1、建立新表2、对表进行插入（指定元素前、后以及指定位置插入）、删除（指定 元素删除及指定位置删除）、修改等操作3、显示当前操作表的全部内容4、存储在文件中5、从文件中读取表五、主要代码SeqList.h中的主要代码:1、类成员声明部分：P rotected:T *data;int maxSize;的项数II存放数组II最大可容纳表项int last;位置(从0开始)void reSize(

5、i nt n ewSize);间大小/当前已存表项的最后II改变data数组空public:SeqList(i nt sz = defaultSize);SeqList(SeqList& L);数SeqList()delete data;int Size()co nstreturn maxSize;纳表项个数II构造函数II复制构造函II析构函数II计算表最大可容int Len gth()c on stretu rn last+1; int search(T& x)c on st;置，函数返回表项序号int Locate(i nt i)c on st;函数返回表项序号II计算表长度II搜索x在

6、表中位/定位第i个表项,II去第i个表项的bool getData(i nt i,T & x)c onst值if(i 0&iv=last+1)x=datai-1;retur n true;else retur n false;void setData(int i,T& x)II 用 x 修改第 i 个表项的值/插入x在第i个表项/删除第i个表项,bool IsE mp ty()return (last = -1)?true:false; 则返回true ;否则返回falsebool lsFull()retur n (last = maxSize-1)?true:false; 回true ;否则

7、返回falsevoid inp ut();void out put();SeqList op erator=(SeqList& L);值void ofile();void ifile();2、部分成员函数/搜索函数：在表中顺序搜索与给定值项是第几个元素/否则函数返回0，表示搜索失败temp latevciass Tint SeqListvT:search(T & x)c on stfor(i nt i = 0;i 0&iv=last+1) datai-1=x; bool In sert(i nt i,T& x);之后bool Remove(i nt i,T& x);通过x返回表项的值temp

8、latevciass Tint SeqListvT:Locate(i nt i)c on stif(i = i&i =0&iv=last+1)个表项之后，函数返回插入成功的信息，若/插入成功，则返回true ;否则返回 第1个元素位置false.i=O是虚拟的，实际上是插入的temp latevciass T/表满，不能插入/参数i不合理，不能插入/依次后移，空出第i号位置bool SeqListvT:l nsert(i nt i,T& x)if(last = maxSize-1) retur n false;if(ilast+1) return false; for(i nt j = las

9、t ;j =i;j-) dataj+1 = dataj;/插入/最后位置+1插入成功datai = x;last+;return true;/删除函数x返回删除的元素值，函数true，否则返回false/从表中删除第i个表项，通过应用型参数 /返回删除成功的信息，如删除成功则返回 temp latevciass Tbool SeqListvT:Remove(i nt i,T& x)if(last = -1 )return false;if(iv1 II ilast+1)return false;x = datai-1;for(i nt j = i;j v= last;j+)dataj-1 =

10、dataj;last-;return true;/输入函数/从标准输入逐个数据输入，建立顺序表temp latevciass Tvoid SeqListvT:i npu t().11.coutvv开始建立顺序表，请输入表中的元素个数while(1)cin last;if(last=maxSize-1) break;coutvv表元素个数有误，范围不能超过maxSize:;for(i nt i = 0;i last;i+)cout#i+1 datai;/输出函数temp latevciass Tvoid SeqListvT:out pu t()coutvv顺序表当前元素最后的位置为：vvlast

11、vvendl;for(i nt i = 0;i void SeqListvT:ofile()ofstream f1(Test1.txt,ios:out);if(!f1)cout存储文件失败！e ndl;exit(1);for(i nt i = 1;i last+1;i+)f1.write(char*) & datai-1,sizeof(datai-1); coutvv存储成功！ void SeqListvT:ifile()ifstream f2(Test1.txt,ios:b in ary);if(!f2)coutvv打开文件失败！vve ndl;exit(1);coutvv文件内容如下：vv

12、endl;for(i nt i = 1;!f2.eof();i+)f2.read(char*)&datai-1,sizeof(datai-1);for(i nt j = 1;j v i-1;j+)coutvv#vvjvv:vvdataj-1vve ndl;f2.close();测试主函数1、插入功能，对不同位置的插入通过修改函数In sert(i nti,x)第一形参实现,位置可通过成员函数search(x)确定case 3:/指定元素后插入int x,y;coutvv请输入指定元素:;cinx; coutvv请输入要插入的元素:;ciny;Seq.I nsert(Seq.search(x),

13、y);break;case 4:/指定位置插入int i,x;coutvv请输入插入的位置:;cini; coutvv请输入要插入的元素:;cinx; Seqn sert(i,x);break;case 5:/按内容删除指定元素int i,x;coutvv请输入要删除的元素内容:;cinx;i = Seq.search(x);/指定元素位置if(Seq.Remove(i,x) coutvv删除成功！ vve ndl;else coutvv删除失败！ vve ndl;break;2、删除功能，指定序号删除直接调用 Remove(i,x)即可实现，指定表项 的内容删除可通过search(x)函数返

14、回得到该表项的序号，再通过 Remove(i,x)实现case 5:/按内容删除指定元素int i,x;coutvv请输入要删除的元素内容:;cinx;if(Seq.Remove(i,x) cout删除成功！ e ndl;else coutvv删除失败！ i;if(Seq.Remove(i,x) coutvv删除成功，删除的元素是:vvxvve ndl;else coutvv 删除失败！ vve ndl;break;直接调用成员函数output()即可实现。指定序号的查找通过成员函数getData(i,x)，其中的应用search(x)即3、显示功能，4、查找功能，型形参可以返回该序号表项的值

15、；指定表项查找通过成员函数 可实现case 8:/查找指定序号的元素int i,x;coutvv请输入要查找元素的序号:;cini;if(Seq.getData(i,x) coutvv 第vvivv个元素的值 是:vvxvve ndl;else coutvv查找失败！ vve ndl;break;case 9:/查找指定内容的元素int x;coutvv请输入要查找元素的内容:;cinx;位!if(Seq.search(x) coutvvxvv 在 vvSeq.search(x)vvvve ndl;else coutvv查找失败！ vve ndl;break;5、修改功能，调用成员函数 set

16、Data(i,x)即可实现case 10:/修改指定位置元素的数据int i,x,y;coutvv请输入要修改元素的序号:;cini; coutvv请输入要替代的元素数据:;cinx;Seq.setData(i,x);Seq.getData(i,y); / 用 y 判定修改成功与if(y = X)coutvv 修改成功！ e ndl; else coutvv修改失败！ e ndl;break;6、存储与读取文件，调用成员函数ofile()与ifileO即可存储在文件中Seq.ofileO; break;case 12:/读取存储的文件case 11:/Seq.ifile(); break;六、

17、测试结果及说明1、新建表及显示功能设置值：sz=5 , #1=7 , #2=4 , #3=1 , #4=5 , #5=6123456789111-012!s素 素元1|0|4#1 元入元匹兀 定宀疋 表刖序- ItWWSS据定- 顺兀元元容号；！wrLUUJB&fihr号素霉5定文件 ns t JV居 素口 元愿 nIRJDU- - h、u*n昴蠶vBj驀，请输入表巾的元素个数:ttl：7m：in4：Stt5：6潴翳輪素最融位置知501:7112:43：14：5ttSzfr2、插入功能在指定元素前插入指定元素x=4，插入值y=3顺序喪当前元素最后的位置为；6 1：7B2；3廿3： 4fi4 =

18、 ltt5；5在指定元素后插入，指定元素 在指定位置插入，位置i=4 ,x=5 ,插入值插入值2，结果如左图9，结果如右图2汚元 m兀入许元 能走插題刖 功指要功当 择择克 选序汐 抚垦垦垦冃页江 *1 el、期为 置 位 的 后 最 素113:4#4:1#5:5117: G请输A牺Xg）疽Sg 廈雲嘻g亍aS兀素円.搞序s当醫元素最后的位置为：8 ftl ：7鸵;3律d ：44：1點：9HE ：57：2O：&3、删除功能按内容删除，指定删除x=1，结果如左图按序号删除，指定序号i=2，结果如右图请选择功熊汚_鬱蠢爭漏元素内容灶 iOS書輪素最后的位H为；V73495Z6ttl tt2 tt3 tt4 ttS96#7为S位 的后 最素 汨除删兰兀 晁址 刖 功要功功当 择入成择表he疋 素元 元的 的除4、查找功能查找指定序号的元素，指定序号i=5，结果如左图查找指定元素的序号，指定元素 x=2，结果如右图擇入5能杳誌 功要诗 透输訂 请请第5、修改功能指定元素x=9，修改为y=1淸选择功證1色專减丁元素晦】i员L表暫需元素最后的位置为i 6 J