数据结构--哈希表代码实现

鱼非愚

2024-06-19 帮助1人

1、直接定制法
哈希函数为关键字的线性函数如 H（key）=a*key b
这种构造方法比较简便，均匀，但是有很大限制，仅限于地址大小=关键字集合的情况

产生hash冲突后在存储数据后面加一个指针，指向后面冲突的数据

2、查找过程和造表过程一致，假设采用开放定址法处理冲突，则查找过程为：
对于给定的key，计算hash地址index = H（key）
如果数组arr【index】的值为空则查找不成功
如果数组arr【index】== key 则查找成功
否则使用冲突解决方法求下一个地址，直到arr【index】== key或者 arr【index】==null
3、决定hash表查找的ASL因素：
1）选用的hash函数
2）选用的处理冲突的方法
3）hash表的饱和度，装载因子 α=n/m(n表示实际装载数据长度 m为表长)
一般情况，假设hash函数是均匀的，则在讨论ASL时可以不考虑它的因素
hash表的ASL是处理冲突方法和装载因子的函数
4、代码实现：

#ifndef _HASH_H_
#define _HASH_H_
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 13 //hash表顺序表部分数组元素个数
typedef int data_t;
//数据节点
struct link
{
data_t data;
struct link *next;
};
typedef struct link LINK;
//hash表顺序表部分（保存数据节点所构成的链表的头节点）
struct hash
{
LINK *hp[N];
};
typedef struct hash HASH;
HASH *CreateHash();
void InsertHash(HASH *p,data_t num);
void ShowHash(HASH *p);
LINK * FindHash(HASH *p,data_t num);
void UpdateHash(HASH *p,data_t old_num,data_t new_num);
void DeleteHash(HASH *p,data_t num);
HASH *DestoryHash(HASH *p);
#endif

#include "hash.h"
HASH *CreateHash()
{
HASH *p = (HASH *)malloc(sizeof(HASH));
if(NULL == p)
{
perror("hash表顺序表部分申请空间失败");
return p;
}
memset(p,0,sizeof(HASH));
return p;
}
//创建新节点
LINK *CreateNode(data_t num)
{
LINK *node = (LINK *)malloc(sizeof(LINK));
if(NULL == node)
{
perror("新节点申请空间失败");
return node;
}
memset(node,0,sizeof(LINK));
node->data = num;
return node;
}
//hash函数：计算插入数据的位置，建立记录与地址的对应关系
int HashFun(data_t num)
{
return num % N;
}
void InsertHash(HASH *p,data_t num)
{
//1、判定入參
if(NULL == p)
{
perror("hash表不能存在");
return;
}
//2、创建新节点保留插入数据
LINK *new_node = CreateNode(num);
if(NULL == new_node)
{
perror("新节点创建失败");
return;
}
//3、通过hash函数计算插入位置 ==》算法时间复杂度是否接近O(C)重要指标
int pos = HashFun(new_node->data);
//4、根据hash函数计算的地址，将数据节点插入到hash表中
if(p->hp[pos] == NULL)//判定pos行没有数据,则新节点就可以直接插入
{
p->hp[pos] = new_node;
}
else//判定pos行有数据,则新节点去寻找合适的插入位置
{
//如果if后为0，则执行按照大小排序插入新节点；如果为1，则执行正常的简易hash表的插入操作
#if 1
LINK *tmp = p->hp[pos];
while(NULL != tmp->next)
{
tmp = tmp->next;
}
tmp->next = new_node;
#else
if(p->hp[pos]->data >= new_node->data)//因为第一个数据节点已经大于插入的数据的特殊处理
{
new_node->next = p->hp[pos];
p->hp[pos] = new_node;
return;
}
LINK *tmp = p->hp[pos];
while(tmp != NULL)//当找到当前表结尾处仍然没有找到合适插入位置，则将新节点直接接到尾节点后
{
if(tmp->data >= new_node->data)//查找到是插入数据将要插入的位置
{
break;
}
tmp = tmp->next;
}
LINK *ntmp = p->hp[pos];
while(ntmp->next != tmp)//查找插入数据将要插入位置的前一个位置
{
ntmp = ntmp->next;
}
tmp = ntmp;//为统一在最后使用tmp进行插入
new_node->next = tmp->next;
tmp->next = new_node;
#endif
}
}
void ShowHash(HASH *p)
{
//1、判定入參
if(NULL == p)
{
perror("hash表不能存在");
return;
}
int i = 0;
for(i = 0;i < N;i )
{
printf("%-2d : ",i);
if(p->hp[i] == NULL)
{
printf("\n");
continue;
}
else
{
LINK *tmp = p->hp[i];
while(tmp != NULL)
{
printf("%d ",tmp->data);
tmp = tmp->next;
}
}
printf("\n");
}
}
LINK * FindHash(HASH *p,data_t num)
{
//1、判定入參
if(NULL == p)
{
perror("hash表不能存在");
return NULL;
}
//2、通过hash函数计算插入位置 ==》算法时间复杂度是否接近O(C)重要指标
int pos = HashFun(num);
//3、根据hash函数计算的地址，查找num是否在hash表中
if(p->hp[pos] == NULL)//判定pos行没有数据,则查找失败
{
printf("该行没有数据，因此查找失败!\n");
return NULL;
}
else
{
LINK *tmp = p->hp[pos];
while(NULL != tmp)
{
if(tmp->data == num)
{
printf("find data = %d\n",tmp->data);
return tmp;
}
tmp = tmp->next;
}
}
printf("该hash表没有该数据，因此查找失败!\n");
return NULL;
}
void UpdateHash(HASH *p,data_t old_num,data_t new_num)
{
//1、判定入參
if(NULL == p)
{
perror("hash表不能存在");
return;
}
LINK * tmp = FindHash(p,old_num);
if(NULL == tmp)
{
return;
}
tmp->data = new_num;
}
void DeleteHash(HASH *p,data_t num)
{
//1、判定入參
if(NULL == p)
{
perror("hash表不能存在");
return;
}
LINK * tmp = FindHash(p,num);
if(NULL == tmp)
{
return;
}
//3、通过hash函数计算插入位置 ==》算法时间复杂度是否接近O(C)重要指标
int pos = HashFun(num);
if(p->hp[pos] == tmp)//删除的数据节点为第一个数据节点
{
p->hp[pos] = tmp->next;
}
else//删除的数据节点不是第一个数据节点
{
LINK *ntmp = p->hp[pos];
while(ntmp->next != tmp)//查找删除数据将要插入位置的前一个位置
{
ntmp = ntmp->next;
}
ntmp->next = tmp->next;
}
free(tmp);
tmp = NULL;
}
HASH *DestoryHash(HASH *p)
{
//1、判定入參
if(NULL == p)
{
perror("hash表不能存在");
return;
}
//2、销毁所有数据链表
int i = 0;
for(i = 0;i < N;i )
{
if(p->hp[i] == NULL)
{
continue;
}
else
{
while(p->hp[i] != NULL)
{
LINK *tmp = p->hp[i];
p->hp[i] = tmp->next;
free(tmp);
tmp = NULL;
}
}
}
//3、销毁hash表的顺序表部分
free(p);
p = NULL;
return p;
}

main函数：

#include "hash.h"
int main()
{
HASH *head = CreateHash();
if(NULL == head)
{
perror("hash表创建失败!");
return -1;
}
printf("hash表创建成功!\n");
int k[12] = {23,34,14,38,46,16,68,15,7,31,26,20};
int i = 0;
for(i = 0;i < 12;i )
{
InsertHash(head,k[i]);
}
printf("打印数据:\n");
ShowHash(head);
//FindHash(head,17);
//UpdateHash(head,46,10000);
//DeleteHash(head,26);
//printf("打印数据:\n");
//ShowHash(head);
HASH *thead = DestoryHash(head);
printf("打印数据:\n");
ShowHash(thead);
return 0;
}

Makefile：

TARGET=hash
CC=gcc
OBJS=main.c hash.c
$(TARGET):$(OBJS)
$(CC) $^ -o $@ -g
clean:
rm *~
rm $(TARGET)

运行结果：

huqin@ubuntu:/mnt/hgfs/share/code/2021/mon11/week1/hash$ ./hash
hash表创建成功!
打印数据:
0 : 26
1 : 14
2 : 15
3 : 16 68
4 :
5 : 31
6 :
7 : 46 7 20
8 : 34
9 :
10 : 23
11 :
12 : 38
打印数据:
hash表不能存在: Success

这篇好文章是转载于：学新通技术网

数据结构--哈希表代码实现

photoshop保存的图片太大微信发不了怎么办

word里面弄一个表格后上面的标题会跑到下面怎么办

photoshop扩展功能面板显示灰色怎么办

《学习通》视频自动暂停处理方法

TikTok加速器哪个好免费的TK加速器推荐

Android 11 保存文件到外部存储，并分享文件

微信公众号没有声音提示怎么办

excel下划线不显示怎么办

excel打印预览压线压字怎么办

微信运动停用后别人还能看到步数吗