没有合适的资源?快使用搜索试试~ 我知道了~
利用哈希表进行存储 针对一组数据进行初始化哈希表,可以进行显示哈希表,查找元素,插入元素,删除元素,退出程序操作
需积分: 1 4 下载量 41 浏览量
2023-05-04
23:40:05
上传
评论
收藏 151KB DOCX 举报
温馨提示
试读
11页
【问题描述】 利用哈希表进行存储。针对一组数据进行初始化哈希表,可以进行显示哈希表,查找元素,插入元素,删除元素,退出程序操作。 【任务要求】 (1)用户可以进行创建哈希表,显示哈希表,查找元素,插入元素,删除元素。 (2)设计思想:哈希函数用除留余数法构造,用线性探测再散列处理冲突。 (3)显示元素:显示已经创建的哈希表。 (4)查找元素:查找哈希表中的元素,分为查找成功和查找不成功。 (5)插入元素:在哈希表中,插入一个元素,分为插入成功和失败。 (6)删除元素:在已有的数据中,删除一个元素。 (7)退出系统:退出程序。 涉及的数据结构知识点和算法: ①哈希表(Hash table) ②哈希函数(Hash function) ③冲突处理方法(Collision resolution) ④除留余数法(Modulo hashing) ⑤线性探测再散列法(Linear probing) 概述: 哈希表(Hash table)是一种基于哈希函数(Hash function)实现的数据结构,用于实现关联数组或者映射等抽象数据类型。哈希表将元素的键(key)通过哈希函数转换为哈希值
资源推荐
资源详情
资源评论
哈希表应用
一、【问题描述】
利用哈希表进行存储。
任务要求:针对一组数据进行初始化哈希表,可以进行显示哈希表,查找元素,插入元
素,删除元素,退出程序操作。
设计思想:哈希函数用除留余数法构造,用线性探测再散列处理冲突。
设计目的:实现哈希表的综合操作
简体中文控制台界面:用户可以进行创建哈希表,显示哈希表,查找元素,插入元素,
删除元素。
显示元素:显示已经创建的哈希表。
查找元素:查找哈希表中的元素,分为查找成功和查找不成功。
插入元素:在哈希表中,插入一个元素,分为插入成功和失败。
删除元素:在已有的数据中,删除一个元素。
退出系统:退出程序。
测试数据:
自行设定,注意边界等特殊情况
二、【设计思路】
1.引言
在数据结构中所提到的查找算法中,其查找过程都需要依据关键字进行若干次比较,最
后确定在查找表中是否存在给定关键字的元素。查找的效率与比较次数密切相关,在查找时
需要不断进行比较的原因是在建立数据表时,只考虑了各数据元素的关键字之间的相对大小,
而数据元素在表中的位置和其关键字无直接关系。如果在数据元素的存储位置和其关键字之
间建立某种关系,那么在查找时就无需进行比较或只做少数比较就直接由关键字找到相应存
储位置。哈希表正是基于这种思想。
若关键字为 k,则其值存放在 f(k)的存储位置上。由此,不需比较便可直接取得所查记
录。称这个对应关系 f 为散列函数,对不同的关键字可能得到同一散列地址,即 k1≠k2,
而 f(k1)=f(k2),这种现象称为碰撞。具有相同函数值的关键字对该散列函数来说称做同义
词。综上所述,根据散列函数 f(k)和处理碰撞的方法将一组关键字映射到一个有限的连续
的地址集上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为散
列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。
若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概
率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键
字经过散列函数得到一个“随机的地址”,从而减少碰撞。
其中处理冲突的一种方法是除留余数法:取关键字被某个不大于散列表表长 m 的数 p 除
后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模,也
可在折叠、平方取中等运算之后取模。对 p 的选择很重要,一般取素数或 m,若 p 选的不好,
容易产生同义词。
1. 开放寻址法:Hi=(H(key) + di) MOD m,i=1,2,…,k(k<=m-1),其中 H(key)为散列
函数,m 为散列表长,di 为增量序列,可有下列三种取法:
(1) di=1,2,3,…,m-1,称线性探测再散列;
(2)di=1^2,-1^2,2^2,-2^2,⑶^2,…,±(k)^2,(k<=m/2)称二次探测再散列;
(3)di=伪随机数序列,称伪随机探测再散列。
2. 再散列法:Hi=RHi(key),i=1,2,…,k RHi 均是不同的散列函数,即在同义词产生
地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但
增加了计算时间。
3. 链地址法(拉链法)
4. 建立一个公共溢出区散列表的查找过程基本上和造表过程相同。
2.需求分析
哈希表是种数据结构,它可以提供快速的插入操作和查找操作。哈希表也有一些缺点它
是基于数组的,数组创建后难于扩展某些哈希表被基本填满时,性能下降得非常严重。这个
问题是哈希表不可避免的,即冲突现象:对不同的关键字可能得到同一哈希地址。
即一些关键码可通过散列函数转换的地址直接找到,另一些关键码在散列函数得到的
地址上产生了冲突,需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中,产
生冲突后的查找仍然是给定值与关键码进行比较的过程。所以,对散列表查找效率的量度,
依然用平均查找长度来衡量。查找过程中,关键码的比较次数,取决于产生冲突的多少,产
生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因
素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:
(1) 散列函数是否均匀;
(2)处理冲突的方法;
(3)散列表的装填因子。
散列表的装填因子定义为:α= 填入表中的元素个数 / 散列表的长度
α是散列表装满程度的标志因子。由于表长是定值,α与“填入表中的元素个数”成正比,
所以,α越大,填入表中的元素较多,产生冲突的可能性就越大;α越小,填入表中的元素
较少,产生冲突的可能性就越小。实际上,散列表的平均查找长度是装填因子α的函数,只
是不同处理冲突的方法有不同的函数。
哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常
数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空
间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。但是,不能够保证每个
元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同
的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素分在了相同的“类”之中。
总的来说,“直接定址”与“解决冲突”是哈希表的两大特点。
3.数据结构
本算法采用顺序表实现。
typedef struct node
{
int key; //关键字
int count; //线性探测次数
}Haxi[M];
4.算法设计
哈希表是一种重要的存储方式,也是一种常见的检索方法。其基本思想是将关系码的值
作为自变量,通过一定的函数关系计算出对应的函数值,把这个数值解释为结点的存储地址,
将结点存入计算得到存储地址所对应的存储单元。检索时采用检索关键码的方法。
算法流程图:
其中个别模块流程图如下:
Y
N
开始
选 择 操 作
删除
插入
建表
查找
线性探测
输入关键字
显 示 输 出 结 果
退出
输入
在哈希表中
比较
返回 ture
返回 false
相同
剩余10页未读,继续阅读
资源评论
小柒_02
- 粉丝: 9
- 资源: 13
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于STM32F103C8T6单片机蓄电池在线监测系统主板硬件(原理图+PCB)工程文件.zip
- mysql大纲资料.txt
- c++大纲资料.txt
- 效率工具bat脚本实现日志提取
- MyBatis 中动态 SQL 的示例
- STM8L101F3P6单片机+CC1100模块433M遥控器设计硬件(原理图+PCB)工程文件.zip
- 上传下载铁人下载系统 Liuxing 1.0-liuxing1.0.rar
- 南京邮电大学数学实验实力雄厚,凭借其优秀的师资力量、丰富的实践教学资源和卓越的科研成果,成为国内一流的数学实验教学和科研基地
- 【火爆朋友圈的今天吃什么源码 v1.0】随机的为用户带来每一天的用餐选择和推荐.rar
- MPU6050中文版数据手册
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功