实现一个简单的哈希表

1. 结构体定义 

typedef struct pair {int key;                   // 哈希表中的键，通常是整数类型char element[20];          // 关联的字符串元素，最多存储20个字符
} DATA, * LPDATA;

 pair 结构体表示哈希表中的一个元素，包含两个字段：

  • key：这是一个整数，作为哈希表的键，通常用于查找或存储值。
  • element：一个字符数组，用来存储与 key 关联的字符串数据。这个字段的大小为 20，这意味着每个元素最多可以存储 19 个字符（最后一个字符用于存储字符串的结束符 '\0'）。
typedef struct hashTable {LPDATA* table;             // 一个指针数组，存储哈希表的桶，每个桶包含一个指向 DATA 的指针int divisor;               // 哈希表的大小，决定了桶的数量int curSize;               // 当前哈希表中存储的元素数量
} HASH, * LPHASH;

hashTable 结构体代表哈希表本身，包含以下字段：

  • table：指向一个 LPDATA 类型的指针数组。每个 LPDATA 是一个指向 DATA 结构体的指针，表示哈希表中的一个桶。
  • divisor：哈希表的大小，决定了哈希表中桶的数量。
  • curSize：当前哈希表中已经存储的元素数量。

2. 创建哈希表函数 createHashTable 

LPHASH createHashTable(int p) {LPHASH hash = (LPHASH)malloc(sizeof(HASH));  // 分配内存为哈希表结构体assert(hash != NULL);  // 确保内存分配成功hash->curSize = 0;                // 初始化哈希表的当前大小为 0hash->divisor = p;                // 设置哈希表的大小hash->table = (LPDATA*)malloc(sizeof(LPDATA) * hash->divisor);  // 为桶数组分配内存assert(hash->table != NULL);  // 确保内存分配成功// 初始化哈希表中的所有桶指针为 NULL，表示所有桶都是空的for (int i = 0; i < hash->divisor; i++) {hash->table[i] = NULL;}return hash;  // 返回创建的哈希表指针
}

 功能：createHashTable 函数用于创建一个哈希表：

  • 使用 malloc 为哈希表结构体分配内存。
  • 设置哈希表的大小为 p，并为桶数组 table 分配内存，每个桶存储一个指向 DATA 结构体的指针。
  • 初始化哈希表中的所有桶为 NULL，表示它们还没有存储任何元素。
  • 返回创建的哈希表指针。

3. 查找函数 search 

int search(LPHASH hash, int key) {int pos = key % hash->divisor;  // 计算哈希值，得到该元素应放置的初始位置int curpos = pos;               // 当前的位置初始化为计算得到的初始位置// 线性探测法查找位置，直到找到空位或已有相同 key 的位置do {if (hash->table[curpos] == NULL || hash->table[curpos]->key == key) {return curpos;  // 如果当前位置为空，或者找到了相同的 key，返回当前的位置}// 如果当前位置被占用且 key 不相同，采用线性探测法，检查下一个位置curpos = (curpos + 1) % hash->divisor;  // 如果超出了表的末尾，则环绕到表的开始位置} while (curpos != pos);  // 如果回到初始位置，表示表已满return -1;  // 如果哈希表已满，返回 -1
}

 功能：search 函数使用线性探测法查找合适的位置插入一个元素或查找一个已有的元素。

  • 首先，计算该元素的哈希值，决定该元素应放置的初始位置。
  • 然后，使用线性探测法（如果当前位置被占用，检查下一个位置）查找该位置。如果当前位置为空或者找到了相同 key 的元素，返回当前位置。
  • 如果遍历完整个哈希表（回到起始位置），说明哈希表已满，返回 -1。

4. 插入数据函数 insertData 

void insertData(LPHASH hash, DATA data) {// 如果哈希表已满，无法插入新数据if (hash->curSize >= hash->divisor) {printf("Hash table is full!\n");return;}// 查找数据的插入位置int pos = search(hash, data.key);// 如果返回 -1，表示表已满，无法插入if (pos == -1) {printf("Hash table is full, cannot insert new data.\n");return;}// 如果该位置为空，插入数据if (hash->table[pos] == NULL) {hash->table[pos] = (LPDATA)malloc(sizeof(DATA));  // 为该位置分配内存assert(hash->table[pos] != NULL);  // 确保内存分配成功// 将数据复制到该位置memcpy(hash->table[pos], &data, sizeof(DATA));hash->curSize++;  // 更新当前哈希表大小}// 如果该位置已经存在相同的 key，则更新该位置的 elementelse if (hash->table[pos]->key == data.key) {// 使用 strncpy 避免字符串溢出，确保 element 的长度不会超过 19 个字符strncpy(hash->table[pos]->element, data.element, sizeof(hash->table[pos]->element) - 1);hash->table[pos]->element[sizeof(hash->table[pos]->element) - 1] = '\0';  // 确保字符串以 '\0' 结尾}else {printf("Key already exists, but handled by rehashing mechanism.\n");}
}

 功能：insertData 函数用于将一个 DATA 数据插入哈希表中：

  • 首先检查哈希表是否已满，如果已满，打印提示并返回。
  • 使用 search 函数查找插入位置。如果返回 -1，表示哈希表已满，无法插入。
  • 如果该位置为空，分配内存存储数据并将数据复制到该位置，并增加当前哈希表大小。
  • 如果该位置已存在相同 key，则使用 strncpy 安全地更新该位置的 element 字段。

5. 打印哈希表函数 printHash 

void printHash(LPHASH hash) {for (int i = 0; i < hash->divisor; i++) {if (hash->table[i] == NULL) {printf("NULL\n");  // 如果桶为空，打印 NULL}else {// 打印当前桶中的 key 和 elementprintf("Key:%d Element:%s\n", hash->table[i]->key, hash->table[i]->element);}}
}

 功能：printHash 函数遍历哈希表中的所有桶，打印每个桶的内容：

  • 如果桶为空（即该位置为 NULL），打印 "NULL"。
  • 如果桶不为空，则打印该桶的 key 和 element。

6. 主函数 main 

int main() {// 创建一个大小为 10 的哈希表LPHASH hash = createHashTable(10);// 定义一个 DATA 数组，包含 4 个元素DATA array[4] = { {1, "雷电"}, {11, "春妙"}, {13, "晓月"}, {17, "雪月"} };// 将数组中的数据插入到哈希表中for (int i = 0; i < 4; i++) {insertData(hash, array[i]);}// 打印哈希表的内容printHash(hash);// 释放哈希表中每个桶存储的数据内存for (int i = 0; i < hash->divisor; i++) {if (hash->table[i] != NULL) {free(hash->table[i]);  // 释放每个桶中的 DATA 元素内存}}// 释放存储桶指针数组的内存free(hash->table);// 释放哈希表结构体本身的内存free(hash);return 0;  // 程序执行成功，返回 0
}

 

  • 创建一个大小为 10 的哈希表。
  • 定义并插入 4 个 DATA 数据元素到哈希表中。
  • 打印哈希表的内容，查看每个桶的 key 和 element。
  • 在程序结束时，释放所有分配的内存，包括哈希表元素和哈希表结构本身。

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <memory.h>// 定义一个结构体 'pair'，表示哈希表中的一个数据元素
// 包含两个字段：key 和 element
typedef struct pair {int key;                   // 哈希表中的键char element[20];          // 关联的字符串元素，假设最大长度为 20
} DATA, * LPDATA;// 定义哈希表结构体
typedef struct hashTable {LPDATA* table;             // 存储元素的桶数组，每个桶存储一个 DATA 指针int divisor;               // 哈希表的大小，决定了桶的数量int curSize;               // 当前哈希表中的元素数量
} HASH, * LPHASH;// 创建一个哈希表
LPHASH createHashTable(int p) {LPHASH hash = (LPHASH)malloc(sizeof(HASH));  // 为哈希表结构体分配内存assert(hash != NULL);  // 检查内存分配是否成功hash->curSize = 0;                // 初始化哈希表的当前大小为 0hash->divisor = p;                // 设置哈希表的大小hash->table = (LPDATA*)malloc(sizeof(LPDATA) * hash->divisor);  // 为桶数组分配内存assert(hash->table != NULL);  // 检查内存分配是否成功// 初始化哈希表中的所有桶指针为 NULL，表示所有桶都是空的for (int i = 0; i < hash->divisor; i++) {hash->table[i] = NULL;}return hash;  // 返回创建的哈希表指针
}// 查找指定 key 的位置
int search(LPHASH hash, int key) {int pos = key % hash->divisor;  // 使用哈希函数计算初始位置int curpos = pos;               // 当前位置初始化为计算得到的初始位置// 线性探测法查找位置，直到找到空位或已有相同 key 的位置do {if (hash->table[curpos] == NULL || hash->table[curpos]->key == key) {return curpos;  // 如果当前位置为空，或者找到了相同的 key，返回当前的位置}// 如果当前位置被占用且 key 不相同，采用线性探测法，检查下一个位置curpos = (curpos + 1) % hash->divisor;  // 如果超出了表的末尾，则环绕到表的开始位置} while (curpos != pos);  // 如果回到初始位置，表示表已满return -1;  // 如果哈希表已满，返回 -1
}// 插入数据到哈希表
void insertData(LPHASH hash, DATA data) {// 如果哈希表已满，无法插入新数据if (hash->curSize >= hash->divisor) {printf("Hash table is full!\n");return;}// 查找数据的插入位置int pos = search(hash, data.key);// 如果返回 -1，表示表已满，无法插入if (pos == -1) {printf("Hash table is full, cannot insert new data.\n");return;}// 如果该位置为空，插入数据if (hash->table[pos] == NULL) {hash->table[pos] = (LPDATA)malloc(sizeof(DATA));  // 分配内存存储数据assert(hash->table[pos] != NULL);  // 确保内存分配成功// 将数据复制到该位置memcpy(hash->table[pos], &data, sizeof(DATA));hash->curSize++;  // 更新当前哈希表大小}// 如果该位置已经存在相同的 key，则更新该位置的 elementelse if (hash->table[pos]->key == data.key) {// 使用 strncpy 避免字符串溢出，确保 element 的长度不会超过 19 个字符strncpy(hash->table[pos]->element, data.element, sizeof(hash->table[pos]->element) - 1);hash->table[pos]->element[sizeof(hash->table[pos]->element) - 1] = '\0';  // 确保字符串以 '\0' 结尾}else {printf("Key already exists, but handled by rehashing mechanism.\n");}
}// 打印哈希表的内容
void printHash(LPHASH hash) {for (int i = 0; i < hash->divisor; i++) {if (hash->table[i] == NULL) {printf("NULL\n");  // 如果桶为空，打印 NULL}else {// 打印当前桶中的 key 和 elementprintf("Key:%d Element:%s\n", hash->table[i]->key, hash->table[i]->element);}}
}// 主函数
int main() {// 创建一个大小为 10 的哈希表LPHASH hash = createHashTable(10);// 定义一个 DATA 数组，包含 4 个元素DATA array[4] = { {1, "雷电"}, {11, "春妙"}, {13, "晓月"}, {17, "雪月"} };// 将数组中的数据插入到哈希表中for (int i = 0; i < 4; i++) {insertData(hash, array[i]);}// 打印哈希表的内容printHash(hash);// 释放哈希表中每个桶存储的数据内存for (int i = 0; i < hash->divisor; i++) {if (hash->table[i] != NULL) {free(hash->table[i]);  // 释放每个桶中的 DATA 元素内存}}// 释放存储桶指针数组的内存free(hash->table);// 释放哈希表结构体本身的内存free(hash);return 0;  // 程序执行成功，返回 0
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/494866.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

pyinstaller打包资源文件和ini配置文件怎么放

pyinstaller打包资源文件和ini配置文件怎么放

1.如果出现无法成功完成操作&#xff0c;因为文件包含病毒或潜在的垃圾软件&#xff0c;说明你的版本太高&#xff0c;更换pyinstaller版本。 pip install pyinstaller6.2.02.一开始打包的时windows下尽量选择打成文件夹的并且要是带命令行窗口的&#xff0c;容易查看错误。 …
阅读更多...
五种msvcr100.dll丢失的解决方法，有效修复msvcr100.dll丢失错误！跟msvcr100.dll错误问题说拜拜！

五种msvcr100.dll丢失的解决方法，有效修复msvcr100.dll丢失错误！跟msvcr100.dll错误问题说拜拜！

在日常电脑使用过程中&#xff0c;尤其是运行某些应用程序或游戏时&#xff0c;可能会遇到“msvcr100.dll丢失”的错误提示。这个动态链接库&#xff08;DLL&#xff09;文件是Microsoft Visual C Redistributable for Visual Studio 2010的一部分&#xff0c;对于许多程序的正…
阅读更多...
【前端】入门指南：Vue中使用Node.js进行数据库CRUD操作的详细步骤

【前端】入门指南：Vue中使用Node.js进行数据库CRUD操作的详细步骤

&#x1f4a5; 欢迎来到我的博客&#xff01;很高兴能在这里与您相遇&#xff01; 首页&#xff1a;GPT-千鑫 – 热爱AI、热爱Python的天选打工人&#xff0c;活到老学到老&#xff01;&#xff01;&#xff01;导航 - 人工智能系列&#xff1a;包含 OpenAI API Key教程, 50个…
阅读更多...
【网络安全产品大调研系列】1. 漏洞扫描

【网络安全产品大调研系列】1. 漏洞扫描

1. 为什么会出现漏扫技术&#xff1f; 每次黑客攻击事件进行追溯的时候&#xff0c;根据日志分析后&#xff0c;我们往往发现基本都是系统、Web、 弱口令、配置这四个方面中的其中一个出现的安全问题导致黑客可以轻松入侵的。 操作系统的版本滞后&#xff0c;没有更新补丁&am…
阅读更多...
Java爬虫：速卖通（AliExpress）商品评论获取指南

Java爬虫：速卖通（AliExpress）商品评论获取指南

引言 在当今的电商时代&#xff0c;商品评论对于消费者决策有着举足轻重的影响。速卖通&#xff08;AliExpress&#xff09;&#xff0c;作为全球知名的在线零售平台之一&#xff0c;拥有海量的商品评论数据。对于商家而言&#xff0c;能够高效地获取这些评论数据&#xff0c;…
阅读更多...
AIDD - 探索语言模型在药物分子生成方面的应用

AIDD - 探索语言模型在药物分子生成方面的应用

AIDD - 探索语言模型在药物分子生成方面的应用 今天给大家讲一篇2024年10月在nature communications上发表的一篇关于分子生成的文章。现有的分子生成方法中往往只关注药物的特定属性&#xff0c;导致其适用性受限。因此作者提出了TamGen方法&#xff0c;用于针对特定靶点的分子…
阅读更多...
【每日学点鸿蒙知识】AVCodec、SmartPerf工具、web组件加载、监听键盘的显示隐藏、Asset Store Kit

【每日学点鸿蒙知识】AVCodec、SmartPerf工具、web组件加载、监听键盘的显示隐藏、Asset Store Kit

1、AVCodec 硬解咨询&#xff1f; 在做视频播放硬解适配&#xff0c;这是 demo&#xff1a;https://gitee.com/openharmony-sig/ohos_videocompressor/blob/master/videoCompressor/src/main/cpp/video/decoder/VideoDec.cpp 请问&#xff1a; int32_t VideoDec::SetOutputS…
阅读更多...
怎么设置电脑密码？Windows和Mac设置密码的方法

怎么设置电脑密码？Windows和Mac设置密码的方法

为电脑设置密码是保护个人信息安全的重要措施。无论是Windows系统还是MacOS系统&#xff0c;设置密码的步骤都相对简单&#xff0c;但需要根据不同的操作系统选择不同的方法。 一、Windows系统电脑密码设置 方法一&#xff1a;通过控制面板设置账户密码 点击桌面左下角的“开…
阅读更多...
谷歌浏览器的网络安全检测工具介绍

谷歌浏览器的网络安全检测工具介绍

作为全球最受欢迎的浏览器之一&#xff0c;谷歌浏览器不仅提供了快速、便捷的浏览体验&#xff0c;还内置了一系列强大的网络安全检测工具&#xff0c;帮助用户识别潜在的网络威胁&#xff0c;保护个人隐私和数据安全。本文将详细介绍谷歌浏览器中的几项关键网络安全检测功能&a…
阅读更多...
一个比RTK或redux更轻量级更易使用的 React 第三方状态管理工具库的配置与使用

一个比RTK或redux更轻量级更易使用的 React 第三方状态管理工具库的配置与使用

本文由作者 Samdy_Chan 原创，未经作者同意，请勿随意转载！ 使用轻量级第三方的 React 状态管理库 zustand 管理共享状态数据 在 react 框架应用中，开发者应该大多数都是采用 redux 状态管理工具库来管理应用的共享状态数据，但用过 redux 的人都知道，其配置和使用相当复杂…
阅读更多...
菜鸟带新鸟——基于EPlan2022的部件库制作

菜鸟带新鸟——基于EPlan2022的部件库制作

首先&#xff0c;我们需要了解一些概念&#xff1a; Eplan的部件制作内容 以上内容是制作一个完整的部件所需要的。如果公司要求没有那么严格&#xff0c;我们就可以制作1-4级的内容就可以满足日常的使用啦&#xff01; 部件的创建方式 部件创建方式有4类&#xff1a; 1、单…
阅读更多...
Charles安装证书过程（手机）

Charles安装证书过程（手机）

背景&#xff1a;使用模拟器抓包时&#xff0c;发现https请求无法抓取&#xff0c;需要安装相应证书。我自己是因为模拟器升级了安卓7&#xff0c;发现之前安装的证书无效了&#xff0c;需要重新安装。 参考博客&#xff1a;夜神模拟器12Charles进行Https抓包_模拟器抓包ssl-C…
阅读更多...
Windows、CentOS环境下搭建自己的版本管理资料库：GitBlit

Windows、CentOS环境下搭建自己的版本管理资料库：GitBlit

可以搭建属于公司内部或者个人的Git服务器&#xff0c;方便程序代码及文档版本管理。 官网&#xff1a;http://www.gitblit.com/ Windows环境下安装 提前已经安装好了JDK。 官网下载Windows版的GitBlit。 将zip包解压到自己想要放置的文件夹下。 建立版本库路径&#xff0c…
阅读更多...
数据库操作【JDBC HIbernate Mybatis】

数据库操作【JDBC HIbernate Mybatis】

JDBC JDBC编程 在java开发中&#xff0c;以前都是通过JDBC&#xff08;Java Data Base Connectivity&#xff09;与数据库打交道的&#xff0c;至少在ORM&#xff08;Object Relational Mapping&#xff09;框架没出现之前是这样&#xff0c;目前常用的ORM框架有JPA、hibernat…
阅读更多...
Linux 常见用例汇总

Linux 常见用例汇总

注&#xff1a;本文为 Linux 常见用例文章合辑。 部分内容已过时&#xff0c;未更新整理。 检查 Linux 上的 glibc 版本 译者&#xff1a;joeren | 2014-11-27 21:33 问&#xff1a;检查 Linux 系统上的 GNU C 库&#xff08;glibc&#xff09;的版本&#xff1f; GNU C 库&…
阅读更多...
web-密码安全口令

web-密码安全口令

目录 一、密码安全概述 二、密码安全现状 三、破解方式 四、暴力破解 五、字典破解 六、密码字典 学习心得&#xff1a; 一、密码安全概述 现在很多地方都是以用户名&#xff08;账号&#xff09;和口令&#xff08;密码&#xff09;作为鉴权的方式&#xff0c;口令&am…
阅读更多...
工控触摸屏用winForms来构建框架，效果还是很不错的

工控触摸屏用winForms来构建框架，效果还是很不错的

工控触摸屏采用 winForms 构建框架具有诸多优势。winForms 提供了丰富的控件和强大的开发工具&#xff0c;使得界面设计更加高效。它具有良好的稳定性和兼容性&#xff0c;能够适应工控环境的复杂要求。通过 winForms 可以实现直观的操作界面&#xff0c;方便操作人员进行监控和…
阅读更多...
开发一个DApp项目：DeFi、DApp开发与公链DApp开发

开发一个DApp项目：DeFi、DApp开发与公链DApp开发

随着区块链技术的快速发展&#xff0c;去中心化应用&#xff08;DApp&#xff09;逐渐成为创新技术的核心之一。DApp能够利用区块链去中心化的特点&#xff0c;提供更高的安全性、透明性和效率&#xff0c;吸引了越来越多的开发者和投资者关注。本文将围绕如何开发一个DApp项目…
阅读更多...
网络下载ts流媒体

网络下载ts流媒体

网络下载ts流媒体 查看下载排序合并 很多视频网站&#xff0c;尤其是微信小程序中的长视频无法获取到准确视频地址&#xff0c;只能抓取到.ts片段地址&#xff0c;下载后发现基本都是5~8秒时长。 例如&#xff1a; 我们需要将以上地址片段全部下载后排序后再合成新的长视频。 …
阅读更多...
性能优化！突破性能瓶颈的尖兵CPU Cache

性能优化！突破性能瓶颈的尖兵CPU Cache

缓存这个专业术语&#xff0c;在计算机世界中是经常使用到的。它并不是CPU所独有的&#xff0c;比如cdn缓存网站信息&#xff0c;浏览器缓存网页的图像视频等&#xff0c;但本文讲述的是狭义Cache&#xff0c;主要指的是CPU Cache&#xff0c;本文将其简称为"缓存"或…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023