第 9 章 排序
静态数据表类定义
#include <iostream.h>
const int DefaultSize = 100;
template <class Type> class dataList //数据表的前视声明
template <class Type> class Element { //数据表元素类的定义
friend class dataList <Type>;
private:
Type key; //排序码
field otherdata; //其它数据成员
public:
Type getKey ( ) { return key; } //取当前结点的排序码
void setKey ( const Type x ) { key = x; } //将当前结点的排序码修改为 x
Element<Type>& operator = ( Element<Type>& x ) //结点 x 的值赋给 this
{ key = x->key; otherdata = x->otherdata; }
int operator == ( Type& x ) { return key == x->key; } //判 this 与 x 相等
int operator <= ( Type& x ) { return key <= x->key; } //判 this 小于或等于 x
int operator > ( Type& x ) { return key > x->key; } //判 this 大于 x
int operator < ( Type& x ) { return key > x->key; } //判 this 小于 x
}
template <class Type> class dataList {
//用顺序表来存储待排序的元素，这些元素的类型是 Type
private:
Element <Type> * Vector; //存储待排序元素的向量
int MaxSize, CurrentSize; //最大元素个数与当前元素个数
int Partition ( const int low, const int high ) //用于快速排序的一次划分算法
public:
datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0)
{ Vector = new Element <Type> [MaxSize]; } //构造函数
int length ( ) { return CurrentSize; }
Element<Type>& operator [ ] ( int i ) { return Vector[i]; }
void swap ( Element <Type>& x, Element <Type>& y ) //交换 x, y
{ Element <Type> temp = x; x = y; y = temp; }
void Sort ( ); //排序
}
静态链表类定义
template <class Type> class staticlinkList; //静态链表类的前视声明
template <class Type> class Element { //静态链表元素类的定义
friend class staticlinkList<Type>;
private:
Type key; //排序码，其它信息略
int link; //结点的链接指针
public:
1
