hashdict.h

用VC实现散列表

#include"Dictionary.h"
//Dictionary implemented with a hash talbe
template<class Key,class Elem,class Comp>
class hashdict:public Dictionary<Key,Elem,Comp>{
 private:
     Elem* HT;    //The hash table
     int M;       //Size of HT
     int currcnt;  //the current number of elements in HT
     Elem EMPTY;   //User-supplied value for an empty slot
     int p(Key K,int i)const  //Probe using linear probing
	 {return i;}

     int h(char *x)const{    //Hash function for character keys
     int i,sum;
     for(sum=0,i=0;x[i]!='\0';i++)
		 sum+=(int)x[i];
     return(sum % M);
	 }
     bool hashInsert(const Elem&);
     bool hashSearch(const Key& ,Elem& )const;
public:
     hashdict(int sz,Elem e){   // e defines an EMPTY slot
     M=sz;EMPTY=e;
     currcnt=0;HT=new Elem[sz];  //Make HT of size sz
     for(int i=0;i<M;i++) HT[i]=EMPTY;   // Initialize HT
	 }
    ~hashdict(){delete HT;}
     void clear(){  //Clear the dictionary
     for(int i=0;i<M;i++) HT[i]=EMPTY; 
     currcnt=0;
	 }
     bool insert(const Elem& e){  //Insert e into dictionary
     if(currcnt==M) return false;
     if(hashInsert(e)){
     currcnt++;
     return true;
	 }
     else return false;
	 }	 
	 int h(int x)const { return x % M;}  //Poor hash function    
	 void print()const{
	      for(int i=0;i<M;i++)
		  {
			  while(HT[i]==EMPTY)
			  {
				  i++;
			  }
			  cout<<"散列表中第 "<<i<<" 个位置的元素为: "<<HT[i]<< endl;
		  }
	 }
  bool removeAny(Elem & e){   //Remove the first element
      for(int i=0;i<M;i++)
       if(!Comp::eq(EMPTY,HT[i])){
       e=HT[i];
       HT[i]=EMPTY;
       currcnt--;
	   return true;
	   }
       return false;
  }

   bool find(const Key& K,Elem& e) const
   {
    return hashSearch(K,e);
   }
    int size(){return currcnt;} // Number stored in table
};

//Insert e into hash table HT
template<class Key,class Elem,class Comp>
bool hashdict<Key,Elem,Comp>::
hashInsert(const Elem& e){
  int home;                         //Home position for e
  int pos=home=h(e);         //Init probe sequence
  for(int i=1;!(Comp::eq(EMPTY,HT[pos]));i++)
  {
  pos=(home+p(e,i)) % M;          //Follow probes
  if(Comp::eq(e,HT[pos]))return false;     //Duplicate
  }
  HT[pos]=e;    //Insert e
  return true;
}  
 //Search for the record with Key K
 template<class Key,class Elem,class Comp>
 bool hashdict<Key,Elem,Comp>::
   hashSearch(const Key& K,Elem& e) const{
   int home;               //Home position for K
   int pos=home=h(K);      //Initial posit on probe sequence
   for(int i=1;!Comp::eq(K,HT[pos])&&!Comp::eq(K,HT[pos]);i++)
   pos=(home+p(K,i))%M ;   //Next on probe sequence
   if(Comp::eq(K,HT[pos])){ //Found it
   e=HT[pos];
   return true;
 }
   else return false;        //k not in hash table
}