摘要:本文主要向大家介绍了C/C++知识点之C语言实现的哈希表,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。
本文主要向大家介绍了C/C++知识点之C语言实现的哈希表,通过具体的内容向大家展示,希望对大家学习C/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;
}
本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号