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