---------------hashing .h-------------------
#include<iostream>
#include<stdlib.h>
using namespace std;
const int DefaultSize=100;
enum KindOfStatus{Active,Empty,Deleted}; //元素分类(活动/空/删)
template<class E,class K>
class HashTable
{
public:
HashTable(const int d,int sz=DefaultSize);
~HashTable(){delete []ht;delete []info;}
bool Insert(const E &e1); //在散列表中插入e1
bool Remove(const K k1); //在散列表中删除
E Search(const K k1,E& e1)const;//在散列表搜索k1
void makeEmpty(); //置散列表为空
private:
int divitor; //散列表的除数
int CurrentSize,TableSize; //当前桶数及最大桶数
E *ht; //散列表存储数组
KindOfStatus *info; //状态数组
int FindPos(const K k1)const; //散列函数,计算初始桶号
};
---------------hashing.cpp----------------------------
#include"hashing.h"
template<class E,class K>
HashTable<E,K>::HashTable(const int d,int sz)
{
divitor=d;
TableSize=sz;
CurrentSize=0;
ht=new E[TableSize];
info=new KindOfStatus[TableSize];
for(int i=0;i<TableSize;i++)
info[i]=Empty;
};
template<class E,class K>
int HashTable<E,K>::FindPos(const K k1)const
{
int i=k1%divitor;//计算初始桶号
int j=i; //检测下一空桶下标
do
{
if(info[j]==Empty||info[j]==Active&&ht[j]==k1) return j; //找到
j=(j+1)%TableSize; //当做循环表处理，找下一个空桶
}while(j!=i);
return j;
};
template<class E,class K>
bool HashTable<E,K>::Insert(const E& e1)
{
K k1=e1; //重载函数::抽取函数
int i=FindPos(k1); //用散列函数计算桶号
if(info[i]!=Active)
{
ht[i]=e1;
info[i]=Active;
CurrentSize++;
return true;
}
if(info[i]==Active&&ht[i]==e1)
{
cout<<"表中已有元素,不能插入!"<<endl;
return false;
}
cout<<"表已满,不能插入数据!";
return false;
};
template<class E,class K>
bool HashTable<E,K>::Remove(const K k1)
{
int i=FindPos(k1);
if(info[i]==Active)
{
info[i]=Deleted;
CurrentSize--;
return true;
}
else return false;
};
template<class E,class K>
E HashTable<E,K>::Search(const K k1,E& e1)const
{
int i=FindPos(k1);
if(info[i]!=Active||ht[i]!=k1) return false;
e1=ht[i];
return e1;
};
template<class E,class K>
void HashTable<E,K>::makeEmpty()
{
for(int i=0;i<TableSize;i++)
info[i]=Empty;
CurrentSize=0;
};
---------------main.cpp--------------------------
#include"hashing.cpp"
int menu()
{
int choice;
cout<<" *************散列函数的基本操作************"<<endl<<endl;
cout<<" 在散列表插入元素，请按1"<<endl;
cout<<" 逻辑删除散列表元素，请按2"<<endl;
cout<<" 在散列表中搜索关键码的值，请按3"<<endl;
cout<<" 退出，请按4"<<endl<<endl;
cout<<" *****************************************"<<endl<<endl;
cout<<" 请选择:";
cin>>choice;
return choice;
}
int main()
{
HashTable<int,int> hash(2,10);
bool exit=false;
while(true)
{
int choice=menu();
switch(choice)
{
case 1:
int s;
cout<<" 请输入要插入值关键码:";
cin>>s;
cout<<" "<<hash.Insert(s)<<endl;break;
case 2:
int c;
cout<<" 请输入要输出值关键码:";
cin>>c;
cout<<" "<<hash.Remove(c)<<endl;break;
case 3:
int y;
cout<<" 请输入要查询值的关键码:";
cin>>y;
int z;
cout<<" "<<hash.Search(y,z)<<endl;break;
case 4:
exit=true;break;
}
system("pause");
system("cls");
if(exit==true)
break;
}
return 0;
}