哈希表的设计与实现

合肥学院

计算机科学与技术系

2007

2008

～2008

课

学

学

专

指

年 9

月

课程设计报告

2

学期

程

数据结构与算法

课程设计名称

哈希表的设计与实现

生

姓

名

号

业

班

级

06 计科 (1)

导

教

师

学年第

一、

课程设计题目 :

（哈希表的设计与实现的问题）

设计哈希表实现电话号码查询系统。

设计程序完成以下

要求：（ 1）设每个记录有下列数据项：电话号码、用户名、地址；

分别以电话号码和用户名为关键字建立哈希表；

（ 2）从键盘输入各记录，

（ 3）采用再哈希法解决冲突；

（ 4 ）查找并

显示给定电话号码的记录；

（5）查找并显示给定用户的记录。

二、

问题分析和任务定义

1、问题分析

要完成如下要求：设计哈希表实现电话号码查询系统。

实现本程序需要解决以下几个问题：

（ 1） 如何设计一个结点使该结点包括电话号码、用户名、地址。

（ 2） 如何分别以电话号码和用户名为关键字建立哈希表。

（ 3） 如何利用再哈希法解决冲突。

（ 4） 如何实现用哈希法查找并显示给定电话号码的记录。

（ 5） 如何查找并显示给定用户的记录。

2、任务定义

由问题分析知， 本设计主要要求分别以电话号码和用户名为关键字建立哈希表，

并实现

查找功能。 所以本设计的核心问题是如何解决散列的问题，

亦即设计一个良好的哈希表。 由

于结点的个数无法确认，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”

的问题。所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，使用链表结构

把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。

首先， 解决的是定义链表结点，

在链地址法中，每个结点对应一个链表结点，它由三个

域组成， 而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，

所以该链表结点

它是由四个域组成

.name[8]

、 num[11] 和 address[20]

都是 char 浮点型，输入输出都只能

是浮点型的。

采用链地址法， 其中的所有同义词构成一个单链表，

再由一个表头结点指向这个单链表

的第一个结点。 这些表头结点组成一个一维数组，

即哈希表。 数组元素的下标对应由散列函

数求出的散列地址。

拉链法处理冲突的散列表结构：

3、主程序分析

本题目最主要的要求是设计散列函数，

本程序需要设计两个散列函数才能解决问题，

程序需

要分别为以电话号码和用户名为关键字建立哈希表。

立两个散列函数，具体思路为：

所以要分别以用户名、

号码为关键字建

对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对

20 求余。得到的

ASCLL码值相加， 然后对

数作为地址。 对于以用户名为关键字的散列函数，

是将所有字母的

20 求余。

要添加用户信息，即要有实现添加结点的功能的函数，所以要设计一个必须包括一个输

入结点信息、添加结点的函数；

要实现查找函数，则必须包括一个查找结点的函数；

另外还有一个必不可少的就是运行之后要有一个主菜单，即要设计一个主函数

（ main() ）。

4、测试数据的选择

最后， 程序完成后要对程序进行编译调试，

执行后要选择数据进行测试，

这里选择的测试数

据为：

1、姓名：张三

电话号码：地址：合肥

Shangha

i

2、姓名： Jack 电话号码：地址：

三、概要设计和数据结构选择

本设计涉及到的数据结构为：哈希表。要求输入电话号码、用户名、地址三个信息，并

要求分别以电话号码和用户名为关键字进行查找，

所以本问题要用到两个哈希函数，

进行哈

希查找。

在链地址法中， 每个结点对应一个链表结点，

它由三个域组成，

而由于该程序需要分别

链地址法结

用电话号码和用户名为关键字建立哈希表，

所以该链表结点它是由四个域组成，

点结构如图：

name[8] num[11] address[20]

next

其中 name[8] 和 num[11] 是分别为以电话号码和用户名为关键字域，存放关键字（

address[20](data)为结点的数据域，用来存储用户的地址。

key ）；

Next 指针是用来指向下一个结点

的地址。

主要算法的流程图如下

：

以号码为关键字的

Hash() 函数流程图

开

始

取整型 num[2] 赋给 key

i 从3开始取

num[i]!=0

Key=key+(int) num[i]

i++

Key=key%20

结束

以姓名为关键字的

Hash() 函数流程图

开

始

取整型 name[0] 赋给 key2

i 从 0 开始取

name[i] 不为空

Key2+=name[i]

i++

Key2=key%20

结束

添加结点信息流程图

:

申请专利开始

开始

申请新的结点

newphone,newname 即新的号码和名字

Newphone=input()

Newname 指向 newphone

调用 hash()函数

调用 hash()函数

拉链法处理冲突

利用用户名为关键字插入

结束

按姓名查找流程图

:

开始

调用 hash()函数中新结点 q 指向

phone[key]->next

q 不为空

q=q->next

q 不为

空

输出无记

输出相应

录

记录

结束

按号码查找流程图

:

开始

调用 hash2()函数中新结点 q 指向

phone[key]->next

q 不为空

q=q->next

q 不为

空

输出无记

输出相应

录

记录

结束

主程序流程图

开 始

Main ()

初始化散列链表（

1）并为

其动态分配内存空间

初始化散列链表（

2）并为

其动态分配内存空间

Menu （）主

菜单

输入选择

选６

查找号码

输 出

find()

结果

选择 1

选 7

查找用户

find2()

输出结

果

选择 2

进行姓名散列 list2()

姓 名 散

列结果

选择 0

添加记录 apend()

选择 3

进行号码散列 list()

号码散列

结果

选择 4

清空

creat();creat2()

列表已清

空

选择 5

退出系统 return 0

结

束

四、详细设计和编码

首先定义结点结构体类型， 在链地址法中， 每个结点对应一个链表结点，

它由三个域组

成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，

所以该链表结点它是

由四个域组成，链地址法结点结构如图：

name[8] num[11] address[20]

next

其中 name[8] 和 num[11] 是分别为以电话号码和用户名为关键字域（

key），存放关键字；

address[20]为结点的数据域

(data)，用来存储用户的地址信息。

点的地址。

next 指针是用来指向下一个结

unsigned int key

和

unsigned int key2

分别被定义为电话号码和用户名关键字。

块如下：

程序的主要模

************************

1、 建立节点

struct node // 建节点

程序部分源代码 *************************

{

char name[8],address[20];//

节点中要包含用户名， 用户地址，电话号码以及指向下一个结点的指针

char num[11];

node * next;

};

typedef node* pnode; //typedef

可以为一个已有的数据类型声明多个别名，

这里为该类型声明了两

个指针

typedef node* mingzi;

node **phone;

node **nam;

node *a;

2、 对哈希函数的定义

本程序要设计两个

hash（）函数，分别对应电话号码和用户名。本设计中对散列函数

（或结点）

选择的是除留余数法， 即对关键字进行模运算， 将运算结果所得的余数作为关键字

的存储地址， 即 H（ key）=key mod p, 本设计中 p 取 20,然后将计算出来的数作为该结点的地

址赋给 key。具体方法如下：以电话号码为关键字建立哈希函数

hash(char num[11]) 。以用户

名为关键字建立哈希函数

hash2(char name[8]) 。利用强制类型转换，将用户名的每一个字母

20 后的余数。将计算出来的数作为该结点的地址赋给

key2。

的 ASCLL 码值相加并且除以

************************

程序部分源代码 *************************

a)

void hash(char num[11]) //

以电话号码为关键字建立哈希函数

{

key=(int)num[2];

while(num[i]!=NULL)

{

key+=(int)num[i];

i++;

}

key=key%20;

}

b)

void hash2(char name[8])

//以用户名为关键字建立哈希函数

{

int i = 1;

key2=(int)name[0];

while(name[i]!=NULL)

{

key2+=(int)name[i];

i++;

}

key2=key2%20;

}

然后，建立结点，并添加结点，利用链地址法解决冲突。建立结点应包括动态申请内

存空间。 向结点中输入信息。

同时将结点中的

next 指针等于 null 。添加结点， 首先需要利用

哈希函数计算出地址即关键字，

其次将该结点插入以关键字为地址的链表后，

当然由于分别

以用户名和电话号码为关键字，所以分两种情况，如果以用户名为关键字则调用

hash2(char name[8]) 函数，并且将结点插入对应的散列链表中，如果以电话号码为关键字则

调用 void hash(char num[11]) 函数，并且将结点插入对应的散列链表中。

void

并且，需要两个建立散列链表的函数，分别动态申请一定的空间，用于动态申请散列

链表。 void create() 用来动态创建以电话号码为关键字的链表数组，

void create2() 用来动态创

建以用户名为关键字的链表数组。

************************

void create() //

新建号码节点

程序部分源代码 *************************

{

}

int i;

phone=new pnode[20]; //

动态创建对象数组

}

for(i=0;i<20;i++)

{

void create2() //

新建姓名节点

{

phone[i]=new node;

phone[i]->next=NULL;

int i;

nam=new mingzi[20];

for(i=0;i<20;i++)

nam[i]->next=NULL;

{

nam[i]=new node;

}

同样，需要两个显示链表的函数，

利用

for

循环和

while

语句将表中信息按要求输出来。

3．哈希查找

想要实现查找功能，同样需要两个查找函数，无论以用户名还是以电话号码为关键字，

首先，都需要利用

hash 函数来计算出地址。再通过比对，如果是以电话号码为关键字，比

较其电话号码是否相同， 如果相同则输出该结点的所有信息，

如果以用户名为关键字，

则比

较用户名是否相同， 如果相同则输出该结点的所有信息。

如果找不到与之对应相同的，

则输

出“无此记录” 。

************************

*************************a)

找用户信息

程

序

部

分

源

代

码

、

void find(char num[11]) //

在以电话号码为关键字的哈希表中查

{

hash(num);

node *q=phone[key]->next;

while(q!= NULL)

{

if(strcmp(num,q->num)==0)

break;

q=q->next;

}

if(q)

printf("%s_%s_%sn",q->name,q->address,q->num);

else printf(" 无此记录 n");

}

b)、 void find2(char name[8]) //

在以用户名为关键字的哈希表中查找用户信息

{

hash2(name);

node *q=nam[key2]->next;

while(q!= NULL)

{

if(strcmp(name,q->name)==0)

break;

q=q->next;

}

if(q)

printf("%s_%s_%sn",q->name,q->address,q->num);

else printf(" 无此记录 n");

}

3、 主函数

本程序需要创建一个主菜单和一个主函数，

主菜单便于用户的使用，

主函数中， 包括所有

功能对应的数值，使之和主菜单相对应。

主函数界面设计如下

0．

添加记录

1．

查找记录

2．

姓名散列

3．

号码散列

4．

清空记录

5．

退出系统

4、程序数据测试

当程序设计出来后的测试数据为：

1、姓名：张三 电话号码：地址：合肥

2、姓名： Jack 电话号码：地址： Shanghai

首先键入

0, 添加结点信息 , 然后按

1 进行查找 , 分别进行号码和姓名查找

, 最后可在主菜单

中，

选择号码散列和姓名散列

, 由此查看程序运行结果。

至此，就解决了哈希表的设计与实现算法可能出现的各种问题， 那么根据以上思路以及对问题的

分析和对出现情况的解决则可以写出源程序。

五、上机调试

1、语法错误及修改：程序是分块写的

键字的哈希表中要注意涉及

, 调试时可以使用分步调试的方式进行

, 以便能查

在以姓名为关

找看程序是在哪出错了。

本算法使用了链表结构和链地址法解决冲突的问题，

ASCLL码的类型转换，要注意输出不能是“

结果。 编写程序时要多注意程序中各种指针的使用，还有各类变量的定义，

些问题均可以根据编译器的警告提示，对应的将其解决。

识难度。 在本程序中每一个函数中都需要涉及到指针的操作。

样才能保证运行时不会出错。

%d”，否则不能输出

函数的使用。这

2、逻辑问题修改和调整：链表结构方法虽然方便了运行，但是增加了对算法过程的认

所以需要仔细分析函数中的指

针指向。在插入结点，查找结点时尤为突出。对于主菜单和主函数的对应，一定要一致，这

3、时间，空间性能分析：散列法本质上是一种通过关键字直接计算存储地址的方法。

在理想情况下， 散列函数可以把结点均匀地分布到散列表中，

比较，其时间复杂度

组连续的存储空间， 往往会发生同义词冲突，

此散列法的查找性能取决于

O（ n） =1。但在实际使用过程中，为了将范围广泛的关键字映射到一

这时在查找过程中就需要进行关键字比较。

3 个因素：散列函数、 冲突处理方法和填充因子。

不发生冲突， 则查找过程无需

因

采用链地址法，

可以从根本上杜绝“二次聚集”的发生，从而提高散列表的均匀度，提高查找性能，不过也

会“浪费” 一部分散列表的空间。当散列函数和冲突处理办法固定时，

散列法的查找性能就

取决于散列表的填充因子。填充因子

a=表中已有的结点数

/ 表的长度。填充因子 a 标志表的

a 越大冲突的机会就越大，查

添满程度。很显然，

a 越小则发生冲突的机会就越小；反之，

S

Nc

=1+a/2 。链地址法查找不

找的性能也就越低。哈希表链地址法查找成功的平均查找长度

成功的平均查找长度

U 满足： U =a+e

. 由以上可以看出，散列表的平均查找长度是填充因

n

nc

-a

子的函数， 和散列表的长度没有关系，

因此在实际应用中，

我们应该选择一个适当的填充因

子，以便把平均查找长度控制在一个尽量小的范围内。

问题时， 我首先想到的查找方法是顺序查找，

哈希表这一存储结构，另外本设计也可以用

4、经验和体会：本设计用到的数据结构是哈希表，并且要实现查找功能，在刚拿到本

这就没有用到哈希表， 而本设计要求必需使用

C++中的类来解决，可以用类来设计哈希表。

六、用户使用说明

本程序运行过程时带有提示性语句，

由于 address[20]、name[8] 和 num[11] 可以看出地址

8，电话号码都为 11 位。在输入的

可输入的最大字符数是

20，姓名可输入的最大字符数是

时候，用户特别注意电话号码的位数。

实现添加结点，将信息从键盘输入，然后根据屏幕的提示进行操作，由此，本设计的要

求就可以被用户实现了。

七、测试结果

程序主菜单 :

添加记录 :

分别按电话号码和姓名查找

:

分别输出按姓名和号码散列的结果

:

清空记录 :

八、参考书目

谭浩强，《C 语言程序设计》 ，北京：清华大学出版社，

王昆仑，李红， 《数据结构与算法》 ，中国铁道出版社，

李春葆，数据结构题集，北京：清华大学出版社，

2005年 7月第 3版。

2007

年 6月第 1版。

1992 年 2

月第一版。

九、附录

************************

#include

#include

程序源代码 **************************

#define NULL 0

unsigned int key; //

unsigned int key2;

定义两个关键字

int *p;

struct node //

{

char name[8],address[20];

char num[11];

node * next;

};

typedef node* pnode; //typedef

可以为一个已有的数据类型声明多个别名，这里为该类型声明了两个指

建节点

每个结点包括用户姓名、地址、电话号码、以及指向下一个结点的指针

针

typedef node* mingzi;

node **phone;

node **nam;

node *a;

void hash(char num[11]) //

//

{

哈希函数 ，以电话号码为关键字建立哈希函数

哈希函数的主旨是将电话号码的十一位数字全部加起来

int i = 3;

key=(int)num[2];

while(num[i]!=NULL)

{

key+=(int)num[i];

i++;

}

key=key%20;

}

void hash2(char name[8]) //

哈希函数

以用户名为关键字建立哈希函数

// 利用强制类型转换， 将用户名的每一个字母的

ASCLL码值相加并且

除以 20 后的余数

{

int i = 1;

key2=(int)name[0];

while(name[i]!=NULL)

{

key2+=(int)name[i];

i++;

}

key2=key2%20;

}

node* input() //

{

node *temp;

输入节点信息 ，建立结点，并将结点的

next 指针指空

temp = new node; //new 的功能是动态分配内存，语法形式： new 类型名 T（初值列表 temp-

>next=NULL;

printf("

请输入姓名 :n");

scanf("%s",temp->name);

printf("

输入地址：

n");

scanf("%s",temp->address);

printf("

输入电话： n");

scanf("%s",temp->num);

return temp; //

对于指针类型返回的是地址

}

int apend() //

{

node *newphone;

node *newname;

newphone=input();

newname=newphone;

newphone->next=NULL;

newname->next=NULL;

hash(newphone->num); //

hash2(newname->name);

newphone->next = phone[key]->next; //

phone[key]->next=newphone; //

利用电话号码为关键字插入

利用哈希函数计算出对应关键字的存储地址

添加节点

是采用链地址法，拉链法处理冲突的散列表结构

利用用户名为关键字插入

newname->next = nam[key2]->next; //

nam[key2]->next=newname;

return 0;

}

void create() //

{

int i;

phone=new pnode[20];//

for(i=0;i<20;i++)

{

phone[i]=new node;

phone[i]->next=NULL;

动态创建对象数组

新建节点

}

}

void create2() //

{

int i;

nam=new mingzi[20];

for(i=0;i<20;i++)

{

nam[i]=new node;

nam[i]->next=NULL;

新建节点

}

}

void list() //

{

int i;

node *p;

for(i=0;i<20;i++)

{

p=phone[i]->next;

while(p)

{

printf("%s_%s_%sn",p->name,p->address,p->num);

显示列表

p=p->next;

}

}

}

void list2() //

{

int i;

node *p;

显示列表

for(i=0;i<20;i++)

{

p=nam[i]->next;

while(p)

{

printf("%s_%s_%sn",p->name,p->address,p->num);

p=p->next;

}

}

}

void find(char num[11]) //

{

hash(num);

node *q=phone[key]->next;

while(q!= NULL)

{

if(strcmp(num,q->num)==0)

break;

q=q->next;

}

if(q)

在以电话号码为关键字的哈希表中查找用户信息

printf("%s_%s_%sn",q->name,q->address,q->num);

else printf("

}

void find2(char name[8]) //

{

hash2(name);

node *q=nam[key2]->next;

while(q!= NULL)

{

if(strcmp(name,q->name)==0)

break;

q=q->next;

}

if(q)

printf("%s_%s_%sn",q->name,q->address,q->num);

else printf("

}

无此记录 n");

在以用户名为关键字的哈希表中查找用户信息

无此记录 n");

void menu() //

{

菜单

printf("0.

printf("1.

printf("2.

printf("3.

printf("4.

printf("5.

}

添加记录 n");

查找记录 n");

姓名散列 n");

号码散列 n");

清空记录 n");

退出系统 n");

int main()

{

char num[11];

char name[8];

create();

create2() ;

int sel;

while(1)

{

menu();

scanf("%d",&sel);

if(sel==1)

{

printf("6

int b;

scanf("%d",&b);

if(b==6)

{

printf("

请输入电话号码 :n");

号码查询， 7 姓名查询 n");

scanf("%s",num);

printf("

输出查找的信息 :n");

find(num);

}

else

{

printf("

请输入姓名 :n");

scanf("%s",name);

printf("

find2(name);}}

if(sel==2)

{printf("

list2();}

姓名散列结果 :n");

输出查找的信息 :n");

if(sel==0)

{printf("

apend();}

if(sel==3)

{printf("

list();

}

if(sel==4)

{printf("

列表已清空 :n");

号码散列结果 :n");

请输入要添加的内容

:n");

create();create2();}

if(sel==6) return 0;

}

return 0;

}