z.txt

这是一个数据结构实验的查找的程序

//////////////////////////////////////////////
/// Created By XiaSen , May 28,2007
///////////////////////////////////////////////

#include <iostream>

using namespace std;

#define NeverUsed -9999
enum ResultCode{Success,Failure,Duplicate,NotPresent,Overflow,Underflow};

//////////////////////////////////////////
//1: 动态集：
template<class T>
class DynamicSet
{
	public:
		virtual ResultCode Search(T&x)const=0;
		virtual ResultCode Insert(T&x)=0;
		virtual ResultCode Remove(T&x)=0;
		//virtual bool IsEmpty()const=0;
		//virtual bool IsFull()const=0;
};

//////////////////////////////////////////
//2: 有序表的折半查找
template<class T>
class ListSet:public DynamicSet<T>
{
	public:
		ListSet(int mSize)
		{
			n=0;
			maxSize=mSize;
			l=new T[mSize];		
		}

		~ListSet(){delete []l;}
		ResultCode Search(T&x)const;
		ResultCode Insert(T&x);
		ResultCode Remove(T&x);

		void Output();  // Added auxiliarily for the sake of display
        
		bool IsEmpty()const{return n==0;}
		bool IsFull()const{return n==maxSize;}

	private:
		int BSearch(T&x,int low,int high)const;  /////
        T *l;
		int maxSize;
		int n;
};


template<class T>
ResultCode ListSet<T>::Search(T&x)const
{
	cout<<"折半查找"<<x<<"的过程如下：  ";
    int i=BSearch(x,0,n-1);
	if(i==-1) return NotPresent;
	
	x=l[i]; 	
	return Success;
}

template<class T>
ResultCode ListSet<T>::Insert(T&x)
{	
	for(int i=0;i<n;i++)
	{
		if(l[i]==x) 
		{
			return Duplicate;
		}
	}

	////
	if(n<maxSize){
		for(int j=n-1;j>=0&&x<l[j];j--)
			l[j+1]=l[j];
		
		l[j+1]=x;
		n++;

		return Success;
	}
	else return Overflow;
}



template<class T>
ResultCode ListSet<T>::Remove(T&x)
{
	for(int i=0;i<n;i++)
	{
		if(l[i]==x)
		{
			for(int j=i+1;j<n;j++)
			{
				l[i]=l[j];
			}

			n--;

			return Success;
		}
	}

    return NotPresent;	
}


//
template<class T>
void ListSet<T>::Output()
{
	cout<<endl;
	for(int i=0;i<n;i++)
	{
		cout<<"l["<<i<<"]="<<l[i]<<endl;
	}
}
//

template<class T>
int ListSet<T>::BSearch(T&x,int low,int high)const
{
	if(low<=high){
		int m=(low+high)/2;
		cout<<m<<"->";
		if(x<l[m]) return BSearch(x,low,m-1);
		else if(x>l[m]) return BSearch(x,m+1,high);
		else { cout<<x<<"查找成功"; return m;}
	}
	
	cout<<"查找失败"<<endl;
	return -1;
}

//////////////////////////////////////////
//2: 二叉排序树（二叉搜索树）
template<class T>
struct BTNode
{
	BTNode(){lChild=rChild=NULL;}
    
	BTNode(const T& x)
	{
		element=x;
		lChild=rChild=NULL;
	}

	BTNode(const T& x,BTNode<T>* l,BTNode<T>* r)
	{
		element=x;
		lChild=l;
		rChild=r;
	}

	T element;
	BTNode<T>* lChild,*rChild;
};



///////
///
template<class T>
class BSTree:public DynamicSet<T>
{
	public:
		BSTree(){root=NULL;}
		ResultCode Search(T&x)const;
		ResultCode Insert(T&x);
		ResultCode Remove(T&x);

	protected:
		BTNode<T>* root;
	private:
		ResultCode Search(BTNode<T>*p,T&x)const;
};


template<class T>
ResultCode BSTree<T>::Search(T&x)const
{
	return Search(root,x);
}

template<class T>
ResultCode BSTree<T>::Search(BTNode<T>*p,T&x)const
{
	if(!p) return NotPresent;
	else if(x<p->element) return Search(p->lChild,x);
    else if(x>p->element) return Search(p->rChild,x);
	else{
		x=p->element;
		return Success;
	}
}


template<class T>
ResultCode BSTree<T>::Insert(T&x)
{
	BTNode<T> *p=root,*q=NULL;
	while(p){
		q=p;
		if(x<p->element) p=p->lChild;
		else if(x>p->element) p=p->rChild;
		else{
			x=p->element;
			return Duplicate;
		}
	}

	p=new BTNode<T>(x);
	if(!root) root=p;
	else if(x<q->element) q->lChild=p;
	else q->rChild=p;

	return Success;
}


template<class T>
ResultCode BSTree<T>::Remove(T&x)
{
	BTNode<T>*c,*s,*r,*p=root,*q=NULL;
	while(p&&p->element!=x){
		q=p;
		if(x<p->element) p=p->lChild;
		else p=p->rChild;
	}
	if(!p) return NotPresent;
	x=p->element;

	if(p->lChild&&p->rChild){
		s=p->rChild;
		r=p;
		while(s->lChild){
			r=s;
			s=s->lChild;
		}
		p->element=s->element;
		p=s; 
		q=r;
	}

	if(p->lChild) c=p->lChild;
	else
		c=p->rChild;

	if(p==root)  root=c;
	else if(p==q->rChild) q->lChild=c;
	else q->rChild=c;

	delete p;

	return Success;
}
///

//////////////////////////////////////////
//////3. Hash Table
template<class T>
class HashTable:public DynamicSet<T>   
{
	public:
		HashTable(int divisor=11);
		~HashTable(){delete []ht; delete []empty;}
		ResultCode Search(T&x)const;
		ResultCode Insert(T&x);
		ResultCode Remove(T&x);
	
		void Output();  // Added auxiliarily for the sake of display
	
	private:
		int M;
		T *ht;
		ResultCode Find(T&x,int& pos)const;
		bool *empty;
};

template<class T>
HashTable<T>::HashTable(int divisor)
{
	M=divisor;

	ht=new T[M];
	empty=new bool[M];
	for(int i=0;i<M;i++) empty[i]=true;
	for(i=0;i<M;i++) ht[i]=NeverUsed;
}

template<class T>
ResultCode HashTable<T>::Find(T&x,int&pos)const
{
	pos=x%M;
	if(pos<0) pos=M+pos;

	int i=pos;
	do{
		if(empty[pos]) return NotPresent;
		if(ht[pos]==x){
			x=ht[pos];
			return Success;
		}
		pos=(pos+1)%M;
	}while(pos!=i);
	return NotPresent;
}	

template<class T>
ResultCode HashTable<T>::Search(T&x)const
{
	int pos;
	return Find(x,pos);
}

template<class T>
ResultCode HashTable<T>::Insert(T&x)
{
	int pos=x%M;
	if(pos<0)pos=M+pos; 
	int i=pos;
	do{
		if(ht[pos]==x){
			x=ht[pos];return Duplicate;
		}
		if(ht[pos]==NeverUsed){
			ht[pos]=x;
			empty[pos]=false;
			return Success;
		}
		pos=(pos+1)%M;
	}while(pos!=i);
	return Overflow;
}

template<class T>
ResultCode HashTable<T>::Remove(T&x)
{
	int pos;
	ResultCode result=Find(x,pos);
	if(result==Success) ht[pos]=NeverUsed;
	return result;
}

template<class T>
void HashTable<T>::Output()
{
	cout<<endl;
	for(int i=0;i<M;i++)
	{
		if(ht[i]!=NeverUsed)
		{
			cout<<"ht["<<i<<"]="<<ht[i]<<endl;
		}
	}
}