哈希表的建立和查找.docx

《哈希表的建立和查找.docx》由会员分享，可在线阅读，更多相关《哈希表的建立和查找.docx（4页珍藏版）》请在优知文库上搜索。

1、哈希表的建立和查找/*针对某个集体（比如所在班级）中的人名设计一个哈希表，使的平均查找的长度不超过2完成相应的建表和查表的程序题目要求：假设人名为姓名的汉语拼音形式，待填入哈希表的人名工有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。测试数据自定义。*/#include#include哈希表的长度随机数人名的个数#defineHASH.LEN50#defineM47#defineNAMENO30typedefstruct(char*py;名字的拼音intk;/拼音所对应的整数NAME;NAMENameListHASH.LEN;全局变量NAMEtype

2、defstruct哈希表(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;Nam

3、eList7.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;

4、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;iNAME_NO;i+)(s0=0;f=

5、NameListi.py;for(r=Oj*(f+r)!=Or+)*方法：将字符串的各个字符所对应的ASCll码相加，所得的整数做为哈希表的关键字*/s=*(f+r)+s;NameListi.k=sO;1voidCreateHashListO建立哈希表iti;for(i=0;iHASH_LEN;i+)(HashListi.py=,M;HashListi.k=O;HashListfi.si=0;)for(i=0;iHASH_LEN;i+)(intsum=0;intadr=(NameListi.k)%M;哈希函数intd=adr;if(HashListadr.si=O)假如不冲突HashLista

6、dr.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请输入姓名的拼音:)；scan

7、f(u%s,name);for(r=0;r20;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)Prind

8、rn姓名: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;i50;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;iHASH_LEN;i+)averag

9、e+=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=Qlchl=q,)return;else(printf(n请输入正确的选择!”);)