《数据结构》课程设计说明书-hash表的建立和查找.doc

《数据结构》课程设计说明书-hash表的建立和查找.doc课程设计任务书
学生姓名: XXX 专业班级: 计算机0502
指导教师: XXX 工作单位:计算机科学与技术学院
题目: Hash表的建立和查找
初始条件:
理论:学习了《数据结构》课程,掌握了基本的数据结构和常用的算法;
实践:计算机技术系实验室提供计算机及软件开发环境。
要求完成的主要任务: (包括课程设计工作量及其技术要求,以及说明书撰写等具体要求)
1、系统应具备的功能:
(1)设计哈希函数和哈希表;
(2)设计解决冲突的方法;
(3)输入一组数据建立哈希表,并实现在哈希表中进行查找。
2、数据结构设计;
3、主要算法设计;
4、编程及上机实现;
5、撰写课程设计报告,包括:
(1)设计题目;
(2)摘要和关键字;
(3)正文,包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、结果分析、设计体会等;
(4)结束语;
(5)参考文献。
时间安排: 2007年7月2日-7日(第18周)
7月2日查阅资料
7月3日系统设计,数据结构设计,算法设计
7月4日-5日编程并上机调试
7月6日撰写报告
7月7日验收程序,提交设计报告书。
指导教师签名: 2007年7月2日
系主任(或责任教师)签名: 2007年7月2日
Hash表的建立和查找
摘要: 本人设计了一个Hash表的建立和查找系统,其主要功能是,用户可以手工输入Hash表元素个数和各个元素的数据内容,系统便相应地建立一个Hash表,(输入错误时,系统会显示输入错误,并提示重新输入);可对已建立的Hash表进行多次查找,系统打印查找到的信息,用户可以按提示信息退出系统。Hash表采用结构体数组进行存储,Hash函数由除留余数法建立,冲突的解决采用线性探测。
关键字: Hash表,结构体数组,除留余数法,线性探测

随着时代的进步,科技的发展,信息时代已经来临,在这样的时代背景之下,人们迫切需要对信息进行存储和查找,而数据结构成为了信息技术中极为重要的一门学科,发挥着关键作用。信息资料之多﹑之杂﹑之广,使如何存储和高效查找信息成为了一个很严肃的问题。本次课程设计中,我设计了一个小程序对用户输入的数据利用Hash表进行存储。存储完成后,用户可利用Hash表查找数据,速度十分快,可多次查找,也可按提示信息退出。

本次课程设计需要实现Hash表的建立和查找,具体内容如下:
Hash 表的建立
建立Hash函数,从而根据用户输入的数据元素个数和各元素的值建立Hash 表,即数据的添加和存储。如果输入的元素个数超出规定范围,则打印出错信息,并提示重新输入信息。
Hash 表的查找
Hash表建立好之后,用户可以输入想要查找的值,屏幕显示相应信息。如果存在此值,屏幕显示该值信息;如果不存在,则显示该值不存在;如果想退出系统,则按提示输入命令。


typedef struct
{
int key; //定义关键字
; //
}hashtable; //定义哈希表类型

hashtable ht[hm]; //定义哈希表空间

Hash函数
该函数利用除留余数法实现“Hash 函数”
#define m 19 //不大于表长的最大质数
Status h(keytype key){
//哈希函数
return(key%m); //除留余数法
}//h

这个函数能查找信息,它既能用于查找所输入信息,又能在建立Hash的时候被建立Hash表的函数调用。用户可以输入想要查找的值,屏幕显示相应信息。如果存在此值,屏幕显示该值信息;如果不存在,则显示该值不存在;如果想退出系统,则按提示输入命令。
Status HashSearch(hashtable ht[],keytype key){
//哈希表查找函数
int d,i;
i=0;
d=h(key); //求哈希地址
ht[d].cn=0; //记录元素被查找的次数
while((ht[d].key!=key)&&(ht[d].key!=free)&&(i<hm)){
//元素位置冲突时,进行线性探测
i++; //寻找下一个单元
ht[d].cn++; //寻找次数加1
d=(d+i)%m; //线性探测记录的插入位置
}
if(i>=hm){
//Hash表已满,插入失败,ess
printf("The hashtable is full!\n");
return(ess);
}
return(d); //若h