哈希表的设计与实现复习进程.doc

哈希表的设计与实现

精品文档
令胆 嗲 院
计算机科 嗲 b 练 水 系

课程设计报告
2007 2008 学年第 2 学期

课 程 数据结构与算法

课 程 设 计 名 称 哈希表的设计与实现

学
生
姓
名

学

号
0604011026
专
业
班
级
06 计科（1)
指
导
教
师

2008 年 9 月

收集于网络，如有侵权请联系管理员删除
课程设计题目：
（哈希表的设计与实现的问题〉 设计哈希表实现电话号码查询系统。设计程序完成以下 要求 ：(1） 设每个记录有下列数据项：电话号码、用户名、地址：（2） 从键盘输入各记录 ， 分别以电话号码和用户名为关键字建立晗希表 ；(3） 采用再哈希法解决冲突；（4） 查找并 显示给定电话号码的记录 ：（5） 查找并显示给定用户的记录。
一、 问题分析和任务定义
1、问题分析
要完成如下要求 ：设计晗希表实现电话号码查询系统。 实现本程序需要解决以下几个问题：
(1) 如何设计一个结点使该结点包括电话号码、用户名、地址。
(2) 如何分别以 电话号码和用户名为关键字建立哈希表 。
(3) 如何利用再晗希法解决冲突。
(4) 如何实现用晗希法查找并显示给定电话号码的记录 。
(5) 如何查找并显示给定用户的记录 。

2、任务定义
由问题分析知，本设计主要要求分别以电话号码和用户名为关键字建立晗希表 ，并实现 查找功能 。所以本设计的核心问题是如何解决散列的问题，亦即设计一个良好的哈希表。由 于结点的个数无法确认，并且如果采用线性探测法散列算法 ，删除结点会引起 “信息丢失” 的问题。所以采用链地址法散列算法 。采用链地址法 ，当出现同义词冲突时，使用链表结构 把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址 。
首先，解决的是定义链表结点，在链地址法中，每个结点对应一个链表结点，它由三个 域组成，而由于该程序需要分别用电话号码和用户名为关键字建立晗希表 所以该链表结点 它是由四个域组成.name[8］ 、num [ll］ 和 address[20］ 都是 char 浮点型，输入输出都只能 是浮点型的。
采用链地址法，其中的所有同义词构成一个单链表，再由一个表头结点指向这个单链表 的第一个结点。这些表头结点组成一个一维数组，即哈希表。数组元素的下标对应由散列函 数求出的散列地址。

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

｜ ｜ ｜ ｜ ｜

3、主程序分析
本题目最主要的要求是设计散列 函数，本程序需要设计两个散列函数才能解决问题，程序需 要分别为以 电话号码和用户名为关键字建立哈希表 。所以要分别以用户名、号码为关键字建 立两个散列画数，具体思路为 ：
对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对 20 求余。得到的 数作为地址 。对于以用户名为关键字的散列函 数，是将所有字母的ASCLL 码值相加 ，然后对 20 求余。
要添加用户信息，即要有实现添加结点的功能的函数，所以要设计一个必须包括一个输 入结点信息、添加结点的函数：
要实现查找函数 ，则必须包括一个查找结点的函数； 另外还有一个必不可少的就是运 行之后要有一个主菜单 ，即要设计一个主函数
(main（） ）。
4、测试数据的选择
最后，程序完成后要对程序进行 编译调试，执行后要选择数据进行测试，这里选择的测试数 据为：
l、姓名：张三 电话号码：[phone] 地址：合肥
2、姓名：Jack 电话号码：[phone] 地址：Shanghai

三、概要设计和数据结构选择
本设计涉及到的数据结构为 ：哈希表。要求输入电话号码、用户名、地址三个信息，并 要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个晗希函数，进行哈 希查找。
在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别 用电话号码和用户名为关键字建立哈希表 ，所以该链表结点它是由 四个域组成 ，链地址法结 点结构如图：
｜ 阳e[8] I 川［口J l a抽出s [20] I next

其中 name[8］和 num[ll ］是分别为以电话号码和用户名为关键字域 ，存放关键字 （key ) ; address[20](data）为结点的数据域，用来存储用户的地址。Next 指针是用来指 向下一个结点 的地址。
主要算法的流程 图如下：
以号码为关键字的 Hash（）函数流程图

开 始

取整型 num[2］赋给 key

i从 3 开始取

Key=key+(int) num[i]

i++

Key=key%20

结束

以姓名为关键字的 HashO函数流程图

／
开 始

取整型name[O］赋给 key2

i从 0 开始取

Key2+=name[i]

i++

Key2:::key%20

结束

添加结点信息流程图：

开始

申请新的结点 newphone,newname 即新的号码和名字

Newphone=input()

Newname 指向 newphone

调用 hash（）函数

调用 hash（）函数

拉链法处理冲突

利用用户名为关键字插入

结束

按姓名查找流程图：

开始

调用 hash（）函数中新结点 q 指向
phone[key]->next

q=q->next

输 出无 记 录


q 不为 空


输 出相 应
记录

结束

按号码查找流程图：

开始

调用 bash2（）函数中新结点 q 指向
pbone[key]->next

q=q->next

输 出无 记 录


q 不为
空


输 出相 应 记录

结束

初始化散列链表 (1） 并为
其动态分配内存空 间

初始化散列链表 （ 2） 并为
其动态分配内存空 间
主程序流程图

Menu （） 主
菜单

进行姓名散1 list2()
添加记录 apend()
进行号码散列 list()
号码散列
结果
清空 creat();creat2()
列表己清
空
退出系统 return O

结 束

四、详细设计和编码
首先定义结点结构体类型，在链地址法 中，每个结点对应一个链表结点，它由三个域组 成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表 ，所以该链表结点它是 由四个域组成 ，链地址法结点结构如图：
I n棚e [s] I 川

其中 name[8］和 num [ll］是分别为以电话号码和用户名为关键 字域 （key） ，存放关键字： address[20］为结点的数据域（data），用来存储用户的地址信息。next 指针是用来指向下一个结 点的地址。
unsigned int key 和 unsigned int key2 分别被定义为电话号码和用户名关键字。程序的主要模 块如下：
＊＊＊＊＊串＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊程序部分源代码中串＊串＊串＊串＊串＊丰＊＊＊＊＊＊＊＊＊＊＊＊＊
1、建立节点
struct node H建节点

char name[8],address[20］矿／节点中要包含用户名，用户地址，电话号码以及指向下一个结点的指针
char num(ll]; node * next;

typedef node* pnode; //typedef 可以为一个己有的数据类型声明多个别名，这里为该类型声明了两 个指针
typedef node* mingzi; node **phone ;
node 肺nam; node *a;
2、对哈希函数的定义
本程序要设计两个 hash O 函数，分别对应电话号码和用户名。本设计中对散列函数 选择的是除留余数法，即对关键字进行模运算，将运算结果所得的余数作为关键字（或 结点〉 的存储地址，即 H (key) =key mod p，本设计中p 取 20，然后将计算出来的数作为该结 点的地 址赋给 key。具体方法如下：以电话号码为关键字建立哈希函数 hash(char num[11］） 。以用户 名为关键字建立哈希 函数bash2(char name[8］） 。利用强制类型转换，将用户名的每一个字母 的ASCLL 码值相加并且除以20 后的余数。将计算出来的数作为该结 点的地址赋给 key2 。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊程序部分源代码＊牢牢牢牢牢牢牢牢牢牢串串串串串串串 串＊本＊本＊中

a)
,•oid hash(char num[ll]) II以电话号码为关键字建立哈希函数

key=(int)num [2];

while(num[i]!=NULL)

key+=(int)num[i];

1+

key=key %20;

b)
void bash2(char name[8]) II以用户名为关键字建立晗希函数

int i = 1; key2=(int)name[O];

while(name[i]!=NULL)

key2+=(int)name[i];
’＋＋；

key2=key2%20;

然后，建立结点 ，并添加结点 ，利用链地址法解决冲突 。建立结点应包括动态申请内 存空间。向结点中输入信息。同时将结点中的 next 指针等于 null 。添加结点，首先需要利用 晗希函数计算出地址即关键字，其次将该结点插入以关键字为地址的链表后 ，当然由于分别 以用户名和电话号码为关键字 ，所以分两种情况 ，如果以用户名为关键字则调用 void hash2(char name[8］）函数，并且将结点插入对应的散列链表中，如果以电话号码为关键字则 调用 void hash(char num[ll］）函数，并且将结点插入对应的散列链表中 。
并且，需要两个建立散列链表的函数 ，分别动态申请一定的空间 ，用于动态申请散列 链表。void creatβ（）用来动态创建以电话号码为关键字的链表数组，void create2（）用来动态创 建以用户名为关键字的链表数组。
＊＊＊＊＊＊＊＊＊＊＊＊串串＊＊＊＊＊＊＊＊＊＊程序部分源代码＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊串＊串＊丰

void create() II新建号码节点 phone[i]=new node; phone[i]->next=NULL;
int i;
phone=new pnode[20]; fl动态创建对象数组
for(i=O;i<20;i++)

void create2() II新建姓名节点


nam[i]=new node;

int i; nam[i]->next=NULL ;
nam=new mingzi[20]; for(i=O;i<20;i叫
同样，需要两个显示链表的函数，利用 for 循环和 while 语句将表中信息按要求输出来 。
3. 哈希查找
想要实现查找功能，同样需要两个查找函数，无论以用户名还是以电话号码为关键字 ， 首先，都需要利用 hash 函数来计算出地址。再通过比对 ，如果是以电话号码为关键字 ，比 较其电话号码是否相同，如果相同则输出该结点的所有信息，如果以用户名为关键字，则比 较用户名是否相同，如果相同则输出该结点的所有信息。如果找不到与之对应相同的，则输 出 “无此记录，，。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊ 程 序 部 分 源 代 码
＊＊＊＊串串＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊a）、void find(char num[ll］） 施以电话号码为关键字的哈希表中查 找用户信息

hash(num);

node *q=phone[key]->next; while(q!= NULL)

if(strcmp(num,q->num)==O) break;
q=q->next;

if(q)
printf（”%s_%s_%s\n",q->name,q->addre邸 q->num); else printf （ 无J1t记录飞n");

b）、void fmd2(char name[S]) II 在以用户名为关键字的哈希表中查找用户信息

hash2(name)

node *q=nam[key2]->next; while(q!= NULL)

if(strcmp(name,q->name)==O) break;
q=q->next;

if(q)
printf（”%s_%s_%s恼”，q->name,q->address,q->nUJD); else printf （ 无此记录飞n");

3、主函数
本程序需要创建一个主菜单和一个主函 数，主菜单便于用户的使用，主函数中，包括所有 功能对应的数值，使之和主菜单相对应 。
主函数界面设计如下
0. 添加记录
1. 查找记录
2. 姓名散列
3. 号码散列
4. 清空记录
5. 退出系统
4、程序数据测试
当程序设计出来后的测试数据为 ：
1、姓名：张三 电话号码：[phone] 地址：合肥
2、姓名：Jack 电话号码：[phone] 地址：Shanghai
首先键入 0，添加结点信息，然后按 1 进行查找，分别进行号码和姓名查找，最后可在主菜单 中，
选择号码散列和姓名散列，由此查看程序运行结果 。

至此，就解决了哈希表的设计与实现算法可能出现的各种问 题，那么根据以上思路以及对问 题的分析和对出现情况的解决则可以写出源程序 。

五、上机调试
1、语法错误及修改 ：程序是分块写的，调试时可以使用分步调试的方式进行，以便能查 找看程序是在哪出错了。本算法使用了链表结构和链地址法解决冲突的问题，在以姓名为关 键字的哈希表中要注意涉及 ASCLL 码的类型转换，要注意输出不能是＂%d ”，否则不能输出 结果。编写程序时要多注意程序中各种指针的使用，还有各类变量的定义，函数的使用。这 些问题均可以根据编译器的警告提示，对应的将其解决。
2、逻辑问题修改和调整：链表结构方法虽然方便了运行，但是增加了对算法过程的认 识难度。在本程序中每一个函数中都需要涉及到指针的操作。所以需要仔细分析函数中的指 针指向。在插入结点，查找结点时尤为突出。对于主菜单和主函数的对应，一定要一致，这 样才能保证运行时不会出错。
3、时间，空间性能分析：散列法本质上是一种通过关键字直接计算存储地址的方法 。 在理想情况下，散列函数可以把结点均匀地分布到散列表 中，不发生冲突，则查找过程无需 比较，其时间复杂度 0 (n) =1。但在实际使用过程中，为了将范围广泛的关键宇映射到一 组连续的存储空间 ，往往会发生同义词冲突，这时在查找过程中就需要进行关键字比较 。因 此散列法的查找性能取决于 3 个因素：散列函数、冲突处理方法和填充因子。采用链地址法 ，

可以从根本上杜绝 “二次聚集” 的发生，从而提高散列表的均匀度，提高查找性能，不过也 会 “浪费” 一部分散列表的空间 。当散列函数和冲突处理办法固定时散列法的查找性能就 取决于散列表的填充因子。填充因子 a 表中已有的结点数／表的长度。填充困子 a 标志表的 添满程度。很显然，a 越小则发生冲突的机会就越小 ；反之，a 越大冲突的机会就越大，查 找的性能也就越低。哈希表链地址法查找成功的平均查找长度 SNc= l+a/2 。链地址法查找不 成功的平均查找长度 Un 满足：Un =a＋ ．由以上可以看出，散列表的平均查找长度是填充困 子的函数，和散列表的长度没有关系，因此在实际应用 中，我们应该选择一个适当的填充因 子，以便把平均查找长度控制在一个尽 量小的范围内。
4、经验和体会 ：本设计用到的数据结构是哈希表，并且要实现查找功能，在刚拿到本 问题时，我首先想到的查找方法是顺序查找，这就没有用到哈希表 ，而本设计要求必需使用 晗希表这一存储结构，另外本设计也可以用 C＋＋中的类来解决，可以用类来设计晗希表 。
六、用户使用说明

本程序运行过程时带有提示性语句，由于 address[20］ 、name[8］和 num[ll］可以看出地址 可输入的最大字符数是 20，姓名可输入的最大字符数是 8，电话号码都为 11 位。在输入的 时候，用户特别注意 电话号码的位数。
实现添加结点 ，将信息从键盘输入 ，然后根据屏幕的提示进行操作，由此，本设计的要 求就可以被用户实现了。
七、测试结果
程序主菜单：

添加记录：

E 圃C:\Users\tige叭Desktop飞课程酣咱希褒酣吃酒 hxb飞Debug\hxb剧理

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

国C:\Users飞回ge叭Des战op＼课程齿，＋鸭精装源代码飞hxb飞' Debug\hxb.exe A坦J到

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

国C飞U”“飞liger飞Desktop＼课程酶，叭晗帮褒漂代码飞hxb飞Debug飞hxb剧e

国C:\Users＼句e叭Desktop飞漂穰副科始每蒙漂代码，＼hxb\Debug\hxb刷e

清空记录：

广m
e:飞Users\tige 飞Des阳op幌程设 t'飞始帮亵漂代码＼hxb\Debug飞hxb刷e

八、参考书 目

i草浩强，《C 语言程序设计》，北京：清华大学出版社 ，2005 年 7 月第 3 版。 王昆仑，李红，《数据结构与算法》，中国铁道出版社 ，2007 年 6 月第 1版。 李春碟，数据结构题集，北京：清华大学出版社 ，1992 年 2 月第一版。

九、附录
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊程序源代码牢牢牢牢牢牢牢牢牢牢牢牢牢牢牢牢牢 ＊本＊本＊本＊本＊

#include
#include

#def ine M儿L 0
unsigned int key ；／／定义两个关键字
unsigned int key2;

int *P ,
struct node ／／建节点 每个结点包括用户姓名、地址、电话号码、以及指向下一个结点的指针

char name ［町，address [20] , char num[ll] ;
node * next ;

typedef node* pnode; // typedef 可以为一个已有的数据类型声明多个别名，这里为该类型声明了两个指
针
typedef node* mingz i; node **phone;
node **n创o; node ＊乱，

void hash(char num [ll]) ／／哈希函数 ，以电话号码为关键字建立哈希函数
／／晗希函数的主旨是将电话号码的十一位数字全部加起来

int i = 3;
key= (int) num [2] ;

while (num[i] ！阳LL)

key+= (int) num [i] ; 1++;

key=key%20;

void hash2 (char name [8]) ／／哈希函数 以用户名为关键字建立哈希函数

除以 20 后的余数

int i = l ;
key2= (int) n棚e[O] ; while (name [i]！阳LL)
key2+= (int) name [i]; 1++ ;

key2=key2%20 ;
／／利用强制类型转换，将用户名的每一个字母的ASCLL 码值相加并且

node* input () ／／输入节点信息 ，建立结点，并将结点的 next 指针指空

node *temp ;
temp = new node; //new 的功能是动态分配内存，语法形式 ：new 类型，名 T （初借列表
temp->next=NU LL ;
printf （’请输入姓名：＼n勺 ， scanf （’%sH, temp->name) , printf （’输入地址：\nH) ; scanf （’%s’，temp->address) ; printf （’输入电话：＼n") ; scanf （飞s’，temp->num) ,

return temp ；／／对于指针类型，返回的是地址

int apend O II添加节点

node *newphone ; node *newname ; newphone=inpu t () ; newname=newphone;
newphone->next 肌儿L ;
newname->next=NULL ;
hash (newphone->num) ; ／／利用哈希函数计算出对应关键字的存储地址
hash2 (newname->name) ;
newphone->next = phone [key) ->next ; II利用电话号码为关键字插入
phone [key) ->next=newphone; ／／是采用链地址法，拉链法处理冲突的散列表结构
newname->next = nam[key2) ->next ; ／／利用用户名为关键字插入
nam [key2〕 ＞next=newn 划1e; return 0:

void create () ／／新建节点

mt i .
phone-1ew pnode [20］ ；／／动态创建对象数纽 for(i=O; i<20 ; i÷＋）

phone [i]=new node; phone [i]->next=NULL;

void create20 ／／新建节点

int i ;
nam=new mingzi[20〕 ；
for (i=O; i<20; i++)

na叫i]=new node; nam (i]->nextNULL ;

void list （） ／／显示列表

int 1,
node *p;
for (i=O; i<20; i++)

p=phone [i]->next; while (p)

printf （’如 %s_%s\n’，p->name, p->address, p->num) ; p=p-)next ;

void list2 0 ／／显示列表

mt i .
node *p;

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

p=nam[i]->next ; while (p)

printf （’如 %s_%s\n’，p->name, p->address, p->num) ; p=p-)nex t ;

void f ind (char num[ ll]) ／／在以电话号码为关键字的哈希袋中查找用户信息

hash (num) ;
node *q=phone [key] ->nex t ; while (q != Nl儿L)

if (strcmp (num, q-)num) =O) break;
q=q-)nex t ;

if (q)
printf （飞s_%s_%s\n’，q->name, q->address, q-)num) ; else pr intf （’无此记录＼n勺 ，

void f ind2 (char name [8]) II 在以用户名为关键字的哈希表中查找用户信息

hash2 (mune) ;
node *q习1am [key2]->next , while (q != Nl儿L)

if (strcmp (name, q-)name)=O) break ;
q=q-)nex t ;

if (q)
printf （飞s_%s_%s\nn, q-)n棚e, q-)address, q-)num) ; else pr intf （’无此记录＼n勺 ，

void menu () ／／菜单

printf （’0. 添加记录＼n勺 ， printf (nl. 查找记录＼n勺 ， printf C2. 姓名散列＼nH) ; printf （’3. 号码散JU\n") ; printf （’4. 清空记录＼n") ;
pr intf （’5. 退出系统＼n’） ，

int main()

char num [ll] ; char name [8] ;

create () , create2 0

int sel; while (1)

menu O ,
scanf （飞d’，＆sel) ; if (sel=l)

printf （’6 号码查询，7 姓名查询＼n’） ；
int b ,
scanf （’%d’，＆b) ;
if (b=6)

printf （’请输入电话号码 ：＼nH) ; scanf （’如’，num) ;
printf （’输出查找的信息：＼nH) ; f ind (num) ;

else

pr intf （’请输入姓名 ：＼n勺 ，
scan: （’如’，name) ;
printf （’输出查找的信息：＼nH) ; f ind2 (name) ;}}
if (sel=2)
{printf （’姓名散列结果 ：＼n") ; list2 0 ;}

if (sel=O)
{printf （’请输入要添加的内容：怡’） ；
apend () ;} if (sel=3)
{pr intf （’号码散列结果 ：＼nn ) ;
list () ,

if (sel=4)
{printf （’列表己消空：＼n勺 ，
巳reate O ;create2 () ;} if (sel=6) return O;

return O ;