数据结构查找-哈希表(开发地址法+线性探测法)+(创建+查找+删除代码)+(C语言代码)

#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
#define NULLKEY -1//单元为空
#define DELKEY -2//单元内容被删除
#define M 20
typedef struct
{
int key;//关键字
int count;//统计哈希冲突探测次数
}HashTable;
//插入到哈希表
void InsertHT(HashTable ha[], int* n, int m,int p,int key)//n为哈希表的元素个数，m为哈希表的表长总数
{
int i, adr;
adr = key % p;//获得插入的哈希地址
if (ha[adr].key == NULLKEY || ha[adr].key == DELKEY)
{
ha[adr].key = key;
ha[adr].count = 1;
}
else
{
i = 1;
do
{
adr = (adr + 1) % m;
i++;
} while (ha[adr].key != NULLKEY && ha[adr].key != DELKEY);
ha[adr].key = key;
ha[adr].count = i;
}
n++;//哈希表的元素个数
}
//创建哈希表
void CreateHT(HashTable ha[], int* n, int m, int p, int keys[],int n1)
{
int i;
//初始化哈希表内容
for (int i = 0; i < m; i++)
{
ha[i].key = NULLKEY;
ha[i].count = 0;
}
n = 0;//统计插入的个数
for (i = 0; i < n1; i++)
{
InsertHT(ha, n, m, p, keys[i]);
}
printf("哈希表如下:\n");
for (int j = 0; j < m; j++)
{
printf("%d  比较次数 %d\n", ha[j].key,ha[j].count);
}
printf("\n");
}
//查找哈希表
int SearchHT(HashTable ha[],int p,int m,int n1,int key)
{
int i, Hi;
int HO = key % p;//求出key的哈希地址
if (ha[HO].key == NULLKEY)
{
ha->count = 1;
return -1;
}
else if (ha[HO].key == key)
{
ha->count = 1;
return HO;
}
else
{
ha->count = 1;
for (i = 1; i <= n1; i++)
{
Hi = (HO + i) % m;
if (ha[Hi].key == NULLKEY)
{
ha->count = ha->count + i;
return -1;
}
else if (ha[Hi].key == key)
{
ha->count = ha->count + i;
return Hi;
}
}
}
}
//删除哈希值
bool DeleteHT(HashTable ha[], int* n, int m, int p, int key)
{
int i = 1, adr;
adr = key % p;
while(ha[adr].key != NULLKEY && ha[adr].key != key)
{
adr = (adr + i) % m;
i++;
}
if (ha[adr].key == key)
{
ha[adr].key = DELKEY;
return true;
}
else
{
return false;
}
}
int main()
{
HashTable ha[M];
int keys[] = { 19,14,23,1,68,20,84,27,55,11,10,79 };
int n1 = sizeof(keys) / sizeof(keys[0]);
int n;
int p = 13;
//哈希表的创建+打印
CreateHT(ha, &n, M, p, keys, n1);
//哈希表的查找
int num = 79;
int result = SearchHT(ha, p, M,n1, num);
if (result != -1)
{
printf("找到key = %d,位置在 %d 比较次数为%d\n", num, result,ha->count);
}
else
{
printf("没有找到key = %d , 比较次数为%d\n", num, ha->count);
}
//删除哈希值
num = 23;
DeleteHT(ha, &n, M, p, num);
printf("删除后:\n");
for (int j = 0; j < M; j++)
{
if (ha[j].key != NULLKEY && ha[j].key != DELKEY)
{
printf(" %d ", ha[j].key);
}
else {
printf(" * ");
}
}
printf("\n");
return 0;
}

原文地址：https://blog.csdn.net/2305_78057683/article/details/143763533

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！