哈希表-算法-hash表-C++实现.docx

《哈希表-算法-hash表-C++实现.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、哈希表算法hash表问题描述：针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。#include#include#include//#include#defineHASH_LEN50//哈希表的长度#defineM47#defineNAME_NO30//人名的个数typedefstru

2、ctNAME{char*py;//名字的拼音intk;//拼音所对应的整数}NAME;NAMENameList[HASH_LEN];typedefstructhterm//哈希表{char*py;//名字的拼音intk;//拼音所对应的整数intsi;//查找长度}HASH;HASHHashList[HASH_LEN];/*-----------------------姓名（结构体数组）初始化---------------------------------*/voidInitNameList(){NameList[0].py="zhanghongshuai

3、";NameList[1].py="xurensong";NameList[2].py="huangxiangyu";NameList[3].py="luoqi";NameList[4].py="zhangsan";NameList[5].py="lisi";NameList[6].py="wangwu";NameList[7].py="renwei";NameList[8].py="zhangchu";NameList[9].py="wangmengyuan";NameList[10].py="libaohua";NameList[11].py="zhao

4、yanlong";NameList[12].py="jwangyuxin";NameList[13].py="duyanmo";NameList[14].py="wangmingyang";NameList[15].py="lijiawei";NameList[16].py="hesiyu";NameList[17].py="zhanghailong";NameList[18].py="lixinyu";NameList[19].py="songdiyao";NameList[20].py="zhaomingzhi";NameList[21].py="zha

5、ngchenglong";NameList[22].py="sunjie";NameList[23].py="zhangdongmei";NameList[24].py="antianyu";NameList[25].py="zhulaiao";NameList[26].py="wangyuting";NameList[27].py="wangxiliang";NameList[28].py="zhangdeshuai";NameList[29].py="xumingming";char*f;intr,s0;for(inti=0;i

6、//求出各个姓名的拼音所对应的整数{s0=0;f=NameList[i].py;for(r=0;*(f+r)!='';r++)//方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字s0=*(f+r)+s0;NameList[i].k=s0;}}/*-----------------------建立哈希表---------------------------------*/voidCreateHashList(){for(inti=0;i

7、List[i].k=0;HashList[i].si=0;}for(inti=0;i<=NAME_NO;){intsum=0;intadr=(NameList[i].k)%M;//哈希函数intd=adr;if(HashList[adr].si==0)//如果不冲突{HashList[adr].k=NameList[i].k;HashList[adr].py=NameList[i].py;HashList[adr].si=1;}else//冲突{do{d=(d+((NameList[i].k))%10+1)%M;//伪散列sum=sum+1;//查找次数加1

8、}while(HashList[d].k!=0);H