search.h

自己在以前学数据结构时用C++模板写的一些常用数据,都测试过

//////////////////哈希表（散列）//////////////////

enum KindOfEntry{Active,Empty,Deleted};
enum {defaultSize=11};

template <class Type>//定义散列表的表项
class HashEntry
{
	public:
		Type element;//表项的关键码
		KindOfEntry info;//3种状态
		HashEntry():info(Empty){};
		bool operator==(HashEntry &x){return(element==x.element);}//判断是否相等
		bool operator!=(HashEntry &x){return(element!=x.element);}//判断是否不相等
		HashEntry(const Type& elem,KindOfEntry i=Empty):element(elem),info(i){};
};

template <class Type>//和线性探测法处理冲突时散列表类的定义
class HashTable
{
	public:
		HashTable():tableSize(defaultSize){AllocateHT();currentSize=0;}
		~HashTable(){delete []ht;}
		const HashTable &operator =(const HashTable &ht2);//表复制
		int Find(const Type &x);//查找
		bool Insert(const Type &x);//插入
		bool Remove(const Type &x);//删除
		bool IsIn(const Type &x){return (Find(x)>0);}//判断是否存在元素X
		void MakeEmpty();//置空
	private:
		HashEntry<Type> *ht;//散列表数组
		int currentSize;
		int tableSize;
		void AllocateHT(){ht=new HashEntry<Type>[tableSize];}//分配空间
		int FindPos(const Type &x)const;//散列函数
};

template <class Type>
int HashTable<Type>::Find(const Type &x)
{
	int i=FindPos(x);//计算散列表的地址
	int j=i;
	while(ht[i].info!=Empty&&ht[i].element!=x)
	{	
		j=(j+1)%tableSize;
		if(j==i)return -tableSize;
	}
	if(ht[j].info==Active)return j;//查找成功
	else
		return (-j);
}

template <class Type>
const HashTable<Type>& HashTable<Type>::operator = (const HashTable<Type> &ht2)
{
	if(this!=&ht2)
	{
		delete []ht;
		tableSize=ht2.tableSize;
		AllocateHT();
		for(int i=0;i<tableSize;i++)
			ht[i]=ht2.ht[i];
		currentSize=ht2.currentSize;	
	}
	return *this;
}

template <class Type>
bool HashTable<Type>::Insert(const Type& x)
{
	if (int i=Find(x)>0)return false;
	else if(i!=-tableSize&&ht[-i].info!=Active)//在负i处插入X
	{
		ht[-i].element=x;
		ht[-i].info=Active;
		currentSize++;
		return true;
	}
	else 
		return false;
}

template <class Type>
bool HashTable<Type>::Remove(const Type &x)
{
	if((int i=Find(x))>=0)//找到删除
	{
		ht[i].info=deleted;//做删除标志
		currentSize--;
		return true;
	}
	else 
		return false;
}

template <class Type>
void HashTable<Type>::MakeEmpty()
{
	for(int i=0;i<tableSize;i++)
		ht[i].info=Empty;
	currentSize=0;
}

template <class Type>
int HashTable<Type>::FindPos(const Type& x)const
{
	return x%10;
}


///////////////二分法查找///////////////////
template <class Type>
int	BinSearch(Type *arr,int low,int high,Type target)
{
	int mid=(low+high)/2;
	while(high>=low)
	{
		if(arr[mid]==target)
			return mid;
		else if(arr[mid]>target)
			high=mid-1;
		else
			low=mid+1;		
	}
	return -1;
}