顺序表新的代码 呵呵，谢谢ilovevc提醒，这个已经把定义和实现合并到了一起，并且加上了输入和输出方法，经过调度，代码已经能够正常运行并完成任务:) 这个就是抽象定义和实现的代码，其中的PrintList和InputList用于输入和输出 /*第2章 数组 第2.2节顺序表
*第42页 抽象数据定义
*
* 2005年6月21号，星期二晚
* -----------by Speed1
*/
#ifndef SEQLIST_H
#define SEQLIST_H
const DefaultSize=20;
template< class Type> class SeqList
{
public:
SeqList(int MaxSize=DefaultSize); //构造函数
~SeqList() {delete []data; } //析构函数
int Length() const {return last+1;} //计算表长度
int Find(Type& x) const; //定位函数：找x在表中的位置
int IsIn(Type& x); //判断x是否在表中
int Insert(Type& x ,int i); //插入x在表中第i个位置处
int Remove(Type& x); //删除x
int Next(Type& x); //寻找x的后继
int Prior(Type& x); //寻找x的前驱
int IsEmpty() {return last==-1;} //判断顺序表是否为空，空则返回1；否则返回0
int IsFull() {return last==MaxSize-1;}//判断顺序表满否，满则返回1；否则返回0
Type Get(int i) {return i<0||i>last?NULL:data[i];} //取第i个元素的值
void Union(SeqList<Type>& LA,SeqList<Type>& LB); //合并LA,LB,重复元素只留一下
void Intersection(SeqList<Type>& LA,SeqList<Type>& LB); //求LA,LB中的共有元素
void PrintList(); //输出顺序表的数据
void InputList(); //输入顺序表的数据
private:
Type* data; //存放顺序表的数组
int MaxSize; //顺序表最大可容纳项数
int last; //顺序表当前是已存表项的最后位置
};
template <class Type> SeqList<Type>::SeqList(int sz)
{
//构造函数，通过描写参数sz定义数组的长度。
if(sz>0)
{
MaxSize=sz;
last=sz-1;
data=new Type[MaxSize];
}
}
template <class Type> int SeqList<Type>::Find(Type& x) const
{
//定位，找x在表中位置 ，若查找成功，函数 返回表项的位置，否则函数返回-1
int i=0;
while(i<=last&&data[i]!=x)
i++;
if(i>last)
return -1;
else
return i;
}
template <class Type> int SeqList<Type>::IsIn(Type& x)
{
//判断x是否在表中
int i=0,found=0;
while(i<==last&&!found)
if(data[i]!=x)
i++;
else
found=1;
return found;
}
template <class Type> int SeqList<Type>::Insert(Type& x,int i)
{
//插入x在表中第i个位置处。函数返回插入是否成功的信息，若为0则插入不成功。
if(i<0||i>last+1||last==MaxSize-1) return 0;
else
{
last++;
for(int j=last;j>i;j--)
data[j]=data[j-1];
data[i]=x;
return 1;
}
}
template <class Type> int SeqList<Type>::Remove(Type& x)
{
int i=Find(x);
if(i>=0)
{
last--;
for(int j=i;j<=last;j++)
data[j]=data[j+1];
return 1;
}
return 0;
}
template <class Type> int SeqList<Type>::Next(Type& x)
{
//寻找x的后继数据
int i=Find(x);
if(i>=0&&i<last)
return i+1;
else
return -1;
}
template <class Type> int SeqList<Type>::Prior(Type& x)
{
int i=Find(x);
if(i>0&&i<=last)
return i-1;
else
return -1;
}
template <class Type> void SeqList<Type>::Union(SeqList<Type>& LA,SeqList<Type>& LB)
{
//合并顺序表LA与LB，重复元素只留一下。
int n=LA.Length();
int m=LB.Length();
for(int i=0;i<m;i++)
{
Type x=LB.Get(i);
int k=LA.Find(x);
if(k==-1)
{
LA.Insert(n+1,x);
n++;
}
}
}
template <class Type> void SeqList<Type>::Intersection(SeqList<Type> &LA,SeqList<Type>& LB)
{
//求顺序表LA与LB中的共有元素
int n=LA.Length();
int m=LB.Length();
int i=0;
while(i<n)
{
Type x=LA.Get(i);
int k=LB.Find(x);
if(-1==k)
{
LA.Remove(x);
n--;
}
else
i++;
}
}
template <class Type> void SeqList<Type>::PrintList()
{
//自己写的输出数据方法
int l=Length()-1;
for(int i=0;i<l;i++)
cout<<"\tData["<<i<<"]:"<<data[i]<<endl;
}
template <class Type> void SeqList<Type>::InputList()
{
//自己写的输入数据方法
int l=Length()-1;
for(int i=0;i<l;i++)
{
cout<<"\tPlease enter data["<<i<<"]:";
cin>>data[i];
//cout<<endl;
}
}
#endif
呵呵，这个就是主程序了，加上了新的输入、输出测试:) /*第2章 数组 第2.2节顺序表
*第42页 测试主程序
*
* 2005年6月21号，星期二晚
* -----------by Speed1
*/
#include <iostream.h>
#include "SeqList.h"
//const defaultSize=20;
void main()
{
SeqList<int> Test1(5);
SeqList<int> Test2(6);
cout<<"Test1.length:"<<Test1.Length()<<endl;
cout<<"Test2.length:"<<Test2.Length()<<endl;
cout<<"未出始化的数据："<<endl;
cout<<"Test1:"<<endl;
Test1.PrintList();
cout<<"Test2:"<<endl;
Test2.PrintList();
cout<<"输入Test1的数据:"<<endl;
Test1.InputList();
cout<<"新的数据:"<<endl;
Test1.PrintList();
}
PS:找了个好东西。这回就不要那么费尽了，而且更加的清楚。
PPS:再次感谢ilovevc的提醒，不然不知道要走多少弯路.
|
