哈希表设计.doc

学号:
0121010340410
课程设计
题目
哈希表设计
学院
计算机科学与技术学院
专业
计算机科学与技术专业
班级
计科1004班
姓名
郭守飞
指导教师
施继珉
2012
年
6
月
21
日
课程设计任务书
学生姓名: 郭守飞专业班级: 1004 班
指导教师: 施继珉工作单位: 计算机科学系
题目: 哈希表设计
初始条件:
针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用伪随机探测再散列发处理冲突。
测试用例见题集p166。
要求完成的主要任务: (包括课程设计工作量及其技术要求,以及说明书撰写等具体要求)
课程设计报告按学校规定格式用A4纸打印(书写),并应包含如下内容:
1、问题描述
简述题目要解决的问题是什么。
2、设计
存储结构设计、主要算法设计(用类C语言或用框图描述)、测试用例设计;
3、调试报告
调试过程中遇到的问题是如何解决的;对设计和编码的讨论和分析。
4、经验和体会(包括对算法改进的设想)
5、附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据,则运行结果要包含这些测试数据和运行输出,
6、设计报告、程序不得相互抄袭和拷贝;若有雷同,则所有雷同者成绩均为0分。
时间安排:
1、第19周完成。
2、6月22 日14:00到计算中心检查程序、交课程设计报告、源程序(CD盘)。
指导教师签名: 年月日
系主任(或责任教师)签名: 年月日
问题描述
针对某一个个体(比如你所在的班级)中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有31个,,用伪随机探测再散列法处理冲突。
详细程序设计
#incudle <>
#include<>
#include<>
#define HASH_LEN 100
#define M 47
#define NAME_NO 31
typedef struct NAME
{
char *py; //名字的拼音
int k; //拼音所对应的整数
}NAME;
NAME NameList[HASH_LEN];
typedef struct hterm //哈希表
{
char *py; //名字的拼音
int k; //拼音所对应的整数
int si; //查找长度
}HASH;
HASH HashList[HASH_LEN];
void InitNameList()
{
NameList[0].py="kanzhenyu";
NameList[1].py="wangshiping";
NameList[2].py="zhaduo";
NameList[3].py="linweizhi";
NameList[4].py="tanghang";
NameL