合肥学院
计算机科学与技术系
课程设计报告
2007 ～2008 学年第 2 学期
课 | | | l6561 程 | 数据结构与算法 |
课程设计名称 | 哈希表的设计与实现 |
学 | 教育评价生 | 姓 | 名 | |
学 | | | 号 | 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码值相加， 然后对
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议