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