C语言实现哈希表(key为字符型)

首先给大家推荐一下我老师大神的人工智能教学网站。教学不仅零基础,通俗易懂,而且非常风趣幽默,还时不时有内涵黄段子!点这里可以跳转到网站

 简单实现了哈希表的插入和查找功能,简要说明如下:

1、数据结构:

struct HashNode

{

            char* sKey;     //键

            int nValue;      //值

            HashNode* pNext; //当Hash值冲突时,指向HASH值相同的下一个节点。

}

HashNode* hashTable[HASH_TABLE_MAX_SIZE]; //哈希表的数组

int hash_table_size;       //哈希表中元素的个数

2、函数:

void hash_table_init() 初始化哈希表

void hash_table_insert(const char* skey, int nvalue) 向哈希表中插入键位skey,值为nvalue的键值对。

                            当skey已经在哈希表中时,忽略该键值对。 

void hash_table_remove(const char* skey) 从哈希表中删除键值对。

HashNode* hash_table_lookup(const char* skey) 查找键值为skey的节点。当找到时,返回对应的HashNode指针,

                            没有找到时,返回NULL。

void hash_table_release() 释放哈希表的内存空间。

C语言实现的哈希表(HashTable)源码如下:

/* * Author: puresky * Date: 2011/01/08 * Purpose: a simple implementation of HashTable in C */ #include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h> /*=================hash table start=========================================*/ #define HASH_TABLE_MAX_SIZE 10000typedef struct HashNode_Struct HashNode; struct HashNode_Struct{    char* sKey;    int nValue;    HashNode* pNext;}; HashNode* hashTable[HASH_TABLE_MAX_SIZE]; //hash table data strcutrueint hash_table_size;  //the number of key-value pairs in the hash table! //initialize hash tablevoid hash_table_init(){    hash_table_size = 0;    memset(hashTable, 0, sizeof(HashNode*) * HASH_TABLE_MAX_SIZE);}  //string hash functionunsigned int hash_table_hash_str(const char* skey){    const signed char *p = (const signed char*)skey;    unsigned int h = *p;    if(h)    {        for(p += 1; *p != '\0'; ++p)            h = (h << 5) - h + *p;    }    return h;} //insert key-value into hash tablevoid hash_table_insert(const char* skey, int nvalue){    if(hash_table_size >= HASH_TABLE_MAX_SIZE)    {        printf("out of hash table memory!\n");        return;    }     unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;     HashNode* pHead =  hashTable[pos];    while(pHead)    {        if(strcmp(pHead->sKey, skey) == 0)        {            printf("%s already exists!\n", skey);            return ;        }        pHead = pHead->pNext;    }     HashNode* pNewNode = (HashNode*)malloc(sizeof(HashNode));    memset(pNewNode, 0, sizeof(HashNode));    pNewNode->sKey = (char*)malloc(sizeof(char) * (strlen(skey) + 1));    strcpy(pNewNode->sKey, skey);    pNewNode->nValue = nvalue;     pNewNode->pNext = hashTable[pos];    hashTable[pos] = pNewNode;      hash_table_size++;}//remove key-value frome the hash tablevoid hash_table_remove(const char* skey){    unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;    if(hashTable[pos])    {        HashNode* pHead = hashTable[pos];        HashNode* pLast = NULL;        HashNode* pRemove = NULL;        while(pHead)        {            if(strcmp(skey, pHead->sKey) == 0)            {                pRemove = pHead;                break;            }            pLast = pHead;            pHead = pHead->pNext;        }        if(pRemove)        {            if(pLast)                pLast->pNext = pRemove->pNext;            else                hashTable[pos] = NULL;             free(pRemove->sKey);            free(pRemove);        }    }} //lookup a key in the hash tableHashNode* hash_table_lookup(const char* skey){    unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;    if(hashTable[pos])    {        HashNode* pHead = hashTable[pos];        while(pHead)        {            if(strcmp(skey, pHead->sKey) == 0)                return pHead;            pHead = pHead->pNext;        }    }    return NULL;} //print the content in the hash tablevoid hash_table_print(){    printf("===========content of hash table=================\n");    int i;    for(i = 0; i < HASH_TABLE_MAX_SIZE; ++i)        if(hashTable[i])        {            HashNode* pHead = hashTable[i];            printf("%d=>", i);            while(pHead)            {                printf("%s:%d  ", pHead->sKey, pHead->nValue);                pHead = pHead->pNext;            }            printf("\n");        }} //free the memory of the hash tablevoid hash_table_release(){    int i;    for(i = 0; i < HASH_TABLE_MAX_SIZE; ++i)    {        if(hashTable[i])        {            HashNode* pHead = hashTable[i];            while(pHead)            {                HashNode* pTemp = pHead;                pHead = pHead->pNext;                if(pTemp)                {                    free(pTemp->sKey);                    free(pTemp);                }             }        }    }} /* ===============================hash table end=========================*/  /* ============================test function ============================*/#define MAX_STR_LEN 20#define MIN_STR_LEN 10void rand_str(char r[]){    int i;    int len = MIN_STR_LEN + rand() % (MAX_STR_LEN - MIN_STR_LEN);    for(i = 0; i < len - 1; ++i)        r[i] = 'a' + rand() % ( 'z' - 'a');    r[len - 1] = '\0';} int main(int argc, char** argv){    srand(time(NULL));    hash_table_init();    printf("insert testing.........\n");    int n = 10;    const char *key1 = "aaammd";    const char *key2 = "xzzyym";    const char *key3 = "cdcded";     hash_table_insert(key1, 110);    hash_table_insert(key2, 220);    hash_table_insert(key3, 330);    char str[MAX_STR_LEN + 1];    while(n--)    {        rand_str(str);        hash_table_insert(str, n);    }    hash_table_print();     printf("\nlookup testing..........\n");    HashNode* pNode = hash_table_lookup(key1);    printf("lookup result:%d\n", pNode->nValue);    pNode = hash_table_lookup(key2);    printf("lookup result:%d\n", pNode->nValue);     printf("\nremove testing..........\n");    printf("before remove %s:\n", key3);    hash_table_print();    hash_table_remove(key3);    printf("after remove:\n");    hash_table_print();    hash_table_release();     system("pause");    return 0;}

点这里可以跳转到人工智能网站

发表评论