线性表的顺序储存结构.docx
《线性表的顺序储存结构.docx》由会员分享，可在线阅读，更多相关《线性表的顺序储存结构.docx（13页珍藏版）》请在冰点文库上搜索。
线性表的顺序储存结构
交通大学
《算法与数据结构》课程
实验报告
班级：
计算机科学与技术2014级2班
实验项目名称：
线性表的顺序储存结构
实验项目性质：
实验所属课程：
算法与数据结构
实验室（中心）：
B01407
指导教师：
鲁云平
实验完成时间：
2016年3月21日
1、实验目的
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；否则返回false
boolIsFull（）;//判表满否，满则返回true；否则返回false
voidinput（）;//输入
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&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；否则返回false
boolIsFull（）{return（last==maxSize-1）?
true:
false;}//判表满否，满则返回true；否则返回false
voidinput（）;//输入
voidoutput（）;//输出
SeqListoperator=（SeqList&L）;//表整体赋值
voidofile（）;//存储在文件中
voidifile（）;//读取文件并显示
2、部分成员函数
//搜索函数：
在表中顺序搜索与给定值x匹配的表项，找到则函数返回该表项是第几个元素
//否则函数返回0，表示搜索失败
template
intSeqList:
:
search（T&x）const{
for（inti=0;i<=last;i++）
if（data[i]==x）returni+1;//顺序搜索
return0;//搜索失败
}
//定位函数：
template
intSeqList:
:
Locate（inti）const{
if（i>=i&&i<=last+1）returni;
elsereturn0;
}
//插入函数
//将新元素x插入到表中第i（i>=0&&i<=last+1）个表项之后，函数返回插入成功的信息，若
//插入成功，则返回true；否则返回false.i=0是虚拟的，实际上是插入的第1个元素位置
template
boolSeqList:
:
Insert（inti,T&x）{
if（last==maxSize-1）returnfalse;//表满，不能插入
if（i<0||i>last+1）returnfalse;//参数i不合理，不能插入
for（intj=last;j>=i;j--）//依次后移，空出第i号位置
data[j+1]=data[j];
data[i]=x;//插入
last++;//最后位置+1
returntrue;//插入成功
}
//删除函数
//从表中删除第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
voidSeqList:
:
input（）{
cout<<"开始建立顺序表，请输入表中的元素个数:
";
while
（1）{
cin>>last;
if（last<=maxSize-1）break;
cout<<"表元素个数有误，围不能超过"<";
}
for（inti=0;icout<<"#"<";
cin>>data[i];
}
}
//输出函数
template
voidSeqList:
:
output（）{
cout<<"顺序表当前元素最后的位置为：
"<for（inti=0;icout<<"#"<"<}
//存储在文件中
template
voidSeqList:
:
ofile（）{
ofstreamf1（"Test1.txt",ios:
:
out）;
if（!
f1）{cout<<"存储文件失败！
"<（1）;}
for（inti=1;if1.write（（char*）&data[i-1],sizeof（data[i-1]））;
cout<<"存储成功！
"<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;jcout<<"#"<"<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<<"删除成功！
"<elsecout<<"删除失败！
"<break;
}
case6:
{//按位置删除指定元素
inti,x;
cout<<"请输入要删除的元素序号:
";cin>>i;
if（Seq.Remove（i,x））cout<<"删除成功，删除的元素是:
"<elsecout<<"删除失败！
"<break;
}
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;
cout<<"请输入要替代的元素数据:
";cin>>x;
Seq.setData（i,x）;Seq.getData（i,y）;//用y判定修改成功与否
if（y==x）cout<<"修改成功！
"<elsecout<<"修改失败！
"<break;
}
6、存储与读取文件，调用成员函数ofile（）与ifile（）即可
case11:
{//存储在文件中
Seq.ofile（）;
break;
}
case12:
{//读取存储的文件
Seq.ifile（）;
break;
}
六、测试结果及说明
1、新建表及显示功能
设置值：
sz=5，#1=7，#2=4，#3=1，#4=5，#5=6
2、插入功能
在指定元素前插入
指定元素x=4，插入值y=3
在指定元素后插入，指定元素x=5，插入值2，结果如左图
在指定位置插入，位置i=4，插入值9，结果如右图
3、删除功能
按容删除，指定删除x=1，结果如左图
按序号删除，指定序号i=2，结果如右图
4、查找功能
查找指定序号的元素，指定序号i=5，结果如左图
查找指定元素的序号，指定元素x=2，结果如右图
5、修改功能
指定元素x=9，修改为y=1
6、存储与读取
七、实验体会
1、写插入删除等操作的代码时注意指针的位置一定要仔细对应，否则会出现节点错位、数据丢失等错误，这要求在我们在写代码尽量细心。
2、线性表的插入、删除操作前后都要进行非法位置的剔除，如删除一个节点应该把之后的节点一一向前移位。
3、插入、删除等操作应该有返回值反馈，以防未知错误。
4、指针在方便算法的同时也可能导致大量的错误，所以使用指针时应该严谨的设计算法，以免造成后期大量的修改工作。
5、编写过程中应当注意细节部分，避免大量无效率的调试时间。
升级会员 