当前位置： 首页 > article >正文

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

article 2024/9/20 19:29:57

文章目录

  • 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.kler.cn/news/305732.html

相关文章：

  • 详解c++多态---上
  • 移动应用开发与测试赛题2
  • 将 YOLOv10 模型从 PyTorch 转换为 ONNX
  • 前端开发的单例设计模式
  • Leetcode面试经典150题-202.快乐数
  • 人工智能时代，程序员如何保持核心竞争力？
  • CSP-J 计算机网络
  • CSS 圆角渐变边框
  • Linux软件安装
  • 虚幻5|使用F插值到，击打敌人使UI血条缓慢缩减|小知识（3）
  • 利用 Vue.js 自定义指令实现权限控制：问题解析与最佳实践20240912
  • 网络通信安全：全面探索与深入分析
  • python的流程控制语句之制作空气质量评估系统
  • 国产化中间件正在侵蚀开源中间件
  • 使用 Vue.js 将数据对象的值放入另一个数据对象中
  • Redis 集群高可用详解及配置
  • mfc140u.dll文件错误的相关修复方法，4种方法修复mfc140u.dll
  • 计算机毕业设计选题推荐-推拿知识互动平台-Java/Python项目实战
  • 通信工程学习：什么是UNI用户网络接口
  • 漏洞复现-泛微-E-Cology-SQL
  • 基于python+django+vue的视频点播管理系统
  • 半导体制造技术中的沉积和驱入（Deposition and drive-in）过程
  • Vue3 全文知识点
  • Spring Boot 驱动的在线读书笔记平台
  • Vue与React的Diff算法
  • 让人物照片跳舞vigen追影
  • Pytorch+Anaconda+Pycharm+Python
  • 工程师 - HUE(Humans in User Experience)介绍
  • Puppeteer-Cluster：并行处理网页操作的新利器
  • MyBatis中多对一关系的三种处理方法