《数据结构》课程设计-哈希表设计.doc

武汉理工大学数据结构课程设计说明书学 号： 课 程 设 计题 目哈希表设计学 院计算机科学与技术专 业计算机科学与技术班 级姓 名指导教师年月日目 录课程设计任务书21问题描述31.1问题描述31.2基本要求31.3测试数据32.实现分析33程序设计43.1存储结构设计43.2主要算法设计43.2.1程序主要函数原型及功能43.2.2各函数的实现53.2.3函数模块93.2.4程序流程图94.调试报告114.1调试中的问题114.2对设计和编码的讨论和分析115. 程序运行结果116.经验和体会136.1感受和体会136.2对算法改进的想法157.哈希表和源程序157.1哈希表157.2源程序16本科生课程设计成绩评定表21课程设计任务书学生姓名： 专业班级： 班 指导教师： 工作单位： 计算机科学系 题 目: 哈希表设计 初始条件： 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。测试用例见题集p166。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容： 1、 问题描述简述题目要解决的问题是什么。2、 设计存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；3、 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、 经验和体会（包括对算法改进的设想）5、 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，6、 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、第19周完成。2、7月1 日14：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日课程设计报告书1问题描述1.1问题描述针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。1.2基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。1.3测试数据取自己班级成员的名字作为测试数据，建立一个相关哈希表，并计算平均查找长度，完成查询。2.实现分析（1） 针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序。（2） 人名为汉语拼音形式，最长不超过19个字符(如：庄双双 zhuangshuangshuang)。（3） 假设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。（4） 如果随机函数自行构造，则应首先调整好随机函数，使其分布均匀。字符的取码方法可直接利用C语言中的toascii函数，并可对过长人名先进行折叠处理。（5） 查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度。3程序设计3.1存储结构设计根据哈希函数可唯一确定一个记录的地址，在理想情况下，记录就可以按照这个存储地址进行存储。因此哈希表的存储结构可以是链表和线性表，但一般情况下选择线性表进行存储。本次课程设计用到的存储结构如下：typedef struct char *name; /名字的拼音 int k; /名字拼音所对应的关键字NAME; /结构体NEMA，存放名字列表 typedef struct /哈希表 char * name; /名字的拼音 int k; /名字拼音所对应的关键字 int si; /名字的查找长度HASH; /结构体HASH，哈希表3.2主要算法设计3.2.1程序主要函数原型及功能1 首先定义两个结构体数组：NAME NameListHASH_LENGTH; /全局变量NAME，存储原始姓名HASH HashListHASH_LENGTH; /全局变量HASH，存储哈希表中的姓名2 主要函数原型及功能：void InitNameList()功能：主要完成初始化姓名列表，并且将字符串的各个字符所对应的ASCII码相加，所得的整数作为哈希表的关键字。以便利用关键字和除留余数法得到每个姓名的哈希地址。void CreateHashList() 功能：构建一个哈希表并进行初始化；利用各个姓名的关键字得到哈希地址，将各个姓名按哈希地址进行存储，如果发生冲突，则利用伪随机探测再序列解决冲突，最终将姓名全部存放在哈希表中。void FindList() 功能：对用户输入的姓名进行查找；查找结果分两种情况：（1）查找成功，则输出姓名、关键字和查找长度；（2）查找失败，则返回相应的失败信息。查找时关键字的求法和处理冲突的方法与函数InitNameList()、CreateHashList()中的相关算法一致。void ShowHash() 功能：完成度已经建立好的哈希表进行输出显示，并输出平均查找长度。void main()功能：完成对个函数的调用和与用户的交互。3.2.2各函数的实现（1） 初始化姓名列表：Ø 哈希地址方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字key。Ø 函数void InitNameList()的实现（以班级30人的人名作为初始值）：void InitNameList() /姓名（结构体数组）初始化 char *f; int r,s0,i; NameList0.name="fanxu" NameList1.name="jiangyong" NameList2.name="guyuze" NameList3.name="liuzhenhai" NameList4.name="chenang" NameList5.name="caoyandong" NameList6.name="yangchenchen" NameList7.name="shenjin" NameList8.name="puping" NameList9.name="luhaibo" NameList10.name="renchao" NameList11.name="wangshichuang" NameList12.name="guoqihui" NameList13.name="chengkang" NameList14.name="wangyuesong" NameList15.name="liangfangping" NameList16.name="wangxufeng" NameList17.name="hejie" NameList18.name="yangyiming" NameList19.name="wushengping" NameList20.name="yangchaoqin" NameList21.name="wulinfeng" NameList22.name="xiehongwei" NameList23.name="liushuo" NameList24.name="yijiabin" NameList25.name="xuhaiyang" NameList26.name="yangwenjuan" NameList27.name="chenjunyan"； NameList28.name="wangjiaxin" NameList29.name="chenwan" for(i=0;i<NAME_NO;i+) s0=0; f=NameListi.name; for(r=0;*(f+r)!='0'r+)/* 哈希地址方法：将字符串的各个字符所对应的ASCII码相加，所得的整数作为哈希表的关键字*/ s0=*(f+r)+s0; NameListi.k=s0; （2） 建立哈希表 Ø 用除留余数法构建哈希函数Ø 用伪随机探测再散列法处理冲突Ø 构建哈希函数void CreateHashList()的实现：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; 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） 查找哈希表Ø 若查找成功，则输出姓名、关键字和查找长度；查找失败，则返回相应的失败信息。Ø 查找函数void FindList()的实现：void FindList() /查找 char name20=0; int s0=0,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 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 姓名nØ 显示哈希表的函数void Display()的：void Display() /显示 int i; float average=0; printf("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_LENGTH;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;case 'F':FindList();cout<<endl;break;case 'Q':exit(0);cout<<"come on !(y/n):"cin>>&ch1;while(ch1!='n'); 3.2.3函数模块模块调用关系主函数模块输出模块查找模块哈希表模块姓名初始化模块3.2.4 程序流程图本次程序流程图如下开始选择操作S、F、Q显示哈希表查找哈希表SFQ退出程序、继续Y退出NYN结束4.调试报告4.1调试中的问题经过对哈希表的研究后，即进行程序的设计和编码；将原程序编好后，经过编译，有如下几个问题：Ø 在声明了结构体NAME后，最开始结构体内的char name20用来存放姓名拼音，最长为20位；经分析，name表示所存姓名拼音的首地址，无需再申明具体的数组长度来存放姓名拼音，这样增加了系统的开销，最后改成char*name，对存放姓名拼音时直接对name赋值，系统直接按照字符数组来存放姓名拼音，而存放长度没有固定。Ø 建立哈希表的函数：void CreateHashList()中，如果遇到冲突后，在dowhile()；语句中，利用伪随机探测再散列法处理冲突，没执行一次就要将记录查找长度的sum增加一次，在这个循环执行完后，即找到一个不冲突的地址来存放姓名拼音，经过自习分析，此时的查找长度需要加1，即将原来的语句HashListd.si=sum; 改成HashListd.si=sum+1;此时的HashListd.si才是正确的查找长度。Ø main函数中的dowhile()语句中，最开始while()语句是：while(a!='N'|a!='n') 经过分析，在用户需要退出时，不论输入a=N还是a=n，都将继续循环；经过自习思考，最终将while()语句改成：while(a='Y'|a='y')，这样就实现了用户的选择。4.2对设计和编码的讨论和分析算法采用结构体和数组来存储数据，利用除留余数法得到哈希地址，利用为随机序列法来处理冲突，姓名拼音的关键字为字符串的各个字符所对应的ASCII码相加，所得的整数。求哈希地址时模为51，哈希表的总长度为50，而实际名字只有30个，因此有20个地址空间被空闲着，这浪费了一定的内存。算法的时间复杂度为：O(n)。平均查找长度为：1.566667装填因子为：30/50=0.65. 程序运行结果经过对程序错误的修改后，程序执行，经过分析，程序运行结果正确，满足题目要求！运行结果主要截图如下：Ø 程序开始后，初始界面为：Ø 选择S后结果为：结果显示，平均查找长度为1.566667，符合题设要求！Ø 选择Y继续后选择F查找查找成功结果为：查找失败结果为：6.经验和体会6.1感受和体会数据结构这门课程是计算机专业一门基础性学科，重要性可见一斑，学好这门课程对以后人生的发展具有深远的影响。而数据结构的课程设计便是对学习效果的检验。数据结构课程设计不仅可以锻炼我们独立思考问题、解决问题的能力，而且可以培养我们的整体性思维的能力；通过课程设计，使我了解了很多数据结构的经典问题和经典算法，加深了对数据结构的再认识，巩固了数据结构的基础性知识，比如：存储结构、数据查找、哈希表的设计和查找、算法分析等。哈希表是根据关键码值而直接进行访问的数据结构，它把关键码值通过哈希函数映射到表中一个地址来存储记录，以加快查找的速度。哈希函数的构造方法有：直接寻址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法等；对于地址冲突要进行解决，主要解决冲突的的方法有：开放寻址法（线性探测再散列、二次探测再散列、伪随机探测再散列）、再散列法、链地址法、建立一个公共溢出区等。查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：散列函数是否均匀、处理冲突的方法、散列表的装填因子。通过查找相关资料还了解了著名的hash算法：MD4、MD5、SHA-1 及其他。哈希表的主要用途为：文件校验、数字签名、鉴权协议等。这也是对于以后继续研究数据结构所必须了解的知识。这次课程设计，我明白了对于编写程序，解题的思路尤为重要。在编写程序之前，如果没有比较清晰的思路，根本不可能编出好的程序。就算马马虎虎的编出来，程序的逻辑性、健壮性、完善性、合理性也不会很强。在编程之前，我们应反复研究题目要求，对题目涉及的情况进行比较充分的分析，以便编写出更加符合题意的程序；其次要充分考虑各种临界情况，对一些错误的输入进行处理。因此在我们编程序之前一定要做好充分的准备，首先要理清自己的思路，然后再将思路分划成几个模块，逐块的写好算法，最后再将所有的模块有机的联系起来，组成一个完整的程序。在成功通过编译的情况下，对程序运行的结果进行系统的分析，检验其正确性，如果有错误，应立即去分析源程序的逻辑错误，直到得到正确的结果。在这次课程设计的过程中，我也遇到了很多难题。在种种的困难中，我明白了在编写程序时要有耐心。如果你没有耐心，即使再好的算法思路也不会得到很好的表达，特别是在调试的过程中，对于各种各样的错误，要特别的有耐心去自习分析原因，特别是一些基本的语法错误，不能一看到错误很多就乱了阵脚，更不能轻易的放弃，半途而废。比如在调试中没有定义某些变量的错误、基本的输入输出错误、数据选取不合理的错误、变量名前后不一的错误、函数返回值的错误等等。其实只要有耐心，你就会发现，在你修改了一个错误之后，其它有的错误也会跟着消失，所以在编译的时候一定要有耐心。数据结构是一门比较难的课程，需要花很多的时间去不断地练习和实践。要想把这门课程学好学精并非一件容易的事，特别是一些经典算法，是几十年前人智慧的结晶，对于初学者的理解和应用有一定的难度；但是事在人为，只要肯下功夫，便一定可以学好。总的来说，这次程序设计让我获益匪浅，相信在以后的学习生活中我也能从中获得启发。6.2对算法改进的想法本次哈希表的设计采用的存储结构为顺序存储，这样的存储结构简单易操作，但是必须实现给定存储大小，这样不利于动态操作，在题目允许的情况下，可以采用链式存储结构，从而实现动态存储；对关键字的选取还可以按照各个姓名的字母表的顺序等方式，哈希地址的除留余数法的模还可以是其他的接近表长的素数，解决冲突的伪随机序列取余的模长也可以是其他的接近表长的素数；本次哈希表的总长度为50，而实际只用到了30个，还余下20个空闲地址被白白浪费了，可以在满足题目要求的情况下适当的选取小一点的总表长。7.哈希表和源程序7.1哈希表经过分析，最后得到的哈希表如下：搜索长度地址存储内容关键字H(key)10(null)0011wangjiaxin1072112liuzhenhai1073243(null)0014chenjunyan1075415xuhaiyang974516wangshichuang1383617hejie517718guoqihui87580900110chenang72410111wangxufeng108211212wulinfeng9756113yangyiming1084130140001500116chengkang9341601700118guyuze6811801900220liushuo7771202100122renchao7362202300424yangwenjuan11911802500126luhaibo74026227chenwan74026328xiehongwei107980290003000131yijiabin847310320003300134wangyuesong120734135yangchenchen125935136fanxu54636137shenjin7513703800139caoyandong1059390400004100042000430004400245liangfangping136539346wushengping119926147puping65947148jiangyong96648249yangchaoqin1170487.2源程序整个程序的源代码为：#include<stdio.h>#include<iostream.h>#include<stdlib.h>#define HASH_LENGTH 50 /哈希表的长度 #define M 51 /随机数#define NAME_NO 30 /人名的个数 typedef struct char *name; /名字的拼音首地址 int k; /拼音所对应的关键字NAME;/结构体NEMA，存放名字列表NAME NameListHASH_LENGTH; /全局变量NAME typedef struct /哈希表 char *name; /名字的拼音首地址 int k; /拼音所对应的关键字 int si; /查找长度HASH;/结构体HASH，哈希表HASH HashListHASH_LENGTH; /全局变量HASH void InitNameList() /姓名（结构体数组）初始化 char *f; int r,s0,i; NameList0.name="fanxu" NameList1.name="jiangyong" NameList2.name="guyuze" NameList3.name="liuzhenhai" NameList4.name="chenang" NameList5.name="caoyandong" NameList6.name="yangchenchen" NameList7.name="shenjin" NameList8.name="puping" NameList9.name="luhaibo" NameList10.name="renchao" NameList11.name="wangshichuang" NameList12.name="guoqihui" NameList13.name="chengkang" NameList14.name="wangyuesong" NameList15.name="liangfangping" NameList16.name="wangxufeng" NameList17.name="hejie" NameList18.name="yangyiming" NameList19.name="wushengping" NameList20.name="yangchaoqin" NameList21.name="wulinfeng" NameList22.name="xiehongwei" NameList23.name="liushuo" NameList24.name="yijiabin" NameList25.name="xuhaiyang" NameList26.name="yangwenjuan" NameList27.name="chenjunyan" NameList28.name="wangjiaxin" NameList29.name="chenwan" for(i=0;i<NAME_NO;i+) s0=0; f=NameListi.name; for(r=0;*(f+r)!='0'r+)/* 哈希地址方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字*/ s0=*(f+r)+s0; NameListi.k=s0; void CreateHashList() /建立哈希表 int i; for(i=0; i<HASH_LENGTH;i+) /哈希表的初始化 HashListi.name="" 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; HashListadr.name=NameListi.name; 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.name=NameListi.name; HashListd.si=sum+1; void FindList() /查找 char name20=0; int s0=0,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.name,s0); else if (HashListadr.k=0) printf("无此记录!"); else int l=0; do d=(d+s0%10+1)%M; /伪随机探测再散列法处理冲突 sum=sum+1; if(HashListd.k=0) printf("无此记录! "); l=1; if(HashListd.k=s0) printf("n姓名:%s 关键字:%d 查找长度为:%d",HashListd.name,s0,sum); l=1; while(l=0); void ShowHash() / 显示哈希表 int i; float average=0; printf("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.name); printf("n"); for(i=0;i<HASH_LENGTH;i+) average+=HashListi.si; average/=NAME_NO; prin