[C++]データ構造:ハッシュHashTableの実現と簡単な応用

2499 ワード

#include <iostream>
using namespace std;

template<class E,class K>
class HashTable{
    public:
        HashTable(int divisor=11);
        ~HashTable(){delete[]ht;delete[]empty;}
        bool Search(const K&k,E&e)const;
		HashTable<E,K>& Insert(const E&e);
		int hSearch(const K&k)const;
		int D;			//       
		E *ht;			//    
		bool *empty;	//    
		void Output(ostream& out)const;
};

//    
template<class E,class K>
HashTable<E,K>::HashTable(int divisor){
	D = divisor;
	
	//      
	ht = new E[D];
	empty=new bool[D];

	
	//      
	for (int i = 0;i<D;i++){
		empty[i]=true;
	}
}


//        
//       k   
//       (        )
//hSearch            b  
//1)empty[b]=false ht[b]      k
//2)        k   ,empty[b]=true,      k     b   
//3)        k   ,empty[b] false,ht[b]        k,    
template<class E,class K>
int HashTable<E,K>::hSearch(const K&k)const{
	int i = k%D;			//   
	int j=i;				//      
	do{
		if(empty[j]||ht[j]==k)
			return j;
		j=(j+1)%D;			//    
		
	} while (j!=i);			//      
	
	return j;				//     
}




//   k         e
//        false
template<class E,class K>
bool HashTable<E,K>::Search(const K&k,E&e)const{
	int b = hSearch(k);
	if(empty[b]||ht[b]!=k)
		return false;
	e=ht[b];
	return true;
}


//            
template<class E,class K>    
ostream& operator<<(ostream& out,const HashTable<E,K>&x){      
    x.Output(out);      
    return out;      
}      

//          
template<class E,class K>  
void HashTable<E,K>::Output(ostream& out)const  
{ 
    for(int i =0;i<D;i++){ 
		if(!empty[i])
			cout<<ht[i]<<" "; 
		else
			cout<<"NULL"<<" ";
	}
    cout<<endl;  
}

class BadInput{  
public:  
	BadInput(){  
		cout<<"Bad Input!"<<endl;  
	}  
};  

class NoMem{  
public:  
	NoMem(){  
		cout<<"No Memory!"<<endl;  
	}  
};  

//       
template<class E,class K>
HashTable<E,K>& HashTable<E,K>::Insert(const E&e){
	K k = e;			//  key 
	int b = hSearch(k);
	
	//         
	if(empty[b]){
		empty[b]=false;
		ht[b]=e;
		return *this;
	}
	if (ht[b]==k)
		throw BadInput();
	throw NoMem();
}


int main(){
	HashTable<float,int>myHash;
	myHash.Insert(12);
	myHash.Insert(23);
	myHash.Insert(40);
	myHash.Insert(22);

	cout<<myHash<<endl;

	return 0;
}