哈希查找.doc

学期: 2010秋季学期
任课教师:
实验题目: 查找算法的设计与实现
小组长:
联系电话:
电子邮件:
一、【实验构思(Conceive)】(10%)
(本部分应包括:描述实验实现的基本思路,包括所用到的离散数学、工程数学、程序设计、算法等相关知识)
本次实验的主要目的在于帮助学生熟练掌握动态查找表的构造和查找方法。熟悉哈希表和哈希函数的构造方法,深刻理解哈希表与其他结构的表的实质性的差别。具体要求如下:对全年级中的“人名”设计一个哈希表,假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名数量>=30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用伪随机探测再散列法处理冲突,实现能够对全年级的学生进行按姓名的哈希查找。
基本思路:首先建立一个线性链表用于接收并存储用户输入的学生信息,然后将学生的姓名进行折叠处理,并将折叠处理后得到的数作为关键字用于哈希表的查找;以学生的姓名为关键字,建立相应的散列表,并用用除留余数法构造哈希函数;最后采用二次探测再散列法解决冲突,按照姓名的关键字进行哈希查找。
算法思想:在这个程序中主要用到线性链表和哈希表以及哈希函数的基本操作。首先定义声明一个线性链表,将用户输入的信息存储在该链表中。然后将学生的姓名进行折叠处理,先将姓名的小写字母转换成大写字母,然后将所有大写字母的ASCII码的值相加得到关键字的值;然后用除留余数法构造哈希函数,字符的取码法可直接利用C语言中的toascii函数,再以学生的姓名为关键字,求得哈希地址,将信息存入,建立相应的哈希表;最后按照姓名的关键字对哈希表进行查找,采用二次探测再散列法解决冲突,并在查找过程中记录查找冲突的次数,然后用子函数将相关结果显示出来。
二、【实验设计(Design)】(20%)
(本部分应包括:抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明,主程序模块与各子程序模块间的调用关系)
抽象数据类型:
//对输入的记录进行声明
typedef struct
{
NAME name;//输入的记录的姓名
}Record;

//对哈希表结构的声明
typedef struct
{
Record *elem[HASHSIZE]; //数据元素存储基址
int count; //当前数据元素个数
int size; //当前容量
}HashTable;
int main(int argc, char* argv[])//调用各子函数,完成哈希表的建立和查找功能
Status eq(NAME x,NAME y) //关键字比较函数,相等返回1;否则返回-1
void Input(Record* a)//输入函数,接收键盘输入的学生信息,并存储在线性链表中
void Display(Record* a) //显示函数,显示输入的学生信息
long Fold(NAME s)//人名折叠处理函数,先将姓名中的小写字母转换成大写字母,在依次把大写字母的ASCII码值相加得到关键字的值
int Hash(NAME str) //哈希函数,将姓名折叠处理后的数,用除留余数法构造哈希函数即m=n%HASHSIZE
Status Collision(int p,int &c) //冲突处理函数,采用二次探测再散列法解决冲突
void CreateHash(HashTable* H,Record* a) //建表函数,以学生的姓名为关键字,建立相应的哈希表,求得哈希地址,将学生的信息存入哈希表
void Search(HashTable* H,int &c) //查找函数,在哈希表里按照姓名关键字查找,若查找成功,显示信息,包括关键字的值;否则返回
函数调用关系:
三、【实现描述(Implement)】(30%)
(本部分应包括:抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系,关键的程序流程图等,给出关键算法的时间复杂度分析。)
函数设计:
//关键字比较函数,相等返回1;否则返回-1
Status eq(NAME x,NAME y)
{if(strcmp(x,y)==0)//调用函数strcmp比较x和y
return 1;
else
return -1;}
//输入函数,用键盘输入学生的信息
void Input(Record* a)
{ printf("\n输入要添加的学生人数: ");
scanf("%d",&NUM_BER);
int i;
for(i=0;i<NUM_BER;i++)
{printf("\n请输入第%d个学生的姓名:",i