实验一顺序表操作验证
一、实验目的
⑴掌握线性表的顺序存储结构；
⑵验证顺序表及其基本操作的实现；
⑶掌握数据结构及算法的程序实现的基本方法。
二、实验内容
⑴建立含有若干个元素的顺序表；
⑵对已建立的顺序表实现插入、删除、查找等基本操作。
三、设计与编码
(a)本实验用到的理论知识
首先定义顺序表的数据类型——顺序表类SeqList，包括题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。
(b)算法设计
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个数据元素的顺序表，即设计构造函数。
算法如下：
最后，对建立的顺序表设计插入、删除、查找等基本操作的算法。
⑴插入算法
⑵删除算法
⑶查找算法
(c)编码
#include<iostream>
#include<stdlib.h>
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;i<n;i++)
data[i]=a[i];
length=n;
}
~SeqList(){}
int Length(){return length;}
char Get(int i){
if(i<1&&i>length)throw"查找位置非法";
else return data[i-1];
}
int Locate(char x){
for(int i=0;i<length;i++)
if(data[i]==x)return i+1;
return 0;
}
void Insert(int i,char x){
if(length>=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<length; j++)
data[j-1]=data[j];
length--;
return x;
}
void PrintList(){
for(int i=0;i<length;i++)
cout<<data[i]<<endl;
}
private:
char data[MaxSize];
int length;
};
void main()
{
int xh1,xh2,xh3;
char x[10],xm1,xm2;
cout<<"输入需要记录的数据："<<endl;
for(int i=0;i<10;i++){
cin>>x[i];
}
SeqList studentx(x,10);
cout<<"表长为："<<studentx.Length()<<endl;
cout<<"输入数据位置：";
cin>>xh1;
cout<<"查找的数据为："<<studentx.Get(xh1)<<endl;
cout<<"输入需要查找的数据：";
cin>>xm1;
cout<<"该数据位置为："<<studentx.Locate(xm1)<<endl;
cout<<"添加数据，输入位置：";
cin>>xh2;
cout<<"输入数据：";
cin>>xm2;
studentx.Insert(xh2,xm2);
cout<<"删除数据，输入位置：";
cin>>xh3;
cout<<"删除结果为："<<studentx.Delete(xh3)<<endl;
cout<<"输出数据："<<endl;
studentx.PrintList();
}
五、运行与调试
(a)在调试程序的过程中遇到什么问题，是如何解决的？
数据类型定义错误，将int改为char解决。
(b)设计了哪些设计数据？测试结果是什么？
(c)程序运行的结果如何?
六、实验小结
由于有上学期学习c++语言的基础，所以本次试验比较容易，主要是通过实验过程掌握线性表的顺序存储结构，验证顺序表及其基本操作的实现以及掌握数据结构及算法的程序实现的基本方法。