《数据结构报告——散列表、哈希表》由会员分享，可在线阅读，更多相关《数据结构报告——散列表、哈希表（12页珍藏版）》请在金锄头文库上搜索。
1、数据构造试验报告班级： 学号：姓名： 时间：一、 题 目散列表的设计二、 要求1、问题描述针对某个集体中人名设计一个散列表，使得平均查找长度不超过 R，并完成相应的建表和查表程序。2、根本要求假设人名为中国人姓名的汉语拼音形式，待填入散列表的人名共有 30 个， 取平均查找长度上限为 2。散列函数用除留余数法构造，用伪随机探测再散列法处理冲突3、测试数据取读者四周较生疏的 30 人的姓名。4、实现提示假设随机函数自行构造，那么应首先调整好随机函数，使其公布均匀。人名的长度不超过 20 个字符。可先对过长的人名作折叠处理。三 、设计思想1、散列函数的构造方法：散列列函数的构造方法有四种：平方取中
2、法、除余法、相乘取整法、随机数法。这里用了除余法，该方法是最为简洁常用的一种方法。它是以表长 m 来除关键字，取其余数作为散列地址，即 h(key)=keym该方法的关键是选取 m。选取的 m 应使得散列函数值尽可能与关键字的各位相关。m 最好为素数。【例】假设选 m 是关键字的基数的幂次，那么就等于是选择关键字的最终假设干位数字作为地址，而与高位无关。于是高位不同而低位一样的关键字均互为同义词。【例】假设关键字是十进制整数，其基为 10，那么当 m=100 时，159，259，359， 等均互为同义词。2、冲突的处理：- 11 -（1） 冲突两个不同的关键字，由于散列函数值一样，因而被映射到
3、同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。（2） 平安避开冲突的条件最抱负的解决冲突的方法是平安避开冲突。要做到这一点必需满足两个条件：其一是|U|m其二是选择适宜的散列函数。这只适用于|U|较小，且关键字均事先的状况，此时经过细心设计散列函数 h 有可能完全避开冲突。（3） 冲突不行能完全避开通常状况下，h 是一个压缩映像。虽然|K|m，但|U| m，故无论怎样设计h，也不行能完全避开冲突。因此，只能在设计 h 时尽可能使冲突最少。同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到表中。（4） 影响冲突的因
4、素冲突的频繁程度除了与 h 相关外，还与表的填满程度相关。设 m 和 n 分别表示表长和表中填人的结点数，那么将 =n/m 定义为散列表的装填因子(Load Factor)。 越大，表越满，冲突的时机也越大。通常取 1。（5） 冲突处理对不同的关键字可能得到同一个哈希地址 即 key1 key2 ， 而f(key1)=f(key2)。因此，在建筑哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。用伪随机探测法。求下一个开放地址的公式为：Hi = (H(k)+di) MOD m Di=伪随机数序列；3、相应的数据构造：1） 、对哈希表的操作 InitNameList()操作结果：
5、姓名构造体数组初始化CreateHashList()操作结果：建立哈希表FindList()操作结果：在哈希表中查找Display()操作结果：显示哈希表2） 、主程序 int main()初始化； InitNameList()； CreateHashList()； do承受命令； 处理命令；while“命令”=“退出”； return 0;3 、本程序包含的模块1） 初始化操作，构造体定义；2） 姓名构造体建立模块；3） 建立哈希表模块；4） 查找模块；5） 显示哈希表模块；4） 主程序模块四、构造图MainInitNameListCreateHashListDisplayFindList五
6、、流程图开头输出 输入字母xx=a?NYDisplay();x=b?NYFindList();break;i=0iHASH_LENGTH?NYfree(NameListi.xm); free(HashListi.xm);return 0;i+完毕注 ：散列表设计a.显示散列表b.查 找c.退 出请选择：六、测试1. 本程序运行环境为 C+，生成的可执行文件为 a.exe;该可执行文件的执行环境为 DOS。用户进入演示程序后的界面为：2. 测试结果输入：a输出：散列表输入：b输入：lilei输出：无此记录！ 输入：chenlinsha输出：姓名：chenlinsha关键字：1053查找长度：1七
7、、程序清单#include #include using namespace std;#define HASH_LENGTH 50#define M 47#define NAME_NO 30typedef structchar *xm; int k;NAME;NAME NameListHASH_LENGTH;typedef structchar *xm; int k;int si;HASH;HASH HashListHASH_LENGTH;void InitNameList()char *f; int r,s0,i;for (i=0; iHASH_LENGTH; i+)NameListi.xm
8、 = new char64; NameListi.xm0 = 0;strcpy(NameList0.xm, “yingjun“); strcpy(NameList1.xm, “shengjiayan“); strcpy(NameList2.xm, “jiangxiya“); strcpy(NameList3.xm, “caihaipou“); strcpy(NameList4.xm, “shengwenbing“); strcpy(NameList5.xm, “chenlinsha“); strcpy(NameList6.xm, “yangqifan“);strcpy(NameList7.xm
9、, “zhanglei“); strcpy(NameList8.xm, “xujie“); strcpy(NameList9.xm, “chencao“); strcpy(NameList10.xm, “fangshongwei“); strcpy(NameList11.xm, “hexiaobing“); strcpy(NameList12.xm, “xubingbing“); strcpy(NameList13.xm, “zhangxi“); strcpy(NameList14.xm, “dinglan“); strcpy(NameList15.xm, “heliting“); strcp
10、y(NameList16.xm, “lexiaoying“); strcpy(NameList17.xm, “rentao“); strcpy(NameList18.xm, “renxinshi“); strcpy(NameList19.xm, “zhangjinjun“); strcpy(NameList20.xm, “lidan“); strcpy(NameList21.xm, “louwangyue“); strcpy(NameList22.xm, “zhuangjianjun“); strcpy(NameList23.xm, “lintingting“); strcpy(NameLis
11、t24.xm, “weili“); strcpy(NameList25.xm, “gaochun“); strcpy(NameList26.xm, “huangfeixiang“); strcpy(NameList27.xm, “wangjiangjie“); strcpy(NameList28.xm, “zhaojuntao“); strcpy(NameList29.xm, “wangchenli“); for(i=0;iNAME_NO;i+)s0=0;f=NameListi.xm; for(r=0;*(f+r)!=”0”;r+) s0=*(f+r)+s0; NameListi.k=s0;v
12、oid CreateHashList()int i;for(i=0; iHASH_LENGTH;i+)HashListi.xm=new char64; HashListi.xm0 = 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.xm=NameListi.xm; HashListadr.si=1;elsewhile (Ha
13、shListd.k!=0)d=(d+NameListi.k%10+1)%M; sum=sum+1;HashListd.k=NameListi.k; HashListd.xm=NameListi.xm; HashListd.si=sum+1;void FindList()string name;int s0=0,r,sum=1,adr,d; coutendl;cout“请输入姓名的拼音:“name; for(r=0;r20;r+)s0+=namer; adr=s0%M; d=adr;if(HashListadr.k=s0)coutendl“姓名:“HashListd.xmendl; cout“关键字:“s0endl;cout“查找长度为: 1“endl; else if (HashListadr.k=0)cout“无此记录!“endl;elseint 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)coutendl“姓名:“HashListd.xmendl; cout“关键字:“s0endl;cout“查找长度为: 1“endl; g=1;voidDis
