哈希表的建立和查找.docx

上传人:p** 文档编号:54392 上传时间:2022-12-10 格式:DOCX 页数:4 大小:24.96KB
下载 相关 举报
哈希表的建立和查找.docx_第1页
第1页 / 共4页
哈希表的建立和查找.docx_第2页
第2页 / 共4页
哈希表的建立和查找.docx_第3页
第3页 / 共4页
哈希表的建立和查找.docx_第4页
第4页 / 共4页
亲,该文档总共4页,全部预览完了,如果喜欢就下载吧!
资源描述

《哈希表的建立和查找.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请输入正确的选择!”);)

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 1wenmi网站版权所有

经营许可证编号:宁ICP备2022001189号-1

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。第壹文秘仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知第壹文秘网,我们立即给予删除!