哈希查找算法的源代码 c 语言【问题描述】针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 基本要求 假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30 个，取平均查找长度的上限为2。哈希函数用除留余数法构照，用链表法处理冲突。 测试数据 读取熟悉的 30 个人的姓名。#include #include #include using namespace std; #define Maxsize 57 struct record char name20; char tel20; 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文件打开失败 !n; exit(1); while(!infile.eof() & infile.get()!=EOF) / 文件不为空并且文件指针没有指到结束符infile.seekg(Number*sizeof(aNumber),ios:beg); /定位文件指针infile.read(char *)&aNumber,sizeof(aNumber); Number+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - infile.close(); void Add(precord a) /添加记录 int i,num; cout 当前文件内已有 Number条记录 n; coutnum; ofstream ofile(telphone.txt,ios:app); if(! ofile) cout文件打开失败 !; exit(1); for(i=0;inum;i+) cout请输入第 Number+1个人的姓名 aNumber.name; cout 请输入第 Number+1 个人的电话 aNumber.tel; cout 请输入第 Number+1 个人的地址 aNumber.add; ofile.seekp(ios:end); ofile.write(char *)&aNumber,sizeof(aNumber); Number+; ofile.close(); void Print(precord a) /显示所有记录 int i; for(i=0;iNumber;i+) cout 第i+1 个人的信息为 :n; cout 姓名:ai.nameendl; cout 电话:ai.telendl; cout 地址:ai.addendl; int Hash(char str) /除留取余 long val=0;char p20,*p1; strcpy(p,str); p1=p; while(*p1!=0) val=val+*p1+; /将字符串中的所有字符对应的ASCII 值相加名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 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_Sollution(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;ielemi=-1; int menu; void Creathash_Name(pHashTable h,precord a) / 以用户名为关键字创建哈希表 cout-n; cout 1-以线性探测建表 n; cout 2-以平方探测建表 n; coutmenu; Init_Hash(h); for(i=0;ielemaddress!=-1) if(menu=1) address=Line_Sollution(address); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - else address=Square_Sollution(address); if(address=-1) break; if(address!=-1) h-elemaddress=i; h-count+; cout 姓名哈希表已成功建立 !n; void Search_Name(pHashTable h,precord a) /查找并显示指定姓名的记录 coutnam; address=Hash(nam); derter=0;n=-1; while(h-elemaddress!=-1 & strcmp(nam,ah-elemaddress.name)!=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-elemaddress.name)=0) cout你要查找的信息为 :n; cout 姓名:elemaddress.nameendl; cout 电话:elemaddress.telendl; cout 地址:elemaddress.addendl; cout 比较次数为 iendl; else cout无此姓名 , 查找失败 !; void Creathash_tel(pHashTable h,precord a) / 以电话号为关键字创建哈希表 cout-n; cout 1-以线性探测建表 n; cout 2-以平方探测建表 n; coutmenu; Init_Hash(h); for(i=0;ielemaddress!=-1) if(menu=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) / 查找并显示指定电话号的记录 couttelphone; 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 & strcmp(telphone,ah-elemaddress.tel)=0) cout你要查找的信息为 :n; cout 姓名:elemaddress.nameendl; cout 电话:elemaddress.telendl; cout 地址:elemaddress.addendl; cout 比较次数为 iendl; else cout无此电话 , 查找失败 !; void Menu() /功能菜单函数for(int i=1;i=5;i+) coutendl; cout 电话号码查询系统 n; coutn; cout n; cout 0 -退出 n; cout 1 -添加 n; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - cout 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.按用户名查找之前 , 请先进行 3 操作建立用户名哈希表 n; cout 3.按用户名查找之前 , 请先进行 4 操作建立电话号哈希表 n; void exit() int i; for(i=1;i=4;i+) coutendl; cout n; cout n; cout 电 话 号 码 查 询 系 统 n; cout n; cout 谢 谢 您 的 使 用 ! n; cout n; coutmenu1; switch(menu1) case 0:system(cls);exit();break; case 1:Add(a);system(pause);system(cls);goto start;break; case 2:Print(a);system(pause);system(cls);goto start;break; case 3:Creathash_Name(H,a);system(pause);system(cls);goto start;break; case 4:Creathash_tel(H,a);system(pause);system(cls);goto start;break; case 5:Search_Name(H,a);system(pause);system(cls);goto start;break; case 6:Search_tel(H,a);system(pause);system(cls);goto start;break; default:cout 请输入正确的操作选项!n;system(cls);goto start;break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -