数据结构课程设计哈希表设计

1、哈希表设计 一 需求分析 1.1 针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过r，完成相应的建立和查表程序. 1.2 人名为汉语拼音形式，最长不超过19个字符(如：庄双双 zhuangshuangshuang). 1.3 假设待填入哈希表的人名有30个，平均查找长度为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。 1.4 测试数据:1)输入数据:zengqinhui,mayuelong,chenzhicheng,sunpeng,wanghui,liqingbo,liujunpeng,jiangquanlei,xingzhengchuan,luzhaoqian,gaow

2、enhu,zhuhaoyin,chenlili,wuyunyun,huangjuanxia,wangyan,zhoutao,jiangzhenyu,liuxiaolong,wangziming,fengjunbo,lilei,wangjia,zhangjianguo,zhuqingqing,huangmin,haoyuhan,zhoutao,zhujiang,lixiaojun.2)d. 显示哈希表地址 关键字 搜索长度 h（key） 姓名0 0 1 0 （null）1 1505 1 1 xingzhengchuan2 1083 1 2 wangziming3 755 1 3 wanghui4

3、 991 1 4 zhuhaoyin5 757 1 5 wangyan6 1272 2 3 jiangquanlei7 853 1 7 liqingbo8 1089 1 8 liujunpeng9 855 1 9 huangmin10 527 1 10 lilei11 0 12 0 (null)12 979 3 39 lixiaojun13 1084 3 3 luzhaoqian14 1283 1 14 huangjuanxia15 861 1 15 haoyuhan16 768 1 16 sunpeng17 0 0 0 18 1193 1 18 zengqinghui19 862 2 16

4、gaowenhu20 1195 1 20 liuxiaolong21 1196 1 21 jiangzhenhu22 1285 2 16 zhangjianguo23 864 2 18 zhujiang24 0 0 025 0 0 026 778 1 26 zhuotao27 958 2 18 fengjunbo28 0 0 029 0 0 030 1205 1 30 zhuqingqing31 0 0 032 737 1 32 wangjia33 0 0 034 0 0 035 778 2 26 zhuotao36 0 0 037 977 1 37 mayuelong38 0 0 039 9

5、32 1 39 wuyunyun40 1262 1 40 chenzhicheng41 840 1 41 chenlili42 0 0 043 0 0 044 0 0 045 0 0 046 0 0 047 0 0 048 0 0 049 0 0 0平均查找长度：asl（30）= 1.766667f. 查找请输入姓名的拼音：wangjia结果：姓名：wangjia 关键字：737 查找长度为：1请输入姓名的拼音：luzhaoqian结果：姓名：luzhaoqian 关键字：1084 查找长度为：3请输入姓名的拼音：luzhao结果：无此记录q. 退出y结果：press ang key to c

6、ontinue二. 概要设计2.1 基本操作 void initnamelist() 姓名（结构体数组）初始化 操作结果：名字以拼音的形式够成字符串，将字符串的各个字符所对应的ascii码相加，所得的整数做为哈希表的关键字。 void createhashlist() 建立哈希表 操作结果： （1） 用除留余数法构建哈希函数 （2） 用伪随机探测再散列法处理冲突 void findlist() 查找哈希表 操作结果：在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度 void display() 操作结果：显示哈希表的的格式：n地址t关键字tt搜索长度th(key)

7、t 姓名n void main() 主函数设计 操作结果：主函数显示格式：d. 显示哈希表nf. 查找nq. 退出n请选择：2.2 主程序void main() 初始化； while（命令！=退出） 接受命令； 处理命令；2.3 模块调用关系主函数模块显示模块查找模块哈希表模块初始化模块三 详细设计 3.1 存储结构设计typedef struct char *py; /名字的拼音 int k; /拼音所对应的整数name; typedef struct /哈希表 char *py; /名字的拼音 int k; /拼音所对应的整数 int si; /查找长度hash; 3.2 姓名（结构体数组

8、）初始化 名字以拼音的形式够成字符串，将字符串的各个字符所对应的ascii码相加，所得的整数做为哈希表的关键字。void initnamelist() char *f; int r,s0,i; namelist0.py=zengqinghui; namelist1.py=mayuelong; namelist2.py=chenzhicheng; namelist3.py=sunpeng; namelist4.py=wanghui; namelist5.py=liqingbo; namelist6.py=liujunpeng; namelist7.py=jiangquanlei; namelis

9、t8.py=xingzhengchuan; namelist9.py=luzhaoqian; namelist10.py=gaowenhu; namelist11.py=zhuhaoyin; namelist12.py=chenlili; namelist13.py=wuyunyun; namelist14.py=huangjuanxia; namelist15.py=wangyan; namelist16.py=zhoutao; namelist17.py=jiangzhenyu; namelist18.py=liuxiaolong; namelist19.py=wangziming; na

10、melist20.py=fengjunbo; namelist21.py=lilei; namelist22.py=wangjia; namelist23.py=zhangjianguo; namelist24.py=zhuqingqing; namelist25.py=huangmin; namelist26.py=haoyuhan; namelist27.py=zhoutao; namelist28.py=zhujiang; namelist29.py=lixiaojun; for(i=0;iname_no;i+) s0=0; f=namelisti.py; for(r=0;*(f+r)!

11、=0;r+) */将字符串的各个字符所对应的ascii码相加，所得的整数做为哈希表的关键字*/ s0=*(f+r)+s0; namelisti.k=s0; 3.3 建立哈希表 （1） 用除留余数法构建哈希函数 （2） 用伪随机探测再散列法处理冲突void createhashlist() int i; for(i=0; ihash_length;i+) hashlisti.py=; hashlisti.k=0; hashlisti.si=0; for(i=0;ihash_length;i+) int sum=0; int adr=(namelisti.k)%m; /哈希函数 int d=adr

12、; if(hashlistadr.si=0) /如果不冲突 hashlistadr.k=namelisti.k; hashlistadr.py=namelisti.py; hashlistadr.si=1; else /冲突 do d=(d+namelisti.k%10+1)%m; /伪随机探测再散列法处理冲突 sum=sum+1; /查找次数加1 while (hashlistd.k!=0); hashlistd.k=namelisti.k; hashlistd.py=namelisti.py; hashlistd.si=sum+1; 3.4 查找哈希表 在哈希表中进行查找，输出查找的结果和

13、关键字，并计算和输出查找成功的平均查找长度void findlist() char name20=0; int s0=0,r,sum=1,adr,d; printf(请输入姓名的拼音:); scanf(%s,name); for(r=0;r20;r+) /求出姓名的拼音所对应的整数(关键字) s0+=namer; adr=s0%m; /使用哈希函数 d=adr; if(hashlistadr.k=s0) /分3种情况进行判断 printf(n姓名:%s 关键字:%d 查找长度为: 1,hashlistd.py,s0); else if (hashlistadr.k=0) printf(无此记录

14、!); else int g=0; do d=(d+s0%10+1)%m; /伪随机探测再散列法处理冲突 sum=sum+1; if(hashlistd.k=0) printf(无此记录! ); g=1; if(hashlistd.k=s0) printf(n姓名:%s 关键字:%d 查找长度为:%d,hashlistd.py,s0,sum); g=1; while(g=0); 3.5 显示哈希表 显示哈希表的的格式： n地址t关键字tt搜索长度th(key)t 姓名nvoid display() int i; float average=0; printf(n地址t关键字tt搜索长度th(k

15、ey)t 姓名n); /显示的格式 for(i=0; i50; i+) printf(%d ,i); printf(t%d ,hashlisti.k); printf(tt%d ,hashlisti.si); printf(tt%d ,hashlisti.k%m); printf(t %s ,hashlisti.py); printf(n); for(i=0;i&ch1;switch(ch1)case d:display(); coutendl;break;case f:findlist();coutendl;break;case q:exit(0); cout&ch1;while(ch1!=

16、n); 四. 调试分析 4.1 本次作业比较简单,只有一个核心算法就是构造散列函数的算法,在调试的时候发现 string的问题(系统自带的),输入的人名不应该含有空格字符，否则回出现逻辑错误，这是程序的一个问题，如果要修改成char型处理方法类似就没改。在调试其他代码时候没有出现问题,比较顺利的调试成功。 4.2 有些函数不写系统会自己生成,为了避免出错自己写了上去只是声名并没有定义,如果用了编译器会报错。 4.3 算法改进:伪随机探查法能够消除基本聚集,但是如果两个关键子有相同的基位置,那么他们就有同样的探查序列。采用双散列法能够避免这样,双散列函数使用两个和散列函数,第一个探查序列的起始值

17、,第二个计算下一个位置的探查步长。 4.4 问题的发现与解决：题目中明确规定了用除留余数法创建哈希函数和用伪随机探测再散列法处理冲突，程序设计的方法几乎已经被规定，只要按照题目要求写程序不会太难。不过在写程序过程中还是发现了一些小问题，主要是因为自己上机试验少，以后多上机实践能够避免的。 4.5 经验体会:借助debug调试器和数据观察窗口,可以加快找到程序中的错误,采用软件工程的方法将程序划分层次结构使得代码设计时思路清晰,实现时调试顺利,得到了一次良好的程序设计训练。五. 用户手册5.1 本程序的运行环境为dos 操作系统，执行文件为：yun.exe。5.2 进入演示程序后即显示文本方式的

18、用户界面：哈希表设计 d. 显示哈希表 f. 查找 q. 退出 请选择：5.3 进入用户界面后，即提示键入操作符号，结束符为“回车符”。5.4 接受其他命令后即执行相应操作和显示相应结果。六. 测试结果测试用例程序运行结果如下 程序运行后显示如下6.1 选择d 查找，显示哈希表和平均查找长度，其中平均查找长度小于2，符合题目要求6.2 选择f 查找， 输入要查找的人的姓名，若存在则显示名字和对应的关键字以及查找长度；若不存在则显示无此记录6.3 选择q 退出 ， 如要继续可按任意键七. 附录 碧云.cpp 哈希表的定义与主程序八. 参考文献1严蔚敏，吴伟民.数据结构m.北京：清华大学出版社，2

19、0062谭浩强，c语言程序设计m.北京：高等教育出版社，2006 3李春葆，数据结构教程m .北京：清华大学出版社，2005 4数据结构c+语言描述william ford和william topp著，刘卫东和沈官林译，清华大学出版社,2009九. 心得与体会经过这次课程设计的学习，让我明白了编写程序的思路是很重要的。在你编写一个程序之前，如果你的脑袋里面没有思路，根本就不可能编出好的程序。就算能编出程序来，相信编出的程序的逻辑性也不会很强，因为你是想到什么就编什么，不系统。因此在我们编程序之前一定要做好充分的准备，首先要理清自己的思路，然后再将思路分划成几个模块，一块一块的编写，最后再将所有的模块联系起来，组成一个完整的程序。在上机实验之前，最好将程序编写好在草稿纸上，这样在编译的时候也比较有效率。借助debug调试器和数据观察窗口,可以加快找到程序中的错误,采用软件工程的方法将程序划分层次结构使得代码设计时思路清晰