静态数据表类定义

《静态数据表类定义》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9章排序静态数据表类定义#includeconstintDefaultSize=100;templateclassdataList//数据表的前视声明templateclassElement{//数据表元素类的定义friendclassdataList;private:Typekey;//排序码fieldotherdata;//其它数据成员public:TypegetKey(){returnkey;}//取当前结点的排序码voidsetKey(constTypex){ke

2、y=x;}//将当前结点的排序码修改为xElement&operator=(Element&x)//结点x的值赋给this{key=x->key;otherdata=x->otherdata;}intoperator==(Type&x){returnkey==x->key;}//判this与x相等intoperator<=(Type&x){returnkey<=x->key;}//判this小于或等于xintoperator>(Type&x){returnkey>x->key;}//判this大于xintoperator<(Ty

3、pe&x){returnkey>x->key;}//判this小于x}templateclassdataList{//用顺序表来存储待排序的元素，这些元素的类型是Typeprivate:Element*Vector;//存储待排序元素的向量intMaxSize,CurrentSize;//最大元素个数与当前元素个数intPartition(constintlow,constinthigh)//用于快速排序的一次划分算法public:datalist(intMaxSz=DefaultSize):MaxSize(Maxsz

4、),CurrentSize(0){Vector=newElement[MaxSize];}//构造函数intlength(){returnCurrentSize;}Element&operator[](inti){returnVector[i];}voidswap(Element&x,Element&y)//交换x,y{Elementtemp=x;x=y;y=temp;}voidSort();//排序}静态链表类定义templateclassstaticlinkList;

5、//静态链表类的前视声明templateclassElement{//静态链表元素类的定义friendclassstaticlinkList;private:Typekey;//排序码，其它信息略intlink;//结点的链接指针public:16第9章排序TypegetKey(){returnkey;}//取当前结点的排序码voidsetKey(constTypex){key=x;}//将当前结点的排序码修改为xintgetLink(){returnlink;}//取当前结点的链接指针voidsetLink(cons

6、tintptr){link=ptr;}//将当前结点的链接指针置为ptr}templateclassstaticlinkList{//静态链表的类定义private:Element*Vector;//存储待排序元素的向量intMaxSize,CurrentSize;//向量中最大元素个数和当前元素个数public:dstaticlinkList(intMaxsz=DefaultSize):MaxSize(Maxsz),CurrentSize(0){Vector=newElement[Maxsz];}}9-1

7、什么是内排序?什么是外排序?什么排序方法是稳定的?什么排序方法是不稳定的?【解答】内排序是排序过程中参与排序的数据全部在内存中所做的排序，排序过程中无需进行内外存数据传送，决定排序方法时间性能的主要是数据排序码的比较次数和数据对象的移动次数。外排序是在排序的过程中参与排序的数据太多，在内存中容纳不下，因此在排序过程中需要不断进行内外存的信息传送的排序。决定外排序时间性能的主要是读写磁盘次数和在内存中总的记录对象的归并次数。不稳定的排序方法主要有希尔排序、直接选择排序、堆排序、快速排序。不稳定的排序方法往往是按一定的间隔移动或交换记录对象的位置，从而可能

8、导致具有相等排序码的不同对象的前后相对位置在排序前后颠倒过来。其他排序方法中如果有数据交换，只