数据结构实验报告二线性表的顺序存储_2线性表顺序存储结构
数据结构实验报告二线性表的顺序存储由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“2线性表顺序存储结构”。
实验报告二 线性表的顺序存储
班级： 2010XXX 姓名： HoogLe 学号： 2010XXXX 专业： XXXX
2858505197@qq.com
一、实验目的：
（1）掌握顺序表的基本操作的实现方法。
（2）应用顺序表的基本算法实现集合A=AUB算法。
（3）应用顺序表的基本算法实现两有序顺序表的归并算法。
二、实验内容：
1、线性表顺序存储结构的基本操作算法实现（要求采用类模板实现）
[实现提示]（同时可参见教材p5822-p60页算法、ppt）函数、类名称等可自定义，部分变量请加上学号后3位。库函数载和常量定义：（代码）#include using namespace std;const int MaxSize=100;
（1）顺序表存储结构的定义(类的声明)：（代码）
template //定义模板类SeqList cla SeqList { public: SeqList();//无参构造函数
SeqList(datatype a[ ], int n);//有参构造函数 ~SeqList(){};//析构函数为空 int Length();//求线性表的长度
datatype Get(int i);//按位查找，取线性表的第i个元素 int Locate(datatype item);//查找元素item void Insert(int i, datatype item);//在第i个位置插入元素item datatype Delete(int i);//删除线性表的第i个元素 void display();//遍历线性表，按序号依次输出各元素 private: datatype data[MaxSize];//存放数据元素的数组 int length;//线性表的长度 };
（2）初始化顺序表算法实现（不带参数的构造函数）/* *输 入：无
*前置条件：顺序表不存在 *功 能：构建一个顺序表 *输 出：无
*后置条件：表长为0 */ 实现代码：
template SeqList:: SeqList(){ length=0;}
（3）顺序表的建立算法（带参数的构造函数）
/* *输 入：顺序表信息的数组形式a[],顺序表长度n *前置条件：顺序表不存在*功 能：将数组a[]中元素建为长度为n的顺序表 *输 出：无
*后置条件：构建一个顺序表 */ 实现代码：
template SeqList:: SeqList(datatype a[], int n){ if(n>MaxSize){
cout
data[i]=a[i];length=n;}（4）在顺序表的第i个位置前插入元素e算法 /* *输 入：插入元素e,插入位置i *前置条件：顺序表存在，i要合法
*功 能：将元素e插入到顺序表中位置i处 *输 出：无
*后置条件：顺序表插入新元素，表长加1 */ 实现代码：
template void SeqList::Insert(int i, datatype item){ int j;if(length>=MaxSize){
coutlength+1){
cout=i;j--)
data[j]=data[j-1];data[i-1]=item;length++;}（5）删除线性表中第i个元素算法 /* *输 入：要删除元素位置i *前置条件：顺序表存在,i要合法
*功 能：删除顺序表中位置为i的元素 *输 出：无
*后置条件： 顺序表册除了一个元素，表长减1 */ 实现代码：
template datatype SeqList::Delete(int i){ int item,j;if(length==0){
coutlength){
cout
for(j=i;j
data[j-1]=data[j];//注意数组下标从0记
length--;return item;}（6）遍历线性表元素算法 /* *输 入：无
*前置条件：顺序表存在 *功 能：顺序表遍历 *输 出：输出所有元素 *后置条件：无 */ 实现代码：
template void SeqList::display(){ if(length==0){
cout
cout
（7）获得线性表长度算法 /* *输 入：无
*前置条件：顺序表存在 *功 能：输出顺序表长度 *输 出：顺序表长度 *后置条件：无 */ 实现代码：
template int SeqList::Length(){ return Length;}
（8）在顺序线性表中查找e值，返回该元素的位序算法 /* *输 入：查询元素值e *前置条件：顺序表存在*功 能：按值查找值的元素并输出位置 *输 出：查询元素的位置 *后置条件：无 */ 实现代码：
template int SeqList::Locate(datatype item){ for(int i=0;i
//下标为i的元素等于item，返回其序号i+1
return 0;//查找失败 }
（9）获得顺序线性表第i个元素的值 /* *输 入：查询元素位置i *前置条件：顺序表存在，i要合法
*功 能：按位查找位置为i的元素并输出值 *输 出：查询元素的值 *后置条件：无 */ 实现代码：
template datatype SeqList::Get(int i){ if(ilength){
cout
（10）判表空算法 /* *输 入：无 *前置条件：无
*功 能：判表是否为空
*输 出：为空返回1，不为空返回0 *后置条件：无 */ 实现代码：
template bool SeqList::Empty(){ if(length==0){
return 1;} else {
return 0;} }
(11)求直接前驱结点算法 /* *输 入：要查找的元素e，待存放前驱结点值e1
*前置条件：无
*功 能：查找该元素的所在位置，获得其前驱所在位置。*输 出：返回其前驱结点的位序。*后置条件：e1值为前驱结点的值 */ 实现代码：
template int SeqList::Pre(datatype item){ int k=Locate(item)-1;if(k>0)
return k;else {
cout
return 0;} }(12)求直接后继结点算法 /* *输 入：要查找的元素e，待存放后继结点值e1 *前置条件：无
*功 能：查找该元素的所在位置，获得其后继所在位置。*输 出：返回其后继结点的位序。*后置条件：e1值为后继结点的值 */ 实现代码：
template int SeqList::Suc(datatype item){ int k=Locate(item)+1;if(k>length){
cout
return k;} }
上机实现以上基本操作，写出main()程序： void main(){ SeqList Seq;//创建
if(Seq.Empty()){
cout
} Seq.Insert(1,1);Seq.Insert(2,2);Seq.Insert(3,3);Seq.Insert(4,4);Seq.Insert(5,5);//插入元素操作
cout
cout
cout
cout
cout
Seq.Delete(3);//删除元素
cout
cout
cout
cout
cout
要求对每个算法都加以测试，判断是否正确；并测试不同类型数据的操作。粘贴测试数据及运行结果：
2、用以上基本操作算法，实现A=AUB算法。（利用函数模板实现）/* *输 入：集合A,集合B *前置条件：无
*功 能：实现A=AUB *输 出：无
*后置条件：A中添加了B中的元素。*/
实现代码：
template SeqList SeqList::Add(SeqList& item){ if(item.Empty())
return *this;else {
int k=item.Length();
int num=this->Length();
for(int i=1;i
{
for(int j=0;j
if(data[j]==item.Get(i))
{
break;
}
else if(num-1==j&&data[num-1]!=item.Get(i))
{
this->Insert(++num,item.Get(i));
}
}
return *this;} } void main(){ SeqList A,B;cout
B.Insert(1,2);B.Insert(2,6);B.Insert(3,1);B.Insert(4,8);B.Insert(5,9);//插入集合B中元素
A.Add(B);A.display();cout
3、对以上顺序表类中的基本操作算法适当加以补充，实现向一个有序的（非递减）的顺序表中插入数据元素e算法。/* *输 入：插入元素e *前置条件：顺序表已有序
*功 能：将元素e插入到顺序表中适当的位置，使顺序表依然有序 *输 出： 无
*后置条件：有序顺序表插入了新元素，且表长加1。*/ 实现代码：
template void SeqList::orderInsert(datatype item){ int num=this->Length();for(int i=0;i
if((data[i]item))
{
for(int k=num;k>i;k--)
data[k]=data[k-1];
data[i+1]=item;
length++;
break;
}
if(data[i]>item)
{
for(int k=num;k>i;k--)
data[k]=data[k-1];
data[i]=item;
length++;
break;
} } } void main(){ SeqList A,B;A.Insert(1,3);A.Insert(2,5);A.Insert(3,6);A.Insert(4,8);A.Insert(5,10);//插入顺序表
cout
cout
cout
4、算法实现：La,Lb为非递减的有序线性表，将其归并为Lc，该线性表仍有序（未考虑相同时删除一重复值）（利用函数类板实现）MergeList： /* *输 入：有序线性表La,有序线性表Lb *前置条件：顺序表已有序
*功 能：将两线性表归并，不去掉相同元素 *输 出： 返回一个新的有序线性表Lc *后置条件：无 */ 实现代码：
template SeqList SeqList::ElseAdd(SeqList Seq1,SeqList Seq2){ int num=Seq2.Length();for(int i=0;i
Seq1.orderInsert(Seq2.Get(i));} return Seq1;} void main(){ SeqList La,Lb,Lc;La.Insert(1,2);La.Insert(2,4);La.Insert(3,6);La.Insert(4,8);//插入La cout
cout
cout
粘贴测试数据及运行结果：
三、心得体会：（含上机中所遇问题的解决办法，所使用到的编程技巧、创新点及编程的心得）
