静态数据表类定义.doc

第9章排序

静态数据表类定义
#include<iostream.h>
constintDefaultSize=100;
template<classType>classdataList //数据表的前视声明

template<classType>classElement{ //数据表元素类的定义
friendclassdataList<Type>;
private:
Typekey; //排序码
fieldotherdata; //其它数据成员
public:
TypegetKey(){returnkey;} //取当前结点的排序码
voidsetKey(constTypex){key=x;} //将当前结点的排序码修改为x
Element<Type>&operator=(Element<Type>&x) //结点x的值赋给this
{key=x->key;otherdata=x->otherdata;}
intoperator==(Type&x){returnkey==x->key;} //判this与x相等
intoperator<=(Type&x){returnkey<=x->key;} //判this小于或等于x
intoperator>(Type&x){returnkey>x->key;} //判this大于x
intoperator<(Type&x){returnkey>x->key;} //判this小于x
}

template<classType>classdataList{
//用顺序表来存储待排序的元素，这些元素的类型是Type
private:
Element<Type>*Vector; //存储待排序元素的向量
intMaxSize,CurrentSize; //最大元素个数与当前元素个数
intPartition(constintlow,constinthigh) //用于快速排序的一次划分算法
public:
datalist(intMaxSz=DefaultSize):MaxSize(Maxsz),CurrentSize(0)
{Vector=newElement<Type>[MaxSize];} //构造函数
intlength(){returnCurrentSize;}
Element<Type>&operator[](inti){returnVector[i];}
voidswap(Element<Type>&x,Element<Type>&y) //交换x,y
{Element<Type>temp=x;x=y;y=temp;}
voidSort(); //排序
}

静态链表类定义
template<classType>classstaticlinkList; //静态链表类的前视声明

template<classType>classElement{ //静态链表元素类的定义
friendclassstaticlinkList<Type>;
private:
Typekey; //排序码，其它信息略
intlink; //结点的链接指针
public:
TypegetKey(){returnkey;} //取当前结点的排序码
voidsetKey(constTypex){key=x;} //将当前结点的排序码修改为x
intgetLink(){returnlink;} //取当前结点的链接指针
voidsetLink(constintptr){link=ptr;} //将当前结点的链接指针置为ptr
}

template<classType>classstaticlinkList{ //静态链表的类定义
private:
Element<Type>*Vector; //存储待排序元素的向量
intMaxSize,CurrentSize; //向量中最大元素个数和当前元素个数
public:
dstaticlinkList(intMaxsz=DefaultSize):MaxSize(Maxsz),CurrentSize(0)
{Vector=newElement<Type>[Maxsz];}
}

9-1什么是内排序?什么是外排序?什么排序方法是稳定的?什么排序方法是不稳定的?
【解答】内排序是排序过程中参与排序的数据全部在内存中所做的排序，排序过程中无需进行内外存数据传送，决定排序方法时间性能的主要是数据排序码的比较次数和数据对象的移动次数。外排序是在排