By FastHorse March 5, 2017
順序表定義
按順序方式存儲的線性表稱為順序表(arry - based list)，又稱為向量(vector)，通過創(chuàng)建數(shù)組來建立。順序表中的每個元素按其順序有唯一的索引值，又稱下標值社裆，可以用來方便地訪問元素內(nèi)容。
順序表的類定義
只要確定了基地址，線性表中的任意元素的地址都可以方便地計算出來涎拉，從而達到隨機存取的效果，因此元素間的物理相鄰關(guān)系表示了他們邏輯上的相鄰關(guān)系的圆。
c++程序?qū)崿F(xiàn)：
class arrList{
private:
int *data; //存儲數(shù)據(jù)表的實例
int maxSize; //順序表實例的最大長度
int last; //當前處理位置
public:
arrList(int sz=defaultSize); //構(gòu)造函數(shù)
~arrList(){delete[] data;} //析構(gòu)函數(shù)
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();//區(qū)域刪除
bool IsEmpty(){return last==-1?true:false;} //判空
bool IsFull(){return last==maxSize-1?true:false;} //判滿
void input();//寫入
void output();//輸出
void upDate();//更新
};
順序表的運算實現(xiàn)
下面著重介紹基于數(shù)組的順序表插入鼓拧、刪除運算。
順序表的插入
（1）根據(jù)位置插入
根據(jù)位置插入是將指定元素插入到指定位置越妈。除了涉及被更新的那個元素之外季俩，其他的線性關(guān)系的相對順序應(yīng)保持不變。為此梅掠，需要對順序表實施一系列的元素移動操作來維護邏輯和存儲的線性關(guān)系酌住。
c++程序?qū)崿F(xiàn)：
bool arrList::Insert(){ //按位置插入
if(last==maxSize-1)return false;
int i,x;
cout<<endl;
cout<<"輸入插入的數(shù)字:";
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）根據(jù)大小插入
根據(jù)大小插入算法適用于數(shù)據(jù)元素遞增的順序表。從順序表的第一個元素開始尋找瓤檐，找到比自己大的元素就插在該元素前面赂韵。輸入一個數(shù)字x，從順序表的第一個元素開始循環(huán)挠蛉，判斷輸入的元素是否小于等于順序表中元素祭示，若成立，則將輸入元素插入表中，若不成立质涛，則繼續(xù)判斷順序表中下一個元素稠歉。
c++程序?qū)崿F(xiàn)：
bool arrList::SeqInsert(){ //按大小順序插入
if(last==maxSize-1)return false;
int x;
cout<<endl;
cout<<"輸入插入的數(shù)字:";
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）根據(jù)位置刪除
刪除運算需要事先檢查順序表是否為空表，只在非空表是才能進行刪除汇陆。該算法要求輸入一個刪除的位置怒炸，判斷該位置是否有效。若有效毡代，通過左移運算將data[i-1]數(shù)組元素刪除阅羹，從而完成對指定位置元素刪除的功能。
c++程序?qū)崿F(xiàn)：
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成功!刪除的數(shù)為："<<x<<endl;
return true;
}
（2）區(qū)域刪除
區(qū)域刪除算法適用于要在順序表中刪除多個相鄰元素教寂。首先輸入兩個刪除的位置捏鱼，同樣通過左移運算將該區(qū)域內(nèi)的所有元素刪除。
c++程序?qū)崿F(xiàn)：
bool arrList::SeqRemove(){ //區(qū)域刪除
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; //存儲數(shù)據(jù)表的實例
int maxSize; //順序表實例的最大長度
int last; //當前處理位置
public:
arrList(int sz=defaultSize); //構(gòu)造函數(shù)
~arrList(){delete[] data;} //析構(gòu)函數(shù)
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();//區(qū)域刪除
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){ //構(gòu)造函數(shù)
if(sz>0)
{
maxSize=sz;last=-1;
data=new int[maxSize];
if(data==NULL)
{
cerr<<"error!!"<<endl;exit(1);
}
}
}
void arrList::input(){ //輸入
cout<<"開始建立順序表,輸入表中元素個數(shù)：";
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<<"輸入插入的數(shù)字:";
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<<"輸入插入的數(shù)字:";
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成功!刪除的數(shù)為："<<x<<endl;
return true;
}
bool arrList::SeqRemove(){ //區(qū)域刪除
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請輸入查詢的數(shù)：";
cin>>x;
for(int i=0;i<=last;i++)
if(data[i]==x)
cout<<"數(shù)字在位置:"<<i+1;
}
void arrList::Locate()const{ //定位
int i;
cout<<"輸入位置：";
cin>>i;
if(i>=1||i<=last+1)
cout<<"位置上的數(shù)為:"<<data[i-1];
}
void arrList::upDate(){ //更新
int i,x;
cout<<"輸入位置：";
cin>>i;
if(i<1||i>last+1) return;
cout<<"輸入更新的數(shù)據(jù)：";
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); //執(zhí)行程序析構(gòu)
default:
cout<<"輸入有誤导梆，請重試"<<endl;
}
}
return 0;
}
參考文獻：
張銘，王騰蛟迂烁，趙海燕. 數(shù)據(jù)結(jié)構(gòu)與算法. 高等教育出版社看尼，2008.6
