C语言实现哈希查找之线性探测算法
C语言中实现一个简单的哈希表,并包括线性探测和二次探测再散列处理冲突的功能:
1. 定义哈希表结构
首先,定义一个哈希表的结构,包括存储空间、哈希表的大小等。
2. 实现哈希函数
选择一个合适的哈希函数来计算键值的哈希值。
3. 实现插入和查找功能
使用哈希函数计算元素的哈希值,并将元素插入到哈希表中。如果发生冲突,使用线性探测或二次探测再散列来解决。
4. 计算平均查找长度 ASL
平均查找长度(ASL)可以通过模拟多次查找操作并计算平均查找步数来得到。
5. 实现线性探测和二次探测再散列
线性探测在发生冲突时,顺序查找下一个空闲位置。二次探测再散列则是在冲突时,以二次方的偏移量查找空闲位置。
下面是一个使用线性探测再散列处理冲突的C语言哈希表的简单实现:
#include <stdio.h>
#include <stdlib.h>#define TABLE_SIZE 10 // 哈希表的大小typedef struct {int key;int data;
} HashTableItem;// 使用 -1 表示空闲位置
HashTableItem* hashTable[TABLE_SIZE];unsigned int hashFunction(int key) {return key % TABLE_SIZE;
}void initHashTable() {for (int i = 0; i < TABLE_SIZE; i++) {hashTable[i] = NULL;}
}void insert(int key, int data) {unsigned int index = hashFunction(key);unsigned int startIndex = index;HashTableItem *item = (HashTableItem*) malloc(sizeof(HashTableItem));item->data = data;item->key = key;while (hashTable[index] != NULL && hashTable[index]->key != -1) {index = (index + 1) % TABLE_SIZE;// 回到起始位置,表明哈希表已满if (index == startIndex) {printf("哈希表已满\n");return;}}hashTable[index] = item;
}HashTableItem* search(int key) {unsigned int index = hashFunction(key);unsigned int startIndex = index;while (hashTable[index] != NULL) {if (hashTable[index]->key == key) {return hashTable[index];}index = (index + 1) % TABLE_SIZE;// 如果回到起始位置,则表示元素不在哈希表中if (index == startIndex) return NULL;}return NULL;
}void printHashTable() {for (int i = 0; i < TABLE_SIZE; i++) {if (hashTable[i] != NULL && hashTable[i]->key != -1) {printf("位置 %d: Key = %d, Data = %d\n", i, hashTable[i]->key, hashTable[i]->data);} else {printf("位置 %d: 空\n", i);}}
}int main() {initHashTable();insert(1, 10);insert(2, 20);insert(11, 30); // 将与键1发生冲突printHashTable();HashTableItem* item = search(11);if (item != NULL) {printf("找到键 11: Data = %d\n", item->data);} else {printf("未找到键 11\n");}return 0;
}
在这个例子中,我们初始化了一个大小为10的哈希表,并实现了插入和查找功能,使用线性探测来处理冲突。
相关文章:
C语言实现哈希查找之线性探测算法
C语言中实现一个简单的哈希表,并包括线性探测和二次探测再散列处理冲突的功能: 1. 定义哈希表结构 首先,定义一个哈希表的结构,包括存储空间、哈希表的大小等。 2. 实现哈希函数 选择一个合适的哈希函数来计算键值的哈希值。 …...
js:lodash template文件模板语法和应用
文档 https://www.lodashjs.com/docs/lodash.templatehttps://lodash.com/docs/4.17.15#template 语法 <% VALUE %> 用来做不转义插值;<%- VALUE %> 用来做 HTML 转义插值;<% expression %> 用来描述 JavaScript 流程控制。 示例 …...
在Windows系统上安装Docker和SteamCMD容器的详细指南有哪些?
在Windows系统上安装Docker和SteamCMD容器的详细指南有哪些? 安装Docker: 首先,需要在Windows操作系统上激活WSL2功能。这是因为Docker作为一个容器工具,依赖于已存在并运行的Linux内核环境。可以通过使用winget来安装Docker。具体…...
点击输入框,获取提示信息
HTML结构代码 <body><input><p>单击输入框获取焦点。</p><span>请输入你的电话号码?</span></body> Java script代码 <script type"text/JavaScript">let pdocument.getElementsByTagName(input)[0];console.lo…...
房贷计算器微信小程序原生语言
微信小程序: 房贷计算器 效果: 输入 300万 结果 还款明细 一共有3个页面 1、输入页面 2、结果页面 3、详情页面 1 index页面 index.wxml文件 <view class="text-black"><!--房屋总价--><view class="cu-bar bg-white solid-bottom"&…...
【C++从0到王者】第四十六站:图的深度优先与广度优先
文章目录 一、图的遍历二、广度优先遍历1.思想2.算法实现3.六度好友 三、深度优先遍历1.思想2.代码实现 四、其他问题 一、图的遍历 对于图而言,我们的遍历一般是遍历顶点,而不是边,因为边的遍历是比较简单的,就是邻接矩阵或者邻接…...
Docker技术概论(2):Docker环境的搭建
Docker技术概论(2) Docker环境的搭建 - 文章信息 - Author: 李俊才 (jcLee95) Visit me at: https://jclee95.blog.csdn.netMy WebSite:http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this article:https://blo…...
电脑休眠之后唤不醒
现象:午休时间电脑休眠了,醒来之后发现在密码输入界面,但鼠标键盘没反应。按重启键或电源机重新开机,结果开不了机。 原因:1、内存条脏了,导致内存条读取失败 2、休眠的时候硬盘休眠了,导致按…...
Python列表中添加删除元素不走弯路
1.append() 向列表中添加单个元素,一般用于尾部追加 list1 ["香妃", "乾隆", "贾南风", "赵飞燕", "汉武帝"]list1.append("周瑜") print(list1) # [香妃, 乾隆, 贾南风, 赵飞燕, 汉武帝, 周瑜]…...
MATLAB环境下脑电信号EEG的谱分析
脑电信号一直伴随着人类的生命,脑电波是脑神经细胞发生新陈代谢、离子交换时细胞群兴奋突触电位总和,脑电信号的节律性则和丘脑相关,含有丰富的大脑活动信息。通常我们所接触的脑电图都是头皮脑电图,在有些特殊场合还需要皮下部位…...
librtmp源码分析
阅读了librtmp的源码,简单记录下。 首先补充下AMF格式基本知识 1 AMF格式 AMF是Action Message Format(动作消息格式)的简写,它是一种二进制的数据格式。它的设计是为了把actionscript里面的数据(包括Object, Array, Boolean, Number等)序列化成二进制…...
CCDP.00.问老师问题前你首先需要做的事情
一、一定要按老师要求做好快照!!!!! 1、在关键节点处,比如做完Part1后,关机状态下做快照。 2、在做没把握的操作前先做快照(这个可以在开机状态下做快照,但推荐关机状态…...
「算法」常见位运算总结
位运算符 异或 按位异或可以实现无进位相加,所谓无进位相加,就是在不考虑进位的情况下将两个数相加(后面有道题需要用到这种操作) 异或的运算律 ①a ^ 0 a ②a ^ a 0 ③a ^ b ^ c a ^ ( b ^ c ) 有符号右移>> 将一个…...
【C++初识】语句
文章目录 1.注释 变量 常量 关键字 标识符命名规则 数据类型 sizeof关键字 数据的输入 运算符2.程序流程结构2.1选择结构2.2循环结构2.21while{循环条件}{循环语句};//满足循环条件,执行循环语句2.22do{循环语句}while{循环条件};//do....whi…...
Python线性代数傅里叶分析和动态系统模拟分析之一
要点 Python向量数值计算、可视化,线性独立性和子空间。了解欧几里德距离、余弦相似度和皮尔逊相关性应用案例:Python数值计算文档相似度时间序列和特征检测示例:Python信号处理边缘检测器, K均值示例:随机簇质心分布Python傅里叶…...
mysql插入GEOMETRY相关字段类型(point,linestring等)
一、问题 向mysql中插入point,linestring等相关空间坐标字段,出现报错: 1416 - Cannot get geometry object from data you send to the GEOMETRY field要插入的数据:...
vue3学习 【5】watch的使用
什么是watch 当我们需要根据一个数据的变化来进行一些操作的时候我们需要使用侦听器,它能够在响应式数据发生变化的时候触发提供的回调函数 基础侦听 watch 可以侦听不同的数据源。例如: ref计算属性响应式对象getter函数多个数据源组层的数据 cons…...
PyTorch深度学习快速入门
PyTorch深度学习快速入门 1.PyTorch环境配置及安装2.python编辑器的选择、安装、配置(pycharm、JupyTer安装)3.为什么torch.cuda.is_available()返回false4.python学习中两大法宝函数(也可用在pytorch)5.pycharm和jupyter…...
种花
分情况: 第一盆k种选择,之后全部k-1种选择 每次相乘结果对1e97取模 #include <iostream> #include <vector> #include <algorithm> using namespace std; #define endl \n const int N 1e9 7;int main() {ios::sync_with_stdio(f…...
Android Shadow插件化框架分析与集成(二)
本文索引 前言插件打包后如何交给宿主使用?宿主加载插件代码分析全局初始化操作加载插件activity测试过程中遇到的问题报错 1 :报错2:报错3 :二次开发支持多插件、多进程功能mPpsController 的构造方式mPluginLoader的构造方式多插件如何改造前言...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...
pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...
