datalist.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

//数据表类
#ifndef DATALIST_H
#define DATALIST_H
#include<iostream>
using namespace std;
const int  DefaultSize = 100;
template <class T>
class Element {			//数据表元素定义
public:
	T key;				//排序码
	Element<T>& operator = (Element<T>& x) {
		key = x.key;  
		return *this;
	}
	bool operator == (Element<T>& x) 
	{ return key == x.key; }	//判*this与x相等
	bool operator <= (Element<T>& x)
	{ return key <= x.key; }	//判*this小于或等于x
	bool operator >= (Element<T>& x)
	{ return key >= x.key; }	//判*this大于或等于x bool operator > (Element<T>& x)
	bool operator > (Element <T>& x)
	{ return key > x.key; }	//判*this大于x
	bool operator < (Element<T>& x)
	{ return key < x.key; }	//判*this小于x
	friend istream & operator >>(istream& in, Element<T> & ele){
		in>>ele.key;
		return in;
	}
	friend ostream & operator <<(ostream& out, Element <T> & ele){
		out<<ele.key;
		return out;
	}
};
template <class T>
class dataList {			//数据表类定义
private:
	Element <T>* Vector;		//存储排序元素的向量
	int maxSize; 			//向量中最大元素个数
	int currentSize; 			//当前元素个数
public:
	dataList (int maxSz = DefaultSize) :     //构造函数
	  maxSize(maxSz), currentSize(0) 
	  { Vector = new Element<T>[maxSize]; }
	  int Length() { return currentSize; }	    //取表长度
	  void Swap (Element<T>& x, Element<T>& y)
	  { Element<T> temp = x;  x = y;  y = temp; }
	  Element<T>& operator [](int i) 	//取第i个元素
	  { return Vector[i]; } 		
	  int Partition (const int low, const int high);
	  //快速排序划分

	  friend ostream& operator << (ostream& out, const dataList<T> & data){
		  for (int i=0; i<data.currentSize; ++i)
			  out<<data.Vector[i]<<"   ";
		  out<<endl;
		  return out;
	  }
	  friend istream& operator >> (istream& in ,  dataList<T> & data){
		  cout<<"数据表长度："<<endl;
		  in>>data.currentSize;
		  if (data.currentSize > data.maxSize)
			  data.maxSize = data.currentSize;
		  delete [] data.Vector;
		  data.Vector = new Element<T> [data.maxSize];
		  for (int i=0; i<data.currentSize; ++i)
		  {
			  cout<<"输入数据：";
			  in>>data.Vector[i];
		  }
		  return in;
	  }

};


template <class T>
int dataList<T>::Partition (const int low, const int high) {
	//数据表类的共有函数
	int pivotpos = low;
	Element<T> pivot = Vector[low];	  //基准元素
	for (int i = low+1; i <= high; i++)
		//检测整个序列, 进行划分
		if (Vector[i] < pivot) {
			pivotpos++;
			if (pivotpos != i)   
				Swap(Vector[pivotpos],Vector[i]);
		}				//小于基准的交换到左侧去
		Vector[low] = Vector[pivotpos];
		Vector[pivotpos] = pivot;								//将基准元素就位	
		return pivotpos;	//返回基准元素位置
};

#endif