数据结构课程设计报告-哈希表设计.doc

数据结构课程设计报告
题目: 哈希表设计
院(系): 计算机工程学院
专业: 计算机科学与技术
班级: 嵌入式1091
学生:
指导教师:

2010年 12月
目录
一、设计目的 1
二、设计内容 1
三、程序设计步骤 2
四、调试分析 11
五、测试结果 11
六、课程设计小结 16
一、设计目的
1、学会根据实际问题建立哈希表,并实现其查找功能。
2、理解哈希表的思想就是以借点的关键字K为变量,通过一个确定的函数关系f,计算出对应的函数值f(k),把这个函数值解释为结点的存储地址,将该结点存入f(k)所指示的存储位置上,这样建立的表称为哈希表。
3、学会使用除留余数法获得哈希地址。
4、学会使用再地址方法解决哈希冲突问题。
5、学会查阅书籍,自我思考,解决实际问题。
二、设计内容
1、系统名称:哈希表设计
针对自己班集体中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。
2、要求:
(1)设计一个哈希表,用来存放30个人名。
(2)要求人名为中国姓名的汉语拼音形式。
(3)要求用除留余数法构造哈希函数,用线性探查法解决哈希冲突。
(4)本设计实现的功能:
①建立哈希表并且将其显示出来。
②通过要查找的关键字用哈希函数计算出相应的地址来查找人名。
三、程序设计步骤
1)查找功能分析说明:
本实验最关键的是实现哈希表的查找功能,因为元素的地址可能存在同义词,所以便会存在查找冲突,关键的就是解决这种冲突问题。哈希中解决冲突的方法有很多种,这里采用线性探查法解决冲突。通过构造函数d=(d+Hash(key))%p,若数据元素在存储地址d发生冲突,则放到存储地址(d1+k)%m;若又发生冲突则放到存储地址(d2+k)%m;若再发生冲突则放到存储地址(d3+k)%m;……;直到碰到第一个为空的存储地址(di+k)%m,则将数据元素存放在该存储空间。
查找的功能分析说明图如下:
开始
输入要查找的姓名
判断是否冲突
线性探查法
输出
否
是
是否冲突
否
是
2)代码分析:
#include <>
#define HASH_LEN 50 /* 哈希表长度*/
#define M 47 /* 定义P值*/
#define NAME_NO 30 /* 人名个数*/
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()
{ int i;
char *f;
int r,s0;
NameList[0].py="bianshan";
NameList[1].py="dengtao";
NameList[2].py="dingjun";
NameList[3].py="fanyongliang";
NameList[4].py="wangchen";
NameList[5].py="wangrong";
NameList[6].py="zhouyu";
NameList[7].py="liuyuanlong";
NameList[8].py="wuliang";
NameList[9].py="wulingjie";
NameList[10].py="wangzhaocai";
NameList[11].py="yujia";
NameList[12].py="zhangzhefu";
NameList[13].py="zhangnannan";
NameList[14].py="zhoujie";
NameList[15].py="yuanhunan";
NameList[16].py="lichunfeng";
NameList[17].py="lishiyan";
NameList[18].py="zhouxiaoqing";
NameList[19].py="liuwei";
NameList[20].py="niliquan";