数据结构哈希表设计

1、一、问题描述 针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表，使得平均查找长 度均不超过R,完成相应的建表和查表顺序。二、基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有 30个,取平均查 找长度的上限为 2。哈希函数用除留余数法构造,用伪随机探测再散列法处理冲突。三、概要设计1. 构造结构体：typedef st rue t;2. 姓名表的初始化： void InitNameTable()；3. 建立哈希表： void CreateHashTable();4. 显示姓名表： void DisplayNameTable();5. 姓名查找： void FindName();6. 主函数： void main() ;四、详细设计1. 姓名表的初始化void InitNameTable()NameTable0.py=louyuhong;NameTable1.py=shenyinghong;NameTable2.py=wangqi;NameTable3.py=zhuxiaotong;NameTable4.py=zhataotao;NameTable5.py=e

2、henbinjie;NameTable6.py=ehenehaoqun;NameTable7.py=eheneheng;NameTable8.py=ehenjie;NameTable9.py=ehenweida;NameTable10.py=shanjianfeng;NameTable11.py=fangyixin;NameTable12.py=houfeng;NameTable13.py=hujiaming;NameTable14.py=huangjiaju;NameTable15.py=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;NameTable24.py=luqiuwei;NameTable25.py=panhaijian

3、;NameTable26.py=shuxiang;NameTable27.py=suxiaolei;NameTable28.py=sunyubo;NameTable29.py=wangwei;for (i=0;iNAME_LEN;i+)/ 将字符串的各个字符所对应的 ASCII 码相加，所得的整数做为哈希表的关键字int s=0;char *p=NameTablei.py;for (j=0;*(p+j)!=0;j+)s+=toascii(*(p+j);NameTablei.m=s;2. 建立哈希表void CreateHashTable() for(i=0;iHASH_LEN;i+) HashTablei.py=0;HashTablei.m =0;HashTablei.si=0;for(i=0;iNAME_LEN;i+)int sum=1,j=0;int adr=(NameTablei.m)%P; / 除留余数法 H(key)=keyMOD p,p=mif(HashTableadr.si=0)/ 如果不冲突，将姓名表赋值给哈希表HashTableadr.m =NameTablei.m;

4、HashTableadr.py=NameTablei.py;else /如果冲突 while(HashTableadr.si!=0)adr=(adr+dj+)%HASH_LEN;/ 伪随机探测再散列法处理冲突sum=sum+1;/ 查找次数加 1HashTableadr.m =NameTablei.m; / 将 姓名表复制给哈希表对应的位置上HashTableadr.py=NameTablei.py;HashTableadr.si=sum;3. 显示姓名表与哈希表void DisplayNameTable()printf(n 地址 tt 姓名 tt 关键字 n);for (i=0;iNAME_LEN;i+)printf(%2d %18stt %d n,i,NameTablei.py,NameTablei.m);void DisplayHashTable()float asl=0.0;printf(nn 地址 tt 姓名 tt 关键字 t 搜索长度 n); / 显示的格 式for (i=0;iHASH_LEN;i+)printf(%2d %18s tt %dtt %dn,i,HashTa

5、blei.py,HashTablei.m,HashTablei.si);asl+=HashTablei.si;asl/=NAME_LEN;/ 求得ASLprintf(nn 平均查找长度： ASL(%d)=%f n,NAME_LEN,asl);4. 姓名查找void FindName()char name20=0;int s=0,sum=1,adr;printf(n 请输入想要查找的姓名的拼音 :);scanf(%s,name);for (j=0;j20;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);else if (HashTableadr.m=0)printf( 没有想要查找的人 !n);elsewhile(1)adr=(adr+dj+)%HASH_LEN;/ 伪随机

6、探测再散列法处理冲突sum=sum+1;/ 查找次数加 1if(HashTableadr.m=0)printf( 没有想要查找的人!n);break;if(HashTableadr.m=s&!strcmp(HashTableadr.py,name)printf(n 姓名：s键字：d 查找长度为：dn,HashTableadr.py,s,sum);break;五、测试结果： dk哥的童若GF色吕VT巳币口诔命名1 .exe2 2 4 5 6?8 9 0 12请选择江姓名 louuhonicf slienimshoriiiEr rarsTgi ihuM Iao t o n(y zhatactao chenbinj ie chenchacqun chencJiemcf chenJ ie clienwc Ida shan j lanf en)r( f anjfyixin houfeng12 3 4示示找岀显显占S一表蔻关键予1002 丄297 C47 121ft 971 1039 116E V31 726 93G 12fiB973748-日:诵 的 ZSCSVC-FireeXTempXSfci

7、SkS l.ewe9chenue ida?3619slianj ianf eng126011fangs1 ix in?7312Jiouf eng74813hujianinsr?5614huangjiaju106215huanqingsongr129816jianghe72617jinleicliensr115218libiaoS2419liqi43129lirenhua85621liul;ai63922louhanglin107323luchaominsr10&324luqiuiuei88525panhaij ian10432Ssliuxiang87127suxiaolei?7928sunvbo78929uangei754六、实验环境C-Free七、源程序代码#include/time 用到的头文件/随机数用到的头文件/toascii()用到的头文件/查找姓名时比较用的头文件/哈希表的长度/小于哈希表长度的 P/姓名表的长度#include#include#include#include#define HASH_LEN 50#define P 47#define NAME_LEN 30 typedef struct /姓名表 char *py;/名字的拼音int m;/拼音所对应的NAME;NAME NameTableHASH_LEN;/全局定义姓名表typedef struct/哈希表char *py;/名字的拼音int m;/拼音所对应的 ASCII 总和int si;/查找长度HASH;HASH HashTableHASH_LEN;/全局定义哈希表int d30,i,j;/全局定义随机数,循环用的 i、jvoid InitNameTable() /姓名表的初始化NameTable0.py=louyuhong;NameTable1.py=shenyinghong;NameTable2.py=wangqi;NameTable3.py=zhuxiaotong;NameTable4.py=zhataotao;NameTable5.py=chenbinjie;NameTable6.py=chenchaoqun;NameTable7.py=chencheng;Name

《数据结构哈希表设计》由会员cn****1分享，可在线阅读，更多相关《数据结构哈希表设计》请在金锄头文库上搜索。