数据结构基础详解:哈希表【C语言代码实践篇】开放地址法__拉链法_哈希表的创建_增删查操作详解

文章目录

  • 1.哈希表代码实现之开放地址法
    • 1.1 开放地址法创建哈希表
    • 1.2 开放地址法之查找
    • 1.3 开放地址法之插入
    • 1.4 开放地址法之删除
  • 2.哈希表代码实现之链地址法(拉链法)
    • 2.1 链地址法之创建哈希表
    • 2.2 链地址法之查找
    • 2.3 链地址法之插入
    • 2.4 链地址法之删除

1.哈希表代码实现之开放地址法

1.1 开放地址法创建哈希表

哈希表本质就是一个线性表，定义一个哈希表结构体，包括一个动态数组PList,表长，和关键字个数（元素个数）
代码实现的一些细节
1.没有关键字的地方，默认初始值要设置成99999（就是无穷大），因为动态设置一个数组是随机值，会影响到代码结果

//开放地址法哈希表的创建
# define INF 999999999;
typedef int ElemType;

typedef struct HashTable
{
    int kNum;
    ElemType *pList;
    int tLength;
}HashTable;

void initial(HashTable &HT,int tlength)
{
    HT.pList=(ElemType *)malloc(sizeof(HashTable)*tlength);
    HT.tLength=tlength;
    for(int i=0;i<tlength;i++)
    {
        HT.pList[i]=INF;
    }
    HT.kNum=0;
}

HashTable creatHT(ElemType tlength)
{
    HashTable HT;
    initial(HT,tlength);
    return HT;
}

1.2 开放地址法之查找

在这里插入图片描述

构建一个如上图所示的哈希表作为样例：

int main()
{
    HashTable HT=creatHT(10);
    getDi(HT.tLength);
    HT.pList[6]=6;
    HT.pList[7]=13;
    HT.pList[8]=27;
    HT.pList[9]=41;
    HT.pList[0]=55;
    HT.tLength=10;
    
    int ret=search(54, HT);
    printf("%d\n",ret);
}

具体查找代码的实现：

#define P 7
int Hash(ElemType key)  //除留余数法哈希函数
{
    return key%P;
}

int Di[100]={0};
void getDi(int tLength) //初始化一个线性探测序列，0，1，2，3，4，5，6，.....
{
    for(int i=1;i<=tLength-1;i++) //为什么是tLength-1,因为假如表长为10，地址空间是0-9
    {
        Di[i]=i;
    }
}

int isUpperBound(int di,int tLength) //判断边界是否超过，意味着若超出边界，则哈希表中没有该元素
{
    if(di>tLength-1) //是否超出查找范围
    {
        return 0;  //超出查找范围
    }
    return 1;
}

int search(ElemType key,HashTable HT)  //给出要查的关键字和哈希表，进行查找
{
    //初始化查找
    int i=0;
    int Hi=(Di[i]+Hash(key))%HT.tLength;   //线性探测法函数的构建，除的是表长
    
    //如果没有超出界限，并且没有查到空白的元素，就一直找到超出界限为止
    while (isUpperBound(Di[i], HT.tLength)&&HT.pList[Hi]!=INF){
        if(HT.pList[Hi]==key)return 1;  //找到了
        
        i++;
        Hi=(Di[i]+Hash(key))%HT.tLength;
    }
    return 0

1.3 开放地址法之插入

开放地址的插入其实就是在查找操作上进行了改进，在查找中，多引入一个pos指针，pos指针返回待插入位置或是当前哈希表已经满了，pos就返回最后一个元素地址。

查找操作的修改代码:

int search(ElemType key,HashTable HT,int &pos)  //给出要查的关键字和哈希表，进行查找
{
    //初始化查找
    int i=0;
    int Hi=(Di[i]+Hash(key))%HT.tLength;   //线性探测法函数的构建，除的是表长
    
    //如果没有超出界限，并且没有查到空白的元素，就一直找到超出界限为止
    while (isUpperBound(Di[i], HT.tLength)&&HT.pList[Hi]!=INF){
        if(HT.pList[Hi]==key)return 1;  //找到了
        
        i++;
        Hi=(Di[i]+Hash(key))%HT.tLength;
    }
    pos=Hi;  //这个位置可能是空白的存储单元，也可能是最后一个访问的关键字位置
    return 0;
}

插入代码的实现：

int insrt(ElemType key,HashTable &HT)
{
    int pos=-1;
    int ret=search(key, HT, pos); //拿到pos
    if(ret==0&&HT.pList[pos]==INF) //ret==0意味着，我们要插入的元素，原哈希表中并不存在
    {
        HT.pList[pos]=key;
        HT.kNum++;
        return 1;  //插入成功
    }
    return 0;  //插入失败
}

测试代码：

int main()
{
    HashTable HT=creatHT(10);
    getDi(HT.tLength);
    HT.pList[6]=6; HT.pList[7]=13;HT.pList[8]=27;
    HT.pList[9]=41;HT.pList[0]=55;
    HT.tLength=10;
    
    int ret=insrt(57, HT);
    for (int i=0; i<HT.tLength; i++) {
        printf("%d\n",HT.pList[i]);
    }
}

1.4 开放地址法之删除

删除操作，本质上也是在查找操作的基础上修改
找到要删除元素的位置，将那个位置的值设置为无穷大，并统计表中元素-1

修改后的查找函数:

int delete_serch(ElemType key,HashTable HT,int &pos)
{
    //初始化查找
    int i=0;
    int Hi=(Di[i]+Hash(key))%HT.tLength;   //线性探测法函数的构建，除的是表长
    
    //如果没有超出界限，并且没有查到空白的元素，就一直找到超出界限为止
    while (isUpperBound(Di[i], HT.tLength)&&HT.pList[Hi]!=INF){
        if(HT.pList[Hi]==key)
        {
            pos=Hi;
            return 1;  //找到了
        }
        i++;
        Hi=(Di[i]+Hash(key))%HT.tLength;
    }
    return 0;
}

删除操作:

int detele_hash(ElemType key,HashTable &HT)
{
    int pos=-1;
    if(delete_serch(key, HT, pos)==1)
    {
        HT.pList[pos]=INF;
    }
    return 0;
}

2.哈希表代码实现之链地址法(拉链法)

在这里插入图片描述

把这个拉链法，分成两部分，右边，就看成多条链表。
左边存储的是指针，是指针数组，也就是存储的它挂着的那些链的第一个结点
pList是指向指针数组的指针，是指针的指针

2.1 链地址法之创建哈希表

typedef struct Node
{
    ElemType key;
    struct Node * next;
    
}Node;


typedef struct ChHashTable
{
    Node **pList;  //指向指针数组的指针
    int tlength;  //哈希表长度
    int kNum;  //关键字的个数
}ChHashTable;


void initial(ChHashTable &CHT,int tLength)
{
    CHT.pList=(struct Node**)malloc(sizeof(struct node *)*tLength); //分配动态数组
    CHT.tlength=tLength;
    for(int i=0;i<tLength;i++)
    {
        CHT.pList[i]=NULL;
    }
    CHT.kNum=0;
}
ChHashTable creat(int tLength)
{
    ChHashTable CHT;
    initial(CHT, tLength);
    return CHT;
}

2.2 链地址法之查找

链地址法的查找和插入基本上一样，这里省略，插入不省略

2.3 链地址法之插入

插入代码如下：

//链地址的插入其实就是单链表的插入，这里用尾插法进行链地址哈希表的插入
void insrt(ElemType key,ChHashTable &CHT)
{
    int i=Hash(key);  //找到待插入的数组下标
    
    Node *pCur=CHT.pList[i]; //获取当前数组下标的第一个元素，可能空的，也可能非空，就是存储的是第一个链表的地址
    Node * preNode=NULL;
    
    if(pCur==NULL)   //如果它是空的
    {
        struct Node * pNode=(Node *)malloc(sizeof(Node));
        pNode->key=key;
        pNode->next=NULL;
        CHT.pList[i]=pNode;
    }else
    {
        //如果它非空，就不断的查找，如果查到了就不插入，查不到就用尾插法插入
        while(pCur!=NULL)
        {
            if(pCur->key==key) break;  //不插入了
            
            preNode=pCur;
            pCur=pCur->next;
            
            if(pCur==NULL)  //没有找到待插入的元素，用尾插法插入
            {
                struct Node * pNode=(Node *)malloc(sizeof(Node));
                pNode->key=key;
                pNode->next=NULL;
               
                preNode->next=pNode;
            }
        }
    }
}

测试代码如下：

int main()
{
    ChHashTable CHT=creat(10);
    
    ElemType keyList[]={31,23,17,27,19,11,13,91,61,41};
    int keyListLength=10;
    
    for(int i=0;i<keyListLength;i++)
    {
        insrt(keyList[i], CHT);
    }
    
  //  int dd=delt(31, CHT);  删除测试
   // int dd1=delt(11, CHT);
    //int dd2=delt(13, CHT);
    
    for(int i=0;i<CHT.tlength;i++)
    {
        Node *pCur=CHT.pList[i];
        while(pCur!=NULL)
        {
            printf("%d ",pCur->key);
            pCur=pCur->next;
        }
        printf("\n");
    }

在这里插入图片描述

2.4 链地址法之删除

int delt(ElemType key,ChHashTable &CHT)
{
    int i=Hash(key);  //找到待插入的数组下标
    
    Node *pCur=CHT.pList[i]; //获取当前数组下标的第一个元素，可能空的，也可能非空，就是存储的是第一个链表的地址
    Node * preNode=NULL;
    
    //在删除操作中，需要分为两种情况，第一种情况，是第一个结点，要在指针数组上操作，不是第一个结点
    
    if(pCur==NULL)
    {
        return 0;
    }else   //在不为空的情况下，删除
    {
        if(pCur->key==key)
        {
            CHT.pList[i]=pCur->next;
            free(pCur);
            return 1;
        }
        else
        {
            while(pCur!=NULL)  //一直找
            {
                if(pCur->key==key)
                {
                    preNode->next=pCur->next;
                    free(pCur);
                    break;
                }
                preNode=pCur;
                pCur=pCur->next;
            }
        }
    }
    return 0;
}

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

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

相关文章

Mac电脑剪切板在哪里找 苹果电脑剪切板打开教程【详解】

Mac电脑剪切板在哪里找 苹果电脑剪切板打开教程【详解】

Windows 和 Mac 电脑在使用方式上存在一些差异&#xff0c;许多习惯了 Windows 系统的用户初次接触 Mac 时可能会对某些操作感到困惑。比如&#xff0c;很多人会问&#xff1a;Mac 上的剪贴板在哪里&#xff1f;如果你也有这样的疑问&#xff0c;不妨看看下面这篇关于如何在 Ma…
阅读更多...
MySQL查询执行（四）：查一行也很慢

MySQL查询执行（四）：查一行也很慢

假设存在表t&#xff0c;这个表有两个字段id和c&#xff0c;并且我在里面插入了10万行记录。 -- 创建表t CREATE TABLE t (id int(11) NOT NULL,c int(11) DEFAULT NULL,PRIMARY KEY (id) ) ENGINEInnoDB;-- 通过存储过程向t写入10w行数据 delimiter ;; create procedure idat…
阅读更多...
Android Studio新建工程(Java语言环境)

Android Studio新建工程(Java语言环境)

一、新建工程流程(java语言环境) 1、File->New->New Project 2、选择“Empty Views Activity” -> Next 3、创建项目名称/项目路径/语言环境 1&#xff09;项目名称&#xff1a;使用默认Name 或 修改Name 2) Package name&#xff1a;每个项目的这个名称唯一&…
阅读更多...
饿了么基于Flink+Paimon+StarRocks的实时湖仓探索

饿了么基于Flink+Paimon+StarRocks的实时湖仓探索

摘要&#xff1a;本文整理自饿了么大数据架构师、Apache Flink Contributor 王沛斌老师在8月3日 Streaming Lakehouse Meetup Online&#xff08;Paimon x StarRocks&#xff0c;共话实时湖仓架构&#xff09;上的分享。主要分为以下三个内容&#xff1a; 饿了么实时数仓演进之…
阅读更多...
self-play RL学习笔记

self-play RL学习笔记

让AI用随机的路径尝试新的任务&#xff0c;如果效果超预期&#xff0c;那就更新神经网络的权重&#xff0c;使得AI记住多使用这个成功的事件&#xff0c;再开始下一次的尝试。——llya Sutskever 这两天炸裂朋友圈的OpenAI草莓大模型o1和此前代码能力大幅升级的Claude 3.5&…
阅读更多...
手机玩机常识____展讯芯片刷机平台ResearchDownload的一些基本常识与问题解决

手机玩机常识____展讯芯片刷机平台ResearchDownload的一些基本常识与问题解决

展讯ResearchDownload工具 展讯芯片的刷机工具--ResearchDownload下载工具"是一款专为用户设计的高效、便捷的下载管理软件&#xff0c;它能够帮助用户快速、稳定地从互联网上获取各种文件。这款工具以其强大的功能和良好的用户体验&#xff0c;在众多展讯芯片下载工具中脱…
阅读更多...
Python [ GUI编程自学 ]，虽然但是，还是想出一个系列

Python [ GUI编程自学 ]，虽然但是，还是想出一个系列

Python [ GUI编程自学 ]&#xff0c;虽然但是&#xff0c;还是想出一个系列。 目前跟着哔站自学完毕&#xff0c;皮毛了解了&#xff0c;本文GUI一系列文章请查看Python_GUI编程专栏&#xff01; 本篇主要介绍了事件处理机制&#xff1a;事件处理原理&#xff08;感觉和之前学的…
阅读更多...
解决win11 使用wsl工具，不能使用systemctl

解决win11 使用wsl工具，不能使用systemctl

使用systemctl命令出现报错&#xff1a; System has not been booted with systemd as init system (PID 1). Can‘t operate. 默认情况下并不启用 systemd&#xff0c;而是使用了其他轻量级的初始化系统&#xff08;SysV init初始化系统&#xff09;。这导致一些需要 system…
阅读更多...
利用未标记数据的半监督学习在模型训练中的效果评估

利用未标记数据的半监督学习在模型训练中的效果评估

数据科学家在实践中经常面临的一个关键挑战是缺乏足够的标记数据来训练可靠且准确的模型。标记数据对于监督学习任务&#xff08;如分类或回归&#xff09;至关重要。但是在许多领域&#xff0c;获取标记数据往往成本高昂、耗时或不切实际。相比之下&#xff0c;未标记数据通常…
阅读更多...
Java获取随机数

Java获取随机数

在Java中获取随机数通常会使用java.util.Random类或者Math.random()方法 1.java.util.Random java.util.Random类用于生成伪随机数。 // 使用无参构造方法创建Random对象Random rand new Random();// 生成一个[0, 100)范围内的随机整数int randomInt rand.nextInt(100);Sys…
阅读更多...
linux使用命令行编译qt.cpp

linux使用命令行编译qt.cpp

步骤&#xff1a; mkdir qttestcd qttestvim hello.cpp #include <QApplication> #include <QDialog> #include <QLabel> int main(int argc,char* argv[]) {QApplication a(argc,argv);QLabel label("aaa");label.resize(100,100);label.show()…
阅读更多...
vulnhub（6）：Tr0ll（隐藏目录、hydra密码爆破、内核漏洞提权）

vulnhub（6）：Tr0ll（隐藏目录、hydra密码爆破、内核漏洞提权）

端口 nmap主机发现 nmap -sn 192.168.178.0/24 ​ Nmap scan report for 192.168.178.33 Host is up (0.00020s latency). ​ 33是新出现的机器&#xff0c;他就是靶机 nmap端口扫描 nmap -Pn 192.168.178.33 -p- --min-rate 10000 -oA nmap/scan 扫描开放端口保存到 nmap/sca…
阅读更多...
【FATFS】FATFS简介及下载

【FATFS】FATFS简介及下载

1、FATFS简介 FatFs 是一个针对嵌入式系统开发的通用文件系统模块&#xff0c;主要用于支持 FAT 文件系统。它最初由 ChaN 开发&#xff0c;并被广泛应用于嵌入式设备上。FatFs 以其轻量级、可配置和设备无关的特性著称&#xff0c;支持 FAT12、FAT16、FAT32 以及 exFAT 文件系…
阅读更多...
【iOS】单例模式

【iOS】单例模式

目录 前言单例模式认识单例模式单例模式的特点及使用情景单例模式的使用单例模式的实现步骤&#xff1a;完整代码 总结 前言 在进行大项目编写之前&#xff0c;开始对前面比较重要的知识进行回顾和重新学习&#xff0c;单例模式在软件开发设计中是比较重要的&#xff0c;尤其是…
阅读更多...
EFI引导模式下配置Windows和Linux双系统共存

EFI引导模式下配置Windows和Linux双系统共存

这几天在VirtualBox虚机里玩Modular MAX下的LLama3大模型&#xff0c;实在受不了这执行速度&#xff0c;于是下决心把Ubuntu系统安装在硬盘上跟Windows11做双系统共存。之前在传统BIOS引导模式下做过不少次双系统引导&#xff0c;EFI模式下第一次做&#xff0c;加之windows系统…
阅读更多...
计算机毕业设计 大学志愿填报系统的设计与实现 Java实战项目 附源码+文档+视频讲解

计算机毕业设计 大学志愿填报系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…
阅读更多...
大数据-129 - Flink CEP 详解 Complex Event Processing - 复杂事件处理

大数据-129 - Flink CEP 详解 Complex Event Processing - 复杂事件处理

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; 目前已经更新到了&#xff1a; Hadoop&#xff08;已更完&#xff09;HDFS&#xff08;已更完&#xff09;MapReduce&#xff08;已更完&am…
阅读更多...
91、K8s之ingress上集

91、K8s之ingress上集

一、Ingress service模式&#xff1a; loadbalance NodePort&#xff1a;每个节点都会有一个指定的端口 30000-32767 内网 clusterip&#xff1a;默认模式&#xff0c;只能pod内部访问 externalName&#xff1a;需要dns提供域名 1.1、对外提供服务的ingress service&…
阅读更多...
线性规划------ + 案例 + Python源码求解（见文中）

线性规划------ + 案例 + Python源码求解（见文中）

目录 一、代数模型&#xff08;Algebraic Models&#xff09;详解1.1什么是代数模型&#xff1f;1.2代数模型的基本形式1.3 安装所需要的Python包--运行下述案例1.4代数模型的应用案例案例 1&#xff1a;市场供需平衡模型Python求解代码Python求解结果如下图&#xff1a; 案例 …
阅读更多...
【快速解决】搭建VUE+VScode+elementUI开发环境，Vue环境配置

【快速解决】搭建VUE+VScode+elementUI开发环境，Vue环境配置

目录 1、通过这个之间下载node.js&#xff08;全选next即可&#xff09; 2、winr检验是否安装成功&#xff08;运行下面两个命令即可&#xff09; 3、将下面我给你的这个压缩包解压&#xff0c;然后放到空间足够的磁盘里面 4、【重点】设置环境变量 第一个变量路径里面长这…
阅读更多...
最新文章

Copyright @ 2022~2023