哈希表开放地址法c语言

实现代码及其原理如下：

原理：

哈希表开放地址法，是一种处理哈希碰撞（哈希冲突）的方法。刚开始时，哈希表中全部元素都未被占用，当要将一个新元素添加到哈希表中时，通过哈希函数计算其所对应的哈希地址，如果该地址已经被占用，就继续往下查找，直到找到一个空的地址为止。

实现代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASHSIZE 12 // 定义哈希表数组长度为12
#define NULLKEY -32768 // 定义空关键字，同时也可以做删除标记
typedef struct
{
int key; // 关键字
} DataNode; // 数据节点类型
DataNode HashTable[HASHSIZE]; // 定义哈希表数组
// 初始化哈希表
void InitHashTable()
{
for (int i = 0; i < HASHSIZE; ++i)
{
HashTable[i].key = NULLKEY; // 将哈希表中全部元素的关键字值初始化为NULLKEY
}
}
// 散列函数
int Hash(int key)
{
return key % HASHSIZE; // 除留余数法
}
// 插入元素
void InsertElement(int key)
{
int hashVal = Hash(key); // 计算key的哈希地址
while (HashTable[hashVal].key != NULLKEY) // 如果该地址已被占用
{
// 线性探测，继续往下查找
hashVal = (hashVal + 1) % HASHSIZE;
}
HashTable[hashVal].key = key; // 将新元素插入哈希表
}
// 查找元素
void SearchElement(int key)
{
int hashVal = Hash(key); // 计算key的哈希地址
while (HashTable[hashVal].key != key) // 未找到时继续查找
{
if (HashTable[hashVal].key == NULLKEY)
{
printf("该关键字不存在！\n"); // 哈希表中没有该元素，退出查找
return;
}
// 线性探测，继续往下查找
hashVal = (hashVal + 1) % HASHSIZE;
}
printf("该元素的位置是：%d\n", hashVal); // 找到该元素，输出其在哈希表中的位置
}
// 删除元素
void DeleteElement(int key)
{
int hashVal = Hash(key); // 计算key的哈希地址
while (HashTable[hashVal].key != key) // 未找到时继续查找
{
if (HashTable[hashVal].key == NULLKEY)
{
printf("该关键字不存在！\n"); // 哈希表中没有该元素，退出删除
return;
}
// 线性探测，继续往下查找
hashVal = (hashVal + 1) % HASHSIZE;
}
HashTable[hashVal].key = NULLKEY; // 将该元素标记为NULLKEY，即删除该元素
}
int main()
{
InitHashTable(); // 初始化哈希表
InsertElement(56); // 插入元素
InsertElement(22);
InsertElement(37);
InsertElement(15);
InsertElement(23);
InsertElement(24);
printf("输入要查找的数据：");
int key;
scanf("%d", &key);
SearchElement(key); // 查找元素
printf("输入要删除的数据：");
scanf("%d", &key);
DeleteElement(key); // 删除元素
return 0;
}