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

《《数据结构》课程设计-哈希表设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、武汉理工大学《数据结构》课程设计说明书学号：课程设计题目哈希表设计学院计算机科学与技术专业计算机科学与技术班级姓名指导教师年月日22武汉理工大学《数据结构》课程设计说明书目录课程设计任务书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.程序运行结果

2、116.经验和体会136.1感受和体会136.2对算法改进的想法157.哈希表和源程序157.1哈希表157.2源程序16本科生课程设计成绩评定表2122武汉理工大学《数据结构》课程设计说明书课程设计任务书学生姓名：专业班级：班指导教师：工作单位：计算机科学系题目:哈希表设计初始条件：针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数

3、法构造，用伪随机探测再散列发处理冲突。测试用例见题集p166。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：1、问题描述简述题目要解决的问题是什么。2、设计存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；3、调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、经验和体会（包括对算法改进的设想）5、附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行

4、结果要包含这些测试数据和运行输出，6、设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、第19周完成。2、7月1日14：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。指导教师签名：年月日系主任（或责任教师）签名：年月日22武汉理工大学《数据结构》课程设计说明书课程设计报告书1．问题描述1.1问题描述针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。1.2基本要求假设人名为中国人姓名的汉语拼音形式。

5、待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。1.3测试数据取自己班级成员的名字作为测试数据，建立一个相关哈希表，并计算平均查找长度，完成查询。2.实现分析（1）针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序。（2）人名为汉语拼音形式，最长不超过19个字符(如：庄双双zhuangshuangshuang)。（3）假设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余数法构造，用伪随机

6、探测在散列法处理冲突。（4）如果随机函数自行构造，则应首先调整好随机函数，使其分布均匀。字符的取码方法可直接利用C语言中的toascii函数，并可对过长人名先进行折叠处理。（5）查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度。22武汉理工大学《数据结构》课程设计说明书3．程序设计3.1存储结构设计根据哈希函数可唯一确定一个记录的地址，在理想情况下，记录就可以按照这个存储地址进行存储。因此哈希表的存储结构可以是链表和线性表，但一般情况下选择线性表进行存储。本次课程设计用到的存储结构如下：

7、typedefstruct{char*name;//名字的拼音intk;//名字拼音所对应的关键字}NAME;//结构体NEMA，存放名字列表typedefstruct//哈希表{char*name;//名字的拼音intk;//名字拼音所对应的关键字intsi;//名字的查找长度}HASH;//结构体HASH，哈希表3.2主要算法设计3.2.1程序主要函数原型及功能[1]首先定义两个结构体数组：NAMENameList[HASH_LENGTH];//全局变量NAME，存储原始姓名HASHHashList

8、[HASH_LENGTH];//全局变量HASH，存储哈希表中的姓名[2]主要函数原型及功能：voidInitNameList()功能：主要完成初始化姓名列表，并且将字符串的各个字符所对应的ASCII码相加，所得的整数作为哈希表的关键字。以便利用关键字和除留余数法得到每个姓名的哈希地址。voidCreateHashList()功能：构建一个哈希表并进行初始化；利用各个姓名的关键字得到哈希地址，将各个姓名按哈希地址进行存储，如果发生冲突，则利