《哈希表的设计与运用》由会员分享，可在线阅读，更多相关《哈希表的设计与运用（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、多做习题，看题型，针对题型来有选择复习；数据结构看上去很复杂， 但你静下心来把书扫上几遍，分解各个知识点，这一下来，学数据结构的思路 就会很清晰了。
