C语言实现散列表（哈希Hash表)实例详解

下面我将为您详细讲解“C语言实现散列表（哈希Hash表)实例详解”的完整攻略。

概述

哈希（Hash）是一种能够快速定位存储位置的技术。哈希表（Hash Table）也叫散列表，是利用哈希函数（Hash Function）进行访问的数据结构。C语言中的哈希表主要分为两种：开放地址法和链表法。

开放地址法又分为线性探测法、二次探测法和双重散列法。本文主要介绍使用链表法实现哈希表的过程。

链表法将数组中的每个元素当作一个链表头，然后将同一个哈希值的元素储存在同一个链表中。

实现步骤

1. 定义哈希表数据结构。哈希表主要由数组和哈希函数组成。

#define MAX_SIZE 100
typedef struct hash_node
{
    int key; //键值
    int value; //值
    struct hash_node *next; 
}HashNode; //哈希表的节点

typedef struct hash_table
{
    HashNode *hash_map[MAX_SIZE]; //哈希表数组
}HashTable; //哈希表

1. 实现哈希函数。哈希函数的作用是将键值转换为对应的哈希值，以便于存储在哈希表中。

int hash_function(int key)
{
    return key % MAX_SIZE;
}

1. 实现插入节点的函数。当哈希表中不存在对应的节点时，将新节点插入到对应的链表中。

void hash_insert(HashTable *ht, int key, int value)
{
    int index = hash_function(key); //计算哈希值

    HashNode *p = ht->hash_map[index];
    while (p != NULL)
    {
        if (p->key == key) //如果存在相同的键值
        {
            p->value = value; //更新值
            return;
        }
        p = p->next;
    }

    //如果不存在相同键值，则将新节点插入到链表头
    HashNode *new_node = (HashNode*)malloc(sizeof(HashNode));
    new_node->key = key;
    new_node->value = value;
    new_node->next = ht->hash_map[index];
    ht->hash_map[index] = new_node;
}

1. 实现查找节点的函数。当哈希表中不存在对应的节点时，返回错误信息；否则返回对应节点的值。

int hash_search(HashTable *ht, int key)
{
    int index = hash_function(key); //计算哈希值

    HashNode *p = ht->hash_map[index];
    while (p != NULL)
    {
        if (p->key == key) //如果找到节点
        {
            return p->value; //返回节点的值
        }
        p = p->next;
    }

    //如果不存在指定的节点，返回错误信息
    return -1;
}

1. 实现删除节点的函数。当哈希表中不存在对应的节点时，返回错误信息；否则删除指定节点。

int hash_delete(HashTable *ht, int key)
{
    int index = hash_function(key); //计算哈希值

    HashNode *p = ht->hash_map[index];
    HashNode *pre = p;

    while (p != NULL)
    {
        if (p->key == key) //如果找到节点
        {
            if (pre == p) //如果该节点是链表头
            {
                ht->hash_map[index] = p->next; //删除链表头
            }
            else //如果该节点不是链表头
            {
                pre->next = p->next; //删除该节点
            }
            free(p); //释放空间
            return 0;
        }
        pre = p;
        p = p->next;
    }

    //如果不存在指定的节点，返回错误信息
    return -1;
}

示例说明

示例1：使用哈希表实现简单的字典

#include <stdio.h>
#include "hash_table.h"

int main()
{
    HashTable ht;
    int key, value, choice;
    int ret;

    while(1) {
        printf("---------------------------\n");
        printf("请选择操作：\n");
        printf("1、插入\n2、查找\n3、删除\n0、退出\n");

        scanf("%d", &choice);
        switch(choice) {
            case 1:
                printf("请输入要插入的键值(key)和对应的值(value)：\n");
                scanf("%d%d", &key, &value);
                hash_insert(&ht, key, value);
                break;
            case 2:
                printf("请输入要查找的键值(key)：\n");
                scanf("%d", &key);
                ret = hash_search(&ht, key);
                if (ret == -1)
                    printf("不存在该节点\n");
                else
                    printf("该键值对应的值为：%d\n", ret);
                break;
            case 3:
                printf("请输入要删除的键值(key)：\n");
                scanf("%d", &key);
                ret = hash_delete(&ht, key);
                if (ret == -1)
                    printf("不存在该节点\n");
                else
                    printf("删除成功\n");
                break;
            case 0:
                return 0;
            default:
                printf("请输入正确的操作\n");
                break;
        }
    }

    return 0;
}

示例2：使用哈希表实现统计字符串中每个字符出现的次数

#include <stdio.h>
#include <string.h>
#include "hash_table.h"

int main()
{
    char str[100];
    printf("请输入字符串：\n");
    scanf("%s", str);

    HashTable ht;
    memset(&ht, 0, sizeof(ht));

    for(int i=0; i<strlen(str); i++) {
        int key = str[i];
        int value = hash_search(&ht, key);

        if (value == -1) {
            hash_insert(&ht, key, 1);
        } else {
            hash_insert(&ht, key, value+1);
        }
    }

    for(int i=0; i<MAX_SIZE; i++) {
        HashNode *p = ht.hash_map[i];
        while(p != NULL) {
            printf("字符'%c'出现了%d次\n", p->key, p->value);
            p = p->next;
        }
    }

    return 0;
}

结束语

以上就是使用链表法实现哈希表的完整攻略，包含了定义哈希表数据结构、实现哈希函数、插入节点、查找节点和删除节点等过程。同时也给出了两个示例，可供参考。