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

学 号： 课 程 设 计 题 目 哈希表设计 学 院 计算机科学与技术 专 业 计算机科学与技术 班 级 姓 名 指导教师 年 月 日 目 录 课程设计任务书 2 1．问题描述 3 1.1问题描述 3 1.2基本要求 3 1.3测试数据 3 2.实现分析 3 3．程序设计 4 3.1存储结构设计 4 3.2主要算法设计 4 3.2.1程序主要函数原型及功能 4 3.2.2各函数的实现 5 3.2.3函数模块 9 3.2.4程序流程图 9 4.调试报告 11 4.1调试中的问题 11 4.2对设计和编码的讨论和分析 11 5. 程序运行结果 11 6.经验和体会 13 6.1感受和体会 13 6.2对算法改进的想法 15 7.哈希表和源程序 15 7.1哈希表 15 7.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，哈希表