《数据结构课程设计哈希表设计》由会员分享，可在线阅读，更多相关《数据结构课程设计哈希表设计（23页珍藏版）》请在金锄头文库上搜索。
1、学 号： 课 程 设 计题 目哈希表设计学 院计算机科学与技术专 业计算机科学与技术班 级姓 名指导教师年月日目 录课程设计任务书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课
2、程设计任务书学生姓名： 专业班级： 班 指导教师： 工作单位： 计算机科学系 题 目: 哈希表设计 初始条件： 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。测试用例见题集p166。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容： 1、 问题描述简述题目要解决的问题是什么。2、 设计
3、存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；3、 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、 经验和体会（包括对算法改进的设想）5、 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，6、 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、第19周完成。2、7月1 日14：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日课程设计报告书1问题描述1.1问题描述针对某个集体（比如你所在
4、的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。1.2基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。1.3测试数据取自己班级成员的名字作为测试数据，建立一个相关哈希表，并计算平均查找长度，完成查询。2.实现分析（1） 针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序。（2） 人名为汉语拼音形式，最长不超过19个字符(如：庄双双 zhuangshuangshuang)。（3） 假设待填入哈希表的人名有30个，平
5、均查找长度的上限为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。（4） 如果随机函数自行构造，则应首先调整好随机函数，使其分布均匀。字符的取码方法可直接利用C语言中的toascii函数，并可对过长人名先进行折叠处理。（5） 查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度。3程序设计3.1存储结构设计根据哈希函数可唯一确定一个记录的地址，在理想情况下，记录就可以按照这个存储地址进行存储。因此哈希表的存储结构可以是链表和线性表，但一般情况下选择线性表进行存储。本次课程设计用到的存储结构如下：typedef struct char *name; /名字的拼音 int k
6、; /名字拼音所对应的关键字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()功能：主要完成初始化姓名列
7、表，并且将字符串的各个字符所对应的ASCII码相加，所得的整数作为哈希表的关键字。以便利用关键字和除留余数法得到每个姓名的哈希地址。void CreateHashList() 功能：构建一个哈希表并进行初始化；利用各个姓名的关键字得到哈希地址，将各个姓名按哈希地址进行存储，如果发生冲突，则利用伪随机探测再序列解决冲突，最终将姓名全部存放在哈希表中。void FindList() 功能：对用户输入的姓名进行查找；查找结果分两种情况：（1）查找成功，则输出姓名、关键字和查找长度；（2）查找失败，则返回相应的失败信息。查找时关键字的求法和处理冲突的方法与函数InitNameList()、Create
8、HashList()中的相关算法一致。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.na
9、me=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; Nam
10、eList13.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;
11、 NameList24.name=yijiabin; NameList25.name=xuhaiyang; NameList26.name=yangwenjuan; NameList27.name=chenjunyan； NameList28.name=wangjiaxin; NameList29.name=chenwan; for(i=0;iNAME_NO;i+) s0=0; f=NameListi.name; for(r=0;*(f+r)!=0;r+)/* 哈希地址方法：将字符串的各个字符所对应的ASCII码相加，所得的整数作为哈希表的关键字*/ s0=*(f+r)+s0; NameLis
12、ti.k=s0; （2） 建立哈希表 用除留余数法构建哈希函数 用伪随机探测再散列法处理冲突 构建哈希函数void CreateHashList()的实现：void CreateHashList() int i; for(i=0; iHASH_LENGTH;i+) HashListi.py=; HashListi.k=0; HashListi.si=0; for(i=0;iHASH_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;
