实验一.顺序表验证实验.doc

线性表
实验一 顺序表操作验证

1. 实验目的
⑴ 掌握线性表的顺序存储结构；
⑵ 验证顺序表及其基本操作的实现；
⑶ 掌握数据结构及算法的程序实现的基本方法。
2. 实验内容
⑴ 建立含有若干个元素的顺序表；
⑵ 对已建立的顺序表实现插入、删除、查找等基本操作。
3. 实现提示
首先定义顺序表的数据类型——顺序表类SeqList，包括题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。
const int MaxSize=10;
template <class T> //定义模板类SeqList
class SeqList
{
public:
SeqList( ){length=0;} //无参构造函数
SeqList(T a[ ], int n); //有参构造函数
void Insert(int i, T x); //在线性表中第i个位置插入值为x的元素
T Delete(int i); //删除线性表的第i个元素
int Locate(T x ); //按值查找，求线性表中值为x的元素序号
void PrintList( ); //遍历线性表，按序号依次输出各元素
private:
T data[MaxSize]; //存放数据元素的数组
int length; //线性表的长度
};

其次，建立含有n个数据元素的顺序表，即设计构造函数。算法如下：
template <class T>
SeqList:: SeqList(T a[ ], int n)
{
if (n>MaxSize) throw "参数非法";
for (i=0; i<n; i++)
data[i]=a[i];
length=n;
}
顺序表有参构造函数SeqList

最后，对建立的顺序表设计插入、删除、查找等基本操作的算法。
⑴ 插入算法
template <class T>
void SeqList::Insert(int i, T x)
{
if (length>=MaxSize) throw "上溢";
if (i<1 | | i>length+1) throw "位置";
for (j=length; j>=i; j--)
data[j]=data[j-1]; //注意第j个元素存在数组下标为j-1处
data[i-1]=x;
length++;
}

顺序表插入算法Insert

⑵ 删除算法
template <class T>
T SeqList::Delete(int i)
{
if (length==0) throw "下溢";
if (i<1 | | i>length) throw "位置";
x=data[i-1];
for (j=i; j<length; j++)
data[j-1]=data[j]; //注意此处j已经是元素所在的数组下标
length--;
return x;
}

顺序表删除算法Delete

⑶ 查找算法
template <class T>
int SeqList::Locate(T x)
{
for (i=0; i<length; i++)
if (data[i]==x) return i+1; //下标为i的元素等于x，返回其序号i+1
return 0; //退出循环，说明查找失败
}
顺序表按值查找算法Locate

班级：_________ 学号：_____________ 姓名：___________ 成绩：_________
实验一 顺序表操作验证
一、 实验目的
二、 实验内容
三、 设计与编码
a) 本实验用到的理论知识
实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关。
b) 算法设计
对本次实验内容设计c++类定义，设计算法完成每个成员函数。
c) 编码
将算法转化为c++程序，设计主函数完成对各成员函数的调用。
四、 运行与调试
a) 在调试程序的过程中遇到什么问题，是如何解决的？
b) 设计了哪些设计数据？测试结果是什么？
c) 程序运行的结果如何？
五、 实验小结

说明：1.实验报告用A4纸打印。
2.实验标题用黑体小三加粗。
3.每节标题用黑体小四加粗。
4.正文用宋体五号字。