实验一.顺序表验证实验

实验一 顺序表操作验证

一、实验目的

⑴ 掌握线性表的顺序存储结构； ⑵ 验证顺序表及其基本操作的实现；

⑶ 掌握数据结构及算法的程序实现的基本方法。

二、实验内容

⑴ 建立含有若干个元素的顺序表；

⑵ 对已建立的顺序表实现插入、删除、查找等基本操作。

三、设计与编码

(a)本实验用到的理论知识

首先定义顺序表的数据类型——顺序表类SeqList，包括题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。 (b)算法设计

const int MaxSize=10;

template //定义模板类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个数据元素的顺序表，即设计构造函数。算法如下：

顺序表有参构造函数SeqList template SeqList:: SeqList(T a[ ], int n) { if (n>MaxSize) throw \"参数非法\"; for (i=0; i最后，对建立的顺序表设计插入、删除、查找等基本操作的算法。 ⑴ 插入算法

顺序表插入算法Insert template 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++; } ⑵ 删除算法

顺序表删除算法Delete template T SeqList::Delete(int i) { if (length==0) throw \"下溢\"; if (i<1 | | i>length) throw \"位置\"; x=data[i-1]; for (j=i; j顺序表按值查找算法Locate template int SeqList::Locate(T x) {

for (i=0; iif (data[i]==x) return i+1; //下标为i的元素等于x，返回其序号i+1

return 0; //退出循环，说明查找失败 }

(c)编码

#include #include using namespace std;

线性表

const int MaxSize=50; class SeqList{ public: SeqList(){length=0;} SeqList(char a[],int n){ if(n>MaxSize)throw\"参数非法\"; for(int i=0;ilength)throw\"查找位置非法\"; else return data[i-1]; } int Locate(char x){ for(int i=0;i=MaxSize)throw\"上溢\"; if(i<1||i>length+1)throw\"位置\"; for(int j=length;j>=i;j--) data[j]=data[j-1]; data[i-1]=x; length++; } char Delete(int i){ if(length==0) throw \"下溢\";

if (i<1||i>length) throw \"位置\"; char x=data[i-1];

for (int j=i; j顺序表

for(int i=0;ivoid main() { int xh1,xh2,xh3; char x[10],xm1,xm2; cout<<\"输入需要记录的数据：\"<>x[i]; } SeqList studentx(x,10); cout<<\"表长为：\"<>xh1; cout<<\"查找的数据为：\"<>xm1; cout<<\"该数据位置为：\"<>xh2; cout<<\"输入数据：\"; cin>>xm2; studentx.Insert(xh2,xm2); cout<<\"删除数据，输入位置：\"; cin>>xh3; cout<<\"删除结果为：\"<五、运行与调试

(a) 在调试程序的过程中遇到什么问题，是如何解决的？

数据类型定义错误，将int改为char解决。

线性表

(b) 设计了哪些设计数据？测试结果是什么？

(c) 程序运行的结果如何?

顺序表

六、实验小结

由于有上学期学习c++语言的基础，所以本次试验比较容易，主要是通过实验过程掌握线性表的顺序存储结构，验证顺序表及其基本操作的实现以及掌握数据结构及算法的程序实现的基本方法。