《哈希表的设计与运用》由会员分享,可在线阅读,更多相关《哈希表的设计与运用(22页珍藏版)》请在金锄头文库上搜索。
1、目目 录录第第 1 1 章章 需求分析需求分析 第第 2 2 章章 概要设计概要设计 第第 3 3 章章 详细设计详细设计 第第 4 4 章章 调试分析调试分析.第第 5 5 章章 核心源程序清单和执行结果核心源程序清单和执行结果.第第 6 6 章章 设计体会设计体会.第第 7 7 章章 附录附录.第 1 章 需求分析1.问题描述:针对某个集体(比如你所在的班级)中的人名设计一个哈希表, 使得平均查找长度不超过 R,完成相应的建表和查表程序;2.人名为中国人姓名的汉语拼音,人名有 30 个,平均查找长度的上限为 2;3.用伪随机探测再散列法处理冲突;4.输入为所要查询的人姓名(拼音) ;输出为
2、该关键字的查找信息;5.测试数据:输入:lihaojie输出:姓名:lihaojie 关键字:837 查找长度:1输入:wangzhou输出:姓名:wangzhou 关键字: 查找长度:3输入:d输出:显示哈希表6.本程序用 C+语言编写,在 vc+6.0 环境下运行。第 2 章 概要设计2.1 算法思想:1 定义:哈希表是为了便于快速搜索而组织的键/值组合的集合。Hash Table 是一种数 组,可以用任意简单变量值来访问其元素,这种数组叫哈希表。2 优点:哈希表最大的优点就是把数据的存储和查找消耗的时间大大降低,几乎可以看 成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存
3、越来 越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的 特点之一。3 基本原理:使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数, 也叫做散列函数) ,使得每个元素的关键字都与一个函数值(即数组下标,hash 值)存在一一对应的关系,于是用这个数组单元来存储这个元素。也可以简单 的理解为,按照关键字为每一个元素“分类” 。4 哈希表的不可避免冲突(collision)现象:对不同的关键字可能得到同一个哈希地址 即 key1key2,而 f(key1)=f(key2)。 因此,在建造哈希表时不仅要设定一个好的哈希函数,而且要设定一种处理冲 突的方法。用伪随机
4、探测法。求下一个开放地址的公式为:Hi = (H(k)+di) MOD m 注意:Di=伪随机数序列;2.2 关于程序设计的基本操作:1.对哈希表的操作InitNameList()操作结果:姓名(结构体数组)初始化CreateHashList()操作结果:建立哈希表FindList()操作结果:在哈希表中查找Display()操作结果:显示哈希表2.主程序int main()初始化;InitNameList();CreateHashList();do 接受命令;处理命令;while(“命令”=“退出” ) ; return 0;3.本程序包含的模块1)初始化操作,结构体定义;2)姓名结构体建立
5、模块;3)建立哈希表模块;4)查找模块;5)显示哈希表模块;4)主程序模块4 程序流程图建立哈希表初始化姓名显示哈希表表查找 主程序第 3 章 详细设计主要功能模块:模块一:建立哈希表void CreateHashList() /建立哈希表 int i;for(i=0; i#includeusing namespace std;#define HASH_LENGTH 50 /哈希表的长度 #define M 47 /取余随机数#define NAME_NO 30 /人名的个数 typedef struct char *py; /名字的拼音int k; /名字所对应的关键字NAME;NAME N
6、ameListHASH_LENGTH; /全局变量 NAME typedef struct /哈希表 char *py; /名字的拼音int k; /拼音所对应的整数int si; /查找长度HASH;HASH HashListHASH_LENGTH; /全局变量 HASH /*姓名(结构体数组)初始化 */void InitNameList() char *f;int r,s0,i;for (i=0; iname;for(r=0;rx)if(x=d)Display();coutendl;else if(x=f)FindList();coutendl;else break;for (int i
7、=0; iHASH_LENGTH; i+)free(NameListi.py);free(HashListi.py);return 0;2.运行结果展示:主界面显示:进行操作 d,显示哈希表中的所有信息:进行操作 f,查找姓名:lihaojie进行操作 f,查找姓名:huangxinglong进行操作 f,查找姓名:lizhuoqun进行操作 f,查找姓名:wangzejun第 6 章 设计体会做了一个星期的程序设计终于做完了,在这次程序设计课中,我选择的课题 是哈希表的设计。此次的课程设计真是让我获益匪浅,我突然发现写程序还挺 有意思的。由于上学期的 C 语言跟这学期的数据结构都算不上真正的
8、懂,对于书上的 稍微难点的知识就是是而非的,所以我只是对老师的程序理解,我也试着去改 变了一些变量,自己也尽量多的去理解老师做程序的思路。当我第一天坐在那 里的时候,我就不知道该做些什么,后来我只有下来自己看了一遍书来熟悉下 以前学过的知识。通过这次的程序设计,发现一个程序设计就是算法与数据结构的结合体, 自己也开始对程序产生了前所未有的兴趣,以前偷工减料的学习也不可能一下 子写出一个程序出来,于是我就认真看老师写的程序,发现我们看懂了一个程 序其实不难,难的是对于一个程序的思想的理解,我们要掌握一个算法,不仅 仅限于读懂,主要的是要理解老师的思路,学习老师的解决问题的方法。这次试验中,我发现
9、书本上的知识是一个基础,但是我基础都没掌握,更 别说写出一个整整的程序了。自己在写程序的时候,也发现自己的知识太少了, 特别是基础知识很多都是模模糊糊的一个概念,没有落实到真正的程序,所以 自己写的时候也感到万分痛苦,基本上涉及一个知识我就会去看看书,对于书 本上的知识没掌握好。在饭后闲暇时间我也总结了一下,自己以前上课也认真 的听了,但是还是写不出来,这主要归结于自己的练习太少了,而且也总是半 懂就不管了。在改写老师的程序中也出现了很多的问题,不断的修改就是不断 的学习过程,当我们全身心的投入其中时,实际上是一件很有乐趣的事情。对于以后的学习有了几点总结:第 1、熟记各种数据结构类型,定义、特点、基本运算(分开点一点也没多 少东西,难度不大,但是基本) ;第 2、第二、各种常用的排序算法,如冒泡排序、堆排序,这些是必考 的内容,分数不会少于 20%;第 3、多做习题,看题型,针对题型来有选择复习;数据结构看上去很复杂, 但你静下心来把书扫上几遍,分解各个知识点,这一下来,学数据结构的思路 就会很清晰了。