数据结构实验答案 数据结构课程设计哈希表设计

1、课 程 设 计 课程名称 数据结构 题目名称 哈希表设计 学生学院 计算机学院 专业班级 07级网络工程2班 学 号 3207007022 学生姓名 刘晓慧 指导教师 杨劲涛 2009 年 6 月 28 日一问题描述1问题描述针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。二. 需求分析（1） 针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序。（2

2、）人名为汉语拼音形式，最长不超过19个字符(如：庄双双 zhuangshuangshuang)。（3） 假设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。（4） 在输入人名过程中能自动识别非法输入，并给与非法输入的反馈信息要求重新输入。（5）查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度三程序设计1 .存储结构设计typedef struct char *py; /名字的拼音 int k; /拼音所对应的整数NAME; typedef struct /哈希表 char *py; /名字的拼音 int k; /拼音所对

3、应的整数 int si; /查找长度HASH;2 .主要算法设计 （1） 姓名（结构体数组）初始化 名字以拼音的形式够成字符串，将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字。void InitNameList() char *f; int r,s0,i; NameList0.py="chenliang"/陈亮 NameList1.py="chenyuanhao"/陈元浩 NameList2.py="chengwenliang"/程文亮 NameList3.py="dinglei"/丁磊

4、NameList4.py="fenghanzao"/冯汉枣 NameList5.py="fuzongkai"/付宗楷 NameList6.py="hujingbin"/胡劲斌 NameList7.py="huangjianwu"/黄建武 NameList8.py="lailaifa"/赖来发 NameList9.py="lijiahao"/李嘉豪 NameList10.py="liangxiaocong"/梁晓聪 NameList11.py="l

5、inchunhua"/林春华 NameList12.py="liujianhui"/刘建辉 NameList13.py="luzhijian"/卢志健 NameList14.py="luonan"/罗楠 NameList15.py="quegaoxiang"/阙高翔 NameList16.py="sugan"/苏淦 NameList17.py="suzhiqiang"/苏志强 NameList18.py="taojiayang"/陶嘉阳 Name

6、List19.py="wujiawen"/吴嘉文 NameList20.py="xiaozhuoming"/肖卓明 NameList21.py="xujinfeng" /许金峰 NameList22.py="yanghaichun"/杨海春 NameList23.py="yeweixiong"/叶维雄 NameList24.py="zengwei"/曾玮 NameList25.py="zhengyongbin"/郑雍斌 NameList26.py=&quo

7、t;zhongminghua"/钟明华 NameList27.py="chenliyan"/陈利燕 NameList28.py="liuxiaohui"/刘晓慧 NameList29.py="panjinmei"/潘金梅 for(i=0;i<NAME_NO;i+) s0=0; f=NameListi.py; for(r=0;*(f+r)!='0'r+) */将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字*/ s0=*(f+r)+s0; NameListi.k=s0; (2) 建

8、立哈希表 （1） 用除留余数法构建哈希函数 （2） 用伪随机探测再散列法处理冲突void CreateHashList() int i; for(i=0; i<HASH_LENGTH;i+) HashListi.py="" HashListi.k=0; HashListi.si=0; for(i=0;i<HASH_LENGTH;i+) int sum=0; int adr=(NameListi.k)%M; /哈希函数 int d=adr; if(HashListadr.si=0) /如果不冲突 HashListadr.k=NameListi.k; HashLis

9、tadr.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) 查找哈希表 在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度void FindList() /查找 char name20=0; int s0=0

10、,r,sum=1,adr,d; printf("请输入姓名的拼音:"); scanf("%s",name); for(r=0;r<20;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("无此记录!"); else

11、 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); (4) 显示哈希表 显示哈希表的的格式： n地址t关键字tt搜索长度tH(key)t 姓名nvoid Display() int i; float average=0; printf(&

12、quot;n地址t关键字tt搜索长度tH(key)t 姓名n"); /显示的格式 for(i=0; i<50; 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<HASH_LENGT

13、H;i+) average+=HashListi.si; average/=NAME_NO; printf("n平均查找长度：ASL(%d)=%f n",NAME_NO,average); (5) 主函数设计void main()char ch1;InitNameList(); CreateHashList (); doprintf("D. 显示哈希表nF. 查找nQ. 退出n请选择： ");cin>>&ch1;switch(ch1)case 'D':Display(); cout<<endl;break;

14、case 'F':FindList();cout<<endl;break;case 'Q':exit(0);cout<<"come on !(y/n):"cin>>&ch1;while(ch1!='n'); 四. 编程环境：五调试报告及体会1.测试用例程序运行结果 程序运行后显示如下: （1）选择D 查找 ， 显示哈希表和平均查找长度，其中平均查找长度小于2，符合题目要求:（2） 选择F 查找， 输入要查找的人的姓名，若存在则显示名字和对应的关键字以及查找长度；若不存在则显示无此记录

15、：（3）选择Q 退出 ， 如要继续可按任意键： 2.时间复杂度O(n)3经验和体会经过这次课程设计的学习，让我明白了编写程序的思路是很重要的。在你编写一个程序之前，如果你的脑袋里面没有思路，根本就不可能编出好的程序。就算能编出程序来，相信编出的程序的逻辑性也不会很强，因为你是想到什么就编什么，不系统。因此在我们编程序之前一定要做好充分的准备，首先要理清自己的思路，然后再将思路分划成几个模块，一块一块的编写，最后再将所有的模块联系起来，组成一个完整的程序。在上机实验之前，最好将程序编写好在草稿纸上，这样在编译的时候也比较有效率。其实在这次课程设计的过程中，我也遇到了很多难题。在种种的困难中，我明

16、白了耐心在编写程序时的重要性。如果你没有耐心就肯定编不出好的程序，特别是在调试的过程中。我们初次写的程序在电脑上调试的时候也许会出项几百个错误，这时候我们应该耐心的检查出错的地方和原因，并予以改正，而不是抱怨自己写的程序太烂错误太多，就此放弃。相信再强的人也不可能一次就能编译成功，总会有一些问题出现。其实只要有耐心，你就会发现，在你修改了一个错误之后，其它有的错误也会跟着消失，所以在编译的时候一定要有耐心。这段时间的课程设计，我也认识到数据结构是一门比较难的课程，需要花很多的时间去练习和实践。要想把这门课程学好学精不是一件容易的事，但是相信事在人为，只要肯下功夫就一定能学好。总的来说，这次程序

17、设计让我获益匪浅，相信在以后的学习生活中我也能从中获得启发。六. 用户使用说明详细视图请参考调试报告程序运行初显示如下:从中选择需要做的操作，输入对应的操作D、F、Q，并按回车，输入错误时，会显示“无此记录！”;正确时，显示姓名，关键字以及查找长度。显示“come on！<y/n>”时，选择y继续回到初始菜单，选择n退出程序。七测试结果输入“chenliang”输出 “姓名：chenliang 关键字：937 查找长度为：1”输入“chenyuanhao”输出 “姓名：chenyuanhao 关键字：1171 查找长度为：1”输入“chengwenliang”输出 “姓名：chen

18、gwenliang 关键字：1370 查找长度为：1”输入“dinglei输出 “姓名：dinglei 关键字：732 查找长度为：1”输入“fenghanzao”输出 “姓名：fenghanzao 关键字：1057 查找长度为：1”输入“fuzongkai”输出 “姓名：fuzongkai 关键字：974 查找长度为：1”输入“hujingbin”输出 “姓名：hujingbin 关键字：958 查找长度为：1”输入“huangjianwu”输出 “姓名：huangjianwu 关键字：1185 查找长度为：1”输入“lailaifa”输出 “姓名：lailaifa 关键字：819 查找长度

19、为：1”输入“lijiahao”输出 “姓名：lijiahao 关键字：833 查找长度为：2”输入“liangxiaocong”输出 “姓名：liangxiaocong 关键字：1379 查找长度为：1”输入“linchunhua”输出 “姓名：linchunhua 关键字：1071 查找长度为：1”输入“liujianhui”输出 “姓名：liujianhui 关键字：1074 查找长度为：1”输入“luzhijian”输出 “姓名：luzhijian 关键字：974 查找长度为：2”输入“luonan”输出 “姓名：luonan 关键字：653 查找长度为：1”输入“quegaoxiang”输出 “姓名：quegaoxiang 关键字：1177 查找长度为：1”输入“sugan”输出 “姓名：sugan 关键字：542 查找长度为：1”输入“suzh