/*
 ============================================================================
 Name        : C_hashMap.c
 Author      : 风的影子
 Version     : 1.0
 Copyright   : Your copyright notice
 Description : Hello World in C, Ansi-style
 ============================================================================
 */

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

/*
 * C语言实现的字符串hash表
 * hash_get 通过key获取value
 * hash_put 向hash表中添加键值
 * 风的影子 编写
 * 2019-11-07
 */

#define VALUE_TYPE char*

typedef struct _NODE{
    char *name;
    VALUE_TYPE desc;
    struct _NODE *next;
} HASH_NODE;

#define HASHSIZE 101
HASH_NODE *hash_node;
//struct _NODE* hashtab[HASHSIZE];

HASH_NODE *create_hash(){
    HASH_NODE *hash = malloc(sizeof(HASH_NODE));
    hash->name = NULL;
    hash->desc = NULL;
    hash->next = NULL;
    return hash;
}

unsigned int hashCode(char *s){
    unsigned int h=0;
    for(;*s;s++)
        h=*s+h*31;
    return h%HASHSIZE;
}

/*通过key获取对应的node*/
static HASH_NODE* lookup(HASH_NODE *hash,char *n){
    unsigned int hi=hashCode(n);
    HASH_NODE* np=hash;
    for(;np!=NULL;np=np->next){
        if(!strcmp(np->name,n))
            return np;
    }
    return NULL;
}

//复制字符串
char* m_strdup(char *o){
    int l=strlen(o)+1;
    char *ns=(char*)malloc(l*sizeof(char));
    strcpy(ns,o);
    if(ns==NULL)
        return NULL;
    else
        return ns;
}

//通过key寻找value
VALUE_TYPE hash_get(HASH_NODE *hash, char* name){
    HASH_NODE* n=lookup(hash,name);
    if(n==NULL)
        return NULL;
    else
        return n->desc;
}

//向hash表中添加一个key
void hash_put(HASH_NODE *hash, char* key, VALUE_TYPE value){
    if(hash->name==NULL){
        hash->name = key;
        hash->desc = value;
    }
    else{
        HASH_NODE *node = create_hash();
        node->name = key;
        node->desc = value;
        while(hash->next){
            hash = hash->next;
        }
        hash->next = node;
    }

}

int install(HASH_NODE *hash,char* name,char* desc){
    unsigned int hi;

    HASH_NODE *np=NULL;
    if((np=lookup(hash,name))==NULL){
        hi=hashCode(name);
        np=(HASH_NODE*)malloc(sizeof(HASH_NODE));
        if(np==NULL)
            return 0;

        np->name=(name);
        if(np->name==NULL) return 0;
        HASH_NODE *temp = create_hash();

        np->next=temp;
        np = temp;
    }
    else
        free(np->desc);
    np->desc=(desc);
    if(np->desc==NULL) return 0;
    return 1;
}

/* A pretty useless but good debugging function,
which simply displays the hashtable in (key.value) pairs
*/

//输出hash表数据
void hash_displaytable(HASH_NODE *hash){
    int i;

    while(hash->next){
        printf("%s %s\n",hash->name,hash->desc);
        hash = hash->next;
    }
    printf("%s %s\n",hash->name,hash->desc);
}

//释放内存
void hash_free(HASH_NODE *hash){
    HASH_NODE *head = hash;
    while(head->next){
        HASH_NODE *next = head->next;
        free(head);
        head = next;
    }
}

int main(){
    int i;
    HASH_NODE *hash_node=create_hash();
    char* names[]={"name","address","phone","k101","k110"};
    char* descs[]={"Sourav","Sinagor","26300788","Value1","Value2"};
//    inithashtab();
//增加部分--------------------------打印hash_table_index
//    for(i = 0; i < 5; i++)
//    {
//        unsigned int hi=hashCode(names[i]);
//        printf("%s--hash_table_index=%d\n", names[i], hi);
//    }
//---------------------------------------打印hash_table_index
    for(i=0;i<5;i++)
        hash_put(hash_node, names[i],descs[i]);
    hash_displaytable(hash_node);
    printf("we have %s and %s\n",hash_get(hash_node,"k101"),hash_get(hash_node,"phone"));
//    hash_displaytable(hash_node);
    hash_free(hash_node);
//    cleanup();

    return 0;
}

1 对 “C语言实现字符串hash表”的想法;

发表评论

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