简单哈希表(hash table c)

hash表,有时候也被称为散列表。

引自wiki: 散列表(Hash table,也叫哈希表),是根据关键字(Key value)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。
下面我们可以写一个简单的hash操作代码。

定义哈希表数据类型

/* hash.h */
#include <stdbool.h>

#ifndef HASH_H
#define HASH_H

typedef struct _NODE {
        int data;
        struct _NODE *next;
} NODE;

typedef struct _HASH_TABLE {
        NODE *value[10];
} HASH_TABLE;

HASH_TABLE *create_hash_table(void);
NODE *find_data_in_hash(HASH_TABLE *pHashTab, int data);
void print_hash_table(HASH_TABLE *pHashTab);
bool insert_data_into_hash(HASH_TABLE *pHashTab, int data);
bool delete_data_from_hash(HASH_TABLE *pHashTab, int data);
bool delete_idx_data_from_hash(HASH_TABLE *pHashTab, int idx);
bool delete_all_data_from_hash(HASH_TABLE *pHashTab);
bool reset_hash_table(HASH_TABLE *pHashTab);
bool destroy_hash_table(HASH_TABLE **ppHashTab);

#endif//HASH_H

哈希表操作函数

/* hash.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hash.h"

HASH_TABLE *create_hash_table(void)
{
        HASH_TABLE *pHashTab = (HASH_TABLE *)malloc(sizeof (HASH_TABLE));
        memset(pHashTab, 0, sizeof (HASH_TABLE));

        return pHashTab;
}

NODE *find_data_in_hash(HASH_TABLE *pHashTab, int data)
{
        NODE *pNode;
        if (NULL == pHashTab)
                return NULL;
        int i = abs(data) % 10;
        if (NULL == (pNode = pHashTab->value[i]))
                return NULL;
        while (pNode) {
                if (data == pNode->data)
                        return pNode;
                pNode = pNode->next;
        }

        return NULL;
}

void print_hash_table(HASH_TABLE *pHashTab)
{
        if (NULL == pHashTab) {
                printf("This hash table is unreal!\a\n");
                return;
        }
        printf("Hash table info: \n");
        NODE *pNode;
        int i;
        for (i = 0; i < 10; i++) {
                if (NULL == (pNode = pHashTab->value[i])) {
                        printf("pHashTab->value[%d]: empty\n", i);
                        continue;
                }
                printf("pHashTab->value[%d]: ", i);
                while (pNode) {
                        printf("%d ", pNode->data);
                        pNode = pNode->next;
                }
                putchar('\n');
        }
        printf("--------------------------------------------\n");

        return;
}

bool insert_data_into_hash(HASH_TABLE *pHashTab, int data)
{
        NODE *pNode;
        if (NULL == pHashTab)
                return false;
        int i = abs(data) % 10;
        if (NULL == pHashTab->value[i]) {
                pNode = (NODE *)malloc(sizeof (NODE));
                memset(pNode, 0, sizeof (NODE));
                pNode->data = data;
                pHashTab->value[i] = pNode;

                return true;
        }

        if (NULL != find_data_in_hash(pHashTab, data)) {
                printf("Same data %d already exists\a\n", data);
                return false;
        }

        pNode = pHashTab->value[i];
        while (NULL != pNode->next)
                pNode = pNode->next;

        pNode->next = (NODE *)malloc(sizeof (NODE));
        memset(pNode->next, 0, sizeof (NODE));
        pNode->next->data = data;

        return true;
}

bool delete_data_from_hash(HASH_TABLE *pHashTab, int data)
{
        NODE *p = NULL;
        NODE *pNode = NULL;
        int i = abs(data) % 10;
        if (NULL == pHashTab || NULL == pHashTab->value[i]) {
                printf("The data %d out of hash table\a\n", data);
                return false;
        }

        pNode = pHashTab->value[i];
        if (pNode->data == data) {
                pHashTab->value[i] = pNode->next;
                free(pNode);
                printf("Delete the data %d from hash table\n", data);
                return true;
        }

        while ((p = pNode->next)) {
                if (p->data == data) {
                        pNode->next = p->next;
                        free(p);
                        printf("Delete the data %d from hash table\n", data);
                        return true;
                }
                pNode = pNode->next;
        }
        printf("The data %d out of hash table\a\n", data);

        return false;
}

bool delete_idx_data_from_hash(HASH_TABLE *pHashTab, int idx)
{
        NODE *pHead;
        NODE *pNode;

        if (NULL == pHashTab)
                return false;
        if (idx < 0 || idx >= 10) {
                printf("error idx %d in hash table\n", idx);
                return false;
        }
        int cnt = 0;
        if (NULL == (pHead = pHashTab->value[idx])) {
                printf("TpHashTab->value[%d] is empty\n", idx);
                return false;
        }

        while ((pNode = pHead->next)) {
                pHead->next = pNode->next;
                free(pNode);
                cnt++;
        }

        if (NULL == pHead->next) {
                pHashTab->value[idx] = pHead->next;
                free(pHead);
                cnt++;
        }
        printf("delete %d data from pHashTab->value[%d]\n", cnt, idx);

        return true;
}

bool delete_all_data_from_hash(HASH_TABLE *pHashTab)
{
        NODE *pHead;
        NODE *pNode;

        if (NULL == pHashTab)
                return false;
        int i, cnt = 0;
        for (i = 0; i < 10; i++) {
                if (NULL == (pHead = pHashTab->value[i]))
                        continue;

                while ((pNode = pHead->next)) {
                        pHead->next = pNode->next;
                        free(pNode);
                        cnt++;
                }

                if (NULL == pHead->next) {
                        pHashTab->value[i] = pHead->next;
                        free(pHead);
                        cnt++;
                }
        }
        printf("delete %d data form this hash. \n", cnt);

        return true;
}

bool reset_hash_table(HASH_TABLE *pHashTab)
{
        if (delete_all_data_from_hash(pHashTab)) {
                memset(pHashTab, 0, sizeof (HASH_TABLE));
                return true;
        } else {
                return false;
        }
}

bool destroy_hash_table(HASH_TABLE **ppHashTab)
{
        if (NULL == *ppHashTab) {
                printf("This hash table is unreal! \n");
                return false;
        }
        HASH_TABLE *p = *ppHashTab;
        if (delete_all_data_from_hash(*ppHashTab)) {
                free(p);
                *ppHashTab = NULL;
                printf("Hash table have been destroyed. \n");
                return true;
        } else {
                return false;
        }
}

哈希表数据测试

/* include hash.c and main.c */
#include <stdio.h>
#include "hash.h"

int main(void)
{
        printf("Creat hash table: \n");
        HASH_TABLE *p = create_hash_table();

        printf("Insert data into hash table: \n");
        insert_data_into_hash(p, 22);
        insert_data_into_hash(p, -12);
        insert_data_into_hash(p, 1);
        insert_data_into_hash(p, 2);
        insert_data_into_hash(p, 10);
        insert_data_into_hash(p, 0);
        print_hash_table(p);

        printf("Delete the existing data: \n");
        delete_data_from_hash(p, 22);
        print_hash_table(p);

        printf("Remove non-existen data: \n");
        delete_data_from_hash(p, 22);
        print_hash_table(p);

        printf("To delete a data list: \n");
        delete_idx_data_from_hash(p, 2);
        print_hash_table(p);

        printf("Reset hash table: \n");
        reset_hash_table(p);
        print_hash_table(p);

        printf("Insert data into hash table: \n");
        insert_data_into_hash(p, 2);
        insert_data_into_hash(p, 10);
        insert_data_into_hash(p, -20);
        insert_data_into_hash(p, 20);
        print_hash_table(p);

        printf("Remove all data from hash table: \n");
        delete_all_data_from_hash(p);
        print_hash_table(p);

        printf("Destroy hash table: \n");
        destroy_hash_table(&p);
        print_hash_table(p);

        return 0;
}

Linux下编译和运行

gcc -Wall -o main main.c hash.c
./main

运行结果:

[xxx@localhost easy]$ ./main
Creat hash table:
Insert data into hash table:
Hash table info:
pHashTab->value[0]: 10 0
pHashTab->value[1]: 1
pHashTab->value[2]: 22 -12 2
pHashTab->value[3]: empty
pHashTab->value[4]: empty
pHashTab->value[5]: empty
pHashTab->value[6]: empty
pHashTab->value[7]: empty
pHashTab->value[8]: empty
pHashTab->value[9]: empty
——————————————–
Delete the existing data:
Delete the data 22 from hash table
Hash table info:
pHashTab->value[0]: 10 0
pHashTab->value[1]: 1
pHashTab->value[2]: -12 2
pHashTab->value[3]: empty
pHashTab->value[4]: empty
pHashTab->value[5]: empty
pHashTab->value[6]: empty
pHashTab->value[7]: empty
pHashTab->value[8]: empty
pHashTab->value[9]: empty
——————————————–
Remove non-existen data:
The data 22 out of hash table
Hash table info:
pHashTab->value[0]: 10 0
pHashTab->value[1]: 1
pHashTab->value[2]: -12 2
pHashTab->value[3]: empty
pHashTab->value[4]: empty
pHashTab->value[5]: empty
pHashTab->value[6]: empty
pHashTab->value[7]: empty
pHashTab->value[8]: empty
pHashTab->value[9]: empty
——————————————–
To delete a data list:
delete 2 data from pHashTab->value[2]
Hash table info:
pHashTab->value[0]: 10 0
pHashTab->value[1]: 1
pHashTab->value[2]: empty
pHashTab->value[3]: empty
pHashTab->value[4]: empty
pHashTab->value[5]: empty
pHashTab->value[6]: empty
pHashTab->value[7]: empty
pHashTab->value[8]: empty
pHashTab->value[9]: empty
——————————————–
Reset hash table:
delete 3 data form this hash.
Hash table info:
pHashTab->value[0]: empty
pHashTab->value[1]: empty
pHashTab->value[2]: empty
pHashTab->value[3]: empty
pHashTab->value[4]: empty
pHashTab->value[5]: empty
pHashTab->value[6]: empty
pHashTab->value[7]: empty
pHashTab->value[8]: empty
pHashTab->value[9]: empty
——————————————–
Insert data into hash table:
Hash table info:
pHashTab->value[0]: 10 -20 20
pHashTab->value[1]: empty
pHashTab->value[2]: 2
pHashTab->value[3]: empty
pHashTab->value[4]: empty
pHashTab->value[5]: empty
pHashTab->value[6]: empty
pHashTab->value[7]: empty
pHashTab->value[8]: empty
pHashTab->value[9]: empty
——————————————–
Remove all data from hash table:
delete 4 data form this hash.
Hash table info:
pHashTab->value[0]: empty
pHashTab->value[1]: empty
pHashTab->value[2]: empty
pHashTab->value[3]: empty
pHashTab->value[4]: empty
pHashTab->value[5]: empty
pHashTab->value[6]: empty
pHashTab->value[7]: empty
pHashTab->value[8]: empty
pHashTab->value[9]: empty
——————————————–
Destroy hash table:
delete 0 data form this hash.
Hash table have been destroyed.
This hash table is unreal!

借鉴:http://blog.csdn.net/feixiaoxing/article/details/6885657

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据