数据结构与算法———顺序表
2017-03-05 本文已影响136人
FastHorse
By FastHorse March 5, 2017
顺序表定义
按顺序方式存储的线性表称为顺序表(arry - based list)，又称为向量(vector)，通过创建数组来建立。顺序表中的每个元素按其顺序有唯一的索引值，又称下标值，可以用来方便地访问元素内容。
顺序表的类定义
只要确定了基地址，线性表中的任意元素的地址都可以方便地计算出来，从而达到随机存取的效果，因此元素间的物理相邻关系表示了他们逻辑上的相邻关系。
c++程序实现：
class arrList{
private:
int *data; //存储数据表的实例
int maxSize; //顺序表实例的最大长度
int last; //当前处理位置
public:
arrList(int sz=defaultSize); //构造函数
~arrList(){delete[] data;} //析构函数
int Size()const
{return maxSize;}
int Length()const //返回此顺序表的当前实际长度
{return last+1;}
void Search()const; //查询
void Locate()const; //定位
bool getData(int i,int& x)const //把位置为i的元素值返回到变量x
{if(i>1&&i<last+1){x=data[i-1];return true;}else return false;}
bool setData(int i,int& x) //用x修改位置i的元素值
{if(i>1&&i<last+1){x=data[i-1];}}
bool Insert();//插入
bool SeqInsert();//顺序插入
bool Remove();//删除
bool SeqRemove();//区域删除
bool IsEmpty(){return last==-1?true:false;} //判空
bool IsFull(){return last==maxSize-1?true:false;} //判满
void input();//写入
void output();//输出
void upDate();//更新
};
顺序表的运算实现
下面着重介绍基于数组的顺序表插入、删除运算。
顺序表的插入
（1）根据位置插入
根据位置插入是将指定元素插入到指定位置。除了涉及被更新的那个元素之外，其他的线性关系的相对顺序应保持不变。为此，需要对顺序表实施一系列的元素移动操作来维护逻辑和存储的线性关系。
c++程序实现：
bool arrList::Insert(){ //按位置插入
if(last==maxSize-1)return false;
int i,x;
cout<<endl;
cout<<"输入插入的数字:";
cin>>x;
cout<<"输入插入的位置:";
cin>>i;
if(i<0||i>maxSize-1)return false;
else
{
for(int j=last;j>=i;j--)
{data[j]=data[j-1];}
data[i-1]=x;
last++;
cout<<"插入成功!"<<endl;
return true;
}
}
（2）根据大小插入
根据大小插入算法适用于数据元素递增的顺序表。从顺序表的第一个元素开始寻找，找到比自己大的元素就插在该元素前面。输入一个数字x，从顺序表的第一个元素开始循环，判断输入的元素是否小于等于顺序表中元素，若成立，则将输入元素插入表中，若不成立，则继续判断顺序表中下一个元素。
c++程序实现：
bool arrList::SeqInsert(){ //按大小顺序插入
if(last==maxSize-1)return false;
int x;
cout<<endl;
cout<<"输入插入的数字:";
cin>>x;
for(int i=0;i<=last;i++){
if (x <= data[i])
{
for(int j=last;j>=i+1;j-- )
{data[j]=data[j-1];}
data[i]=x;
last++;
break;
}
else if(x > data[last-1])
{
data[last]=x;
last++;
break;
}
}
cout<<"插入成功!"<<endl;
return true;
}
顺序表的删除
（1）根据位置删除
删除运算需要事先检查顺序表是否为空表，只在非空表是才能进行删除。该算法要求输入一个删除的位置，判断该位置是否有效。若有效，通过左移运算将data[i-1]数组元素删除，从而完成对指定位置元素删除的功能。
c++程序实现：
bool arrList::Remove(){ //删除
int i,x;
if(last==-1)return false;
cout<<"\n请输入删除的位置：";
cin>>i;
if(i<0||i>maxSize-1)return false;
x=data[i-1];
for(int j=i;j<=last;j++)
data[j-1]=data[j];
last--;
cout<<"delete成功!删除的数为："<<x<<endl;
return true;
}
（2）区域删除
区域删除算法适用于要在顺序表中删除多个相邻元素。首先输入两个删除的位置，同样通过左移运算将该区域内的所有元素删除。
c++程序实现：
bool arrList::SeqRemove(){ //区域删除
int i,k;
if(last==-1)return false;
cout<<"\n请输入删除的位置1：";
cin>>i;
cout<<"\n请输入删除的位置2：";
cin>>k;
int h=k-i;
if(i<0||i>maxSize-1)return false;
for(int j=k;j<=last;j++)
data[j-h-1]=data[j];
last = last-h-1;
cout<<"delete成功!"<<endl;
return true;
}
顺序表的完整c++程序
#include <iostream.h>
#include<stdlib.h>
const int defaultSize=100;
class arrList{
private:
int *data; //存储数据表的实例
int maxSize; //顺序表实例的最大长度
int last; //当前处理位置
public:
arrList(int sz=defaultSize); //构造函数
~arrList(){delete[] data;} //析构函数
int Size()const
{return maxSize;}
int Length()const //返回此顺序表的当前实际长度
{return last+1;}
void Search()const; //查询
void Locate()const; //定位
bool getData(int i,int& x)const //把位置为i的元素值返回到变量x
{if(i>1&&i<last+1){x=data[i-1];return true;}else return false;}
bool setData(int i,int& x) //用x修改位置i的元素值
{if(i>1&&i<last+1){x=data[i-1];}}
bool Insert();//插入
bool SeqInsert();//顺序插入
bool Remove();//删除
bool SeqRemove();//区域删除
bool IsEmpty(){return last==-1?true:false;} //判空
bool IsFull(){return last==maxSize-1?true:false;} //判满
void input();//写入
void output();//输出
void upDate();//更新
};
arrList::arrList(int sz){ //构造函数
if(sz>0)
{
maxSize=sz;last=-1;
data=new int[maxSize];
if(data==NULL)
{
cerr<<"error!!"<<endl;exit(1);
}
}
}
void arrList::input(){ //输入
cout<<"开始建立顺序表,输入表中元素个数：";
while(1)
{
cin>>last;
if(last<=maxSize-1)break;
cout<<"输入有误，范围不能超过"<<maxSize-1<<":";
}
for(int i=0;i<last;i++)
{cout<<i+1<<"\t";cin>>data[i];}
}
void arrList::output(){ //输出
cout<<endl;
cout<<"最后位置为:"<<last<<endl;
for(int i=0;i<last;i++)
{cout<<"#"<<i+1<<":"<<data[i]<<endl;}
}
bool arrList::Insert(){ //按位置插入
if(last==maxSize-1)return false;
int i,x;
cout<<endl;
cout<<"输入插入的数字:";
cin>>x;
cout<<"输入插入的位置:";
cin>>i;
if(i<0||i>maxSize-1)return false;
else
{
for(int j=last;j>=i;j--)
{data[j]=data[j-1];}
data[i-1]=x;
last++;
cout<<"插入成功!"<<endl;
return true;
}
}
bool arrList::SeqInsert(){ //按大小顺序插入
if(last==maxSize-1)return false;
int x;
cout<<endl;
cout<<"输入插入的数字:";
cin>>x;
for(int i=0;i<=last;i++){
if (x <= data[i])
{
for(int j=last;j>=i+1;j-- )
{data[j]=data[j-1];}
data[i]=x;
last++;
break;
}
else if(x > data[last-1])
{
data[last]=x;
last++;
break;
}
}
cout<<"插入成功!"<<endl;
return true;
}
bool arrList::Remove(){ //删除
int i,x;
if(last==-1)return false;
cout<<"\n请输入删除的位置：";
cin>>i;
if(i<0||i>maxSize-1)return false;
x=data[i-1];
for(int j=i;j<=last;j++)
data[j-1]=data[j];
last--;
cout<<"delete成功!删除的数为："<<x<<endl;
return true;
}
bool arrList::SeqRemove(){ //区域删除
int i,k;
if(last==-1)return false;
cout<<"\n请输入删除的位置1：";
cin>>i;
cout<<"\n请输入删除的位置2：";
cin>>k;
int h=k-i;
if(i<0||i>maxSize-1)return false;
for(int j=k;j<=last;j++)
data[j-h-1]=data[j];
last = last-h-1;
cout<<"delete成功!"<<endl;
return true;
}
void arrList::Search()const{ //查询
int x;
cout<<"\n请输入查询的数：";
cin>>x;
for(int i=0;i<=last;i++)
if(data[i]==x)
cout<<"数字在位置:"<<i+1;
}
void arrList::Locate()const{ //定位
int i;
cout<<"输入位置：";
cin>>i;
if(i>=1||i<=last+1)
cout<<"位置上的数为:"<<data[i-1];
}
void arrList::upDate(){ //更新
int i,x;
cout<<"输入位置：";
cin>>i;
if(i<1||i>last+1) return;
cout<<"输入更新的数据：";
cin>>x;
data[i-1]=x;
cout<<"\n更新成功"<<endl;
}
int main()
{
int n;
arrList s1(30);
s1.input();
while(1){
cout<<"\n------------------------"<<endl;
cout<<"1,插入"<<endl;
cout<<"2,顺序插入"<<endl;
cout<<"3,删除"<<endl;
cout<<"4,顺序删除"<<endl;
cout<<"5,查找"<<endl;
cout<<"6,定位"<<endl;
cout<<"7,输出"<<endl;
cout<<"8,更新"<<endl;
cout<<"9,退出"<<endl;
cout<<"-----------------------"<<endl;
cout<<"输入选项：";
cin>>n;
switch(n){
case 1:
s1.Insert();break;
case 2:
s1.SeqInsert();break;
case 3:
s1.Remove();break;
case 4:
s1.SeqRemove();break;
case 5:
s1.Search();break;
case 6:
s1.Locate();break;
case 7:
s1.output();break;
case 8:
s1.upDate();break;
case 9:
exit(1); //执行程序析构
default:
cout<<"输入有误，请重试"<<endl;
}
}
return 0;
}
参考文献：
张铭，王腾蛟，赵海燕. 数据结构与算法. 高等教育出版社，2008.6
