哈希表的设计与实现
- 格式：doc
- 大小：136.50 KB
- 文档页数：14
课程设计任务书
学生姓名： 专业班级：
指导教师： 工作单位：
题 目: 哈希表的设计与实现
初始条件：
针对某个集体（比如你所在的班级）中的“人名”设计并实现一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。
（1）假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。
（2）哈希函数用除留余数法构造
（3）用伪随机探测再散列法处理冲突。
（4）测试用例见严蔚敏《数据结构习题集(C语言版)》p166。
要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：
1. 问题描述
简述题目要解决的问题是什么。
2. 设计
存储结构设计、主要算法设计（用类C/C++语言或用框图描述）、测试用例设计；
3. 调试报告
调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。
4. 经验和体会（包括对算法改进的设想）
5. 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。
说明：
1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。
2. 凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。
时间安排：
1、第19周完成。
2、6月30日下午-7月1日在实验中心检查程序、交课程设计报告、源程序（U盘）。
指导教师签名： 2011年6月22日 武汉理工大学《数据结构》课程设计
1 系主任（或责任教师）签名： 年 月 日
1问题描述
1.1问题描述
针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。
1.2基本要求
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。
2设计
2.1存储结构设计
typedef struct
{ char *py; //名字的拼音
int k; //拼音所对应的整数
}NAME;
typedef struct //哈希表
{ char *py; //名字的拼音
int k; //拼音所对应的整数
int si; //查找长度
}HASH;
2.2主要算法设计
2.2.1 姓名（结构体数组）初始化
名字以拼音的形式够成字符串，将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字。
void InitNameList()
{ char *f;
int r,s0,i;
NameList[0].py="zhouyulin";
NameList[1].py="chengjianfeng";
NameList[2].py="qinxudong"; 武汉理工大学《数据结构》课程设计
2 NameList[3].py="fangxin";
NameList[4].py="yangzongcheng";
NameList[5].py="tangxuewei";
NameList[6].py="sunjie";
NameList[7].py="chentao";
NameList[8].py="chendehui";
NameList[9].py="xubiao";
NameList[10].py="chenxiaokun";
NameList[11].py="xuyulin";
NameList[12].py="huwei";
NameList[13].py="yehanfan";
NameList[14].py="changzhen";
NameList[15].py="zhoupenghui";
NameList[16].py="liweipeng";
NameList[17].py="gengguangzhen";
NameList[18].py="weikaikai";
NameList[19].py="leiyutian";
NameList[20].py="wangwei";
NameList[21].py="liumingxi";
NameList[22].py="nvchunqiu";
NameList[23].py="congxiaofei";
NameList[24].py="weitaifei";
NameList[25].py="guijie";
NameList[26].py="huangliang";
NameList[27].py="mahuizhi";
NameList[28].py="huye";
NameList[29].py="shengxianqin";
for(i=0;i
{ s0=0;
f=NameList[i].py;
for(r=0;*(f+r)!='\0';r++) */将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字*/
s0=*(f+r)+s0;
NameL
ist[i].k=s0;
}
}
2.2.2 建立哈希表
（1） 用除留余数法构建哈希函数
（2） 用伪随机探测再散列法处理冲突
void CreateHashList() 武汉理工大学《数据结构》课程设计
3 { int i;
for(i=0; i
{ HashList[i].py="";
HashList[i].k=0;
HashList[i].si=0;
}
for(i=0;i
{ int sum=0;
int adr=(NameList[i].k)%M; //哈希函数
int d=adr;
if(HashList[adr].si==0) //如果不冲突
{ HashList[adr].k=NameList[i].k;
HashList[adr].py=NameList[i].py;
HashList[adr].si=1;
}
else //冲突
{ do
{ d=(d+NameList[i].k%10+1)%M; //伪随机探测再散列法处理冲突
sum=sum+1; //查找次数加1
}while (HashList[d].k!=0);
HashList[d].k=NameList[i].k;
HashList[d].py=NameList[i].py;
HashList[d].si=sum+1;
}
}
}
2.2.3查找哈希表
在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度
void FindList()
{ char name[20]={0};
int s0=0,r,sum=1,adr,d;
printf("请输入姓名的拼音:");
scanf("%s",name);
for(r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字)
s0+=name[r];
adr=s0%M; //使用哈希函数
d=adr;
if(HashList[adr].k==s0) //分3种情况进行判断
printf("\n姓名:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);
else if (HashList[adr].k==0) 武汉理工大学《数据结构》课程设计
4 printf("无此记录!");
else
{ int g=0;
do
{ d=(d+s0%10+1)%M; //伪随机探测再散列法处理冲突
sum=sum+1;
if(HashList[d].k==0)
{ printf("无此记录! ");
g=1;
}
if(HashList[d].k==s0)
{ printf("\n姓名:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum);
g=1;
}
}while(g==0);
}
}
2.2.4显示哈希表
显示哈希表的的格式：
\n地址\t关键字\t\t搜索长度\tH(key)\t 姓名\n
void Display()
{ int i;
float average=0;
printf("\n地址\t关键字\t\t搜索长度\tH(key)\t 姓名\n"); //显示的格式
for(i=0; i<50; i++)
{
if(HashList[i].py==NULL)
