哈希表的建立和查找

哈希表的建立和查找 /* 针对某个集体（比如所在班级）中的人名设计一个哈希表，使的平均查找的长度不超过2完成相应的建表和查表的程序题目要求：假设人名为姓名的汉语拼音形式，待填入哈希表的人名工有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。测试数据自定义。 */#include#include#define HASH_LEN 50/哈希表的长度#define M 47/随机数#define NAME_NO 30/人名的个数typedef structchar *py;/名字的拼音int k;/拼音所对应的整数NAME;NAME NameListHASH_LEN;/全局变量NAMEtypedef struct/哈希表char *py;/名字的拼音int k;/拼音所对应的整数int si;/查找长度HASH;HASH HashListHASH_LEN;/全局变量HASHvoid InitNameList() /姓名（结构体数组）初始化char *f;int r,s0,i;NameList0.py=wanghui;NameList1.py=mayuelong;NameList2.py=chenzhicheng;NameList3.py=sunpeng;NameList4.py=zengqinghui;NameList5.py=liqingbo;NameList6.py=liujunpeng;NameList7.py=jiangquanlei;NameList8.py=xingzhengchuan;NameList9.py=luzhaoqian;NameList10.py=gaowenhu;NameList11.py=zhuhaoyin;NameList12.py=chenlili;NameList13.py=wuyunyun;NameList14.py=huangjuanxia;NameList15.py=wangyan;NameList16.py=zhoutao;NameList17.py=jiangzhenyu;NameList18.py=liuxiaolong;NameList19.py=wangziming;NameList20.py=fengjunbo;NameList21.py=lilei;NameList22.py=wangjia;NameList23.py=zhangjianguo;NameList24.py=zhuqingqing;NameList25.py=huangmin;NameList26.py=haoyuhan;NameList27.py=zhoutao;NameList28.py=zhujiang;NameList29.py=lixiaojun;for (i=0;iNAME_NO;i+)s0=0;f=NameListi.py;for (r=0;*(f+r)!=0;r+)/* 方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字*/s0=*(f+r)+s0;NameListi.k=s0; void CreateHashList() /建立哈希表int i;for (i=0; iHASH_LEN;i+) HashListi.py=;HashListi.k=0;HashListi.si=0;for (i=0;iHASH_LEN;i+)int sum=0;int adr=(NameListi.k)%M;/哈希函数int d=adr;if(HashListadr.si=0)/如果不冲突HashListadr.k=NameListi.k;HashListadr.py=NameListi.py;HashListadr.si=1;else/冲突dod=(d+NameListi.k%10+1)%M;/伪随机探测再散列法处理冲突sum=sum+1;/查找次数加1while (HashListd.k!=0);HashListd.k=NameListi.k;HashListd.py=NameListi.py;HashListd.si=sum+1;voidFindList() /查找char name20=0; int s0=0,r,sum=1,adr,d;printf(n请输入姓名的拼音:);scanf(%s,name); for (r=0;r20;r+)/求出姓名的拼音所对应的整数(关键字)s0+=namer; adr=s0%M;/使用哈希函数d=adr;if(HashListadr.k=s0)/分3种情况进行判断printf(n姓名:%s关键字:%d查找长度为: 1,HashListd.py,s0); else if (HashListadr.k=0) printf(无此记录!);elseint g=0;dod=(d+s0%10+1)%M;/伪随机探测再散列法处理冲突sum=sum+1;if (HashListd.k=0)printf(无此记录! );g=1;if (HashListd.k=s0)printf(n姓名:%s关键字:%d查找长度为:%d,HashListd.py,s0,sum); g=1;while(g=0); voidDisplay() / 显示哈希表int i;float average=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 %s ,HashListi.py);printf(n);for (i=0;iHASH_LEN;i+)average+=HashListi.si; average/=NAME_NO;printf(nn平均查找长度：ASL(%d)=%f nn,NAME_NO,average); void main()char ch1;printf(n哈希表的建立和查找n);printf(*-*n); printf(|D. 显示哈希表|n); printf(|F. 查找|n); printf(|Q. 退出|n);printf(*-*n); InitNameList();CreateHashList ();while(1)printf(nOption-:)