学步园

在所有的数据结构的种类中，有一种简单顺序存放的表，这种数据结构简单而且很实用，就是顺序表。

顺序表是一种线性聚集。顺序表的特点是为了得到顺序表中所要求的表项，必须从表的第一个表项开始，逐个访问表项，直到找到满足要求的表项为止，也就是说，对于顺序表只能顺序存取。

下面，我用代码实现顺序表的基本操作。

#include <iostream><br /> using namespace std;<br /> class SeqList<br /> {<br /> public:<br /> SeqList(int MaxSize);<br /> ~SeqList(){delete []data;}<br /> int Length()const{return last + 1;}<br /> int Find(int &x)const;<br /> int IsIn(int &x);<br /> int Insert(int &x,int i);<br /> int Remove(int &x);<br /> int Next(int &x);<br /> int Prior(int &x);<br /> int IsEmpty(){return last == -1;}<br /> int IsFull(){return last == MaxSize - 1;}<br /> int Get(int i){return i < 0 || i > last ? NULL : data[i];}<br /> void ChooseConduct();<br /> void ShowList();<br /> private:<br /> int *data;<br /> int MaxSize;<br /> int last;<br /> };<br /> SeqList::SeqList(int sz)<br /> {<br /> if(sz > 0)<br /> {<br /> MaxSize = sz;<br /> last = -1;<br /> data = new int[MaxSize];<br /> }<br /> cout<<"请输入顺序表的数值：";<br /> for(int i = 0;i < MaxSize;i++)<br /> {<br /> cin>>data[i];<br /> last++;<br /> }<br /> }<br /> int SeqList::Find(int &x)const<br /> {<br /> int i = 0;<br /> while(i <= last && data[i] != x)<br /> i++;<br /> if(i > last)<br /> return -1;<br /> else<br /> return i;<br /> }<br /> int SeqList::IsIn(int &x)<br /> {<br /> int i = 0,found = 0;<br /> while(i <= last && !found)<br /> {<br /> if(data[i] != x)<br /> i++;<br /> else found = 1;<br /> }<br /> return found;<br /> }<br /> int SeqList::Insert(int &x,int i)<br /> {<br /> if(i < 0 || i > last + 1 || last == MaxSize - 1)<br /> return 0;<br /> else<br /> {<br /> last++;<br /> for(int j = last;j > i;j--)<br /> data[j] = data[j - 1];<br /> data[i] = x;<br /> return 1;<br /> }<br /> }<br /> int SeqList::Remove(int &x)<br /> {<br /> int i = Find(x);<br /> if(i >= 0)<br /> {<br /> last--;<br /> for(int j = i;j <= last;j++)<br /> data[j] = data[j + 1];<br /> return 1;<br /> }<br /> return 0;<br /> }<br /> int SeqList::Next(int &x)<br /> {<br /> int i = Find(x);<br /> if(i >= 0 && i < last)<br /> return data[i + 1];<br /> else<br /> return -1;<br /> }<br /> int SeqList::Prior(int &x)<br /> {<br /> int i = Find(x);<br /> if(i > 0 && i <= last)<br /> return data[i - 1];<br /> else<br /> return -1;<br /> }<br /> void SeqList::ShowList()<br /> {<br /> for(int i = 0;i < last + 1;i++)<br /> cout<<data[i]<<" ";<br /> cout<<endl;<br /> }<br /> void SeqList::ChooseConduct()<br /> {<br /> int Choose = 1;<br /> cout<<"1:求顺序表的长度"<<endl;<br /> cout<<"2:查找"<<endl;<br /> cout<<"3:判断是否存在某个数"<<endl;<br /> cout<<"4:插入"<<endl;<br /> cout<<"5:删除"<<endl;<br /> cout<<"6:后继"<<endl;<br /> cout<<"7:前驱"<<endl;<br /> cout<<"8:取值"<<endl;<br /> cout<<"9:判断是否为空"<<endl;<br /> cout<<"10:判断是否为满"<<endl;<br /> cout<<"11:打印顺序表"<<endl;<br /> cout<<"12:退出程序"<<endl;<br /> while(Choose)<br /> {<br /> cout<<"请输入选择：";<br /> cin>>Choose;<br /> switch(Choose)<br /> {<br /> case 1:cout<<Length()<<endl;break;<br /> case 2:<br /> {<br /> int i;<br /> cout<<"please input the number:";<br /> cin>>i;<br /> cout<<Find(i)<<endl;<br /> break;<br /> }<br /> case 3:<br /> {<br /> int i;<br /> cout<<"please input the number:";<br /> cin>>i;<br /> cout<<IsIn(i)<<endl;<br /> break;<br /> }<br /> case 4:<br /> {<br /> int Num,Location;<br /> cout<<"please input the number and location:";<br /> cin>>Num;<br /> cin>>Location;<br /> cout<<Insert(Num,Location)<<endl;<br /> break;<br /> }<br /> case 5:<br /> {<br /> int i;<br /> cout<<"please input the number:";<br /> cin>>i;<br /> cout<<Remove(i)<<endl;<br /> break;<br /> }<br /> case 6:<br /> {<br /> int i;<br /> cout<<"please input the number:";<br /> cin>>i;<br /> cout<<Next(i)<<endl;<br /> break;<br /> }<br /> case 7:<br /> {<br /> int i;<br /> cout<<"please input the number:";<br /> cin>>i;<br /> cout<<Prior(i)<<endl;<br /> break;<br /> }<br /> case 8:<br /> {<br /> int i;<br /> cout<<"please input the number:";<br /> cin>>i;<br /> cout<<Get(i)<<endl;<br /> break;<br /> }<br /> case 9:cout<<IsEmpty()<<endl;break;<br /> case 10:cout<<IsFull()<<endl;break;<br /> case 11:ShowList();break;<br /> default:<br /> {<br /> cout<<"Bye - Bye!"<<endl;<br /> return;<br /> }<br /> }<br /> }<br /> }<br /> void main()<br /> {<br /> SeqList list(5);<br /> list.ChooseConduct();<br /> }<br />

下面在介绍一下作为抽象数据类型，使用顺序表的事例。

“并”运算和“交”运算：

Void
Union(SeqList &LA,SeqList &LB)

{

Int n =
LA.Length();

Int m =
LB.Length();

For(int I = 0;I

＜
m;i++)

{

Int x =
LB.Get(i);

Int k =
LA.Find(x);

If(k ==  -1)

{

LA.Insert(n +
1,x);

N++;

}

}

}

Void
Insertsection(SeqList &LA,SeqList &LB)

{

Int n =
LA.Length();

Int m =
LB.Length();

Int I = 0;

While(I <
ｎ
)

｛

Int x =
LA.Get(i);

Int k =
LB.Find(x);

If(k == -1)

{

LA.Remove(x);

N--;

}

Else

I++;

｝

}

因为代码比较简单，所以没有什么注释！