学士学位论文--哈希表的设计与实现.doc

哈希表的设计与实现
哈希表的设计与实现

摘 要
哈希表的设计与实现是用Visual C++ 6.0编写的能够实现数据的存储，更新与查找的程序。它可以方便的进行基本数据信息的输入（如:姓名、电话、地址等），查询（按姓名查询.按电话号查询），删除（运用姓名删除），添加新的数据等。易于管理员进行管理。本设计使用Visual C++ 6.0开发工具利用其提供的各种面向对象的开发工具将数据信息定义在结构体中，运用类实现了对数据不同信息的操作功能。

关键字：哈希表; Visual C++ 6.0; 地址

1

目 录
1、题目分析 3
2、设计思路 3
2.1问题描述 3
2.2基本要求 3
2.3数据结构 3
3、设计思路 4
4、测试的实验结果和测试过程 11
4.1详细设计 11
4.2屏幕截图 11
4.3问题分析： 13
5、课程设计体会及问题分析 13
6、参考文献 14
7、源程序清单 14

1、 题目分析
在21世纪信息时代里，各个机构企业都需要处理一些庞大的重要的数据，而这些数据既需要随时查找还需要随时纪录新的数据。这工作量无疑是巨大，如果用人力去完成，不仅效率底`，易出错，而且其他各个方面都受到一定的限制，如时间资源等。针对这种情况，应用哈希表来规范化管理这些数据是一个既明知又科学选折。它不但能有效的准确的存储大量数据，还可以根据需要不断的更新与插入新的数据。
2、设计思路
2.1问题描述
实现本程序需要解决以下几个问题：
（1） 如何设计一个结构体数组使该数组中每个元素包含电话号码、用户名、地址。
（2） 如何分别以电话号码和用户名为关键字建立哈希表。
（3） 如何利用线性探测再散列法解决冲突。
（4） 如何实现用哈希法查找并显示给定电话号码的记录。
（5） 如何查找并显示给定用户的记录。
2.2基本要求
（哈希表的设计与实现的问题）设计哈希表实现电话号码查询系统。设计程序完成以下要求：（1）、设每个记录有下列数据项：电话号码用户名、地址；（2）、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；（3）、采用再哈希法解决冲突（4）、查找并显示给定电话号码的记录；（5）、查找并显示给定用户的记录。要完成以上要求，设计哈希表实现电话号码查询系统。

2.3数据结构
本设计涉及到的数据结构为：哈希表。要求输入电话号码、用户名、地址三个信息，并要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个哈希函数，进行哈希查找。
typedef struct
{
char name[20];//名字
char num[20];//电话号码
char add[30];//地址
}Record;
Record Inf[M];//辅助数组
Record H[M];//哈希表

3、设计思路
主要算法的流程图如下：
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[key].name,name)==0)
while(1)
key++
在以姓名为关键字的哈希表中删除数据，标志位赋1
结束
while(key<30)
key++
将存放在后面的下标为i的元素依次向前移动

11、主函数调用函数流程图：

开始
选择1调用Create创建辅助数组
选择2以姓名为关键字创建哈希表input_name
选择3以号码为关键字创建哈希表input_num

选择0退出

选择0退出
选择0退出

选择1查找，调用Search_name函数
选择2插入，调用Insert_name函数
选择3删除，调用Del_name函数
选择1查找，调用Search_num函数

选择2插入，调用Insert_num函数

选择3删除，调用Del_num函数

4、测试的实验结果和测试过程
4.1详细设计
首先定义结构体类型，在线性探测法中，每个结构体元素对应一个数组位置，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该数组的元素它由三个域组成：

name[20]
num[20]
address[30]

其中name[20]和num[20]是分别为以电话号码和用户名为关键字域（key），存放关键字；address[30]为元素的数据域(data)，用来存储用户的地址信息。

42屏幕截图
主界面如图

图1
1、给出一组测试数据及运行结果如下：
输入数据后按姓名散列结果如下：

图2

每个元素的哈希地址正是用名字中每个字母的ASCII码值相加再对小于哈希表长的最大素数求余得到的，根据输入数据计算和书上ASCII值计算出结果相比对，数据正确，刚开始老师检查时，觉得我的程序缺少输出哈希地址的步骤，回来后我又加以改进，把哈希地址正常输出。

图3

输入数据后按号码散列结果如下：
每个元素的哈希地址正是用号码中每个字符的ASCII码值相加再对小于哈希表长的最大素数求余得到的，根据输入数据计算和书上ASCII值计算出结果相比对，数据正确。
4.3问题分析：
刚开始调试时运行删除功能时，发现删除元素后，哈希地址也在该位置而却往后移动的元素不能回到该位置，然后我又分析算法，进行改进，现在算法可以在删除元素后将哈希地址在该位置的而又移到后面的元素依次向前移动。

5、课程设计体会及问题分析
课程设计的过程是艰辛的,但是收获确实另人欣喜的,这次课程设计我主要是应用我们以前学习的C语言及C++中的知识来完成的,虽然这个程序功能还很不完善,但自己从中却学到了很多东西.首先，综合课程设计让我把以前学习到的知识得到巩固和进一步的提高认识，对已有知识有了更进一步的理解和认识，再次，我在课程设计中碰到了很多的问题，我通过查阅相关书籍，资料，通过自己钻研，特别是得到了老师的谆谆教导，老师给予了我很大的帮助，不仅给了我思路上的开阔，还让我认识到了自己对以前所学知识的不足方面。
首先,综合课程设计让我把以前学习的知识得到了加深与巩固,对自己学习的知识有了一次全面的认识,也给自己指明了以后复习的重点与方向,再次,在程序设计中遇到的一些问题,我通过查阅资料,请教老师与同学,提高了自己解决问题的能力。但由于还有很多问题无法解决，导致很多功能不能实现，未能达到预期的目的。
随着社会的不断发展,计算机在各领域也得到广泛的应用，同时对软件的要求也越来越高，只有不断的利用新的知识来更新程序，才能满足社会的需求。
但是，对于一个初学者来说，要想编译一个完美的程序是十分困难的。本程序就有许多的不足，以及编译时出现的困难。列如：
（1）在准备资料时，选取及设计适合的哈希函数，成首要难题，也是整个程序关键。因为在设计哈希函数时，要做到最大的减少冲突，确定在记录的储存位置和他个关键字之间建立一个取得对应关系，使没关键字和结构中的一个惟一的储存位置相对应，这是以个比较复杂的过程。
（2）冲突是使用哈希表不可避免的问题。对不同的关键字却可能得到同一哈希地址，并且在一般情况下，冲突只能尽可能避免而不能完全避免。因此，在建造哈希表时不仅要设定以个好的哈希函数，而且要设定一种处理冲突的方法。在泵系统的开发过程中，主要采用了开放地址法中的二次探测法。
通过这次课程设计,我发现了自身的很多不足,在以后的学习中,我会不断完善自我.不断进取,使自己在编程这方面的能力得到更进一步的提高.
6、参考文献
[1] 谭浩强.C程序设计（第三版）.北京：清华大学出版社.2005
[2] 刘斌.王忠.面向对象程序设计 Visual C++.北京：清华大学出版社.2003
[3] 严蔚敏.吴伟民.数据结构（C语言版）.北京：清华大学出版社.2007
[4] 谭浩强编著.C++程序设计.北京：清华大学出版社，2004.
[5] [美]S巴斯计算机算法：设计和分析引论.朱洪等译.上海：复旦大学出版社.1985.
[6] Huddard J R.Prohramming with C++(英文版，第二版).北京：机械工业出版社.2002.8
[7] 陈华生.CV++程序设计基础.江苏：苏州大学出版社.2002

7、源程序清单
************************程序源代码*************************
#include
#include
#include
#define M 30
#define NULLKEY "\0"

typedef struct
{
char name[20];
char num[20];
char add[30];
}Record;
Record Inf[M];//定义辅助数组为全局变量
Record H[M];//定义哈希表为全局变量
int menu_select() /*菜单函数*/
{
int c;
do{
system("cls"); /*运行前清屏*/
printf(" **************************\n");
printf(" ***** 哈希表 *****\n");
printf(" * 1. 创建哈希表 *\n");
printf(" * 2. 按姓名散列 *\n");
printf(" * 3. 按号码散列 *\n");
printf(" 0. 结束程序 *\n");
printf(" **************************\n");
printf("请选择您要运行的选项按(0-3):");
scanf("%d",&c); /*读入选择*/
getchar();
}while(c<0||c>3);
return(c); /*返回选择*/
}
int Create(Record H[M])//创建辅助数组
{
int i;
for(i=0;i<30;i++)//初始化哈希表
{
strcpy( H[i].add,"\0");
strcpy( H[i].num,"\0");
strcpy( H[i].name,"\0");
}
i=0;
char sign;
while(sign!='n'&&sign!='N')
{
printf("请输入名字\n");
scanf("%s",Inf[i].name);
printf("请输入号码\n");
scanf("%s",Inf[i].num);
printf("请输入地址\n");
scanf("%s",Inf[i].add);
printf("\t\t\t还需要继续输入吗?(Y/N)");
scanf("\t\t\t%c",&sign); /*输入判断*/
i++;
}
return i;
}

int Hash_name(char name[20])//以姓名为关键字的哈希函数
{
int i=0;
int a=0;
while(name[i]!='\0')//计算姓名中每个字符的ASCII码值相加
{
a=a+name[i];
i++;
}
a=a%29;//对小于哈希表的最大素数求余，此处哈希表长为30，对29求余
return(a);
}

void input_name(Record Inf[M],int m,Record H[M])//以姓名为关键字创建哈希表
{
int j,key=0;
for(j=0;jEY)==0)//判断该位置是否为空，不为空就把辅助数组中的元素存到该位置
{
strcpy(H[key].name,Inf[j].name);
strcpy(H[key].num,Inf[j].num);
strcpy(H[key].add,Inf[j].add);
break;
}
else
key++;//如果为空，采用线性探测法，将元素后移
}
}
}
int Hash_num(char num[20])//以姓名为关键字的哈希函数
{
int i=0;
int b=0;
while(num[i]!='\0')//计算电话号码中每个字符的ASCII码值相加
{
b=b+num[i];
i++;
}
b=b%29;//对小于哈希表的最大素数求余，此处哈希表长为30，对29求余
return(b);
}
void input_num(Record Inf[M],int m,Record H[M])//以电话号码为关键字创建哈希表
{
int j,key=0;
for(j=0;j while(1)
{
if(strcmp(H[key].num,NULLKEY)==0)//判断该位置是否为空，不为空就把辅助数组中的元素存到该位置
{
strcpy(H[key].name,Inf[j].name);
strcpy(H[key].num,Inf[j].num);
strcpy(H[key].add,Inf[j].add);
break;
}
else
key++;//如果为空，采用线性探测法，将元素后移
}
}
}
int Search_name(Record H[],char name[20])//以姓名为关键字的哈希表的查找函数
{
int key=0;
key=Hash_name(name);//计算哈希地址
while(strcmp(H[key].name,name)!=0)//如果元素不在该位置，将元素后移再判断
{
key++;
if(strcmp(H[key].name,NULLKEY)==0)//遇到空格表示该元素不存在
{
printf("查找名字不存在!\n");
return(-1);
break;
}
}
return(key);//返回查找到的哈希地址
}
int Search_num(Record H[],char num[20])//以电话号码为关键字的哈希表的查找函数
{
int key=0;
key=Hash_num(num);//计算哈希地址
while(strcmp(num,H[key].num)!=0)//如果元素不在该位置，将元素后移再判断
{
key++;
if(strcmp(H[key].num,NULLKEY)==0)//遇到空格表示该元素不存在
{
printf("查找号码不存在\n");
return(-1);
break;
}
}
return(key);//返回查找到的哈希地址
}

void Insert_name(Record H[M],char name[20],char num[20],char add[30])//以姓名为关键字哈希表的插入函数
{
int key;
key=Hash_name(name);//计算哈希地址
while(1)
{
if(strcmp(H[key].name,NULLKEY)==0)//如果该位置为空，把元素存到该位置
{
strcpy(H[key].name,name);
strcpy(H[key].num,num);
strcpy(H[key].add,add);
break;
}
else
key++;//如果该位置不为空，向后移插入元素
}
}
void Insert_num(Record H[M],char name[20],char num[20],char add[30])//以电话号码为关键字的哈希表插入函数
{
int key;
key=Hash_num(num);//计算哈希地址
while(1)
{
if(strcmp(H[key].num,NULLKEY)==0)//如果该位置为空，把元素存到该位置
{
strcpy(H[key].name,name);
strcpy(H[key].num,num);
strcpy(H[key].add,add);
break;
}
else
key++;//如果该位置不为空，向后移插入元素
}
}
void Print_name(Record H[M])//以姓名为关键字的哈希表的输出函数
{
int i;
printf("\t哈希地址\t姓名\t\t号码\t\t地址\n");
for(i=0;i<30;i++)
{

if(strcmp(H[i].name,"\0")!=0)
{
printf("\t%d\t\t%s\t\t%s\t\t%s\n",i,H[i].name,H[i].num,H[i].add);
}
}
}
void Print_num(Record H[M])//以电话号码为关键字的哈希表的输出函数
{
int i;
printf("\t哈希地址\t姓名\t\t号码\t\t地址\n");

for(i=0;i<30;i++)
{
if(strcmp(H[i].num,"\0")!=0)
{
printf("\t%d\t\t%s\t\t%s\t\t%s\n",i,H[i].name,H[i].num,H[i].add);
}
}
}
void Del_name(Record H[M],char name[20])//以姓名为关键字的哈希表的删除函数
{
int key,t=0;//设置t为标志位，如果该元素被删除了，把t置为1
int i,k;
key=Hash_name(name);//计算哈希地址
i=key;
while(1)
{
if(strcmp(H[key].name,name)==0)//如果元素存在该位置，将该位置置空
{
t=1;
strcpy(H[key].name,"\0");
strcpy(H[key].num,"\0");
strcpy(H[key].add,"\0");
k=key;
while(key<30)
{
key++;
if(Hash_name(H[key].name)==i)//然后将哈希地址在该位置的存在后面的元素依次前移

{
strcpy(H[k].name,H[key].name);
strcpy(H[k].num,H[key].num);
strcpy(H[k].add,H[key].add);
k=key;
strcpy(H[key].name,"\0");
strcpy(H[key].num,"\0");
strcpy(H[key].add,"\0");
}
}
break;
}
key++ //如果元素不在该位置，向后移查找该元素再删除
}
if(t==0)//t为0表示没有执行删除操作
printf("该姓名不存在!");
}
void Del_num(Record H[M],char num[20])//以电话号码为关键字的哈希表的删除函数
{
int key=0,t=0;//设置t为标志位，如果该元素被删除了，把t置为1
key=Hash_num(num);//计算哈希地址
int i,k;
i=key;
while(1)
{
if(strcmp(H[key].num,num)0)//如果元素存在该位置，将该位置置空
{
t=1;
strcpy(H[key].name,"\0");
strcpy(H[key].num,"\0");
strcpy(H[key].add,"\0");
k=key;
while(key<30)
{
key++;
if(Hash_num(H[key].num)==i)//然后将哈希地址在该位置的存在后面的元素依次前移
{
strcpy(H[k].name,H[key].name);
strcpy(H[k].num,H[key].num);
strcpy(H[k].add,H[key].add);
k=key;
strcpy(H[key].name,"\0");
strcpy(H[key].num,"\0");
strcpy(H[key].add,"\0");
}
}
break;
}
else
key++; //如果元素不在该位置，向后移查找该元素再删除
}
if(t==0)//t为0表示没有执行删除操作
printf("该号码不存在!\n");
}
void main()//主函数
{
char name[20],num[20];
char a0[20],b0[20],c0[30];
char a1[20],b1[20],c1[20];
int m,i,g;
int w,k;
int flag=0;
while(1)
{
switch(menu_select() )
{
case 1:
m=Create(H);//创建辅助数组
break;
case 2:
input_name(Inf,m,H);//以姓名为关键字创建哈希表
Print_name(H);
while(1)
{
flag=0;
printf("\n");
printf("1:查找\n");
printf("2:插入\n");
printf("3:删除\n");
printf("0:返回\n");
printf("输入（0-3）:\n");
scanf("%d",&g);
switch(g)
{
case 1:
printf("\n请输入要查找的名字：\n");
scanf("%s",name);
k=Search_name(H,name);
printf("查找该人的信息是：\n");
printf("该人的姓名是:%s\n",H[k].name);
printf("该人的电话号码是:%s\n",H[k].num);
printf("该人的地址是:%s\n",H[k].add);
break;
case 2:
printf("\n请输入要插入的信息：\n");
printf("插入的姓名是:");
scanf("%s",a0);
printf("插入的电话是:");
scanf("%s",b0);
printf("插入的地址是:");
scanf("%s",c0);
Insert_name(H,a0,b0,c0);
printf("插入后的结果:\n");
Print_name(H);
break;
case 3:
printf("请输入要删除的名字:\n");
scanf("%s",name);
Del_name(H,name);
printf("删除后的信息:\n");
Print_name(H);
break;
case 0:
flag=1;break;

}
if(flag==1)
break;
}
for(i=0;i<30;i++)//将哈希表清空
{
strcpy( H[i].add,"\0");
strcpy( H[i].num,"\0");
strcpy( H[i].name,"\0");
}
break;
printf("\n");
case 3:
input_num(Inf,m,H);//以电话号码为关键字创建哈希表
Print_num(H);
while(1)
{
flag=0;
printf("\n");
printf("1:查找\n");
printf("2:插入\n");
printf("3:删除\n");
printf("0:返回");
printf("输入（0-3）:\n");
scanf("%d",&g);
switch(g)
{
case 1:
printf("请输入要查找的号码：\n");
scanf("%s",num);
w=Search_num(H,num);
printf("查找该人的信息是：\n");
printf("该人的姓名是：%s\n",H[w].name);
printf("该人的电话号码是:%s\n",H[w].num);
printf("该人的地址是:%s\n",H[w].add);
break;
case 2:
printf("\n请输入要插入的信息：\n");
printf("插入的姓名是:");
scanf("%s",a1);
printf("插入的电话是:");
scanf("%s",b1);
printf("插入的地址是:");
scanf("%s",c1);
Insert_num(H,a1,b1,c1);
printf("插入后的结果:\n");
Print_num(H);
break;
case 3:
printf("请输入要删除的号码：");
scanf("%s",num);
Del_num(H,num);
printf("删除后的信息：\n");
Print_