C语言实现散列查找的编程
C语言实现散列查找的编程
一 、目的：
- 掌握散列查找的基本概念及其基本操作的实现；
二 、环境：
operating system version：Win11
CPU instruction set: x64
Integrated Development Environment：Viusal Studio 2022
三 、内容：
1）创建一个 hash 空表，实现动态空间分配的初始化
2）构造一个 hash 函数和某种处理冲突的方法将数据元素存放到hash表中
3）设计相应的 hash 查找函数对 hash 表中的元素进行查找
4）hash 构造函数可选用除留余数法或其他方法
5）处理冲突可选开放定址法或其他方法 。
四 、要求：
- 构造哈希函数，实现哈希查找 。
五 、步骤：
1.程序：
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
//设置一个数组分配空间大小
#define HASHSIZE 10
//设置最小int用于初始化
#define NULLKEY -32768
int m = 0;
typedef struct
{
int* elem;
int count;
}HashTable;
//初始化哈希表
int Init(HashTable* H)
{
m = HASHSIZE;
H->count = m;
H->elem = (int*)malloc(sizeof(int) * m);
if (H->elem == nullptr)
{
printf("动态内存分配失败！");
exit(-1);
}
for (int i = 0; i < m; i++)
{
H->elem[i] = NULLKEY;
}
return 1;
}
//哈希算法
int Hash(int k)
{
//采用除留余数法
return k % m;
}
//根据k插入元素
void Insert(HashTable* H, int k)
{
int addr = Hash(k);
while (H->elem[addr] != NULLKEY)
{
//开放定址法
addr = (addr + 1) % m;
}
H->elem[addr] = k;
}
//搜索某个元素位置
int Search(HashTable* H, int k)
{
int addr = Hash(k);
while (H->elem[addr] != k)
{
//采用开放定址法
addr = (addr + 1) % m;
//若addr==Hash(k)则该数组已满，无法再插入元素
if (H->elem[addr] == NULLKEY || addr == Hash(k))
{
return -1;
}
}
return addr;
}
//遍历哈希表
void Result(HashTable* H)
{
for (int i = 0; i < m; i++)
{
printf_s("%d\n", H->elem[i]);
}
}
void main()
{
int i, j, addr;
HashTable H;
int arr[HASHSIZE] = { NULL };
Init(&H);
printf("输入关键字集合:");
for (i = 0; i < HASHSIZE; i++)
{
scanf_s("%d", &arr[i]);
Insert(&H, arr[i]);
}
Result(&H);
printf("输入需要查找的元素：");
scanf_s("%d", &j);
addr = Search(&H, j);
if (addr == -1)
printf("元素不存在\n");
else
printf("%d元素在表中的位置是:%d\n", j, addr);
}2.程序、结果： 程序运行，在此次、中我使用的测试数据如下所示：
可见，较好地完成了哈希查找的操作。
六 、小结：
此次是关于散列查找的编程与实现，哈希查找的本质是先将数据映射成它的哈希值。哈希查找的核心是构造一个哈希函数，它将原来直观、整洁的数据映射为看上去似乎是随机的一些整数。因此哈希查找算法又称散列查找算法，是一种借助哈希表（散列表）查找目标元素的方法，查找效率最高时对应的时间复杂度为 O(1)。
哈希函数我采用了除留余数法，即取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。对关键字直接取模，p一般取素数或m，若p选的不好，容易产生同义词，并且在解决冲突时我采用了开放选址法，即如果两个数据元素的哈希值相同，则在哈希表中为后插入的数据元素另外选择一个表项。当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。
腾讯云开发者
