哈希表的设计与实现.docx
- 文档编号:9336117
- 上传时间:2023-05-18
- 格式:DOCX
- 页数:19
- 大小:59.95KB
哈希表的设计与实现.docx
《哈希表的设计与实现.docx》由会员分享,可在线阅读,更多相关《哈希表的设计与实现.docx(19页珍藏版)》请在冰点文库上搜索。
哈希表的设计与实现
课程设计任务书
学生姓名:
专业班级:
指导教师:
工作单位:
题目:
哈希表的设计与实现
初始条件:
针对某个集体(比如你所在的班级)中的“人名”设计并实现一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。
(1)假设人名为中国人姓名的汉语拼音形式。
待填入哈希表的人名共有30个,取平均查找长度的上限为2。
(2)哈希函数用除留余数法构造
(3)用伪随机探测再散列法处理冲突。
(4)测试用例见严蔚敏《数据结构习题集(C语言版)》p166。
要求完成的主要任务:
(包括课程设计工作量及其技术要求,以及说明书撰写等具体要求)
课程设计报告按学校规定格式用A4纸打印(书写),并应包含如下内容:
1.问题描述
简述题目要解决的问题是什么。
2.设计
存储结构设计、主要算法设计(用类C/C++语言或用框图描述)、测试用例设计;
3.调试报告
调试过程中遇到的问题是如何解决的;对设计和编码的讨论和分析。
4.经验和体会(包括对算法改进的设想)
5.附源程序清单和运行结果。
源程序要加注释。
如果题目规定了测试数据,则运行结果要包含这些测试数据和运行输出。
说明:
1.设计报告、程序不得相互抄袭和拷贝;若有雷同,则所有雷同者成绩均为0分。
2.凡拷贝往年任务书或课程设计充数者,成绩一律无效,以0分记。
时间安排:
1、第19周完成。
2、6月30日下午-7月1日在实验中心检查程序、交课程设计报告、源程序(U盘)。
指导教师签名:
2011年6月22日
系主任(或责任教师)签名:
年月日
1问题描述
1.1问题描述
针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。
1.2基本要求
假设人名为中国人姓名的汉语拼音形式。
待填入哈希表的人名共有30个,取平均查找长度的上限为2。
哈希函数用除留余数法构造,用伪随机探测再散列发处理冲突。
2设计
2.1存储结构设计
typedefstruct
{char*py;//名字的拼音
intk;//拼音所对应的整数
}NAME;
typedefstruct//哈希表
{char*py;//名字的拼音
intk;//拼音所对应的整数
intsi;//查找长度
}HASH;
2.2主要算法设计
2.2.1姓名(结构体数组)初始化
名字以拼音的形式够成字符串,将字符串的各个字符所对应的ASCII码相加,所得的整数做为哈希表的关键字。
voidInitNameList()
{char*f;
intr,s0,i;
NameList[0].py="zhouyulin";
NameList[1].py="chengjianfeng";
NameList[2].py="qinxudong";
NameList[3].py="fangxin";
NameList[4].py="yangzongcheng";
NameList[5].py="tangxuewei";
NameList[6].py="sunjie";
NameList[7].py="chentao";
NameList[8].py="chendehui";
NameList[9].py="xubiao";
NameList[10].py="chenxiaokun";
NameList[11].py="xuyulin";
NameList[12].py="huwei";
NameList[13].py="yehanfan";
NameList[14].py="changzhen";
NameList[15].py="zhoupenghui";
NameList[16].py="liweipeng";
NameList[17].py="gengguangzhen";
NameList[18].py="weikaikai";
NameList[19].py="leiyutian";
NameList[20].py="wangwei";
NameList[21].py="liumingxi";
NameList[22].py="nvchunqiu";
NameList[23].py="congxiaofei";
NameList[24].py="weitaifei";
NameList[25].py="guijie";
NameList[26].py="huangliang";
NameList[27].py="mahuizhi";
NameList[28].py="huye";
NameList[29].py="shengxianqin";
for(i=0;i {s0=0; f=NameList[i].py; for(r=0;*(f+r)! ='\0';r++)*/将字符串的各个字符所对应的ASCII码相加,所得的整数做为哈希表的关键字*/ s0=*(f+r)+s0; NameL ist[i].k=s0; } } 2.2.2建立哈希表 (1)用除留余数法构建哈希函数 (2)用伪随机探测再散列法处理冲突 voidCreateHashList() {inti; for(i=0;i {HashList[i].py=""; HashList[i].k=0; HashList[i].si=0; } for(i=0;i {intsum=0; intadr=(NameList[i].k)%M;//哈希函数 intd=adr; if(HashList[adr].si==0)//如果不冲突 {HashList[adr].k=NameList[i].k; HashList[adr].py=NameList[i].py; HashList[adr].si=1; } else//冲突 {do {d=(d+NameList[i].k%10+1)%M;//伪随机探测再散列法处理冲突 sum=sum+1;//查找次数加1 }while(HashList[d].k! =0); HashList[d].k=NameList[i].k; HashList[d].py=NameList[i].py; HashList[d].si=sum+1; } } } 2.2.3查找哈希表 在哈希表中进行查找,输出查找的结果和关键字,并计算和输出查找成功的平均查找长度 voidFindList() {charname[20]={0}; ints0=0,r,sum=1,adr,d; printf("请输入姓名的拼音: "); scanf("%s",name); for(r=0;r<20;r++)//求出姓名的拼音所对应的整数(关键字) s0+=name[r]; adr=s0%M;//使用哈希函数 d=adr; if(HashList[adr].k==s0)//分3种情况进行判断 printf("\n姓名: %s关键字: %d查找长度为: 1",HashList[d].py,s0); elseif(HashList[adr].k==0) printf("无此记录! "); else {intg=0; do {d=(d+s0%10+1)%M;//伪随机探测再散列法处理冲突 sum=sum+1; if(HashList[d].k==0) {printf("无此记录! "); g=1; } if(HashList[d].k==s0) {printf("\n姓名: %s关键字: %d查找长度为: %d",HashList[d].py,s0,sum); g=1; } }while(g==0); } } 2.2.4显示哈希表 显示哈希表的的格式: \n地址\t关键字\t\t搜索长度\tH(key)\t姓名\n voidDisplay() {inti; floataverage=0; printf("\n地址\t关键字\t\t搜索长度\tH(key)\t姓名\n");//显示的格式 for(i=0;i<50;i++) { if(HashList[i].py==NULL) { HashList[i].k=0; HashList[i].py=""; HashList[i].si=0; } else printf("%d",i); printf("\t%d",HashList[i].k); printf("\t\t%d",HashList[i].si); printf("\t\t%d",HashList[i].k%M); printf("\t%s",HashList[i].py); printf("\n"); } for(i=0;i average+=HashList[i].si; average/=NAME_NO; printf("\n平均查找长度: ASL(%d)=%f\n",NAME_NO,average); } 2.2.5主函数设计 voidmain() {charch1; InitNameList(); CreateHashList(); do {printf("D.显示哈希表\nF.查找\nQ.退出\n请选择: "); cin>>&ch1; switch(ch1) { case'D': Display();cout< case'F': FindList();cout< case'Q': exit(0); } cout<<"comeon! (y/n): "; cin>>&ch1; }while(ch1! ='n'); } 2.3测试用例设计(见源程序清单) 3调试报告 3.1调试问题的处理 问题1: 调式过程经常遇到标点符号遗失,或者运用错误,造成了许多了麻烦。 分析: 通过出错信息,不断寻找错误点,并修正。 问题2: 运行结果出现错误,提示内存不足。 分析: 哈希表的长度设置太短,实用伪随机探测再散列法处理冲突并不难把数据完全填入表中。 通过修改哈希表长度即可。 问题3: 运行结果出现人名出现 分析: 通过重新修改程序,避免了此事件的发生。 3.2设计和编码的讨论和分析 本次课程设计采用的c++语言进行编写,运用了数组这种数据结构。 哈希表的设计与实现编码在书本上已有详细的介绍,我只是将各个部分的知识通过整理,面对实际问题作了变通。 其中对于伪随机探测再散列法处理冲突的编码在书本上并无详细的介绍,我则通过参考其他书籍方找到此种处理方法。 4经验和体会 数据结构作为计算机科学的基础学科,需要花很多的时间去练习和实践,才能为以后的编程打下坚实的基础。 要学好计算机编程,那必须学好数据结构,只要相信自己,只要肯下功夫就一定能学好。 经过这次课程设计的学习,让我明白了编写程序的思路是很重要的。 当有一个很复杂的设计在你面前时,你不能够慌张。 只要逐步分析,需要用到哪些知识,找到自己的思路。 在你编写一个程序之前,如果你的脑袋里面没有思路,根本就不可能编出好的程序。 就算能编出程序来,相信编出的程序的逻辑性也不会很强,因为你是想到什么就编什么,没有系统性。 因此在我们编程序之前一定要做好充分的准备,首先要理清自己的思路,然后再将思路分划成几个模块,一块一块的编写,最后再将所有的模块联系起来,组成一个完整的程序。 这样编写程序就不在是一个脑力活了,其实都是简单的模块组合而成。 在这次课程设计的过程中,我也遇到了很多困难。 在种种的困难中,我明白了耐心在编写程序时的重要性。 如果你没有耐心就肯定编不出好的程序,特别是在调试的过程中。 我们初次写的程序在电脑上调试的时候也许会出很多的错误,这时候我们应该耐心的检查出错的地方和原因,并予以改正。 而不是抱怨自己写的程序太烂错误太多,就此放弃。 相信再强的人也不可能一次就能编译成功,总会有一些问题出现。 其实只要有耐心,你就会发现,在你修改了一个错误之后,其它有的错误也会跟着消失,所以在编译的时候一定要有耐心。 总的来说,这次程序设计让我收获很多,锻炼了我的耐力和细心,增强我自己的实践能力。 在以后的日子里,我一定要保持这种孜孜不倦的精神,做好身边的每一件事。 5附源程序清单和运行结果 5.1源程序 #include #include #include #defineHASH_LENGTH50//哈希表的长度 #defineM47//随机数 #defineNAME_NO30//人名的个数 typedefstruct {char*py;//名字的拼音 intk;//拼音所对应的整数 }NAME; NAMENameList[HASH_LENGTH];//全局变量NAME typedefstruct//哈希表 {char*py;//名字的拼音 intk;//拼音所对应的整数 intsi;//查找长度 }HASH; HASHHashList[HASH_LENGTH];//全局变量HASH voidInitNameList()//姓名(结构体数组)初始化 {char*f; intr,s0,i; NameList[0].py="zhouyulin"; NameList[1].py="chengjianfeng"; NameList[2].py="qinxudong"; NameList[3].py="fangxin"; NameList[4].py="yangzongcheng"; NameList[5].py="tangxuewei"; NameList[6].py="sunjie"; NameList[7].py="chentao"; NameList[8].py="chendehui"; NameList[9].py="xubiao"; NameList[10].py="chenxiaokun"; NameList[11].py="xuyulin"; NameList[12].py="huwei"; NameList[13].py="yehanfan"; NameList[14].py="changzhen"; NameList[15].py="zhoupenghui"; NameList[16].py="liweipeng"; NameList[17].py="gengguangzhen"; NameList[18].py="weikaikai"; NameList[19].py="leiyutian"; NameList[20].py="wangwei"; NameList[21].py="liumingxi"; NameList[22].py="nvchunqiu"; NameList[23].py="congxiaofei"; NameList[24].py="weitaifei"; NameList[25].py="guijie"; NameList[26].py="huangliang"; NameList[27].py="mahuizhi"; NameList[28].py="huye"; NameList[29].py="shengxianqin"; for(i=0;i {s0=0; f=NameList[i].py; for(r=0;*(f+r)! ='\0';r++)/*方法: 将字符串的各个字符所对应的ASCII码相加,所得的整数做为哈希表的关键字*/ s0=*(f+r)+s0; NameList[i].k=s0; } } voidCreateHashList()//建立哈希表 {inti; for(i=0;i {HashList[i].py=""; HashList[i].k=0; HashList[i].si=0; } for(i=0;i {intsum=0; intadr=(NameList[i].k)%M;//哈希函数 intd=adr; if(HashList[adr].si==0)//如果不冲突 {HashList[adr].k=NameList[i].k; HashList[adr].py=NameList[i].py; HashList[adr].si=1; } else//冲突 {do {d=(d+NameList[i].k%10+1)%M;//伪随机探测再散列法处理冲突 sum=sum+1;//查找次数加1 } while(HashList[d].k! =0); HashList[d].k=NameList[i].k; HashList[d].py=NameList[i].py; HashList[d].si=sum+1; } } } voidFindList()//查找 {charname[20]={0}; ints0=0,r,sum=1,adr,d; printf("请输入姓名的拼音: "); scanf("%s",name); for(r=0;r<20;r++)//求出姓名的拼音所对应的整数(关键字) s0+=name[r]; adr=s0%M;//使用哈希函数 d=adr; if(HashList[adr].k==s0)//分3种情况进行判断 printf("\n姓名: %s关键字: %d查找长度为: 1",HashList[d].py,s0); elseif(HashList[adr].k==0) printf("无此记录! "); else {intg=0; do {d=(d+s0%10+1)%M;//伪随机探测再散列法处理冲突 sum=sum+1; if(HashList[d].k==0) {printf("无此记录! "); g=1; } if(HashList[d].k==s0) {printf("\n姓名: %s关键字: %d查找长度为: %d",HashList[d].py,s0,sum); g=1; } }while(g==0); } } voidDisplay()//显示哈希表 {inti; floataverage=0; printf("\n地址\t关键字\t\t搜索长度\tH(key)\t姓名\n");//显示的格式 for(i=0;i<50;i++) { if(HashList[i].py==NULL) { HashList[i].k=0; HashList[i].py=""; HashList[i].si=0; } else printf("%d",i); printf("\t%d",HashList[i].k); printf("\t\t%d",HashList[i].si); printf("\t\t%d",HashList[i].k%M); printf("\t%s",HashList[i].py); printf("\n"); } for(i=0;i average+=HashList[i].si; average/=NAME_NO; printf("\n平均查找长度: ASL(%d)=%f\n",NAME_NO,average); } voidmain() {charch1; InitNameList(); CreateHashList(); do {printf("d.显示哈希表\nf.查找\nq.退出\n请选择: "); cin>>&ch1; switch(ch1) { case'd': Display();cout< case'f': FindList();cout< case'q': exit(0); } cout<<"comeon! (y/n): "; cin>>&ch1; }while(ch1! ='n'); } 5.2运行结果 5.2.1程序运行后显示如下 5.2.2选择d查找,显示哈希表和平均查找长度,其中平均查找长度小于2,符合题目要求 5.2.3选择f查找,输入要查找的人的姓名,若存在则显示名字和对应的关键字以及查找长度;若不存在则显示无此记录 3.选择q退出,如要继续可按任意键
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈希表 设计 实现