文档介绍：前言
人类已经跨入了新世纪,正在进入信息时代。现在信息技术的应用越来越普及,不但促进了社会的高速发展,也改变着人们的工作、学习、生活和娱乐的方式以及思想观念。随着计算机的日益普及,计算机软件无处不在。软件在计算机的发展和应用中至关重要,在人类进入信息化社会时成为新兴信息产业的支柱
计算机技术的迅猛发展,特别是随着网络技术的出现标志着信息时代已经来临。信息化浪潮、网络革命在给社会带来冲击的同时,也使哈希表的应用越来越广泛,传统的查找和服务方式已不能适应现代社会对日益增长的文献信息的需求。随着信息量的不断增加,数据资料的著录和查询的难度也就相应增加,手工方式已经不能满足要求,如何运用先进的信息技术,提高查找效率和服务水平,是我们面临的一个新的挑战。
一直以来人们使用传统的查找方式,在日常工作,比如图书馆的借书、还书和书籍的相关信息,想必大家都想很方便的在网上查找其相关信息。借书、还书等一些信息的查询过程主要依靠传统的查找方式。这个过程的不足之处显而易见,首先他要对全部数据逐个比较,效率很低。其次处理能力比较低,一段时间内,所能服务的查询人数是有限的。利用哈希表来处理这些查找过程无疑会极大程度地提高效率和处理能力。我们将会看到哈希表给我们带来的方便,查询者可以花更多的时间在信息的查询上。
哈希表建成无疑会为信息的查询者提供极大的帮助。
目录
摘要 1
2
3
3
3
4
4
5
3. 函数构造 6
4. 冲突处理 6
7
8
19
20
参考文献 20
致谢 21
摘要
利用哈希表查找是重要的查找方法,对于我们大学生来说研究哈希查找是我们最好的获取信息的方式。但由于哈希查找有一定的复杂度,使得传统的查找方式现在仍然占据主要地位,使人们利用新的查找方法还很陌生。本文作者在学习了C语言和数据结构的基础上,为方便对信息的准确查找,编写了一个小型的哈希查找系统。它包括:设每个记录有下列数据项:电话号码、用户名、地址;从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表;采用双散列法解决冲突;查找并显示给定电话号码的记录;查找并显示给定用户名的记录;设计不同的散列函数,比较冲突率;在散列函数确定的前提下,尝试各种不同类型处理冲突的方法,考察平均查找长度的变化
关键词:哈希函数,模块功能,流程图,处理冲突。
散列表的设计与实现,设每个记录有下列数据项:电话号码、用户名、地址;从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表;采用双散列法解决冲突;
基本要求:
(1).查找并显示给定电话号码的记录;
(2).查找并显示给定用户名的记录;
(3).设计不同的散列函数,比较冲突率;
(4).在散列函数确定的前提下,尝试各种不同类型处理冲突的方法,考察平均查找长度的变化。
系统必须是win2000以上,在TURBE C或Win-TC 环境下运行程序。
选取某个函数(通常它是关键字的函数),将每个元素的关键字代入该函数得到一个函数值,就依此作为该元素的存储位置,按这个思想构造的查找表称为散列表,求其散列地址的函数即为散列函数。
h(k1)
h(k3)
h(k2)
h(k5)
h(k4)
. . U. . . . .
. . .
0
h(k1)
h(k3)
h(k2)=h(k5)
h(k4)
m-1
T
(关键字和哈希表的关系图)
开始
初始化
处理冲突
是否有冲突
Y
调用子函数,建立哈希表
不以关键字的比较为基本操作,采用直接寻址技术。在理想情况下,无须任何比较就可以找到待查关键字,查找的期望时间为O(1)。
哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。哈希表是一种高效的数据结构。
哈希表又叫做散列表,分为"开散列" 和"闭散列"。考虑到竞赛时多数人通常避免使用动态存储结构,本文中的"哈希表"仅指"闭散列"。
散列表种类
处理冲突方法
平均查找长度
成功的查找
不成功的查找
开散列表
拉链法
1 + α/2
α+ e-α
闭散列表
线性探测法
(1+
  1  
1-α
)/2
(1+