《数据库系统概论》第四版课后习题答案（完整版）.pdf

学号:
课程设计
题目
哈希表设计
学院
计算机科学与技术
专业
计算机科学与技术
班级
姓名
指导教师
年
月
日
目录
课程设计任务书 2
3
3
3
3
3
4
4
4
4
5
9
9
11
11
11
5. 程序运行结果 11
13
13
15
15
15
16
本科生课程设计成绩评定表 21
课程设计任务书
学生姓名: 专业班级: 班
指导教师: 工作单位: 计算机科学系
题目: 哈希表设计
初始条件:
针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用伪随机探测再散列发处理冲突。
测试用例见题集p166。
要求完成的主要任务: (包括课程设计工作量及其技术要求,以及说明书撰写等具体要求)
课程设计报告按学校规定格式用A4纸打印(书写),并应包含如下内容:
1、问题描述
简述题目要解决的问题是什么。
2、设计
存储结构设计、主要算法设计(用类C语言或用框图描述)、测试用例设计;
3、调试报告
调试过程中遇到的问题是如何解决的;对设计和编码的讨论和分析。
4、经验和体会(包括对算法改进的设想)
5、附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据,则运行结果要包含这些测试数据和运行输出,
6、设计报告、程序不得相互抄袭和拷贝;若有雷同,则所有雷同者成绩均为0分。
时间安排:
1、第19周完成。
2、7月1 日14:00到计算中心检查程序、交课程设计报告、源程序(CD盘)。
指导教师签名: 年月日
系主任(或责任教师)签名: 年月日
课程设计报告书


针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。

假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用伪随机探测再散列发处理冲突。

取自己班级成员的名字作为测试数据,建立一个相关哈希表,并计算平均查找长度,完成查询。

(1) 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序。
(2) 人名为汉语拼音形式,最长不超过19个字符(如:庄双双 zhuangshuangshuang)。
(3) 假设待填入哈希表的人名有30个,平均查找长度的上限为2。哈希表用除留余数法构造,用伪随机探测在散列法处理冲突。
(4) 如果随机函数自行构造,则应首先调整好随机函数,使其分布均匀。字符的取码方法可直接利用C语言中的toascii函数,并可对过长人名先进行折叠处理。
(5) 查找成功时,显示姓名及关键字,并计算和输出查找成功的平均查找长度。


根据哈希函数可唯一确定一个记录的地址,在理想情况下,记录就可以按照这个存储地址进行存储。因此哈希表的存储结构可以是链表和线性表,但一般情况下选择线性表进行存储。本次课程设计用到的存储结构如下:
typedef struct
{ char *name; //名字的拼音
int k; //名字拼音所对应的关键字
}NAME; //结构体NEMA,存放名字列表

typedef struct //哈希表
{ char * name; //名字的拼音
int k; //名字拼音所对应的关键字
int si; //名字的查找长度
}HASH; //结构体HASH,哈希表


首先定义两个结构体数组:
NAME NameList[HASH_LENGTH]; //全局变量NAME,存储原始姓名
HASH HashList[HASH_LENGTH]; //全局变量HASH,存储哈希表中的姓名
主要函数原型及功能:
void InitNameList()