这个就真的是再数组层面上的操作了。直接上代码
目录
预先要引用的头文件以及宏定义
#include<stdio.h>
#include<iostream>
//
//using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define UNSUCCESS 0
#define SUCCESS 1
typedef int ElemType;
typedef int Status;
typedef int KeyType;
所使用哈希表的结构
typedef struct {
KeyType Key;
//这里可以存放其他数据
}RecordType, RcdType;
typedef struct {
RcdType* rcd; //记录存储基址，动态分配数组
int size; //哈希表容量
int count; //当前表中含有的记录个数
int* tag; //标记，0空，1有效，-1已删除
int(*hash)(KeyType key, int hashSize); //函数指针变量，选取的哈希函数
void(*collision)(int& hashValuue, int hashSize);//函数指针变量，用于处理冲突的函数
}HashTable_k;所选取的哈希函数和处理冲突的函数
int hash(int key, int hashSize)
{//哈希函数，hashSize为地址空间长度
return (3 * key) % hashSize;
}
void collision_1(int& hashValue, int hashSize)//线性探测
{
hashValue = (hashValue + 1) % hashSize;
}哈希函数我之前的文章有提，现在讲的是处理冲突的函数
1，线性探测法 H = (H(key)+i)%m，i<=m<=m-1
m是哈希表的长度，
H(key)的意思是你要对关键字做何种处理。
i棵表示为第i次冲突时探测的地址空间。
如图
假定我有这么个哈希表，我现在要将2插入进这个表里，而2用哈希函数所求的哈希值为0，冲突，则哈希值加1，变为1，还是冲突，继续加，一直加到能插进去这个表里。（这只是个比方，数值什么的不要在意）
可以看出，其探测地址是连续的
2，二次探测法 H = (H(key)+di)%m.i<=m<=m-1,探测地址是跳跃式的
m是哈希表的长度，
H(key)的意思是你要对关键字做何种处理。
求得哈希值，
第一次冲突，+ (1的平方)
第二次冲突，- (1的平方)
第三次冲突，+ (2的平方)
第四次冲突，- (2的平方)
第五次冲突，+ (3的平方)
第六次冲突，- (3的平方)
数字2，求得的哈希值为1，冲突，处理后为2，冲突，再次处理后为0，还是冲突，再次处理后为5
插入，完成，这就是二次探测法。
本人本次用的是线性探测法
其基本操作接口
Status InitHash_k(HashTable_k& H, int size, int(*hash)(KeyType, int),
void(*collision)(int&, int)); //初始化哈希表
Status DestroyHash_k(HashTable_k& H); //销毁哈希表
//Status CreateHash_k(HashTable_k& H); //构造哈希表
Status SearchHash_k(HashTable_k H, KeyType key, int& p, int& c); //在哈希表中查找关键字为Key的记录
int InsertHash_k(HashTable_k& H, RcdType e); //在哈希表H中插入e；
Status DeleteHash_k(HashTable_k& H, KeyType key, RcdType& e); //在哈希表中删除关键字为Key的记录
void Hash_KTraverse(HashTable_k& H); //哈希表的遍历初始化哈希表
Status InitHash_k(HashTable_k& H, int size, int(*hash)(KeyType, int), void(*collision)(int&, int))
{//构造一个初始容量为size的哈希表H，hash为哈希函数，collision为冲突处理函数
H.rcd = (RcdType*)malloc(size * sizeof(RcdType));
H.tag = (int*)malloc(size * sizeof(int));
if (H.rcd == NULL || H.tag == NULL)
{
return OVERFLOW;
}
else
{
for (int i = 0; i < size; i++)
{
H.tag[i] = 0;
}
H.size = size;
H.hash = hash;
H.collision = collision;
H.count = 0;
return OK;
}
}销毁哈希表
Status DestroyHash_k(HashTable_k& H)
{
if (H.rcd != NULL && H.tag != NULL)
{
free(H.rcd);
free(H.tag);
H.collision = NULL;
H.hash = NULL;
H.count = 0;
H.size = 0;
return OK;
}
else
{
return OVERFLOW;
}
}在哈希表中查找关键字为Key的记录
Status SearchHash_k(HashTable_k H, KeyType key, int& p, int& c)
{
p = H.hash(key, H.size);//求得哈希地址
while ((H.tag[p] == 1) && H.rcd[p].Key != key || H.tag[p] == -1)//判断是否有冲突，若有,执行冲突函数，取得对应地址，并用c记录冲突次数。
{
H.collision(p, H.size);
c++;
}
if (H.rcd[p].Key == key && H.tag[p] == 1)//找到
{
return SUCCESS;
}
else//没有找到
{
return UNSUCCESS;
}
}在哈希表H中插入e
int InsertHash_k(HashTable_k& H, RcdType e)
{
int c = 0, j = 0;
if (SearchHash_k(H, e.Key, j, c) == SUCCESS)
{
return -1;
}
else
{
H.rcd[j] = e;
H.tag[j] = 1;
++H.count;
return c;
}
}在哈希表中删除关键字为Key的记录
Status DeleteHash_k(HashTable_k& H, KeyType key, RcdType& e)
{
int j, c = 0;
if (SearchHash_k(H, key, j, c) == UNSUCCESS)
{
return UNSUCCESS;
}
else
{
e = H.rcd[j];
H.tag[j] = -1;
H.count--;
return SUCCESS;
}
}哈希表的遍历
void Hash_KTraverse(HashTable_k& H)
{
if (H.tag != NULL && H.rcd != NULL)
{
for (int i = 0; i < H.size; i++)
{
if (H.tag[i] == 0 || H.tag[i] == -1)
{
printf("#\n");
}
else if (H.tag[i] == -1)
{
printf("!#\n");
}
else
{
printf("%d\n", H.rcd[i].Key);
}
}
}
}一些接口的测试
int main()
{
// 开放定址
HashTable_k H;
InitHash_k(H, 5, hash, collision_1);
//构造你所要插入的数据
KeyType E[10] = { 0,1,2,3,4,5,6,7,8,9 };
RcdType EE[10];
for (int i = 0; i < 5; i++)
{
EE[i].Key = E[i];
}
for (int i = 0; i < 5; i++)
{
InsertHash_k(H, EE[i]);
}
Hash_KTraverse(H);
RcdType e;
printf("--------%d\n", DeleteHash_k(H, 2, e));
Hash_KTraverse(H);
DestroyHash_k(H);
}