sortedlist.h

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

//有序顺序表类
#ifndef SORTEDLIST_H
#define SORTEDLIST_H
#include<iostream>
using namespace std;
#define defaultSize 100
template <class E, class K> 
class SortedList{
	int CurrentSize;									 //表长
	int maxSize;
	E * data;								 //元素数组
public: 
	SortedList(int sz=defaultSize):CurrentSize(0),maxSize(sz){data=new E[maxSize];}
	int Search (K k1) const;			     //顺序搜索关键码为x的数据对象，返回待搜索元素的位置，返回0表示没有找到
	void Insert (const E& e1);				 //插入，将值为e1的元素插入到表中
	bool Remove (const K k1, E& e1);	     /*删除
											 在dataList中删除关键码为x的元素, 通过e1返回。
											 用尾元素填补被删除元素。*/
	int BinarySearch(K k1,  int low,  int high ) const;	/*折半搜索的递归算法
														接受三个参数，分别为待查值得关键码，表的左边界和表的右边界
														返回待搜索元素的位置，返回0表示没有找到*/
	int BinarySearch (K k1) const;									/*折半搜索的迭代算法
																	接受一个参数，为待查的关键码
																	返回待搜索元素的位置，返回0表示没有找到*/
	void build()							 //自定义函数用于输入一个表
	{
		cout<<"请输入元素个数：";
		int n;
		cin>>n;
		cout<<endl;
		int temp;

		for(int i=0;i<n;i++)
		{
			cout<<"输入元素值：";
			cin>>temp;
			Insert(temp);
			cout<<endl;
		}
	}
	void show()							//自定义函数，用于输出一个表
	{
		cout<<"表为："<<endl;
		for(int i=0;i<CurrentSize;i++)
			cout<<data[i]<<"  ";
		cout<<endl;
	}

	int Length(){return CurrentSize;}
};

template <class E, class K> 
int SortedList<E, K>::Search (K k1) const {
	//顺序搜索关键码为x的数据对象
	for (int i = 1;  i <= CurrentSize;  i++)
		if (data[i-1] == k1) return i;         //成功
		else if (data[i-1] > k1) break;
		return 0;       //顺序搜索失败, 返回失败信息
};

template<class E, class K>
int SortedList<E, K>::BinarySearch
(K k1,  int low,  int high ) const {
	//折半搜索的递归算法,用到E的重载操作"<"和">"
	int mid = 0;		        //元素序号从1开始
	if (low <= high) {
		mid = (low + high) / 2;
		if (data[mid-1] < k1)     //元素序号与下标差一
			mid = BinarySearch (k1, mid +1, high);
		else if (data[mid-1] > k1)	
			mid = BinarySearch (k1, low, mid -1); 
	}
	return mid;
};

template<class E, class K> 
int SortedList <E, K>::BinarySearch (K k1) const {	      
	//折半搜索的迭代算法,用到E的重载操作"<"和">" 
	int high = CurrentSize,  low = 1,  mid;    //元素序号从1开始	      
	while (low <= high) {		 
		mid = (low + high) / 2;		 
		if (data[mid-1] < k1) low = mid+1; 
		//右缩搜索区间	 
		else if (data[mid-1] > k1) high = mid-1;
		//左缩搜索区间
		else return mid;                 //搜索成功
	}	  
	return 0;                                  //搜索失败
}

template <class E, class K>
void SortedList<E,K>::Insert(const E& e1) {
	if(CurrentSize==maxSize)
	{
		cout<<"List if full!"<<endl;
		return;
	}
	int i = 1;									//查找插入位置
	while (i <= CurrentSize && data[i-1] <= e1) i++;
	for (int j = CurrentSize; j >= i; j--) data[j] = data[j-1];
	data[i-1] = e1;
	CurrentSize++;
};

template <class E, class K>
bool SortedList<E, K>::Remove (const K k1, E& e1) {
	//在dataList中删除关键码为x的元素, 通过e1返回。
	//用尾元素填补被删除元素。
	if (CurrentSize == 0) return false;
	for (int i == 0; i < CurrentSize && 
		data[i] != x; i++);	     //在表中顺序寻找
		if (i == CurrentSize) return false;	         //未找到
	e1 = data[i].other;	     //找到,保存被删元素的值
	data[i] = data[CurrentSize-1];    //填补
	CurrentSize--;  return true;
};
#endif