合肥学院
计算机科学与技术系
课程设计报告
2007 ～2008 学年第 2 学期
课 程 数据结构与算法
课 程 设 计 名 称 哈希表的设计与实现
学 生 姓 名
学 号
0604011026
专 业 班 级 06 计科(1)
指 导 教 师
2008 年 9 月
一、 课程设计题目:
（哈希表的设计与实现的问题）设计哈希表实现电话号码查询系统。设计程序完成以
下要求：（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、姓名：张三 电话号码：13805690141 地址：合肥
2、姓名：Jack 电话号码：13500408899 地址：Shanghai
三、概要设计和数据结构选择
本设计涉及到的数据结构为：哈希表。要求输入电话号码、用户名、地址三个信息，
并要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个哈希函数，进
行哈希查找。
在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分
别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链地址
法结点结构如图：
name[
8]
num[1
1]
address[2
0]
next
其中 name[8]和 num[11]是分别为以电话号码和用户名为关键字域，存放关键字（key）；
address[20](data)为结点的数据域，用来存储用户的地址。Next 指针是用来指向下一个结点
的地址。
主要算法的流程图如下：
以号码为关键字的 Hash()函数流程图
取整型 num[2]赋给 key
结束
Key=key%20
Key=key+(int) num[i]
i++
i 从 3 开始取
num[i]!=0
开 始
以姓名为关键字的 Hash()函数流程图
取整型 name[0]赋给 key2
结束
Key2=key%20
Key2+=name[i]
i++
i 从 0 开始取
name[i]不为空
开 始
