《数据结构课程设计之姓名哈希表的建立及查找》由会员分享，可在线阅读，更多相关《数据结构课程设计之姓名哈希表的建立及查找（12页珍藏版）》请在金锄头文库上搜索。
1、课程设计任务书学生姓名：刘颖 专业班级：计科1003班指导教师：谭新明 工作单位：计算机科学系 题 目: 哈希表的设计与实现初始条件： 针对某个集体比方你所在的班级中的“人名设计并实现一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 1假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。2哈希函数用除留余数法构造3用伪随机探测再散列法处理冲突。4测试用例见严蔚敏?数据结构习题集(C语言版)?p166。要求完成的主要任务: 包括课程设计工作量及其技术要求，以及说明书撰写等具体要求课程设计报告按学校规定格式用A4纸打印书写，并应包含如下内容：
2、1. 问题描述简述题目要解决的问题是什么。2.设计存储结构设计、主要算法设计用类C/C+语言或用框图描述、测试用例设计；3.调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4.经验和体会包括对算法改良的设想5.附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，那么运行结果要包含这些测试数据和运行输出。说明：1.设计报告、程序不得相互抄袭和拷贝；假设有雷同，那么所有雷同者成绩均为0分。2. 凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。时间安排：1、6月15日6月21日完成。2、6月22日上午和下午在实验中心检查程序、交课程设计报告、源程序U盘。指导
3、教师签名： 2021年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问题描述设计哈希表
4、，要求用除留余数法构造哈希函数，用伪随机探测再散列法处理冲突，使平均查找长度的上限为2。待填入哈希表的人名共有30个，且为中国人姓名的汉语拼音形式。1.2问题分析1待填入哈希表的人名有30个，平均查找长度的上限为2。用除留余数法构造哈希表，用伪随机探测再散列法处理冲突，完成相应的建立和查表程序。2人名为汉语拼音形式，最长不超过20个字符。3查找成功时，显示姓名、关键字、初散列值、再散列值、哈希表中的位置及查找长度；查找失败时，显示无此记录。4可屡次查找，继续查找输入1，退退出输入0。2开发平台系统：Windows 7开发工具：Visual studio 2021 语言：C+3数据类型和系统设计
5、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=haokai
6、qi; 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=jiangw
7、ei; 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=
8、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.reh
9、a=(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.rehatithi.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
