hashtable.h

哈希表 哈希表 哈希表 哈希表 哈希表 哈希表 哈希表

/////////////////////////////////////////////////
////  完成哈希表类设计                    ///////
/////////////////////////////////////////////////

enum KindOfItem{Empty,Active,Deleted};//枚举数据元素的道歉状态
struct HashItem
{
	DataType data;
	KindOfItem info;
	HashItem(KindOfItem i=Empty):info(i){}
	HashItem(const DataType &D,KindOfItem i=Empty):data(D),info(i){}
	int operator ==(HashItem &a)//重载运算符==
	{return data==a.data;}
	int operator !=(HashItem &a) //重载运算符!=
	{return data!=a.data;}
};
class HashTable//哈希表类
{
private:
   HashItem *ht;//用于存储数据元素的哈希表数组
   int TableSize; 
   int currentSize;  
public:
   HashTable(int m); 
   ~HashTable(void) 
	{delete []ht;}

   int Find(const DataType &x)const; //查找
   int Insert(const DataType &x); //插入
   int Delete(const DataType &x); //删除

   int IsIn(const DataType &x) //判断数据是否在哈希表数组中
     {int i=Find(x);return i>=0 ? 1:0;}
   DataType GetValue(int i)const //去数据元素的值
     {return ht[i].data;}
};
////////////////////////////////////////////////
/////          哈希表类初使实现        /////////
////////////////////////////////////////////////
HashTable::HashTable(int m)
{
   TableSize=m;
   ht=new HashItem[TableSize];//动态申请数组空间
   currentSize=0;
}

//////////////////////////////////////////////////
/////          查找实现                 //////////
//////////////////////////////////////////////////

int HashTable::Find(const DataType&x)const
{
   int i=x.key % TableSize;//采用的出留余数法
   int j=i;

   while(ht[j].info==Active&&ht[j].data!=x)
   {
		j=(j+1)%TableSize;//冲突解决方法中的线形探查法

		if(j==i)//说明已经遍历了整个哈希表未找到且表已满
		return -TableSize;
	}
          
	if(ht[j].info==Active)
		return j;//找到,返回正值
	else
		return -j;//未找到,返回负值
}

////////////////////////////////////////////////
/////            插入实现                //////
//////////////////////////////////////////////

int HashTable::Insert(const DataType &x)
{
  int i=Find(x);

  if(i>0) return 0;
  else if(i!=-TableSize)
  {
    ht[-i].data=x;
    ht[-i].info=Active;
    currentSize++;
    return 1;

	}
	else return 0;
}

/////////////////////////////////////////////////
/////             删除实现                   ////
/////////////////////////////////////////////////

int HashTable::Delete(const DataType&x)
   {
      int i=Find(x);

      if(i>=0)
      {
        ht[i].info=Deleted;
        currentSize--;
        return 1;
		}
	else return 0;
}