线性表的顺序储存结构.docx
- 文档编号:12912042
- 上传时间:2023-06-09
- 格式:DOCX
- 页数:12
- 大小:48.48KB
线性表的顺序储存结构.docx
《线性表的顺序储存结构.docx》由会员分享,可在线阅读,更多相关《线性表的顺序储存结构.docx(12页珍藏版)》请在冰点文库上搜索。
线性表的顺序储存结构
《算法与数据结构》课程实验报告
班级:
计算机科学与技术2014级2班
实验项目名称:
线性表的顺序储存结构
实验项印性质:
实验所属课程:
算法与数据结构
实验室(中心):
B01407
指导教师:
鲁云平
实验完成时间:
2016年月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返回表项的值boollsEmpty();〃判表空否,空则返回true;否则返回falseboollsFull();〃判表满否,满则返回true;否则返回falsevoidinput();//输入voidoutput();〃输出voidofile();/存储在文件中voidifile();//读取文件并显示
㈢主要功能
1、建立新表
2、对表进行插入(指定元素前、后以及指定位置插入)、删除(指定元素删除及指定位置删除)、修改等操作
3、显示当前操作表的全部容
4、存储在文件中
5、从文件中读取表
五、主要代码
㈠SeqList.h中的主要代码:
1、类成员声明部分:
T*data;intmaxSize;
protected:
//存放数组
//最大可容纳表项的项
数
intlast;
位置(从0开始)
voidreSize(intnewSize);
//当前已存表项的最后
//改变data数组空间大
public:
SeqList(intsz=defaultSize);SeqList(SeqList
//构造函数
//复制构造函数
//析构函数
//计算表最大可容纳表
项个数
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);
后
boolRemove(inti,T&x);
x返回表项的值
boolIsEmpty(){return(last==-1)?
true:
false;}true;否则返回false
boolIsFull(){return(last==maxSize-1)?
true:
false;}true;否则返回false
voidinput();
voidoutput();
SeqList
voidofile();
voidifile();
//插入x在第i个表项之//删除第i个表项,通过//判表空否,空则返回//判表满否,满则返回
//输入
//输出
//表整体赋值
//存储在文件中
//读取文件并显示
2、部分成员函数//搜索函数:
在表中顺序搜索与给定值项是第几个元素
//否则函数返回0,表示搜索失败template
:
search(T&x)const{for(inti=0;i<=last;i++)if(data[i]==x)returni+1;
return0;
}
//定位函数:
template
:
Locate(inti)const{if(i>=i&&i<=last+1)returni;elsereturn0;
}
//插入函数
//将新元素x插入到表中第入成功的信息,若
//插入成功,则返回个元素位置
x匹配的表项,找到则函数返回该表
//顺序搜索
//搜索失败
i(i>=0&&i<=last+1)个表项之后,函数返回插
true;否则返回false.i=O是虚拟的,实际上是插入的第1
template
boolSeqList
:
Insert(inti,T&x){
if(last==maxSize-1)returnfalse;//表满,不能插入
if(i
for(intj=last;j>=i;j--)data[j+1]=data[j];
data[i]=x;
last++;
returntrue;
//参数i不合理,不能插入
//依次后移,空出第i号位置
//插入
//最后位置+1
//插入成功
}
//删除函数
//从表中删除第i个表项,通过应用型参数x返回删除的元素值,函数
//返回删除成功的信息,如删除成功则返回true,否则返回false
template
boolSeqList
:
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
:
input(){
coutvv"开始建立顺序表,请输入表中的元素个数:
";while
(1){cin>>last;if(last<=maxSize-1)break;
cout«"表元素个数有误,围不能超过"vvmaxSizevv":
";}
for(inti=0;i ";cin>>data[i]; } }//输出函数template : output(){ coutvv"顺序表当前元素最后的位置为: "vvlastvvendl;for(inti=0;i "vvdata[i]vvendl; } //存储在文件中 templatevclassT>voidSeqList : ofile(){ ofstreamf1("Test1.txt",ios: : out); if(! f1){cout<<"存储文件失败! "< (1);}for(inti=1;i f1.write((char*)&data[i-1],sizeof(data[i-1])); coutvv"存储成功! "< f1.close(); } //读取文件并打印出文件容 template voidSeqList : ifile(){ ifstreamf2("Test1.txt",ios: : binary); if(! f2){cout<<"打开文件失败! "< (1);} cout«"文件容如下: "< for(inti=1;! f2.eof();i++){f2.read((char*)&data[i-1],sizeof(data[i-1])); } for(intj=1;j "< 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<<"删除成功! "< elsecout<<"删除失败! "< 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<<"删除成功! "< "< break; } case6: {//按位置删除指定元素 inti,x; cout<<"请输入要删除的元素序号: ";cin>>i;if(Seq.Remove(i,x))cout<<"删除成功,删除的元素是: "< elsecout«删除失败! "< } 3、显示功能,直接调用成员函数output()即可实现。 4、查找功能,指定序号的查找通过成员函数getData(i,x),其中的应用型 形参可以返回该序号表项的值;指定表项查找通过成员函数search(x)即可实 现 case8: {//查找指定序号的元素 inti,x; cout«"请输入要查找元素的序号: ";cin>>i; if(Seq.getData(i,x))cout<<"第"< "< elsecout<<'查找失败! "< break; } case9: {//查找指定容的元素 intx; cout«"请输入要查找元素的容: ";cin>>x; if(Seq.search(x))cout< "< elsecout<<'查找失败! "< break; } 5、修改功能,调用成员函数setData(i,x)即可实现 case10: {//修改指定位置元素的数据 inti,x,y; cout«"请输入要修改元素的序号: ";cin>>i; coutvv"请输入要替代的元素数据: ";cin>>x; Seq.setData(i,x);Seq.getData(i,y);〃用y判定修改成功与否if(y==x)cout<<"修改成功! "< elsecoutvv'修改失败! "< break; } 6存储与读取文件,调用成员函数ofile()与ifile()即可 case11: {//存储在文件中 Seq.ofile(); break; } case12: {//读取存储的文件 Seq.ifile();break; } 六、测试结果及说明 1、新建表及显示功能 设置值: sz=5,#仁7,#2=4,#3=1,#4=5,#5=6在指定元素后插入,指定元素x=5,插入值2,结果如左图在指定位置插入,位置i=4,插入值9,结果如右图 2、插入功能 在指定元素前插入 指定元素x=4,插入值y=3 3、删除功能 按容删除,指定删除x=1,结果如左图 按序号删除,指定序号i=2,结果如右图 4、查找功能 查找指定序号的元素,指定序号i=5,结果如左图 查找指定元素的序号,指定元素x=2,结果如右图 5、修改功能 指定元素x=9,修改为y=1 6、存储与读取 七、实验体会 1、写插入删除等操作的代码时注意指针的位置一定要仔细对应,否则会出现节点错位、 数据丢失等错误,这要求在我们在写代码尽量细心。 2、线性表的插入、删除操作前后都要进行非法位置的剔除,如删除一个节点应该把之后的节点一一向前移位。 3、插入、删除等操作应该有返回值反馈,以防未知错误。 4、指针在方便算法的同时也可能导致大量的错误,所以使用指针时应该严谨的设计算法,以免造成后期大量的修改工作。 5、编写过程中应当注意细节部分,避免大量无效率的调试时间。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性 顺序 储存 结构