实现一个简单的哈希表

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;                // 初始化哈希表的当前大小为 0
    hash->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，则更新该位置的 element
    else 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 和 element
            printf("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;                // 初始化哈希表的当前大小为 0
    hash->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，则更新该位置的 element
    else 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 和 element
            printf("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
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

tortoisegit推送失败

tortoisegit推送失败

tortoisegit推送失败 git.exe push --progress -- "origin" testLidar:testLidar /usr/bin/bash: gitgithub.com: No such file or directory fatal: Could not read from remote repository. Please make sure you have the correct access rights and the reposit…
阅读更多...
pyinstaller打包资源文件和ini配置文件怎么放

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

1.如果出现无法成功完成操作&#xff0c;因为文件包含病毒或潜在的垃圾软件&#xff0c;说明你的版本太高&#xff0c;更换pyinstaller版本。 pip install pyinstaller6.2.02.一开始打包的时windows下尽量选择打成文件夹的并且要是带命令行窗口的&#xff0c;容易查看错误。 …
阅读更多...
autMan奥特曼机器人-autMan的PHP环境

autMan奥特曼机器人-autMan的PHP环境

直装版请自行安装php环境。 docker版本预置了php环境&#xff0c;如下图&#xff1a; 如果使用插件"test php"测试环境时&#xff0c;实时日志有报错如下&#xff1a; 可进入终端&#xff0c;输入两条命令 apk add curl apk add php-curl
阅读更多...
uniApp打包H5发布到服务器（docker）

uniApp打包H5发布到服务器（docker）

使用docker部署uniApp打包后的H5项目记录&#xff0c;好像和VUE项目打包没什么区别... 用HX打开项目&#xff0c;首先调整manifest.json文件 开始用HX打包 填服务器域名和端口号~ 打包完成后可以看到控制台信息 我们可以在web文件夹下拿到下面打包好的静态文件 用FinalShell或…
阅读更多...
【Leetcode】1705. 吃苹果的最大数目

【Leetcode】1705. 吃苹果的最大数目

文章目录 题目思路代码复杂度分析时间复杂度空间复杂度 结果总结 题目 题目链接&#x1f517; 有一棵特殊的苹果树&#xff0c;一连 n n n 天&#xff0c;每天都可以长出若干个苹果。在第 i i i 天&#xff0c;树上会长出 a p p l e s [ i ] apples[i] apples[i] 个苹果&a…
阅读更多...
4、数据结构与算法解析(C语言版)--栈

4、数据结构与算法解析(C语言版)--栈

栈的数据存储遵循“后进先出的规则”&#xff0c;这在计算机里面是非常有用的&#xff0c;比如word等编辑软件的"撤销"功能&#xff0c;就是使用栈进行实现的。 1、创建项目 main.h #ifndef _MAIN_H #define _MAIN_H#include <stdio.h> #include <stdlib.…
阅读更多...
施耐德变频器ATV320系列技术优势：创新与安全并重

施耐德变频器ATV320系列技术优势：创新与安全并重

在工业自动化领域&#xff0c;追求高效、安全与智能已成为不可阻挡的趋势。施耐德变频器ATV320系列凭借其强大的设计标准和全球认证&#xff0c;成为能够帮助企业降低安装成本&#xff0c;提高设备性能的创新解决方案。 【全球认证&#xff0c;品质保障】ATV320 系列秉持施耐德…
阅读更多...
【软考高级】系统架构设计师复习笔记-精华版

【软考高级】系统架构设计师复习笔记-精华版

文章目录 前言0 系统架构设计师0.1 考架构还是考系分0.2 架构核心知识0.3 架构教材变化 1 计算机操作系统1.1 cpu 组成1.2 内核的五大功能1.3 流水线技术1.4 段页式存储1.5 I/O 软件1.6 文件管理1.7 系统工程相关 2 嵌入式2.1 嵌入式技术2.2 板级支持包&#xff08;BSP&#xf…
阅读更多...
并发编程（19）——引用计数型无锁栈

并发编程（19）——引用计数型无锁栈

文章目录 十九、day191. 引用计数2. 代码实现2.1 单引用计数器无锁栈2.2 双引用计数器无锁栈 3. 本节的一些理解 十九、day19 上一节我们学习通过侯删链表以及风险指针与侯删链表的组合两种方式实现了并发无锁栈&#xff0c;但是这两种方式有以下缺点&#xff1a; 第一种方式…
阅读更多...
大恒相机开发（2）—Python软触发调用采集图像

大恒相机开发（2）—Python软触发调用采集图像

大恒相机开发&#xff08;2&#xff09;—Python软触发调用采集图像 完整代码详细解读和功能说明扩展学习 这段代码是一个Python程序&#xff0c;用于从大恒相机采集图像&#xff0c;通过软件触发来采集图像。 完整代码 咱们直接上python的完整代码&#xff1a; # version:…
阅读更多...
步进电机直线插补

步进电机直线插补

基础原理 代码部分
阅读更多...
数据结构经典算法总复习（上卷）

数据结构经典算法总复习（上卷）

第一章&#xff1a;数据结构导论 无重要考点&#xff0c;仅需了解时间复杂度。 第二章&#xff1a;线性表 1.获得线性表第i个元素 void GetElem_sq(SqList L, int i, ElemType &e) {if (i<1 || i>L.length) ErrorMsg("Invalid i value"); //注意错误监…
阅读更多...
Windows11 安装 Ubuntu-20.04，同时安装配置 zsh shell，配置 git 别名（alias），大大提高开发效率

Windows11 安装 Ubuntu-20.04，同时安装配置 zsh shell，配置 git 别名（alias），大大提高开发效率

背景&#xff1a;家里配置了一台 Windows 电脑&#xff0c;有时候需要用到 vscode 开发测试一些代码&#xff0c;在使用过程中发现原生 windows 敲代码不是很友好&#xff0c;于是想到配置 wsl&#xff0c;安装 Ubuntu&#xff0c;并安装配置 zsh shell&#xff0c;同时配置 gi…
阅读更多...
PE文件结构

PE文件结构

PE文件是Windows系统下可执行文件的总称&#xff0c;英文全称 Portable Executable 可移植的可执行文件&#xff0c;常见的有exe、dll、sys、com、ocx 对于学习反&#xff08;木马、免杀、病毒、外挂、内核&#xff09;&#xff0c;了解PE文件结构是非常有必要且非常非常重要的…
阅读更多...
Helm 官方脚本

Helm 官方脚本

Helm 官方脚本 #!/usr/bin/env bash# Copyright The Helm Authors. # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # …
阅读更多...
JSON 系列之1：将 JSON 数据存储在 Oracle 数据库中

JSON 系列之1：将 JSON 数据存储在 Oracle 数据库中

本文为Oracle数据库JSON学习系列的第一篇&#xff0c;讲述如何将JSON文档存储到数据库中&#xff0c;包括了版本为19c和23ai的情形。 19c中的JSON 先来看一下数据库版本为19c时的情形。 创建表colortab&#xff0c;其中color列的长度设为4000。若color的长度需要设为32767&a…
阅读更多...
C语言-结构体内存大小

C语言-结构体内存大小

#include <stdio.h> #include <string.h> struct S1 { char a;//1 int b;//4 char c;//1 }; //分析 默认对齐数 成员对齐数 对齐数(前两个最小值) 最大对齐数 // 8 1 …
阅读更多...
PyTorch 神经网络回归（Regression）任务：关系拟合与优化过程

PyTorch 神经网络回归（Regression）任务：关系拟合与优化过程

PyTorch 神经网络回归&#xff08;Regression&#xff09;任务&#xff1a;关系拟合与优化过程 本教程介绍了如何使用 PyTorch 构建一个简单的神经网络来实现关系拟合&#xff0c;具体演示了从数据准备到模型训练和可视化的完整过程。首先&#xff0c;利用一维线性空间生成带噪…
阅读更多...
渐开线齿轮和摆线齿轮有什么区别？

渐开线齿轮和摆线齿轮有什么区别？

摆线齿形与渐开线齿形的区别 虽然在比对这两种齿形&#xff0c;但有一个事情希望大家注意&#xff1a;渐开线齿轮只是摆线齿轮的一个特例。 &#xff08;1&#xff09;摆线齿形的压力角在啮合开始时最大&#xff0c;在齿节点减小到零&#xff0c;在啮合结束时再次增大到最大…
阅读更多...
Debian 12 安装配置 fail2ban 保护 SSH 访问

Debian 12 安装配置 fail2ban 保护 SSH 访问

背景介绍 双十一的时候薅羊毛租了台腾讯云的虚机, 是真便宜, 只是没想到才跑了一个月, 系统里面就收集到了巨多的 SSH 恶意登录失败记录. 只能说, 互联网真的是太不安全了. 之前有用过 fail2ban 在 CentOS 7 上面做过防护, 不过那已经是好久好久之前的故事了, 好多方法已经不…
阅读更多...
最新文章

Copyright @ 2022~2023