哈希表的实现
我数据结构课程设计的题目,如有不足之处还望大家批评指正。
在vc 6.0下面调试通过。
file:<HashList.h>
#define HashMaxsize 40
#define NullTag -100
#define DeleteTag -200
typedef int Keytype;
struct Elemtype{
int key;
char name[20];
char telephone[15];
char address[20];
int search;
};
typedef struct Elemtype HashList[HashMaxsize];
file:<main.cpp>
#include <iostream.h>
#include <string.h>
#include <process.h>
#include <conio.h>
#include <iomanip.h>
#include "HashList.h"
int n=7,m=19;
int count,index[HashMaxsize];
Elemtype people[]={{0,"one","027-86532287","湖北武汉",0},{0,"two","027-86532287","湖北襄樊",0},{0,"three","027-86532285","湖北公安",0},{0,"four","027-86532284","贵州织金",0},{0,"five","027-86532283","湖北武汉",0},{0,"six","027-86532282","安徽裴岗",0},{0,"eight","027-86532280","湖北汉川"}};
HashList ht;
HashList ht1;
void ClearHashList(HashList ht)//清空散列表
{
int i;
for(i=0;i<HashMaxsize;i++)
{
ht[i].key=NullTag;
}
}//ClearHashList
int HashFunction1(Keytype key,int m)//散列函数1
{
return key%m;
}//HashFunction1
int HashFunction2(Keytype key,int m) //散列函数2
{
return 1+key%(m-2);
}//HashFunction2
int ProduceKey(char *p)//产生数字关键字
{
int sum=0,i,length;
length=strlen(p);
for(i=0;i<length;i++)
{
if(p[i]>0)
{
sum<<=2; //sum 左移两位
sum=sum+p[i];
}
else
{ sum<<=2;
sum=sum-p[i];
}
}
return sum%10000;
}//ProduceKey
istream & operator >>(istream & in, Elemtype& str)//输入操作符重载
{
cout<<"请输入学生的姓名："<<endl;
cin>>str.name;
cout<<"请输入学生的电话号码:"<<endl;
cin>>str.telephone ;
cin.get();//吸收掉换行回车符
cout<<"请输入家庭住址："<<endl;
cin>>str.address;
str.key=ProduceKey(str.name );
cout<<endl;
return in;
}
ostream & operator <<(ostream & out, Elemtype& str)//输出操作符重载
{
cout<<setiosflags(ios::left)<<setw(15)<<str.key<<setw(15)<<str.name<<setw(15)<<str.address<<setw(20)<<str.telephone<<setw(15)<<str.search ;
cout<<endl;
return out;
}
void PrintHashList(HashList ht,int m)//输出散列表
{
int i,total=0;
float sum=0.0;
cout<<"散列表为:\n"<<endl;
cout<<setiosflags(ios::left)<<setw(15)<<"下标"<<setw(15)<<"关键字"<<setw(15)<<"姓名"<<setw(15)<<"家庭地址"<<setw(20)<<"联系电话"<<setw(15)<<"搜索次数"<<endl;
for(i=0;i<m;i++)
{
if(ht[i].key!=NullTag&& ht[i].key!=DeleteTag)
{ cout<<setiosflags(ios::left)<<setw(15)<<i;
cout<<ht[i];
sum+=ht[i].search;
total++;
}
}
cout<<"\n\t\t\t\t平均搜索长度为:"<<sum/total<<endl;
}//PrintHashList
/////////
bool Insert(HashList ht,int m,Elemtype x)//添加新的记录
{
x.key =ProduceKey(x.name );
int d=HashFunction1(x.key,m);
x.search =1;
int temp=d;
while(ht[d].key!=NullTag&&ht[d].key!=DeleteTag)
{
d=(d+HashFunction2(x.key ,m))%m;
x.search++;
if(d==temp)
{
cout<<"散列表空间已被占满，应重新建立!"<<endl;
return false;
}
}
ht[d]=x;
return true;
}//Insert
bool Insert1(HashList ht,int m,Elemtype x)
{
x.key =ProduceKey(x.telephone);
int d=HashFunction1(x.key,m);
x.search =1;
int temp=d;
while(ht[d].key!=NullTag&&ht[d].key!=DeleteTag)
{
d=(d+HashFunction2(x.key ,m))%m;
x.search++;
if(d==temp)
{
cout<<"散列表空间已被占满，应重新建立!"<<endl;
return false;
}
}
ht[d]=x;
return true;
}
void InitHashList(HashList ht) //初始化散列表
{
int i;
for(i=0;i<HashMaxsize;i++)
{
ht[i].key=NullTag;
}
for(i=0;i<n;i++)
{
Insert(ht,m,people[i]);
}
}//InitHashList
void InitHashList1(HashList ht)
{
int i;
for(i=0;i<HashMaxsize;i++)
{
ht[i].key=NullTag;
}
for(i=0;i<n;i++)
{
Insert1(ht,m,people[i]);
}
}
void Search(HashList ht,int m,int * index) //查找记录
{
char ch1[20];
cout<<"\n请输入要查询的姓名:";
cin>>ch1;
int i,temp;
int k=ProduceKey(ch1);
int d=HashFunction1(k,m);
temp=d;
int visit[HashMaxsize];
int test;
for(i=0;i<m;i++)
{
visit[i]=0;
}
count=0;
while(ht[d].key!=NullTag)
{
visit[d]=1;
if(ht[d].key==k)
{
index[count]=d;
count++;
}
d=(d+HashFunction2(k,m))%m;
test=1;
for(i=0;i<m;i++)
{
if(visit[i]==0)
{
test=0;
}
}
if(test)
{
exit(0);
}
}
}
void Search1(HashList ht,int m,int * index)
{
char ch1[20];
cout<<"\n请输入要查询的电话号码:";
cin>>ch1;
int i,temp;
int k=ProduceKey(ch1);
int d=HashFunction1(k,m);
temp=d;
int visit[HashMaxsize];
int test;
for(i=0;i<m;i++)
{
visit[i]=0;
}
count=0;
while(ht[d].key!=NullTag)
{
visit[d]=1;
if(ht[d].key==k)
{
index[count]=d;
count++;
}
d=(d+HashFunction2(k,m))%m;
test=1;
for(i=0;i<m;i++)
{
if(visit[i]==0)
{
test=0;
}
}
if(test)
{
exit(0);
}
}
}
void CreateHashList(HashList ht) //以默认的数据建立散列表
{
Elemtype x;
int i;
cout<<"\n从键盘输入待散列元素的个数n和散列表的长度m:";
do{
cin>>n>>m;
if(n>m-1||m>HashMaxsize)
{
cout<<"输入错误,n应小于m,";
}
if(m%2==0)
{
cout<<"m应该为奇数,";
}
cout<<"请重新输入:";
}while(n>m-1||m>HashMaxsize||m%2==0);
for(i=0;i<n;i++)
{
cin>>x;
Insert(ht,m,x);
}
}
void MainMenu() //系统主菜单
{
cout<<"请输入操作菜单:"<<endl;
cout<<"\t①.建立散列表"<<endl;
cout<<"\t②.显示散列表(姓名为关键字)"<<endl;
cout<<"\t③.显示散列表(电话为关键字)"<<endl;
cout<<"\t④.按姓名查询"<<endl;
cout<<"\t⑤.按电话查询"<<endl;
cout<<"\t⑥.添加记录"<<endl;
cout<<"\t⑦.清除屏幕"<<endl;
cout<<"\t⑧.退出系统"<<endl;
}
void MainChoice()
{
char ch;
bool flag1=false;
bool flag2=true;
do{
MainMenu();
ch=getch();
if(ch=='1')
{
char ch1;
cout<<"你已经建立了散列表,是否要重新建立(Y/N)?"<<endl;
ch1=getch();
if(ch1=='Y'||ch1=='y')
{
ClearHashList(ht);
CreateHashList(ht);
ClearHashList(ht1);
for(int i=0;i<m;i++)
{
if(ht[i].key!=NullTag)
{
ht1[i]=ht[i];
ht1[i].key=ProduceKey(ht[i].telephone);
}
}
flag1=true;
flag2=false;
}
else if(ch1=='N'||ch1=='n')
{
}
}
else if(ch=='2')
{
cout<<"\n以姓名为关键字建立的";
PrintHashList(ht,m);
}
else if(ch=='3')
{
cout<<"\n以电话号码为关键字建立的";
PrintHashList(ht1,m);
}
else if(ch=='4')
{
if(flag1||flag2)
{
//int index[HashMaxsize];
Search(ht,m,index);
if(count==0)
{
cout<<"查询失败,没有找到要查询的记录!\n\n"<<endl;
}
else
{
int p;
cout<<"查询结果如下:"<<endl;
cout<<setiosflags(ios::left)<<setw(10)<<"下标"<<setw(15)<<"关键字"<<setw(15)<<"姓名"<<setw(15)<<"家庭地址"<<setw(15)<<"联系电话"<<setw(10)<<"搜索次数"<<endl;
for(int i=0;i<count;i++)
{
cout<<setw(10)<<index[i];
p=index[i];
cout<<ht[p];
}
}
}
else
{
cout<<"\n你还没有建立散列表!\n\n"<<endl;
}
}
else if(ch=='5')
{
if(flag1||flag2)
{
//int index[HashMaxsize];
Search1(ht1,m,index);
if(count==0)
{
cout<<"查询失败,没有找到要查询的记录!\n\n"<<endl;
}
else
{
cout<<"查询结果如下:"<<endl;
cout<<"下标\t"<<"关键字\t\t"<<"姓名\t\t"<<"家庭地址\t\t"<<"联系电话\t"<<"搜索次数"<<endl;
for(int i=0;i<count;i++)
{
cout<<index[i]<<"\t";
cout<<ht1[index[i]];
}
}
}
else
{
cout<<"\n你还没有建立散列表!\n\n"<<endl;
}
}
else if(ch=='6')
{
if(flag1||flag2)
{
Elemtype x;
cin>>x;
Insert(ht,m,x);
Insert1(ht1,m,x);
}
else
{
cout<<"\n你还没有建立散列表!\n\n"<<endl;
}
}
else if(ch=='7')
{
system("cls");
}
else if(ch=='8')
{
return ;
}
else
{
cout<<"输入错误!!"<<endl;
}
}while(1);
}
void main() //主函数
{
InitHashList(ht);
InitHashList1(ht1);
MainChoice();
}
