哈希表

用此程序,演示了

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

数据结构文章被收录于专栏

数据结构大篇幅笔记记录