设为首页 加入收藏

TOP

C语言实现的哈希表(一)
2018-10-28 16:08:23 】 浏览:82
Tags:语言 实现 哈希

C语言实现的哈希表


哈希表可以简单理解为多个链表的集合,将每个新的成员根据其哈希值进行分类,这样可以加快链表的查找速度


#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define HASHSIZE 10


typedef unsigned int uint;
/*定义一个链表的节点*/
typedef struct Node{
    char key[17];
    char value[4];
    struct Node *next;
}Node;


/*定义一组链表*/
Node *node[HASHSIZE];


/*初始化:为链表头开辟空间*/
int init(Node *node)
{
    node = (Node *)malloc(sizeof(Node));
    if(NULL == node)
        return 1;


    bzero(node, sizeof(Node));


    return 0;
}


/*计算哈希值*/
uint hash(const char *key){
    uint hash = 0;
    for(; *key; ++key)
    {
        hash = hash*33+*key;
    }
    return hash%HASHSIZE;
}


/*查找:根据哈希值得出index, 然后到对应的链表中查找*/
Node *lookup(const char *key)
{
    Node *np;
    uint index;
    index = hash(key);
    for(np = node[index];np;np = np->next){
        if(!strcmp(key, np->key))
            return np;
    }
    return NULL;
}


/*插入:先查找该值是否存在,然后计算哈希值,插入对应的链表*/
uint install(const char *key, const char *value)
{
    uint index;
    Node *np;


    if(!(np = lookup(key))){
        index = hash(key);
        np = (Node*)malloc(sizeof(Node));
        if(!np)
            return 1;
        strcpy(np->key, key);
        strcpy(np->value, value);


        np->next = node[index];
        node[index] = np;
    }
    return 0;
}


/*例:*/
int main(void)
{
    /*为哈希表插入一组数据*/
    char key[17] = "10.10.16.31";
    char value[4] = "001";
    install(key, value);


    char key1[17] = "10.10.16.32";
    char value1[4] = "002";
    install(key1, value1);


    char key2[17] = "10.10.16.33";
    char value2[4] = "003";
    install(key2, value2);


    char key3[17] = "10.10.16.34";
    char value3[4] = "004";
    install(key3, value3);


    char key4[17] = "10.10.16.41";
    char value4[4] = "005";
    install(key4, value4);


    Node *np;


    /*哈希表初始化:如果不为表头赋值的话可以省略*/
    int i,j;
    for(i=0;i<HASHSIZE;i++){
        init(node[i]);
    }


    /*遍历哈希表*/
    for(i=0; i<HASHSIZE; i++)
    {
        if(node[i]){
            printf("i:%d, key:%s, value:%s\n", i, node[i]->key, node[i]->value);


            np = node[i]->next;
            while(np){
                printf("key:%s, value:%s\n", np->key, np->value);
                np = np->next;
            }
        }
    }
    return 0;
}


输出如下:


i:0, key:10.10.16.41, value:00
编程开发网

首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C++必备基础知识和编程规范 下一篇C语言双向循环链表api(源自glust..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }