用此程序,演示了
1哈希表的建表和删除
2哈希函数
3哈希表插入结点
4打印哈希表对应位置
5哈希表根据键值查找
等功能
#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <stdlib.h>
#define HARSH_TABLE_MAX_SIZE 3 // 哈希数组的最大元素个数
//哈希表节点定义
typedef struct HarshNode
{
char *sKey;
int nValue;
// [sKey,nValue]是一对键值对
//名值对=键值对=属性值对
//元组的集合< name，value >
struct HarshNode *pNext;
} HarshNode;
//哈希结点指针数组
//表中每一个元素都是指向结点的指针
HarshNode *myHarshTable[HARSH_TABLE_MAX_SIZE];
//这个变量用于记录哈希表中结点总数
unsigned int myHarshTableNodeNum = 0;
//用于将上述myHarshTable初始化
void myHarshTableInit()
{
memset(myHarshTable, 0, sizeof(HarshNode *) * HARSH_TABLE_MAX_SIZE);
myHarshTableNodeNum = 0;
}
//用于删除myHarshTable
//首先要删除各个结点中,为了保存字符串而分配的动态内存
//其次要删除各个结点本身
//该哈希表(指针数组)本身不是动态分配,故不需要删除
void myHarshTableFree()
{
for (int i = 0; i < HARSH_TABLE_MAX_SIZE; i++)
{
//如果此处为空,则不必删除
if (myHarshTable[i] == NULL)
continue;
//若非空则遍历该位置的每一个结点
HarshNode *tmp1 = myHarshTable[i];
HarshNode *tmp2;
while (tmp1 != NULL)
{
free(tmp1->sKey);
tmp2 = tmp1->pNext;
free(tmp1);
tmp1 = tmp2;
}
}
}
//利用键值求得哈希值的哈希函数
//使用时,要再进行模运算才能真正得到在哈希表中的位置
unsigned int HashFunction(const char *sKey)
{
// https://blog.csdn.net/guotianqing/article/details/77341657
//在遇到有char类型扩充的时候,必须要使用unsigned char才不会出错
//默认的signed char只能表示-128~127,负数拓展到int时,会有符号拓展错误
//只有用unsigned char才行
//将char拓展为int时,要习惯于使用unsigned char和unsigned int
const unsigned char *p = (const unsigned char *)sKey;
//最初时value中保存着的,是sKey字符串中,第一个ASCII字符的int形式
unsigned int value = *p;
//通过这样一个变换
//得到了跟所有的字符串都相关的哈希值value
if (value)
{
for (p += 1; *p != '\0'; p++)
{
value = (value << 5) - value + *p;
}
}
return value;
}
//根据键值对向哈希表中添加节点，如果sKey已经存在则直接更新键值nValue
//添加成功返回0，添加失败返回-1
int myHarshTableInsertNode(const char *sKey, int nValue)
{
//首先存入哈希表指针数组中对应位置的头指针
//随后经过遍历,达到对应位置链表的尾部
HarshNode *pHarshNode = NULL;
//保存键值对的新结点
HarshNode *pNewNode = NULL;
unsigned int pos = 0x0;
//要保证装填因子小于1,并且要保证输入的键值非空
//否则输入无效,返回-1
if ((myHarshTableNodeNum >= HARSH_TABLE_MAX_SIZE) || (NULL == sKey))
{
printf("Node-Insert fail!\n");
return -1;
}
//求出该键值对应在哈希表中的位置
pos = HashFunction(sKey) % HARSH_TABLE_MAX_SIZE; //用这种方法计算sKey在哈希数组中对应的位置
//插入成功,告知结点插入位置
printf("The node is inserted at %d. \n", pos);
pHarshNode = myHarshTable[pos];
//此处首先判断现有键值是否已经存在
//并为采用尾插法插入结点做准备
//注意到此处没有头结点,只有头指针,故要对头指针采用特殊对待
int isEmptyPos = 0;
if (!pHarshNode)
isEmptyPos = 1;
else
{
HarshNode *tmp = pHarshNode->pNext;
while (NULL != tmp)
{
if (strcmp(pHarshNode->sKey, sKey) == 0)
{
pHarshNode->nValue = nValue;
return 0;
}
pHarshNode = tmp;
tmp = pHarshNode->pNext;
}
}
/* ----------- 以下语句用于赋值新结点 ---------- */
//申请一块HarshNode大小的内存,分配给新结点
//用于保存键值对
pNewNode = (HarshNode *)malloc(sizeof(HarshNode));
//如果内存不够则返回一个-1
if (NULL == pNewNode)
{
return -1;
}
memset(pNewNode, 0, sizeof(HarshNode));
//在这个结点内,申请一块存放字符串键值的空间
pNewNode->sKey = (char *)malloc(strlen(sKey) + 1);
//同样地,内存不够则返回-1
if (NULL == pNewNode->sKey)
{
free(pNewNode);
return -1;
}
memset(pNewNode->sKey, 0, strlen(sKey) + 1);
//以上将空间分配完毕
//以下将键值和值都赋予对应结点,正式初始化结点
strcpy(pNewNode->sKey, sKey);
pNewNode->nValue = nValue;
pNewNode->pNext = NULL;
/* ---------------------------------- */
//采用尾插法插入结点
if (isEmptyPos)
myHarshTable[pos] = pNewNode;
else
pHarshNode->pNext = pNewNode;
//最终成功插入了一个新结点,哈希表总结点数加1
myHarshTableNodeNum++;
return 0;
}
//哈希表中对应的pos位置的一串哈希值打印出来
void PrintHarshNode(int pos)
{
HarshNode *pHarshNode = NULL;
if (pos >= HARSH_TABLE_MAX_SIZE)
return;
pHarshNode = myHarshTable[pos];
if (NULL == pHarshNode)
printf("This position is empty!\n");
else
printf("This position is not empty: \n");
while (NULL != pHarshNode)
{
printf("This node is: \n");
printf("Position:%d, sKey:%s, nValue:%d \n", pos, pHarshNode->sKey, pHarshNode->nValue);
pHarshNode = pHarshNode->pNext;
}
}
//根据键值sKey查找对应的哈希节点
//找到则返回对应结点指针
//没有找到则返回空指针
HarshNode *myHarshTableLookUp(const char *sKey)
{
unsigned int pos = 0;
HarshNode *pHarshHead = NULL;
if (NULL == sKey)
return NULL;
//根据哈希值计算出在哈希表中的位置
pos = HashFunction(sKey) % HARSH_TABLE_MAX_SIZE;
pHarshHead = myHarshTable[pos];
//在对应位置寻找
while (NULL != pHarshHead)
{
if (strcmp(sKey, pHarshHead->sKey) == 0)
//找到了则返回对应指针
return pHarshHead;
pHarshHead = pHarshHead->pNext; // 没有找到的话来到下一个节点
}
//最终没有找到则返回空指针
return NULL;
}
int main()
{
//用于初始化哈希表
myHarshTableInit();
//先多插入几组数据
myHarshTableInsertNode("hungers", 12345);
myHarshTableInsertNode("qwerty", 54321);
//待插入的键值对如下
//在"abcd"的名称下,存有1234这个值
char *pSkey = "abcd";
int nValue = 1234;
// return指示哈希结点是否成功插入哈希表中
int ret = -1;
//pos存入哈希值插入的位置
int pos = 0xffffffff;
//用于存放查找哈希值时,返回的指针
HarshNode *pHarshNode = NULL;
//将键值对存入哈希表中
ret = myHarshTableInsertNode(pSkey, nValue);
if (!ret)
{
pos = HashFunction(pSkey) % HARSH_TABLE_MAX_SIZE;
printf("Try to find and print all the saved data at:%d\n", pos);
PrintHarshNode(pos);
}
pHarshNode = myHarshTableLookUp(pSkey);
if (NULL != pHarshNode)
{
printf("We could also find the node directly according to the sKey:%s\nthe nValue is: %d\n", pHarshNode->sKey, pHarshNode->nValue);
}
//一定要释放动态分配的空间
myHarshTableFree();
return 0;
}
/*
The node is inserted at 1.
The node is inserted at 0.
The node is inserted at 1.
Try to find and print all the saved data at:1
This position is not empty:
This node is:
Position:1, sKey:hungers, nValue:12345
This node is:
Position:1, sKey:abcd, nValue:1234
We could also find the node directly according to the sKey:abcd
the nValue is: 1234
*/
参考:https://blog.csdn.net/weixin_40204595/article/details/81584679
京公网安备 11010502036488号