哈希表的设计与实现.doc

课程设计报告
课程名称数据结构
设计题目哈希表的设计与实现
专业计算机科学与技术
班级
学号
姓名
完成日期 2012年6月10日
课程设计任务书
设计题目: 哈希表的设计与实现
设计内容与要求:设计散列表实现电话号码查找系统。
1) 设每个记录有下列数据项:电话号码、用户名、地址;
2) 从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表;
3) 采用一定的方法解决冲突;
4) 查找并显示给定电话号码的记录;
5) 查找并显示给定用户名的记录。
指导教师:
2012年6月10日
课程设计评语
成绩:
指导教师:
2012年6月10日
问题描述
实现本程序需要解决以下几个问题:
如何设计一个结构体数组使该数组中每个元素包含电话号码、用户名、地址。
如何分别以电话号码和用户名为关键字建立哈希表。
如何利用线性探测再散列法解决冲突。
如何实现用哈希法查找并显示给定电话号码的记录。
如何查找并显示给定用户的记录。
基本要求
(哈希表的设计与实现的问题)设计哈希表实现电话号码查询系统。设计程序完成以下要求:(1)、设每个记录有下列数据项:电话号码、用户名、地址;(2)、从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表;(3)、采用再哈希法解决冲突(4)、查找并显示给定电话号码的记录;(5)、查找并显示给定用户的记录。要完成以上要求,设计哈希表实现电话号码查询系统。
数据结构
本设计涉及到的数据结构为:哈希表。要求输入电话号码、用户名、地址三个信息,并要求分别以电话号码和用户名为关键字进行查找,所以本问题要用到两个哈希函数,进行哈希查找。
typedef struct
{
char name[20];//名字
char num[20];//电话号码
char add[30];//地址
}Record;
Record Inf[M];//辅助数组
Record H[M];//哈希表
总体设计
主要算法的流程图如下:
1、创建辅助数组流程图:
开始
初始化哈希表
往辅助数组输入元素
N结束
Y结束并返回数组元素总数
选择Y/N

2、以姓名为关键字的哈希函数流程图:
开始
取整形数据0赋给a
i从0开始取
num[i]!=’\0’
a=a+(int)(name[i])
a=a%29
结束
i++
3、以姓名为关键字创建哈希表流程图:
开始
j从0开始
else
key++
计算以姓名为关键字的哈希地址key
if(strcmp(H[key].name,NULLKEY)==0)
将辅助数组中的元素存入哈希表
结束
4、以电话号码为关键字的哈希函数流程图:
开始
取整形数据0赋给b
i从0开始取
num[i]!=’\0’
i++
b=b+(int)(name[i])
b=b%29
结束
5、以电话号码为关键字创建哈希表流程图:
开始
j从0开始
计算以电话号码为关键字的哈希地址key
if(strcmp(H[key].num,NULLKEY)==0)
将辅助数组中的元素存入哈希表
else
key++
结束
6、以姓名为关键字的哈希表按姓名查找函数流程图:
查找名字不存在
return(key);
结束
开始
调用Hash_name
while(strcmp(H[key].name,name)!=0)
key++
if(strcmp(H[key].name,NULLKEY)==0)
7、以电话号码为关键字的哈希表按号码查找函数流程图:
查找号码不存在
return(key);
结束
开始
调用Hash_num
while(strcmp(H[key].num,num)!=0)
key++
if(strcmp(H[key].num,NULLKEY)==0)
8、以姓名为关键字的哈希表按姓名插入函数流程图:
开始
调用Hash_name
if(strcmp(H[key].name,NULLKEY)==0)
else key++
while(1)
将数据以姓名为关键字插入哈希表
结束

9、以号码为关键字的哈希表按号码插入函数流程图:
开始
调用Hash_num
if(strcmp(H[key].num,NULLKEY)==0)
else key++
while(1)
将数据以号码为关键字插入哈希表
结束
10、以姓名为关键字的哈希表按姓名删除函数流程图:
开始
调用Hash_name,计算下标key,记录key为i
if(strcmp(H[ke