哈希查找算法的源代码 c语言

1、哈希查找算法的源代码 c语言【问题描述】针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。基本要求假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构照，用链表法处理冲突。测试数据读取熟悉的30个人的姓名。#include <fstream>#include <iostream>#include <cmath>using namespace std;#define Maxsize 57 struct record char name20;char tel

2、20;char add20;typedef record * precord;struct HashTable int elemMaxsize; /存放数组a的下标int count; ;typedef HashTable * pHashTable;int Number; /统计当前数组a中的记录总数void Getdata(precord a) /从文件telphone.txt中读取数据存放到数组a Number=0;ifstream infile("telphone.txt",ios:in|ios:binary);if(!infile) cout<<&quo

3、t;文件打开失败!n" exit(1);while(!infile.eof() && infile.get()!=EOF) /文件不为空并且文件指针没有指到结束符infile.seekg(Number*sizeof(aNumber),ios:beg); /定位文件指针infile.read(char *)&aNumber,sizeof(aNumber);Number+;infile.close();void Add(precord a) /添加记录 int i,num;cout<<"当前文件内已有"<<Number&

4、lt;<"条记录n"cout<<"请输入添加的个数:"cin>>num;ofstream ofile("telphone.txt",ios:app);if(! ofile) cout<<"文件打开失败!" exit(1); for(i=0;i<num;i+) cout<<"请输入第"<<Number+1<<"个人的姓名"<<endl;cin>>aN;

5、 cout<<"请输入第"<<Number+1<<"个人的电话"<<endl;cin>>aNumber.tel; cout<<"请输入第"<<Number+1<<"个人的地址"<<endl;cin>>aNumber.add; ofile.seekp(ios:end);ofile.write(char *)&aNumber,sizeof(aNumber);Number+;ofile.clos

6、e();void Print(precord a) /显示所有记录 int i;for(i=0;i<Number;i+)cout<<"第"<<i+1<<"个人的信息为:n"cout<<" 姓名:"<<<<endl;cout<<" 电话:"<<ai.tel<<endl;cout<<" 地址:"<<ai.add<<endl;int Has

7、h(char str) /除留取余 long val=0;char p20,*p1;strcpy(p,str);p1=p;while(*p1!='0')val=val+*p1+; /将字符串中的所有字符对应的ASCII值相加return(val%Maxsize);int derter; /线性增量int Line_Sollution(int address) /采用线性探测解决冲突 derter+;if(derter=Maxsize) return(-1);else return(address+derter)%Maxsize);int n;int Square_Solluti

8、on(int address) /采用平方探测法解决冲突 int j;derter+;if(derter=Maxsize) return -1;n=n*(-1);j=(int(pow(derter,2)*n+address)%Maxsize;return(j);void Init_Hash(pHashTable h) /初始化哈希表 int i;for(i=0;i<Maxsize;i+)h->elemi=-1;int menu;void Creathash_Name(pHashTable h,precord a)/以用户名为关键字创建哈希表 cout<<"-n

9、"cout<<" 1-以线性探测建表n"cout<<" 2-以平方探测建表n"cout<<"-n"int i,address;cin>>menu;Init_Hash(h);for(i=0;i<Number;i+) derter=0;n=-1;address=Hash();while(h->elemaddress!=-1)if(menu=1) address=Line_Sollution(address);else address=Square_Soll

10、ution(address);if(address=-1) break;if(address!=-1) h->elemaddress=i; h->count+;cout<<"姓名哈希表已成功建立!n"void Search_Name(pHashTable h,precord a) /查找并显示指定姓名的记录 cout<<"请输入要查找的姓名:"char nam20;int address,i=1;cin>>nam;address=Hash(nam);derter=0;n=-1;while(h->ele

11、maddress!=-1 && strcmp(nam,ah->)!=0) if(menu=1) address=Line_Sollution(address);else address=Square_Sollution(address);i+;if(address=-1) break;if(h->elemaddress!=-1 && strcmp(nam,ah->)=0) cout<<"你要查找的信息为:n"cout<<" 姓名

12、:"<<ah-><<endl;cout<<" 电话:"<<ah->elemaddress.tel<<endl;cout<<" 地址:"<<ah->elemaddress.add<<endl;cout<<"比较次数为"<<i<<endl;else cout<<"无此姓名,查找失败!"void Creathash_te

13、l(pHashTable h,precord a) /以电话号为关键字创建哈希表 cout<<"-n"cout<<" 1-以线性探测建表n"cout<<" 2-以平方探测建表n"cout<<"-n"int i,address;cin>>menu;Init_Hash(h);for(i=0;i<Number;i+) derter=0;n=-1;address=Hash(ai.tel);while(h->elemaddress!=-1)if(menu

14、=1) address=Line_Sollution(address);else address=Square_Sollution(address);if(address=-1) break;if(address!=-1) h->elemaddress=i; h->count+;cout<<"电话号哈希表已成功建立!n"void Search_tel(pHashTable h,precord a)/查找并显示指定电话号的记录 cout<<"请输入要查找的电话:"char telphone20;int address,i

15、=1; /i统计比较次数cin>>telphone;address=Hash(telphone);derter=0; n=-1; /初始化线性增量while(h->elemaddress!=-1 && strcmp(telphone,ah->elemaddress.tel)!=0) if(menu=1) address=Line_Sollution(address);else address=Square_Sollution(address);i+;if(address=-1) break;if(h->elemaddress!=-1 &&a

16、mp; strcmp(telphone,ah->elemaddress.tel)=0) cout<<"你要查找的信息为:n"cout<<" 姓名:"<<ah-><<endl;cout<<" 电话:"<<ah->elemaddress.tel<<endl;cout<<" 地址:"<<ah->elemaddress.add<<endl;cout&

17、lt;<"比较次数为"<<i<<endl;else cout<<"无此电话,查找失败!"void Menu() /功能菜单函数for(int i=1;i<=5;i+)cout<<endl;cout<<" 电话号码查询系统n"cout<<'n'cout<<" n"cout<<" 0-退出 n"cout<<" 1-添加 n"cout<<

18、;" 2-显示所有 n" cout<<" 3-以性命建立哈希表 n"cout<<" 4-以电话建立哈希表 n"cout<<" 5-按用户名查找 n"cout<<" 6-按电话号查找 n"cout<<" n"cout<<" 使用说明:n"cout<<" 1.添加新纪录后,如要进行查找请先进行3或4操作n"cout<<" 2.按用户名查

19、找之前,请先进行3操作建立用户名哈希表n"cout<<" 3.按用户名查找之前,请先进行4操作建立电话号哈希表n"void exit() int i;for(i=1;i<=4;i+)cout<<endl;cout<<" n"cout<<" n"cout<<" 电 话 号 码 查 询 系 统 n"cout<<" n"cout<<" 谢 谢 您 的 使 用 ! n"cout<<" n"cout<<" n"int main() record aMaxsize;pHashTable H=new HashTable;Getdata(a); /将文件中的数据读入到数组a中start:Menu();int menu1;cin>>menu1;switch(menu1) case 0:system(&q