数据结构实验报告(哈希表)

《数据结构实验报告(哈希表)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、散列表的设计实验报告1、题目：散列表的设计:针对某个集体中人名设计一个散列表，使得平均查找长度不超过R,并完成相应的建表和查表程序。2、基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共30个，取平均查找长度上限为2，哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。人名长度不超过20个字符。可先对过长的人名作折叠处理。3、设计思想：a.构造哈希函数的方法很多，常用的有(1)直接定址法(2)数字分析法;(3)平方取中法;(4)折叠法;(5)除留余数法;(6)随机数法；本实验采用的是除留

2、余数法:取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址H(key)=keyMODp,p<=m.b.哈希函数可以减少冲突，但不能避免。通常用的处理冲突的方法有：（1）开放定址法，这种方法还包含三种形式，一种叫线性探测再散列，一种叫二次探测再散列，另一种叫伪随机探测再散列。本实验采用的是第三种伪随机探测再散列。求下一个开放地址的公式为：Hi=(H(k)+di)MODm(Di=伪随机数序列)c.对哈希表的操作InitNameList()操作结果：姓名（结构体数组）初始化CreateHashList(

3、)操作结果：建立哈希表FindList()操作结果：在哈希表中查找Display()操作结果：显示哈希表4、程序结构图主程序查找显示哈希表建立哈希表初始化姓名5、流程图6、数据测试7、程序清单#include#includeusingnamespacestd;#defineHASH_LENGTH50#defineM47#defineNAME_NO30typedefstruct{char*py;intk;}NAME;NAMENameList[HASH_LENGTH];typ

4、edefstruct{char*py;intk;intsi;//查找长度}HASH;HASHHashList[HASH_LENGTH];voidInitNameList(){char*f;intr,s0,i;for(i=0;i

5、rcpy(NameList[2].py,"jianghaiyan");strcpy(NameList[3].py,"wangtingting");strcpy(NameList[4].py,"zhouhuihui");strcpy(NameList[5].py,"zhuzhenguo");strcpy(NameList[6].py,"wuqingwen");strcpy(NameList[7].py,"chenzuopeng");strcpy(NameList[8].py,"jinlining");strc

6、py(NameList[9].py,"zhandakan");strcpy(NameList[10].py,"linjiajia");strcpy(NameList[11].py,"huangwenjun");strcpy(NameList[12].py,"lizhongjing");strcpy(NameList[13].py,"sushiding");strcpy(NameList[14].py,"ouyangyaoyao");strcpy(NameList[15].py,"chenwei");strc

7、py(NameList[16].py,"linxiaxiao");strcpy(NameList[17].py,"zhanjie");strcpy(NameList[18].py,"baishujun");strcpy(NameList[19].py,"gongqiaoqiao");strcpy(NameList[20].py,"lvhaitao");strcpy(NameList[21].py,"jiangqingsong");strcpy(NameList[22].py,"gubaolong");str

8、cpy(NameList[23].py,"yehuaisong");strcpy(NameList[24].py,"wangyuqin");strcpy(NameList[25].py,"xuefeifei");strcpy(NameList[26].py,"wujianshu");strcpy(NameList[27].py,"zhanghuajiang");strcpy(NameList[28].py,"zh