数据布局哈希表-(开放地点法+二次探测法解决哈希冲突)(创建+删除+插入)+(C
#include<stdio.h>#include<stdlib.h>
#include<stdbool.h>
#define M 20
#define NULLDEL -1
#define DELDEY -2
typedef struct
{
int key;
int count;
}HashTable;
//创建和插入
void Insert(HashTable ha[], int m, int p, int key)
{
int i, HO, HI;
HO = key % p;
if (ha.key == NULLDEL || ha.key == DELDEY)
{
ha.key = key;
ha.count = 1;
}
else
{
i = 1;
do
{
HI = (HO + i * i) % m;
i++;
} while (ha.key != NULLDEL && ha.key != DELDEY);
ha.key = key;
ha.count = i;
}
}
void Create(HashTable ha[],int m,int n1,int p,int keys[])
{
int i;
for (i = 0; i < m; i++)
{
ha.key = NULLDEL;
ha.count = 0;
}
for (i = 0; i < n1; i++)
{
Insert(ha, m, p, keys);
}
printf("二次探测法哈希表如下:\n");
for (i = 0; i < m; i++)
{
printf("%d查找次数 %d 次\n", ha.key,ha.count);
}
}
//查找
int Search(HashTable ha[], int m, int p, int key)
{
int HO, HI;
HO = key % p;
if (ha.key == NULLDEL)
{
ha.count = 1;
return -1;
}
else if (ha.key == key)
{
ha.count = 1;
return HO;
}
else
{
ha.count = 1;
for (int i = 0; i < m; i++)
{
HI = (HO + i * i) % m;//HO还是那个HO，这里变的是HI和i的值
if (ha.key == NULLDEL)
{
ha->count = ha.count + i;//哈希冲突的次数
return -1;
}
else if (ha.key == key)
{
ha->count = ha.count + i;
return HI;
}
}
}
}
//删除哈希值
bool deleteNode(HashTable ha[], int m, int p, int key)
{
int HO,i = 1;
HO = key % p;
while (ha.key != NULLDEL && ha.key != key)
{
HO = (HO + i * i);
i++;
}
if (ha.key == key)
{
ha.key = DELDEY;
return true;
}
else
{
return false;
}
}
int main()
{
HashTable ha;
int keys[] = { 19,14,23,1,68,20,84,27,55,11,10,79 };
int n1 = sizeof(keys) / sizeof(keys);
int p = 13;
Create(ha, M, n1, p, keys);
int key = 79;
int result = Search(ha, M, p, key);
if (result!=-1)
{
printf("找到 %d 位置在 %d 哈希冲突 %d 次\n", key, result, ha->count);
}
else {
printf("找不到 %d 哈希冲突 %d 次\n", key, ha->count);
}
key = 23;
deleteNode(ha, M, p, key);
printf("删除 %d 元素后遍历如下:\n", key);
for (int i = 0; i < M; i++)
{
if (ha.key != NULLDEL && ha.key != DELDEY)
{
printf(" %d ", ha.key);
}
else {
printf(" * ");
}
}
return 0;
} https://i-blog.csdnimg.cn/direct/87fbd4fdd97b4b46ac4a091ee79d0d37.png
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]