哈希表设计与实现课程设计文档

《哈希表设计与实现课程设计文档》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、课程名称：数据结构XXXXXXXX本科学生课程设计（论文）题目哈希表的设计与实现姓名XXX学号XXXXXXXXXXXX学部计算机科学与技术专业、年级计算机科学与技术大二指导教师XX2010年11月28日摘要随着信息技术的发展，关于各种程序中的数据结构也是层出不穷，对于项目某一方面的计算或者是某一方面的研究，出现了专门的数据结构，哈希表就是其中之一，哈希表作为另类的一种数据结构，其作用也是区别于其它同类的数据结构的，它是由两部分组成的：键(key)和值，通过键可以迅速的查找到你需要的值。常见的构造哈希函数的方法

2、有直接定址法除留余数法平方取中法数字分析法等。一般创建哈希表时可能会出现很多的冲突，常用的处理冲突的方法为开放定址法再哈希法链地址法建立一个公共溢出区。关键词:数据结构；哈希表；键(key)；哈希表的设计与实现第1章前言第26页哈希表的设计与实现第1章前言目录第1章前言与系统实现21.1前言21.2系统实现31.2.1开发环境31.2.2VisualC++环境的安装3第2章系统功能分析42.1系统功能需求分析42.2任务定义4第3章总体设计53.1系统数据结构53.2主要算法流程图63.2.1以姓名为关键字的

3、CreateHashList()函数流程图63.2.2哈希表查找算法流程图73.2.3主程序流程图8第4章详细设计和编码94.1节点的建立94.2对哈希函数的定义94.3创建哈希表算法、代码如下所示:104.3.1算法104.3.2代码104.4哈希查找114.5显示哈希表144.6主菜单设计164.7主函数设计16第5章程序运行测试195.1程序主界面195.2哈希表初始化195.3按姓名查找记录215.4显示哈希表全部记录22总结23参考文献24第26页哈希表的设计与实现第1章前言第1章前言与系统实现1.

4、1前言在信息化时代的今天，计算机技术已经是发展到一个很可观的地步了，特别是面向窗口的操作系统的出现，使得程序设计更加的容易了。在过去计算机内存容量小，CPU计算速度慢，关于程序设计中的数据结构也因此提出来很多的关于解决这方面的问题。哈希表就是其中之一，哈希表是一个由关键字与值组成的特殊的一种数据结构。它的出现主要是为了解决在结构中查找记录时需要进行一系列和关键字的比较,这一类查找方法是建立在“比较”的基础上的，在顺序等的查找中，查找的效率是依赖于查找过程中所比较的次数。理想的情况是希望不经过任何的比较一次存取

5、便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系，使得每个关键字和结构中一个唯一的存储位置相对应。因而在查找时只要根据这个对应关系找到给定的值的像。若结构中存在关键字和该值相等的记录，则所要查找的数就必定就是这个所查找到的记录。哈希函数是建立哈希表的一个重要的成员，它的构造方法分为以下几种：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。本程序中主要用的是除余取留法,除留取余法主要是取关键字被某个不大于哈希表表长m的数p出后所得余数为哈希地址即:H(key)=

6、keyMODp,p<=m，这是一种最简单，也是一种最常用的构造函数的方法，它不仅可以对关键字直接取模，也可在折叠、平方中等运算之后取模。在哈希表的建立中，很容易出现同义词，这些同义词的出现也导致了建立哈希表时冲突的出现，如果不解决这些冲突那么建立好的哈希表与预料的哈希表不同。关于处理冲突的方法主要有：开放定址法、再哈希法、链地址法。本程序中主要用的就是链地址法莱解决冲突的。第26页哈希表的设计与实现第1章前言1.2系统实现本程序是在Vc++6.0环境下编写测试运行的。1.2.1开发环境表1-1列出了系统硬件配

7、置，表6-2列出了系统软件配置。设备名称配置CPUE12002.6GHz内存128MB硬盘40GB表1.1组装台式机配置设备名称版本操作系统WindowsXPsp3开发环境VisualStudioC++6.0设计工具VC++表1.2软件环境1.2.2VisualC++环境的安装在计算机中安装VisualC++安装程序，VisualC++应用程序的开发主要有两种模式，一种是WINAPI方式，另一种则是MFC方式，传统的WINAPI开发方式比较繁琐，而MFC则是对WINAPI再次封装，所以MFC相对于WINAPI

8、开发更具备效率优势。本软件中因为程序主要是为了实现某个算法所以这里没有用到MFC。第26页哈希表的设计与实现第2章系统功能分析第2章系统功能分析2.1系统功能需求分析实现本程序需要解决以下几个问题：1.设计一个结点使该结点包括电话号码、用户名、QQ等结点信息。2.利用用户名为关键字建立哈希表，哈希函数用除留余数法构照。3.利用链表法处理冲突问题。4.实现用哈希法查找并显示给定姓名的记录。5.显示哈希