//SequentialList.h 顺序表模板类
#ifndef SEQUENTIAL_LIST_HXX
#define SEQUENTIAL_LIST_HXX
using std::cout;
using std::endl;
const int MaxSize=100; //顺序表数组最大值
template<class T>
class SeqList //定义模板类SeqList(顺序表)
{
public:
SeqList() { length=0; } //无参构造函数,建立一个空的顺序表
SeqList(T a[],int n); //有参构造函数,建立一个长度为n的顺序表 n不大于MaxSize
~SeqList() {} //析构函数
int Length() { return length; } //求线性表长度
T Get(int i); //按位查找,在线性表中查找第i个元素
int Locate(T x); //按值查找,在线性表中找值为x的元素序号
void Insert(int i,T x); //插入操作,在线性表中的第i个位置插入值为x的元素
T Delete(int i); //删除操作,删除线性表的第i个元素
void PrintList(); //遍历操作,按序号依次输出各元素
private:
T data[MaxSize]; //存放数据元素的数组
int length; //线性表的长度
};
template<class T>
SeqList<T>::SeqList(T a[],int n)
{
if(n>MaxSize) throw "参数非法";
for(int i=0;i<n;i++)
data[i]=a[i];
length=n;
}
template<class T>
T SeqList<T>::Get(int i)
{
if(i<1||i>length) throw "参数非法";
return data[i-1];
}
template<class T>
int SeqList<T>::Locate(T x)
{
for(int i=0;i<length;i++)
if(data[i]==x) return i+1; //下标为i的元素等于x,返回其序号i+1
return 0; //退出循环,说明查找失败
}
template<class T>
void SeqList<T>::Insert(int i,T x)
{
if(length>=MaxSize) throw "上溢";
if(i<1||(i>length+1)) throw "位置溢出";
for(int j=length;j>=i;j--)
data[j]=data[j-1]; //注意第j个元素存在于数组小标为j-1处
data[i-1]=x;
length++;
}
template<class T>
T SeqList<T>::Delete(int i)
{
if(length==0) throw "下溢";
if(i<1||i>length) throw "位置";
T x=data[i]; //取出位置i的元素
for(int j=i;j<length;j++)
data[j-1]=data[j]; //此处j已经是元素所在的数组下表
length--;
return x;
}
template<class T>
void SeqList<T>::PrintList()
{
for(int i=0;i<length;i++)
cout<<data[i]; //依次输出线性表的元素值
}
#endif
//seqlisttest.cpp
#include <iostream>
#include "SequentialList.h"
using std::cout;
using std::endl;
int main()
{
int m[10]={1,2,3,4,28,50,7,8,9,10};
SeqList<int> seqList(m,10);
cout<<"顺序表原始状态"<<endl;
seqList.PrintList();
cout<<"顺序表第5个元素值"<<seqList.Get(5)<<endl;
cout<<"顺序表长度"<<seqList.Length()<<endl;
cout<<"顺序表删除一个元素后的状态"<<endl;
seqList.Delete(5);
seqList.PrintList();
cout<<"顺序表第5个元素值"<<seqList.Get(5)<<endl;
cout<<"顺序表长度"<<seqList.Length()<<endl;
cout<<"顺序表增加一个元素后的状态"<<endl;
seqList.Insert(5,108);
seqList.PrintList();
cout<<"顺序表第5个元素值"<<seqList.Get(5)<<endl;
cout<<"顺序表长度"<<seqList.Length()<<endl;
cout<<"顺序表中数值=108在表中第"<<seqList.Locate(108)<<"位"<<endl;
return 0;
}