数据结构优秀课程设计之姓名哈希表的建立及查找.doc

课程设计任务书学生姓名： 刘颖 专业班级： 计科1003班 指导老师： 谭新明 工作单位： 计算机科学系 题 目: 哈希表设计和实现初始条件： 针对某个集体（比如你所在班级）中“人名”设计并实现一个哈希表，使得平均查找长度不超出R，完成对应建表和查表程序。 （1）假设人名为中国人姓名汉语拼音形式。待填入哈希表人名共有30个，取平均查找长度上限为2。（2）哈希函数用除留余数法结构（3）用伪随机探测再散列法处理冲突。（4）测试用例见严蔚敏数据结构习题集(C语言版)p166。要求完成关键任务: （包含课程设计工作量及其技术要求，和说明书撰写等具体要求）课程设计汇报按学校要求格式用A4纸打印（书写），并应包含以下内容： 1. 问题描述简述题目要处理问题是什么。2. 设计存放结构设计、关键算法设计（用类C/C+语言或用框图描述）、测试用例设计；3. 调试汇报调试过程中碰到问题是怎样处理；对设计和编码讨论和分析。4. 经验和体会（包含对算法改善设想）5. 附源程序清单和运行结果。源程序要加注释。假如题目要求了测试数据，则运行结果要包含这些测试数据和运行输出。说明：1. 设计汇报、程序不得相互剽窃和拷贝；若有雷同，则全部雷同者成绩均为0分。2. 凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。时间安排：1、6月15日6月21日完成。2、6月22日早晨和下午在试验中心检验程序、交课程设计汇报、源程序（U盘）。指导老师署名： 6月14日系主任（或责任老师）署名： 年 月 日目录1问题分析和任务定义.31.1问题描述.31.2问题分析.32开发平台.33数据类型和系统设计.33.1存放结构设计.33.2关键算法设计.43.2.1姓名结构体数组初始化.43.2.2获取关键码.53.2.3哈希表结构体数组初始化.53.2.4结构哈希表.53.2.5打印哈希表.63.2.6在哈希表中查找姓名.64调试结果和运行情况分析.84.1程序运行结果.84.2运行情况分析.94.3算法时间复杂度.95自我评价和总结.96参考文件.107附：源代码.11哈希表设计和实现1问题分析和任务定义1.1问题描述 设计哈希表，要求用除留余数法结构哈希函数，用伪随机探测再散列法处理冲突，使平均查找长度上限为2。待填入哈希表人名共有30个，且为中国人姓名汉语拼音形式。1.2问题分析（1）待填入哈希表人名有30个，平均查找长度上限为2。用除留余数法结构哈希表，用伪随机探测再散列法处理冲突，完成对应建立和查表程序。（2）人名为汉语拼音形式，最长不超出20个字符。（3）查找成功时，显示姓名、关键字、初散列值、再散列值、哈希表中位置及查找长度；查找失败时，显示无此统计。（4）可数次查找，继续查找输入1，退退出输入0。2开发平台系统：Windows 7开发工具：Visual studio 语言：C+3数据类型和系统设计3.1 存放结构设计 typedef struct int key; char *p; NAME; typedef struct int key;/关键字 int hash;/初始地址 int reha;/再散列值 char *p;/名字 int l;/查找长度 HASH;3.2关键算法设计3.2.1 NAME（结构体数组）初始化 NAME a30; a0.p=wangjunzhe; a1.p=mahaiping; a2.p=luozijian; a3.p=luoxiangzhou; a4.p=zhangkai; a5.p=fengyuyang; a6.p=wuzhenzhen; a7.p=haokaiqi; a8.p=caopu; a9.p=liuying; a10.p=cuijuan; a11.p=hanqianqiqn; a12.p=lixiaoyu; a13.p=caoyingnan; a14.p=jinbaoyu; a15.p=zhaduo; a16.p=wenbo; a17.p=cuichangwei; a18.p=zhangqiu; a19.p=luopeng; a20.p=hudie; a21.p=xieshanshan; a22.p=liming; a23.p=zhangshuai; a24.p=qiuyajun; a25.p=yanruibin; a26.p=jiangwei; a27.p=fangzhaohua; a28.p=yujia; a29.p=liuzhenzhen;3.2.2获取关键码 字符串各个字符所对应ASCII码相加，所得整数做为关键字。 int i,s,r; for(i=0;i30;i+) s=0; for(r=0;*(ai.p+r)!=0;r+) s+=*(ai.p+r);ai.key=s; 3.2.3 HASH(结构体数组)初始化 HASH h40; for(i=0; i40;i+) hi.key=0; hi.hash=0; hi.reha=0; hi.p= ; hi.l=0;3.2.4结构哈希表 for(i=0;i30;i+) int sum=0; int hi=(ai.key)%37;/哈希函数int hj=(7*ai.key)%10+1;/再散列函数 if(hhi.l=0)/假如不冲突 hhi.key=ai.key; hhi.hash=(ai.key)%37; hhi.reha=(7*ai.key)%10+1; hhi.p=ai.p; hhi.l=1; else /冲突 int finh;/最终地址 do finh=(hi+hj)%40; /伪随机探测再散列法处理冲突 hi=finh; sum=sum+1; /查找次数加 while(hhi.l !=0); hhi.key=ai.key; hhi.hash=(ai.key)%37; hhi.reha=(7*ai.key)%10+1; hhi.p=ai.p; hhi.l=sum+1; 3.2.5打印哈希表 float average=0; cout关键码 初散列 再散列 哈希地址 查找次数 姓名endl;/格式 for(i=0; i40; i+) couthi.keythi.hashthi.rehati thi.lthi.pendl; for(i=0;i40;i+) average+=hi.l; average/=30; cout平均查找长度：ASL=averageendl; 3.2.6在哈希表中查找姓名 int m; do /m=1,继续查找；m=0,退出查找 char *f=new char20; int key=0,n=0,g,l=1,adr; cout请输入姓名拼音:f; for(g=0;*(f+g)!=0;g+) /求出姓名拼音所对应整数(关键字) n+=*(f+g);key=n; adr=key%37; /哈希函数求初散列值 if(hadr.key=key)/分3种情况进行判定 cout关键字:keyendl; cout初散列值为:hadr.hashendl; cout再散列值为:hadr.rehaendl; cout表中位置为:adrendl; cout查找长度为: lendl; else if (hadr.key=0) cout无此统计!endl; else int finh;/最终地址 int sign=0; do finh=(adr+7*key%10+1)%40; /再散列法处理冲突 adr=finh; l=l+1; /查找次数加 if(hadr.key=0) sign=1; cout无此统计!endl; if(hadr.key=key) sign=1; cout关键字:keyendl; cout初散列值为:hadr.hashendl; cout表中位置为:adrendl; cout查找长度为: lendl; while(sign=0); cout继续查询请输入,退出请输入：m;while(m=1);4调试结果和运行情况分析4.1程序运行结果4.2运行情况分析哈希表输出和预期相同且正确，并查找了liuying、jiangwei、huangxiao三个姓名，分别代表查找一次、数次后成功及查找不成功情况，且查找结果正确。4.3算法时间复杂度O(n)5自我评价和总结经过这次课程设计学习，让我明白了编写程序思绪是很关键，不仅检验了我所学习知识，也培养了我怎样去把握一件事情，怎样去做一件事情，又怎样完成一件事情方法和技巧。在编写一个程序之前，假如脑袋里面没有思绪，根本就不可能编出好程序。就算能编出程序来，相信编出程序逻辑性也不会很强，因为是想到什么就编什么，不系统。所以在我们编程序之前一定要做好充足准备，首先要理清自己思绪，然后再将思绪分划成多个模块，一块一块编写，最终再将全部模块联络起来，组成一个完整程序。在上机试验之前，最好将程序编写好在初稿纸上，这么在编译时候也比较有效率。课程设计是我们专业课程知识综合应用实践训练，着是我们迈向社会，从事职业工作前一个必不少过程“千里之行始于足下” ，经过这次课程设计，我深深体会到这句千古 名言真正含义。今天认真进行课程设计，学会脚扎实地迈开这一步，就是为明天能稳 健地在社会大潮中奔跑打下坚实基础。数据结构，是一门研究非数值计算程序设计问题中计算机操作对象（数据元素）和它们之间关系和运算等学科，而且确保经过这些运算后所得到新结构仍然是原来结构类型。这一门课内容不仅是通常程序设计基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序关键基础。经过这次哈希表设计，我在多方面全部有所提升。 在这次课程设计过程中，我也碰到了很多难题。在种种困难中，我明白了耐心在编写程序时关键性。假如你没有耐心就肯定编不出好程序，尤其是在调试过程中。我们首次写程序在电脑上调试时候可能会出项几百个错误，这时候我们应该耐心检验犯错地方和原因，并给予更正，而不是埋怨自己写程序太烂错误太多，就此放弃。相信再强人也不可能一次就能编译成功，总会有部分问题出现。其实只要有耐心，就会发觉，在修改了一个错误以后，其它有错误也会跟着消失，所以在编译时候一定要有耐心。经过这次课程设计，我认识到了自己动手实践弱势，尤其是在编程方面，知道了计算机实践操作是很关键，只有经过上机编程才能充足了解自己不足。而自己完成了这么课程设计，也是对自己实力检测，使我对以后学习也充满了信心和期待。这次课程设计，更是让我深刻认识到自己在学习中不足， 同时也找到了克服这些不足方法，这也是一笔很大资源。数据结构是一门比较难课程，需要花很多时间去练习和实践。要想把这门课程学好学精不是一件轻易事，不过相信事在人为，只要肯下功夫就一定能学好。总来说，这次程序设计让我获益匪浅，相信在以后学习生活中我也能从中取得启发。在以后时间中，我们应该利用更多时间去上机 试验，加强自学能力，多编写程序，相信很快后我们编程能力全部会有很大提升能设计 出更多更有创新作品。 我认为我设计优点在于只是用了简单面向过程编程，而没有用面向对象类设计。类在用于比较大程序设计时会显露较大优势，而在此反而会增加无须要麻烦。我设计缺点在于不是面向大众，即不能由用户在运行时输入姓名，只能经过在代码中修改达成效果。这个课题另一个方法是使用模板类，这么做能够使程序结构看起来更整齐简明，多种方法相关函数一览无余；在主函数中直接调用定义在模版类中函数，使读者能够很快明白主函数做了哪些工作，程序运行后会有哪些输入输出。6. 参考文件1.数据结构（用面向对象方法和C+语言描述）（第2版）清华大学出版社2.C+ Primer(汉字版)（第4版）人民邮电出版社7.附：源代码#include using namespace std;int main() typedef struct int key; char *p; NAME; NAME a30; a0.p=wangjunzhe; a1.p=mahaiping; a2.p=luozijian; a3.p=luoxiangzhou; a4.p=zhangkai; a5.p=fengyuyang; a6.p=wuzhenzhen; a7.p=haokaiqi; a8.p=caopu; a9.p=liuying; a10.p=cuijuan; a11.p=hanqianqiqn; a12.p=lixiaoyu; a13.p=caoyingnan; a14.p=jinbaoyu; a15.p=zhaduo; a16.p=wenbo; a17.p=cuichangwei; a18.p=zhangqiu; a19.p=luopeng; a20.p=hudie; a21.p=xieshanshan; a22.p=liming; a23.p=zhangshuai; a24.p=qiuyajun; a25.p=yanruibin; a26.p=jiangwei; a27.p=fangzhaohua; a28.p=yujia; a29.p=liuzhenzhen; int i,s,r; for(i=0;i30;i+) s=0; for(r=0;*(ai.p+r)!=0;r+) s+=*(ai.p+r);ai.key=s; typedef struct int key;/关键字 int hash;/初始地址 int reha;/再散列值 char *p;/名字 int l;/查找长度 HASH; HASH h40; for(i=0; i40;i+) hi.key=0; hi.hash=0; hi.reha=0; hi.p=; hi.l=0; for(i=0;i30;i+) int sum=0; int hi=(ai.key)%37;/哈希函数int hj=(7*ai.key)%10+1;/再散列函数 if(hhi.l=0) /假如不冲突 hhi.key=ai.key;hhi.hash=(ai.key)%37;hhi.reha=(7*ai.key)%10+1; hhi.p=ai.p; hhi.l=1; else /冲突 int finh;/最终地址 do finh=(hi+hj)%40; /伪随机探测再散列法处理冲突 hi=finh; sum=sum+1; /查找次数加 1 while(hhi.l !=0); hhi.key=ai.key; hhi.hash=(ai.key)%37; hhi.reha=(7*ai.key)%10+1; hhi.p=ai.p; hhi.l=sum+1; float average=0; cout关键码初散列再散列哈希地址查找次数姓名endl; /显示格式 for(i=0; i40; i+) couthi.keythi.hashthi.rehati thi.lthi.pendl; for(i=0;i40;i+) average+=hi.l; average/=30; cout平均查找长度：ASL=averageendl; int m; do char *f=new char20; int key=0,n=0,g,l=1,adr; cout请输入姓名拼音:f; for(g=0;*(f+g)!=0;g+) /求出姓名拼音所对应整数(关键字) n+=*(f+g);key=n; adr=key%37; /哈希函数求初散列值 if(hadr.key=key)/分3种情况进行判定 cout关键字:keyendl; cout初散列值为:hadr.hashendl; cout再散列值为:hadr.rehaendl; cout表中位置为:adrendl; cout查找长度为: lendl; else if(hadr.key=0) cout无此统计!endl; else int finh;/最终地址 int sign=0; do finh=(adr+7*key%10+1)%40; /再散列法处理冲突 adr=finh; l=l+1; /查找次数加 if(hadr.key=0) sign=1; cout无此统计!endl; if(hadr.key=key) sign=1; cout关键字:keyendl; cout初散列值为:hadr.hashendl; cout表中位置为:adrendl; cout查找长度为: lendl; while(sign=0); cout继续查询请输入,退出请输入：m; while(m=1); return 0;