哈希表的建立和查找.docx
哈希表的建立和查找/*针对某个集体（比如所在班级）中的人名设计一个哈希表，使的平均查找的长度不超过2完成相应的建表和查表的程序题目要求：假设人名为姓名的汉语拼音形式，待填入哈希表的人名工有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。测试数据自定义。*/#include<stdio.h>#include<conio.h>哈希表的长度随机数人名的个数#defineHASH.LEN50#defineM47#defineNAMENO30typedefstruct(char*py;名字的拼音intk;/拼音所对应的整数NAME;NAMENameListHASH.LEN;全局变量NAMEtypedefstruct哈希表(char*py;名字的拼音intk;/拼音所对应的整数intsi;查找长度HASH;HASHHashListHASH_LEN;全局变量HASHVOidlnitNameLiSt()姓名(结构体数组)初始化(char*f;intr,s,i;NameListOJ.py="wanghui"NameListl.py="mayuelong;NameList2.py="chenzhicheng"NameList3J.py="sunpeng"NameList4.py="zengqinghui"NameList5.py=',liqingbo,'NameList6.py="liujunpeng;NameList7.py="jiangquanlei;NameList8.py="xingzhengchuan"NameLiSU9.py="luzhaoqian"NameListlO.py="gaowenhu"NameListll.py=,'zhuhaoyin;NameList12J.py="chenlili"NameList13.py=,'wuyunyun;NameList14.py=,huangjuanxia"NameList15.py=,'wangyan"NameList16J.py=zhoutao;NameList17J.py=',jiangzhenyu"NameList18.py=',liuxiaolong"NameList19.py=,'wangziming"NameList20.py=,fengjunbo,'NameList2lj.py=,'lilein;NameList22.py=,wangjia,*;NameLiSt23.py="zhangjianguo"NameList24.py=zhuqingqing"NameList25J.py="huangmin;NameList26.py="haoyuhan,"NameList27.py=,'zhoutao;NameList28.py=zhujiang"NameList29.py=,lixiaojun"for(i=0;i<NAME_NO;i+)(s0=0;f=NameListi.py;for(r=Oj*(f+r)!="Or+÷)*方法：将字符串的各个字符所对应的ASCll码相加，所得的整数做为哈希表的关键字*/s=*(f+r)+s;NameListi.k=sO;1voidCreateHashListO建立哈希表iti;for(i=0;i<HASH_LEN;i+)(HashListi.py=,M;HashListi.k=O;HashListfi.si=0;)for(i=0;i<HASH_LEN;i+)(intsum=0;intadr=(NameListi.k)%M;哈希函数intd=adr;if(HashListadr.si=O)假如不冲突HashListadr.k=NameListi.k;HashListIadr.py=NameListi.py;HashListIadr.si=l;1else冲突(do(d=(d+NameListi.k%10+l)%M;伪随机探测再散列法处理冲突sum=sum+l;/查找次数加1while(HashListd.k!=O);HashListd.k=NameListi.k;HashListd.py=NameListi.py;HashListd.si=sum+1;)1voidFindLiSt()/查找(charname20=0;intsO=O,r,sum=1,adr,d;printf(',n请输入姓名的拼音:")；scanf(u%s",name);for(r=0;r<20;r+)求出姓名的拼音所对应的整数(关键字)s+=namer;adr=sO%M;使用哈希函数d=adr;if(HashListIadrI.k=s)分3种状况进行推断Printf("n姓名:S关键字:d查找长度为：1,HashListfd.py,s);elseif(HashListadr.k=O)Printf("无此纪录!”)；else(intg=0;do(d=(d+s0%10+l)%M;伪随机探测再散列法处理冲突sum=sum+l;if(HashListd.k=O)(Printf("无此纪录!”)；g=l；)if(HashListd.k=sO)Prindrn姓名:s关键字:d查找长度为:d”,HaShLiStd.py,s,sum);while(g=O);)voidDispIayO/显示哈希表iti;floataverage=0;printf("nn地址t关键字tt搜寻长度tH(key)t姓名n");显示的格式for(i=0;i<50;i+)(printf("%d,',i);printf(,t%d,HashListi.k);printf("tt%d",HashListi.si);printf("tt%d",HashListi.k%M);printf("t%su,HashListi.py);printf("nu);)for(i=0;i<HASH_LEN;i+)average+=HashListi.si;average/=NAME_NO;printf("nn平均查找长度：ASL(%d)=%fnn,NAME_NO,average);1voidmain()charch1;printf(',n哈希表的建立和查找n")；printf("*n");printf("ID.显示哈希表n");printf("IF.查找|吟；printf("IQ.退出n");printf("*n");InitNameListO;CreateHashList();while(l)(printf(',nOption-:");fflush(stdin);chl=getchar();if(chl=,D,chl=,d,)DisplayO;elseif(chl=,Fchl=T)FindList();elseif(chl='Q'lchl='q,)return;else(printf(n请输入正确的选择!”);)
