学 号：
课 程 设 计
题 目 学 院 专 业 班 级 姓 名 指导教师
哈希表设计 计算机科学与技术 计算机科学与技术
年
月
日
目 录
1．问题描述..................................................................................................................................... 3
问题描述................................................................................................................................... 3 大体要求................................................................................................................................... 3 测试数据................................................................................................................................... 3 2.实现分析 ...................................................................................................................................... 3 3．程序设计..................................................................................................................................... 4
存储结构设计 ........................................................................................................................... 4
函数模块 ........................................................................................................................... 7 程序流程图 ....................................................................................................................... 7
4.调试报告 ...................................................................................................................................... 9
调试中的问题 ........................................................................................................................... 9 对设计和编码的讨论和分析 ................................................................................................... 9 5. 程序运行结果 ........................................................................................................................... 10 6.体会和体会................................................................................................................................. 11
感受和体会............................................................................................................................. 11 对算法改良的方式 ................................................................................................................. 13 7.哈希表和源程序 ......................................................................................................................... 13
哈希表 .................................................................................................................................... 13 源程序 .................................................................................................................................... 15
课程设计任务书
学生姓名： 专业班级： 班 指导教师： 工作单位： 运算机科学系 题 目: 哈希表设计 初始条件：
针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处置冲突。 测试用例见题集p166。
要求完成的要紧任务: （包括课程设计工作量及其技术要求，和说明书撰写等
具体要求）
课程设计报告按学校规定格式用A4纸打印（书写），并应包括如下内容： 一、 问题描述
简述题目要解决的问题是什么。 2、 设计
存储结构设计、要紧算法设计（用类C语言或用框图描述）、测试用例设计； 3、 调试报告
调试进程中碰到的问题是如何解决的；对设计和编码的讨论和分析。 4、 体会和体会（包括对算法改良的假想）
5、 附源程序清单和运行结果。源程序要加注释。若是题目规定了测试数据，那么运行结果要包括这些测试数据和运行输出，
6、 设计报告、程序不得彼此剽窃和拷贝；假设有类似，那么所有类似者成绩均为0分。
时刻安排：
一、第19周完成。
二、7月1 日14：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。
指导教师签名： 年 月 日
系主任（或责任教师）签名： 年 月 日
课程设计报告书
1．问题描述
问题描述
针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。
大体要求
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处置冲突。
测试数据
取自己班级成员的名字作为测试数据，成立一个相关哈希表，并计算平均查找长度，完成查询。
2.实现分析
（1） 针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的成立和查表程序。
（2） 人名为汉语拼音形式，最长不超过19个字符(如：庄双双 zhuangshuangshuang)。
（3） 假设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余数法构造，用伪随机探测在散列法处置冲突。
（4） 若是随机函数自行构造，那么应第一调整好随机函数，使其散布均匀。字符的取码方式可直接利用C语言中的toascii函数，并可对太长人名先进行折叠处置。
（5） 查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度。
3．程序设计
存储结构设计
依照哈希函数可唯一确信一个记录的地址，在理想情形下，记录就能够够依照那个存储地址进行存储。因此哈希表的存储结构能够是链表和线性表，但一样情形下选择线性表进行存储。本次课程设计用到的存储结构如下： typedef struct { char *name; ➢ ame=\"fanxu\"; NameList[1].name=\"jiangyong\"; NameList[2].name=\"guyuze\"; NameList[3].name=\"liuzhenhai\"; NameList[4].name=\"chenang\"; NameList[5].name=\"caoyandong\"; NameList[6].name=\"yangchenchen\"; NameList[7].name=\"shenjin\"; NameList[8].name=\"puping\"; NameList[9].name=\"luhaibo\"; NameList[10].name=\"renchao\"; NameList[11].name=\"wangshichuang\"; NameList[12].name=\"guoqihui\"; NameList[13].name=\"chengkang\"; NameList[14].name=\"wangyuesong\"; NameList[15].name=\"liangfangping\"; NameList[16].name=\"wangxufeng\"; NameList[17].name=\"hejie\"; NameList[18].name=\"yangyiming\"; NameList[19].name=\"wushengping\"; NameList[20].name=\"yangchaoqin\"; NameList[21].name=\"wulinfeng\"; NameList[22].name=\"xiehongwei\"; NameList[23].name=\"liushuo\"; NameList[24].name=\"yijiabin\"; NameList[25].name=\"xuhaiyang\"; NameList[26].name=\"yangwenjuan\"; NameList[27].name=\"chenjunyan\"； NameList[28].name=\"wangjiaxin\"; NameList[29].name=\"chenwan\"; for(i=0;i ➢ 构建哈希函数void CreateHashList()的实现： void CreateHashList() { int i; for(i=0; i 应的失败信息。 ➢ 查找函数void FindList()的实现： void FindList() ==s0) y,s0); else if (HashList[adr].k==0) printf(\"无此记录!\"); else { int g=0; do { d=(d+s0%10+1)%M; ==0) { printf(\"无此记录! \"); g=1; } if(HashList[d].k==s0) { printf(\"\\n姓名:%s 关键字:%d 查找长度为:%d\ g=1; } }while(g==0); } } （3）显示哈希表 ➢ 显示哈希表的的格式： \\n地址\关键字\\搜索长度\H(key)\ 姓名\\n ➢ 显示哈希表的函数void Display()的： void Display() ; printf(\"\\%d \ printf(\"\\%d \ printf(\"\ %s \ printf(\"\\n\"); } for(i=0;i 模块挪用关系 姓 名 初块 始化 模 主函数模块 哈希表模块查找模块输出模块 程序流程图 本次程序流程图如下 开始 选择操作 S、F、Q Q S 显 示 哈 希 表 F 查 找 哈 希 表 Y 继续Y 退出N N 退 出 程 序 结束 4.调试报告 调试中的问题 通过对哈希表的研究后，即进行程序的设计和编码；将原程序编好后，通过编译，有如下几个问题： ➢ 在声明了结构体NAME后，最开始结构体内的char name[20]用来寄存姓名 拼音，最长为20位；经分析，name表示所存姓名拼音的首地址，无需再申明具体的数组长度来寄存姓名拼音，如此增加了系统的开销，最后改成char*name，对寄存姓名拼音时直接对name赋值，系统直接依照字符数组来寄存姓名拼音，而寄存长度没有固定。 ➢ 成立哈希表的函数：void CreateHashList()中，若是碰到冲突后，在 do{}while()；语句中，利用伪随机探测再散列法处置冲突，没执行一次就要将记录查找长度的sum增加一次，在那个循环执行完后，即找到一个不冲突的地址来寄存姓名拼音，通过自习分析，现在的查找长度需要加1，即将原先的语句HashList[d].si=sum; 改成HashList[d].si=sum+1;现在的HashList[d].si才是正确的查找长度。 ➢ main函数中的do{}while()语句中，最开始while()语句是：while(a!='N'||a!='n') 通过度析，在用户需要退出时，不论输入a=N仍是a=n，都将继续循环；通过自习试探，最终将while()语句改成：while(a=='Y'||a=='y')，如此就实现了用户的选择。 对设计和编码的讨论和分析 算法采纳结构体和数组来存储数据，利用除留余数法取得哈希地址，利用为随机序列法来处置冲突，姓名拼音的关键字为字符串的各个字符所对应的ASCII码相加，所得的整数。求哈希地址时模为51，哈希表的总长度为50，而实际名字只有30个，因此有20个地址空间被空闲着，这浪费了必然的内存。 算法的时刻复杂度为：O(n)。 平均查找长度为： 装填因子为：30/50= 5. 程序运行结果 通过对程序错误的修改后，程序执行，通过度析，程序运行结果正确，知足题目要求！运行结果要紧截图如下： ➢ 程序开始后，初始界面为： ➢ 选择S后结果为： 结果显示，平均查找长度为，符合题设要求！ ➢ 选择Y继续后选择F查找 查找成功结果为： 查找失败结果为： 6.体会和体会 感受和体会 《数据结构》这门课程是运算机专业一门基础性学科，重要性可见一斑，学好这门课程对以后人一辈子的进展具有深远的阻碍。而数据结构的课程设计即是对学习成效的查验。数据结构课程设计不仅能够锻炼咱们独立试探问题、解决问题的能力，而且能够培育咱们的整体性思维的能力；通过课程设计，使我了解了很多数据结构的经典问题和经典算法，加深了对数据结构的再熟悉，巩固了数据 结构的基础性知识，比如：存储结构、数据查找、哈希表的设计和查找、算法分析等。 哈希表是依照关键码值而直接进行访问的数据结构，它把关键码值通过哈希函数映射到表中一个地址来存储记录，以加速查找的速度。哈希函数的构造方式有：直接寻址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法等；关于地址冲突要进行解决，要紧解决冲突的的方式有：开放寻址法（线性探测再散列、二次探测再散列、伪随机探测再散列）、再散列法、链地址法、成立一个公共溢出区等。查找进程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，阻碍产生冲突多少的因素，也确实是阻碍查找效率的因素。阻碍产生冲突多少有以下三个因素：散列函数是不是均匀、处置冲突的方式、散列表的装填因子。通过查找相关资料还了解了闻名的hash算法：MD4、MD五、SHA-1 及其他。哈希表的要紧用途为：文件校验、数字签名、鉴权协议等。这也是关于以后继续研究数据结构所必需了解的知识。 这次课程设计，我明白了关于编写程序，解题的思路尤其重要。在编写程序之前，若是没有比较清楚的思路，全然不可能编出好的程序。就算马马虎虎的编出来，程序的逻辑性、健壮性、完善性、合理性也可不能很强。在编程之前，咱们应反复研究题目要求，对题目涉及的情形进行比较充分的分析，以便编写出加倍符合题意的程序；第二要充分考虑各类临界情形，对一些错误的输入进行处置。因此在咱们编程序之前必然要做好充分的预备，第一要理清自己的思路，然后再将思路分划成几个模块，逐块的写好算法，最后再将所有的模块有机的联系起来，组成一个完整的程序。在成功通过编译的情形下，对程序运行的结果进行系统的分析，查验其正确性，若是有错误，应当即去分析源程序的逻辑错误，直到取得正确的结果。 在这次课程设计的进程中，我也碰到了很多难题。在各类的困难中，我明白了在编写程序时要有耐心。若是你没有耐心，即便再好的算法思路也可不能取得专门好的表达，专门是在调试的进程中，关于各类各样的错误，要专门的有耐心去自习分析缘故，专门是一些大体的语法错误，不能一看到错误很多就乱了阵脚，更不能轻易的舍弃，半途而废。比如在调试中没有概念某些变量的错误、大体的 输入输犯错误、数据选取不合理的错误、变量名前后不一的错误、函数返回值的错误等等。其实只要有耐心，你就会发觉，在你修改了一个错误以后，其它有的错误也会随着消失，因此在编译的时候必然要有耐心。 数据结构是一门比较难的课程，需要花很多的时刻去不断地练习和实践。要想把这门课程学勤学精并非一件容易的事，专门是一些经典算法，是几十年前人聪慧的结晶，关于初学者的明白得和应用有必然的难度；可是事在人为，只要肯下功夫，便必然能够学好。总的来讲，这次程序设计让我获益匪浅，相信在以后的学习生活中我也能从中取得启发。 对算法改良的方式 本次哈希表的设计采纳的存储结构为顺序存储，如此的存储结构简单易操作，可是必需实现给定存储大小，如此无益于动态操作，在题目许诺的情形下，能够采纳链式存储结构，从而实现动态存储；对关键字的选取还能够依照各个姓名的字母表的顺序等方式，哈希地址的除留余数法的模还能够是其他的接近表长的素数，解决冲突的伪随机序列取余的模长也能够是其他的接近表长的素数；本次哈希表的总长度为50，而实际只用到了30个，还余下20个空闲地址被白白浪费了，能够在知足题目要求的情形下适当的选取小一点的总表长。 7.哈希表和源程序 哈希表 通过度析，最后取得的哈希表如下： 搜索 长度 1 1 1 4 1 1 1 地址 0 1 2 3 4 5 6 关键字 (null) 0 wangjiaxin 1072 liuzhenhai 1073 (null) 0 chenjunyan 1075 xuhaiyang 974 wangshichuang 1383 存储内容 H(key) 0 1 2 0 4 5 6 1 1 0 1 1 2 1 7 8 9 10 11 12 13 hejie guoqihui chenang wangxufeng wulinfeng yangyiming 517 875 0 724 1082 975 1084 7 8 0 10 11 6 13 0 14 0 0 15 0 1 16 chengkang 934 0 17 0 1 18 guyuze 681 0 19 0 2 20 liushuo 777 0 21 0 1 22 renchao 736 0 23 0 4 24 yangwenjuan 1191 0 25 0 1 26 luhaibo 740 2 27 chenwan 740 3 28 xiehongwei 1079 0 29 0 0 30 0 1 31 yijiabin 847 0 32 0 0 33 0 1 34 wangyuesong 1207 1 35 yangchenchen 1259 1 36 fanxu 546 1 37 shenjin 751 0 38 0 1 39 caoyandong 1059 0 40 0 0 41 0 0 42 0 0 43 0 0 44 0 2 45 liangfangping 1365 3 46 wushengping 1199 1 47 puping 659 1 48 jiangyong 966 2 49 yangchaoqin 1170 0 0 16 0 18 0 12 0 22 0 18 0 26 26 8 0 0 31 0 0 34 35 36 37 0 39 0 0 0 0 0 39 26 47 48 48 源程序 整个程序的源代码为： #include<> #include<> #include<> #define HASH_LENGTH 50 ame=\"fanxu\"; NameList[1].name=\"jiangyong\"; NameList[2].name=\"guyuze\"; NameList[3].name=\"liuzhenhai\"; NameList[4].name=\"chenang\"; NameList[5].name=\"caoyandong\"; NameList[6].name=\"yangchenchen\"; NameList[7].name=\"shenjin\"; NameList[8].name=\"puping\"; NameList[9].name=\"luhaibo\"; NameList[10].name=\"renchao\"; NameList[11].name=\"wangshichuang\"; NameList[12].name=\"guoqihui\"; NameList[13].name=\"chengkang\"; NameList[14].name=\"wangyuesong\"; NameList[15].name=\"liangfangping\"; NameList[16].name=\"wangxufeng\"; NameList[17].name=\"hejie\"; NameList[18].name=\"yangyiming\"; NameList[19].name=\"wushengping\"; NameList[20].name=\"yangchaoqin\"; NameList[21].name=\"wulinfeng\"; NameList[22].name=\"xiehongwei\"; NameList[23].name=\"liushuo\"; NameList[24].name=\"yijiabin\"; NameList[25].name=\"xuhaiyang\"; NameList[26].name=\"yangwenjuan\"; NameList[27].name=\"chenjunyan\"; NameList[28].name=\"wangjiaxin\"; NameList[29].name=\"chenwan\"; for(i=0;i 参考文献： 《数据结构（C语言版）》，严蔚敏 吴伟民 编著，清华大学出版社，出版时刻： 《数据结构题集（C语言版）》，严蔚敏 吴伟民 米宁 编著，清华大学出版社，出版时刻： 本科生课程设计成绩评定表 班级：运算机班 姓名： 学号： 序号 1 2 3 4 5 6 评分项目 学习态度认真、遵守纪律 设计分析合理性 设计方案正确性、可行性、创造性 设计结果正确性 设计报告的规范性 设计验收 满分 10 10 20 40 10 10 总得分/等级 实得分 评语： 注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、 合格（60-69分）、60分以下为不合格 指导教师签名： 年月日 因篇幅问题不能全部显示，请点此查看更多更全内容