当前位置: 首页 > news >正文

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语言中实现一个简单的哈希表&#xff0c;并包括线性探测和二次探测再散列处理冲突的功能&#xff1a; 1. 定义哈希表结构 首先&#xff0c;定义一个哈希表的结构&#xff0c;包括存储空间、哈希表的大小等。 2. 实现哈希函数 选择一个合适的哈希函数来计算键值的哈希值。 …...

js:lodash template文件模板语法和应用

文档 https://www.lodashjs.com/docs/lodash.templatehttps://lodash.com/docs/4.17.15#template 语法 <% VALUE %> 用来做不转义插值&#xff1b;<%- VALUE %> 用来做 HTML 转义插值&#xff1b;<% expression %> 用来描述 JavaScript 流程控制。 示例 …...

在Windows系统上安装Docker和SteamCMD容器的详细指南有哪些?

在Windows系统上安装Docker和SteamCMD容器的详细指南有哪些&#xff1f; 安装Docker&#xff1a; 首先&#xff0c;需要在Windows操作系统上激活WSL2功能。这是因为Docker作为一个容器工具&#xff0c;依赖于已存在并运行的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.代码实现 四、其他问题 一、图的遍历 对于图而言&#xff0c;我们的遍历一般是遍历顶点&#xff0c;而不是边&#xff0c;因为边的遍历是比较简单的&#xff0c;就是邻接矩阵或者邻接…...

Docker技术概论(2):Docker环境的搭建

Docker技术概论&#xff08;2&#xff09; Docker环境的搭建 - 文章信息 - Author: 李俊才 (jcLee95) Visit me at: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 291148484163.com. Shenzhen ChinaAddress of this article:https://blo…...

电脑休眠之后唤不醒

现象&#xff1a;午休时间电脑休眠了&#xff0c;醒来之后发现在密码输入界面&#xff0c;但鼠标键盘没反应。按重启键或电源机重新开机&#xff0c;结果开不了机。 原因&#xff1a;1、内存条脏了&#xff0c;导致内存条读取失败 2、休眠的时候硬盘休眠了&#xff0c;导致按…...

Python列表中添加删除元素不走弯路

1.append() 向列表中添加单个元素&#xff0c;一般用于尾部追加 list1 ["香妃", "乾隆", "贾南风", "赵飞燕", "汉武帝"]list1.append("周瑜") print(list1) # [香妃, 乾隆, 贾南风, 赵飞燕, 汉武帝, 周瑜]…...

MATLAB环境下脑电信号EEG的谱分析

脑电信号一直伴随着人类的生命&#xff0c;脑电波是脑神经细胞发生新陈代谢、离子交换时细胞群兴奋突触电位总和&#xff0c;脑电信号的节律性则和丘脑相关&#xff0c;含有丰富的大脑活动信息。通常我们所接触的脑电图都是头皮脑电图&#xff0c;在有些特殊场合还需要皮下部位…...

librtmp源码分析

阅读了librtmp的源码&#xff0c;简单记录下。 首先补充下AMF格式基本知识 1 AMF格式 AMF是Action Message Format(动作消息格式)的简写&#xff0c;它是一种二进制的数据格式。它的设计是为了把actionscript里面的数据(包括Object, Array, Boolean, Number等)序列化成二进制…...

CCDP.00.问老师问题前你首先需要做的事情

一、一定要按老师要求做好快照&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 1、在关键节点处&#xff0c;比如做完Part1后&#xff0c;关机状态下做快照。 2、在做没把握的操作前先做快照&#xff08;这个可以在开机状态下做快照&#xff0c;但推荐关机状态…...

「算法」常见位运算总结

位运算符 异或 按位异或可以实现无进位相加&#xff0c;所谓无进位相加&#xff0c;就是在不考虑进位的情况下将两个数相加&#xff08;后面有道题需要用到这种操作&#xff09; 异或的运算律 ①a ^ 0 a ②a ^ a 0 ③a ^ b ^ c a ^ ( b ^ c ) 有符号右移>> 将一个…...

【C++初识】语句

文章目录 1.注释 变量 常量 关键字 标识符命名规则 数据类型 sizeof关键字 数据的输入 运算符2.程序流程结构2.1选择结构2.2循环结构2.21while{循环条件}{循环语句}&#xff1b;//满足循环条件&#xff0c;执行循环语句2.22do{循环语句}while{循环条件}&#xff1b;//do....whi…...

Python线性代数傅里叶分析和动态系统模拟分析之一

要点 Python向量数值计算、可视化&#xff0c;线性独立性和子空间。了解欧几里德距离、余弦相似度和皮尔逊相关性应用案例&#xff1a;Python数值计算文档相似度时间序列和特征检测示例&#xff1a;Python信号处理边缘检测器, K均值示例&#xff1a;随机簇质心分布Python傅里叶…...

mysql插入GEOMETRY相关字段类型(point,linestring等)

一、问题 向mysql中插入point&#xff0c;linestring等相关空间坐标字段&#xff0c;出现报错&#xff1a; 1416 - Cannot get geometry object from data you send to the GEOMETRY field要插入的数据&#xff1a;...

vue3学习 【5】watch的使用

什么是watch 当我们需要根据一个数据的变化来进行一些操作的时候我们需要使用侦听器&#xff0c;它能够在响应式数据发生变化的时候触发提供的回调函数 基础侦听 watch 可以侦听不同的数据源。例如&#xff1a; ref计算属性响应式对象getter函数多个数据源组层的数据 cons…...

PyTorch深度学习快速入门

PyTorch深度学习快速入门 1.PyTorch环境配置及安装2.python编辑器的选择、安装、配置&#xff08;pycharm、JupyTer安装&#xff09;3.为什么torch.cuda.is_available()返回false4.python学习中两大法宝函数&#xff08;也可用在pytorch&#xff09;5.pycharm和jupyter&#xf…...

种花

分情况&#xff1a; 第一盆k种选择&#xff0c;之后全部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的构造方式多插件如何改造前言...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...

Axure 下拉框联动

实现选省、选完省之后选对应省份下的市区...