数据结构哈希表设计

1、1、 问题描述针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表，使得平均查找长度均不超过R,完成相应的建表和查表顺序。2、 基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。3、 概要设计1 .构造结构体：typedefstruct。；2 .姓名表的初始化：voidInitNameTable();3 .建立哈希表：voidCreateHashTable();4 .显示姓名表：voidDisplayNameTable();5 .姓名查找：voidFindName();6 .主函数：

2、voidmain()；4、 详细设计1 .姓名表的初始化voidInitNameTable()(NameTable0.py="louyuhong"NameTable1.py="shenyinghong"NameTable2.py="wangqi"NameTable3.py="zhuxiaotong"NameTable4.py="zhataotao"NameTable5.py="chenbinjie"NameTable6.py="chenchaoqun"Na

3、meTable7.py="chencheng"NameTable8.py="chenjie"NameTable9.py="chenweida"NameTable10.py="shanjianfeng"NameTable11.py="fangyixin"NameTable12.py="houfeng"NameTable13.py="hujiaming"NameTable14.py="huangjiaju"NameTable15.py=&q

4、uot;huanqingsong”;NameTable16.py="jianghe"NameTable17.py="jinleicheng"NameTable18.py="libiao"NameTable19.py="liqi"NameTable20.py="lirenhua"NameTable21.py="liukai"NameTable22.py="louhanglin"NameTable23.py="luchaoming"Name

5、Table24.py="luqiuwei"NameTable25.py="panhaijian"NameTable26.py="shuxiang"NameTable27.py="suxiaolei"NameTable28.py="sunyubo"NameTable29.py="wangwei"for(i=0;i<NAME_LEN;i+)将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关桎字ints=0;char*p=NameTablei.py;for(

6、j=0;*(p+j)!='0'j+)s+=toascii(*(p+j);NameTablei.m=s;2 .建立哈希表voidCreateHashTable()for(i=0;i<HASH_LEN;i+)HashTablei.py="0"HashTablei.m=0;HashTablei.si=0;for(i=0;i<NAME_LEN;i+)intsum=1,j=0;intadr=(NameTablei.m)%P;/除留余数法H(key)=keyMODp,p<=mif(HashTableadr.si=0)/如果不冲突，将姓名表赋值给哈希表H

7、ashTableadr.m=NameTablei.m;HashTableadr.py=NameTablei.py;HashTableadr.si=1;)else/如果冲突(while(HashTableadr.si!=0)(adr=(adr+dj+)%HASH_LEN;/伪随机探测再散列法处理冲突sum=sum+1;/查找次数加1)HashTableadr.m=NameTablei.m;/将姓名表复制给哈希表对应的位置上HashTableadr.py=NameTablei.py;HashTableadr.si=sum;)3 .显示姓名表与哈希表voidDisplayNameTable()(pr

8、intf("n地址tt姓名tt关键字n");for(i=0;i<NAME_LEN;i+)printf("%2d%18stt%dn",i,NameTablei.py,NameTablei.m);voidDisplayHashTable()(floatasl=0.0;printf("nn地址tt姓名tt关键字t搜索长度n");显示的格式for(i=0;i<HASH_LEN;i+)(printf("%2d%18stt%dtt%dn",i,HashTablei.py,HashTablei.m,HashTable

9、i.si);asl+=HashTablei.si;)asl/=NAME_LEN;/求得ASLprintf("nn平均查找长度：ASL(%d)=%fn",NAME_LEN,asl);)4 .姓名查找voidFindName()(charname20=0;ints=0,sum=1,adr;printf("n请输入想要查找的姓名的拼音：")；scanf("%s",name);for(j=0;j<20;j+)/求出姓名的拼音所对应的ASCII作为关键字s+=toascii(namej);adr=s%P;/除留余数j=0;if(HashT

10、ableadr.m=s&&!strcmp(HashTableadr.py,name)/分3种情况进行判断，并输出超找结果printf("n姓名:%s关键字:%d查找长度为：1n",HashTableadr.py,s);elseif(HashTableadr.m=0)printf("没有想要查找的人!n");elsewhile(1)adr=(adr+dj+)%HASH_LEN;/伪随机探测再散列法处理冲突sum=sum+1;/查找次数加1if(HashTableadr.m=0)printf("没有想要查找的人!n");b

11、reak;if(HashTableadr.m=s&&!strcmp(HashTableadr.py,name)printf("n姓名:%s关键字:d查找长度为：dn",HashTableadr.py,s,sum);break;5、 测试结果c:我的文君i.C-FreeYTenip法命名l.ejce一表表豺虻除一得示示找出一号显显看一退一-1234请选择:工地址姓名关键字Qlouyuhongi10021shenyinghong12972叫angqiE，73ghuMiaoton9121G4zhataotao?715chenbinjie10396chenchaoq

12、uiinii11657chenchengi9318chenjiie7269chenwe93610shanjianfeng12&0E1fangfyixio?7312houfeng748I：,'.d：懂的文若C-FeeVTemp侏命名1.exer?chenueida93610shanjianfeng126011fangyixin97312houfeng74813hujiaming95614huangjiaju106215huanqingsong129816jianghe72617jinleicheng115218libiao62419liqi431Q0lii'enhua85

13、6Elliukai639Q2louhancflin1073E3luchaoming1063Q4luqiuwei885panhaijian1043shuxiang871G7suxiaolei979Q8sunsFLibo789G9wangwei7541063H856104343172h1039754关键字wangweichenhinjiejlanghechenjiesunyuboc：4：我的文若工干已用161叩球命名1.田（©87国姓名liqipanhaiJiaiolirenhuaihuangjiajuluchaomingilouyulionghujianinor0援察长度BQ10012

14、111002211000012六、实验环境C-Free七、源程序代码/time用到的头文件/随机数用到的头文件/toascii()用到的头文件#include<stdio.h>#include<time.h>#include<stdlib.h>查找姓名时比较用的头文件/哈希表的长度小于哈希表长度的P/姓名表的长度#include<ctype.h>#include<string.h>/# defineHASH_LEN50# defineP47/# defineNAME_LEN30typedefstruct/姓名表char*py;/名字的

15、拼音intm;/拼音所对应的NAME;NAMENameTableHASH_LEN;/全局定义姓名表typedefstruct/哈希表char*py;/名字的拼音intm;/拼音所对应的ASCII总和intsi;/查找长度HASH;HASHHashTableHASH_LEN;/全局定义哈希表intd30,i,j;/全局定义随机数，循环用的i、jvoidInitNameTable()/姓名表的初始化NameTable0.py="louyuhong"NameTable1.py="shenyinghong"NameTable2.py="wangqi&q

16、uot;NameTable3.py="zhuxiaotong”;NameTable4.py="zhataotao”;NameTable5.py="chenbinjie”;NameTable6.py="chenchaoqun”;NameTable7.py="chencheng"NameTable8.py="chenjie"NameTable9.py="chenweida"NameTable10.py="shanjianfeng"NameTable11.py="fang

17、yixin"NameTable12.py="houfeng"NameTable13.py="hujiaming"NameTable14.py="huangjiaju"NameTable15.py="huanqingsong"NameTable16.py="jianghe"NameTable17.py="jinleicheng"NameTable18.py="libiao"NameTable19.py="liqi"NameTab

18、le20.py="lirenhua"NameTable21.py="liukai"NameTable22.py="louhanglin"NameTable23.py="luchaoming"NameTable24.py="luqiuwei"NameTable25.py="panhaijian”;NameTable26.py="shuxiang"NameTable27.py="suxiaolei"NameTable28.py="sunyu

19、bo"NameTable29.py="wangwei"for(i=0;i<NAME_LEN;i+)/将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字ints=0;char*p=NameTablei.py;for(j=0;*(p+j)!='0'j+)s+=toascii(*(p+j);NameTablei.m=s;voidCreateHashTable()/建立哈希表for(i=0;i<HASH_LEN;i+)HashTablei.py="0"HashTablei.m=0;HashTablei.

20、si=0;for(i=0;i<NAME_LEN;i+)intsum=1,j=0;intadr=(NameTablei.m)%P;/除留余数法H(key)=keyMODp,p<=mif(HashTableadr.si=0)/如果不冲突，将姓名表赋值给哈希表HashTableadr.m=NameTablei.m;HashTableadr.py=NameTablei.py;HashTableadr.si=1;else/如果冲突while(HashTableadr.si!=0)adr=(adr+dj+)%HASH_LEN;/伪随机探测再散列法处理冲突sum=sum+1;/查找次数加1将姓名

21、表复制给哈希表对应的位置上HashTableadr.m=NameTablei.m;/HashTableadr.py=NameTablei.py;HashTableadr.si=sum;voidDisplayNameTable()/显示姓名表(printf("n地址tt姓名tt关键字n");for(i=0;i<NAME_LEN;i+)printf("%2d%18stt%dn",i,NameTablei.py,NameTablei.m);)voidDisplayHashTable()/显示哈希表(floatasl=0.0;printf("nn

22、地址tt姓名tt关键字t搜索长度n");显示的格式for(i=0;i<HASH_LEN;i+)(printf("%2d%18stt%dtt%dn",i,HashTablei.py,HashTablei.m,HashTablei.si);asl+=HashTablei.si;)asl/=NAME_LEN;/求得ASLprintf("nn平均查找长度：ASL(%d)=%fn",NAME_LEN,asl);)voidFindName()/查找charname20=0;ints=0,sum=1,adr;printf("n请输入想要查找的

23、姓名的拼音：")；scanf("%s",name);for(j=0;j<20;j+)/求出姓名的拼音所对应的ASCII作为关键字s+=toascii(namej);adr=s%P;/除留余数法j=0;if(HashTableadr.m=s&&!strcmp(HashTableadr.py,name)/分3种情况进行判断，并输出超找结果printf("n姓名:s关键字:d查找长度为：1n",HashTableadr.py,s);elseif(HashTableadr.m=0)printf("没有想要查找的人!n");elsewhile(1)adr=(adr+dj+)%HASH_LEN;/伪随机探测再散列法处理冲突sum=sum+1;/查找次数加1if(HashTableadr.m=0)printf("没有想要查找的人