哈希表的实例
一、课程设计的目的与要求
1. 目的: 应用数据结构和算法来设计相应的程序，培养学生问题求解模块的框架设计和详细设计、相关程序实现和调试能力，完成创新能力和实践能力的训练。
2. 要求: 用高级程序设计语言C编码，用VC++开发平台调试。 二、设计正文
（一）
课程设计题目
设计哈希表实现电话号码查询系统 （二）
需求分析
设每个记录有下列数据项：电话号码、用户名、地址；
(1)数据导入（从文件中读取各记录，分别以电话号码为关键字建立哈希表）；
(2)从键盘读记录，并插入到哈希表中；
(3)查找并显示给定电话号码的记录；
(4)将电话号码记录保存在文件中；
(5)尝试各种不同类型处理冲突的方法,考察平均查找长度的变化。 分析:由于题目要求以电话号码为关键字建表，考虑到电话号码长短不一，如果直接以表示电话号码的字符串为关键字，可能会造成一定的麻烦。故而，利用一个函数将表示电话号码的字符串转换成其相应的数字，然后把这些数字之和作为关键字即可将上述麻烦解除。
（三）
概要设计
为了实现上述程序的功能，需要定义下列抽象数据类型：
ADT hashtable {
数据对象：哈希表中存储的个条电话记录；
数据关系：表中相邻元素之间有前去和后继的关系；
基本操作：
init(Hashtable &h)
操作结果：初始化了哈希表；
int exchange(char str[])
操作结果：球取关键字；
int HashSearch1(Hashtable &h,char *str,int &p)
操作结果：在表中线性探测数据，返回数据的插入位置； int HashSearch2(Hashtable &h,char *str,int &p)
操作结果：在表中二次探测数据，返回数据的插入位置； void disp(Hashtable h)
操作结果：显示出哈希表中储存的电话记录； }ADT hashtable
将每个人的信息作为一条记录，包括电话号码、用户名、地址，还有一个整型变量用来记录冲突的次数，便于计算ASL,然后哈希表由记录数组、表现存量、容量组成,具体数据类型见下：
typedef struct {
char name[30];
char address[20];
char num[30];
}record;
typedef struct{
record data[Size];
int count;
int size; }Hashtable;
关键字处理-----利用一个函数将表示电话号码的字符串转换成其相应的数字，然后把这些数字之和作为关键字。具体函数见下：
int exchange(char str[])
{
int i,n,sum=0;
n=strlen(str);
for(i=0;i<n;i++)
sum=sum+str[i]-'0';
return sum;
}
最后就是用两种方法建表，分别用线性和二次探测的方法来处理冲突。
本程序所有函数清单：
void init(Hashtable &h)；//哈希表的初始化
int exchange(char str[])；//求取关键字
int HashSearch1(Hashtable &h,char *str,int &p)；//线性探测处理冲突
int HashSearch2(Hashtable &h,char *str,int &p)；//二次探测处理冲突
void disp(Hashtable h)；//显示哈希表
int menu()；//主菜单
void main()；//主函数 各函数之间的调用关系是：
主函数main（）
菜单函数menu（）
线性探测解决冲突hashserch1（）
查找用户
考察ASL1
二次探测解决冲突hashsearch2（）
查找用户
考察ASL
显示电话簿disp（）
（四）
详细设计
1）为了实现上述程序的功能，需要定义下述数据类型：
typedef struct{
char name[30];
char address[20];
//float num;
char num[30];
int c;//统计比较次数
}record; //记录
typedef struct{
record data[Size];
int count;
int size;
}Hashtable; //哈希表
2）一些主要的函数：
int exchange(char str[]) //关键字处理函数
{
int i,n,sum=0;
n=strlen(str);
for(i=0;i<n;i++)
sum=sum+str[i]-'0';
return sum;
}
int HashSearch1(Hashtable &h,char *str,int &p) //线性探测
{
int i,j,k=exchange(str);
j=k%Size;
if(strcmp(str,h.data[j].num)==0)
{
return j;
h.data[j].c++;//!
}//没有发生冲突，比较一次查找成功
if(h.data[j].num[0]==0)
{
p=j;
return 0;
}
else
{
h.data[j].c++;//!
i=(j+1)%Size;//第1次解决冲突
while(h.data[i].num[0]!=0&&i!=j)
{
if(strcmp(str,h.data[j].num)==0)
{
h.data[j].c++;//!
return i;
}//发生冲突，比较若干次查找成功
i=(i+1)%Size; //向后探测一个位置
}
if (i==j)
printf("溢出\n");
else
{
p=i;
h.data[j].c++;//!
return 0;//查找不成功
}
} }
int HashSearch2(Hashtable &h,char *str,int &p) //二次探测
{
int i,j,t=1,d=1;
int k=exchange(str);
j=k%Size;
if(strcmp(str,h.data[j].num)==0)
{
h.data[j].c++;//!
return j;
} //没有发生冲突，比较一次查找成功
if(h.data[j].num[0]==0)
{
p=j;
return 0;
}
else
{
i=(j+d)%Size;//第1次解决冲突
while(h.data[i].num[0]!=0&&i!=j)
{
if(strcmp(str,h.data[j].num)==0)
{
h.data[j].c++;//!
return i;
}
if(t>0)
t=-1*d*d;
else
{
d=d+1;
t=-1*d*d ;
}
i=(j+t+Size)%Size; //探测一个新的位置
while(i<0)
{
h.data[j].c++;//!
i=(i+Size)%Size;
}
if (i==j)
printf("溢出\n");
else
{
p=i;
h.data[j].c++;//!
return 0;//查找不成功时插入
}
}
}
} （五）
调试分析 本实验的运行环境是VC++。按照要求，应该事先导入一些记录，以下为本实验的测试数据：
4
侯进斌 北京 6627584
王璐 太原 6650370
唐磊 天津 6626074
高启波 太原 6651805
然后按照菜单中的提示操作即可
（六）
使用说明
程序名为hashtable.exe，运行环境为VC++。由于菜单中有详细的操作提示，您只要按照上面的提示一步一步进行操作即可。 （七）测试数据
程序运行后将会出现以下菜单：
选择1，立即会显示下面窗口，显示已存在的记录：
再选操作2，可以向电话簿1里添加记录，如下：
操作3，向电话簿2中添加记录，如下：
然后还可以进行查询操作，选4，可以在电话簿1中查询您想要的找的人的信息：
同理，选5还可以在电话簿2中作相应的查询：
如果您想比较着看一下在电话簿1中查找的速度（专业术语：ASL），可以选择操作6：
同理还可以查看电话簿2的这项功能：
如果您想结束操作，直接选0，即可退出该系统：
以上就是本系统的主要功能。 三、课程设计总结或结论
1．完成的工作
该实验的所有要求：哈希表的创建，用两种不同的方法处理冲突，考察各种处理冲突方法的ASL；
2．未完成的工作
无；
3．所需做的改进
应该尝试更多的处理冲突的方法
一些代码的效率很低，有待改进
四、参考文献
《数据结构》（C语言版）
清华大学出版社 严蔚敏 吴伟民 编著
