[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;
}