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

散列表的设计实验报告1、题目：散列表的设计:针对某个集体中人名设计一个散列表，使得平均查找长度不超过R,并完成相应的建表和查表程序。2、基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共30个，取平均查找长度上限为2，哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。人名长度不超过20个字符。可先对过长的人名作折叠处理。3、设计思想：a.构造哈希函数的方法很多，常用的有(1)直接定址法(2)数字分析法;(3)平方取中法;(4)折叠法;( 5)除留余数法;(6)随机数法；本实验采用的是除留余数法:取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址H(key)=key MOD p,p=m. b.哈希函数可以减少冲突，但不能避免。通常用的处理冲突的方法有：（1）开放定址法，这种方法还包含三种形式，一种叫线性探测再散列，一种叫二次探测再散列，另一种叫伪随机探测再散列。本实验采用的是第三种伪随机探测再散列。求下一个开放地址的公式为：Hi=(H(k)+di)MOD m (Di=伪随机数序列)c.对哈希表的操作InitNameList() 操作结果：姓名（结构体数组）初始化CreateHashList() 操作结果：建立哈希表FindList() 操作结果：在哈希表中查找Display() 操作结果：显示哈希表4、程序结构图主程序查找显示哈希表建立哈希表初始化姓名5、流程图6、数据测试7、程序清单#include#includeusing namespace std;#define HASH_LENGTH 50#define M 47#define NAME_NO 30typedef struct char *py;int k;NAME;NAME NameListHASH_LENGTH;typedef struct char *py; int k; int si;/查找长度HASH;HASH HashListHASH_LENGTH;void InitNameList() char *f; int r,s0,i;for (i=0; iHASH_LENGTH; i+) NameListi.py = new char20; NameListi.py0 = 0;strcpy(NameList0.py, lintingting);strcpy(NameList1.py, chenxiaoping);strcpy(NameList2.py, jianghaiyan);strcpy(NameList3.py, wangtingting);strcpy(NameList4.py, zhouhuihui);strcpy(NameList5.py, zhuzhenguo);strcpy(NameList6.py, wuqingwen);strcpy(NameList7.py, chenzuopeng);strcpy(NameList8.py, jinlining);strcpy(NameList9.py, zhandakan);strcpy(NameList10.py, linjiajia);strcpy(NameList11.py, huangwenjun);strcpy(NameList12.py, lizhongjing);strcpy(NameList13.py, sushiding);strcpy(NameList14.py, ouyangyaoyao);strcpy(NameList15.py, chenwei);strcpy(NameList16.py, linxiaxiao);strcpy(NameList17.py, zhanjie);strcpy(NameList18.py, baishujun);strcpy(NameList19.py, gongqiaoqiao);strcpy(NameList20.py, lvhaitao);strcpy(NameList21.py, jiangqingsong); strcpy(NameList22.py, gubaolong);strcpy(NameList23.py, yehuaisong);strcpy(NameList24.py, wangyuqin);strcpy(NameList25.py, xuefeifei);strcpy(NameList26.py, wujianshu);strcpy(NameList27.py, zhanghuajiang);strcpy(NameList28.py, zhengpan);strcpy(NameList29.py, sudongdong);for(i=0;iNAME_NO;i+) s0=0; f=NameListi.py; for(r=0;*(f+r)!=0;r+) s0=*(f+r)+s0; NameListi.k=s0; void CreateHashList() int i;for(i=0; iHASH_LENGTH;i+) HashListi.py=new char20; HashListi.py0 = 0; HashListi.k=0; HashListi.si=0;for(i=0;iHASH_LENGTH;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 /冲突 while (HashListd.k!=0) d=(d+NameListi.k%10+1)%M; /伪随机探测再散列法处理冲突 sum=sum+1; ; HashListd.k=NameListi.k; HashListd.py=NameListi.py; HashListd.si=sum+1; void FindList() string name; int s0=0,r,sum=1,adr,d; cout请输入人名的拼音:name; for(r=0;r20;r+) s0+=namer; adr=s0%M; /使用哈希函数 d=adr; if(HashListadr.k=s0) cout姓名:HashListd.pyendl关键字:s0endl查找长度为: 1endl; else if (HashListadr.k=0) cout无此记录!endl; else int g=0; while(g=0) d=(d+s0%10+1)%M; sum=sum+1; if(HashListd.k=0) cout无此记录!endl; g=1; if(HashListd.k=s0) cout姓名:HashListd.pyendl关键字:s0endl查找长度为:sumendl; g=1; ; void Display() int i; float average=0; coutn地址t关键字tt搜索长度tH(key)t 姓名n;for(i=0; i50; i+) couti ; couttHashListi.k ; coutttHashListi.si ; couttt(HashListi.k%M) ; coutt HashListi.py ; coutn;for(i=0;iHASH_LENGTH;i+) average+=HashListi.si; average/=NAME_NO;cout平均查找长度：ASL(NAME_NO)=averageendl;int main()char x;InitNameList(); CreateHashList (); coutd. 显示哈希表endlf. 查找end