hashdict.h

利用闭散列方法中的线形探查建立散列表。用c实现的。

#ifndef HASHDICT_H
#define HASHDICT_H
class hashdict
{
   private:
      int*HT;
      int M;
      int currcnt;
      int EMPTY;
      int p(int K,int i)const
      {return i;}
      int h(int x)const{return x%M;}
      int h(char*x)const{
        int i,sum;
        for(sum=0,i=0;x[i]!='\0';i++)sum+=(int)x[i];
        return (sum%M);
      }
      bool hashInsert(const int&);
      bool hashSearch(const int&,int&)const;
   public:
      hashdict(int sz,int e)
      {
        M=sz;
        EMPTY=e;
        currcnt=0;HT=new int[sz];
        for(int i=0;i<M;i++)HT[i]=EMPTY;
      }
      ~hashdict(){delete HT;}
      void clear()
      {
         for(int i=0;i<M;i++)HT[i]=EMPTY;
         currcnt=0;
      }
      bool insert(const int&e){
       if(currcnt==M)return false;
       if(hashInsert(e)){
         currcnt++;
         return true;
       }
       else return false;
      }
      bool removeAny(int& e)
      {
        for(int i=0;i<M;i++)
          if(EMPTY!=HT[i])
          {
            e=HT[i];HT[i]=EMPTY;
            currcnt--;
            return true;
          }
        return false;
      }
      bool find(const int&k,int&e)const
      { return hashSearch(k,e);
      }
      int size(){return currcnt;}
};
bool hashdict::hashInsert(const int &e)
{
  int home;
  int pos=home=h(e);

  for(int i=1;EMPTY!=HT[pos];i++)
  {
     pos=(home+p(e,i))%M;
     if(e==HT[pos])return false;
  }
  HT[pos]=e;
  return true;
}

bool hashdict::
hashSearch(const int&K,int&e)const
{
   int home;
   int pos=home=h(K);
   for(int i=1;K!=HT[pos]&&EMPTY!=HT[pos];i++)
     pos=(home+p(K,i))%M;
   if(K==HT[pos]){
   e=HT[pos];
   return true;
   }
   else return false;
}
#endif