一.顺序表
(1)顺序存储
(2)随机存取
(3)数组下标从0开始,而线性表中元素序号是从1开始的。
(4)数组的长度要大于当前线性表的长度。
顺序表的实现:
将顺序表的 “ 抽象数据类型 ” 定义在 顺序表存储结构下 用 c++ 的类实现:顺序表类!
#include<iostream>
using namespace std;
template<typename Datatype>
class Sequential{
private:
Datatype data[120];
int length;
public:
Sequential(){length=0;} // 空的顺序表
Sequential(Datatype a[],int n); // 有参构造函数
~Sequential(){length=0;} // 析构函数
int get_long(){return length;} // 元素个数(长度)
Datatype get_y(int i); // 第i位上元素
int get_x(Datatype x); // x 的位置
void insert_i(int i,Datatype x); // 在i位置上插入x
Datatype schu(int k); // 输出k位置上元素
int empty_data(){ // 是否为空
if(length==0)
return 0;
else
return 1;
}
void shuc(); // 输出全部元素
};
template<typename Datatype>
Sequential<Datatype>::Sequential(Datatype a[],int n){
if(n > 120)
{
throw "参数异常";
}
else
{
for(int i=0;i<n;++i)
{
data[i]=a[i];
}
length=n;
}
}
template<typename Datatype>
Datatype Sequential<Datatype>::get_y(int i){
if(i<1||i>length)
{
throw "查找位置异常";
}
else
{
return data[i-1];
}
}
template<typename Datatype>
int Sequential<Datatype>::get_x(Datatype x){
for(int i=0;i<length;++i)
{
if(data[i]==x)
return ++i;
}
return 0;
}
template<typename Datatype>
void Sequential<Datatype>::insert_i(int i,Datatype x){
if(i<1||i>length)
{
throw "上溢";
}
else
{
for(int j=length;j>=i;j--)
{
data[j]=data[j-1];
}
data[i-1]=x;
length++;
}
}
template<typename Datatype>
Datatype Sequential<Datatype>::schu(int k){
if(length==0)
{
throw "下溢";
}
else
{
if(k<1||k>length)
{
throw "输出位置错误";
}
else
{
Datatype x;
x=data[k-1];
for(int i=k;i<length;++i)
{
data[i-1]=data[i];
}
length--;
return x;
}
}
}
template<typename Datatype>
void Sequential<Datatype>::shuc(){
for(int i=0;i<length;i++)
{
cout<<data[i]<<" ";
}
cout<<endl;
}
int main()
{
int l=0,c[150],j;
while(cin>>j&&j!=0)
{
c[l]=j;
++l;
}
Sequential<int> biao(c,l);
biao.shuc();
cout<<"长度:"<<biao.get_long()<<endl;
cout<<" 第3个是:"<<biao.get_y(3)<<endl;
biao.insert_i(3,520);
cout<<" 520 的位置: "<<biao.get_x(520)<<endl;
biao.schu(5);
biao.schu(6);
cout<<" 是否为空: "<<biao.empty_data()<<endl;
biao.shuc();
cout<<"长度: "<<biao.get_long()<<endl;
return 0;
}
对于下标序号的理解:
一群人按顺序住进小平房里,第一个人住进0号房间,第二个人住进1号房间······第n个人住进n-1号房间。
-------课本小例题:约瑟夫环问题:
#include<iostream>
using namespace std;
int main()
{
int n,k,m;
cin>>n>>k>>m;
int a[120];
int yi=0;
for(int i=1;i<=n;++i)
{
a[i] = i;
}
int y=n;
for(int x=k;y>1; )
{
if(a[x]!=0)
{
++yi;
if(yi==m)
{
a[x]=0;
--y;
yi=0;
}
}
++x;
if(x>n)
{
x=x%n;
}
}
for(int i=1;i<=n;++i)
{
if(a[i]!=0)
cout<<i;
}
return 0;
}