c语言哈希表数据结构_c语言列表数据结构

c语言哈希表数据结构_c语言列表数据结构简单的哈希表实现这是一个简单的哈希表的实现,用c语言做的。原理先说一下原理。先是有一个bucket数组,也就是所谓的桶。哈希表的特点就是数据与其在表中的位置存在相关性,也就是有关系的,通过数据应该可以计算出其位置。这个哈希表是用于存储一些键值对(key–value)关系的数据,其key也就是其在表中的索引,value是附带的数据。通过散列算法,将字符串的key映射到某个桶中,这个算法是确定的…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

简单的哈希表实现

这是一个简单的哈希表的实现,用c语言做的。

原理

先说一下原理。

先是有一个bucket数组,也就是所谓的桶。

哈希表的特点就是数据与其在表中的位置存在相关性,也就是有关系的,通过数据应该可以计算出其位置。

这个哈希表是用于存储一些键值对(key — value)关系的数据,其key也就是其在表中的索引,value是附带的数据。

通过散列算法,将字符串的key映射到某个桶中,这个算法是确定的,也就是说一个key必然对应一个bucket。

然后是碰撞问题,也就是说多个key对应一个索引值。举个例子:有三个key:key1,key3,key5通过散列算法keyToIndex得到的索引值都为2,也就是这三个key产生了碰撞,对于碰撞的处理,采取的是用链表连接起来,而没有进行再散列。

019ac0debad9498fb26efda52d55fc9b.jpg

这是包含的头文件

#include

#include

#include

#define BUCKETCOUNT 16

哈希表和节点数据结构的定义

struct hashEntry

{

const char* key;

char* value;

struct hashEntry* next;

};

typedef struct hashEntry entry;

struct hashTable

{

entry bucket[BUCKETCOUNT]; //先默认定义16个桶

};

typedef struct hashTable table;

初始化和释放哈希表

//初始化哈希表

void initHashTable(table* t)

{

int i;

if (t == NULL)return;

for (i = 0; i < BUCKETCOUNT; ++i) {

t->bucket[i].key = NULL;

t->bucket[i].value = NULL;

t->bucket[i].next = NULL;

}

}

//释放哈希表

void freeHashTable(table* t)

{

int i;

entry* e,*ep;

if (t == NULL)return;

for (i = 0; i

e = &(t->bucket[i]);

while (e->next != NULL) {

ep = e->next;

e->next = ep->next;

free(ep->key);

free(ep->value);

free(ep);

}

}

}

哈希散列算法

//哈希散列方法函数

int keyToIndex(const char* key)

{

int index , len , i;

if (key == NULL)return -1;

len = strlen(key);

index = (int)key[0];

for (i = 1; i

index *= 1103515245 + (int)key[i];

}

index >>= 27;

index &= (BUCKETCOUNT – 1);

return index;

}

辅助函数strDup

这是比较多余的做法,因为C标准库中string.h中有一系列这样的函数。

//在堆上分配足以保存str的内存

//并拷贝str内容到新分配位置

char* strDup(const char* str)

{

int len;

char* ret;

if (str == NULL)return NULL;

len = strlen(str);

ret = (char*)malloc(len + 1);

if (ret != NULL) {

memcpy(ret , str , len);

ret[len] = ‘\0’;

}

return ret;

}

string.h中的相关函数

#include

char *strdup(const char *s);

char *strndup(const char *s, size_t n);

char *strdupa(const char *s);

char *strndupa(const char *s, size_t n);

哈希表的插入和修改

这个了插入和修改是一个方法,如果key在哈希表中已经存在,那么就是修改value,否则就是插入一个节点。

//向哈希表中插入数据

int insertEntry(table* t , const char* key , const char* value)

{

int index , vlen1 , vlen2;

entry* e , *ep;

if (t == NULL || key == NULL || value == NULL) {

return -1;

}

index = keyToIndex(key);

if (t->bucket[index].key == NULL) {

t->bucket[index].key = strDup(key);

t->bucket[index].value = strDup(value);

}

else {

e = ep = &(t->bucket[index]);

while (e != NULL) { //先从已有的找

if (strcmp(e->key , key) == 0) {

//找到key所在,替换值

vlen1 = strlen(value);

vlen2 = strlen(e->value);

if (vlen1 > vlen2) {

free(e->value);

e->value = (char*)malloc(vlen1 + 1);

}

memcpy(e->value , value , vlen1 + 1);

return index; //插入完成了

}

ep = e;

e = e->next;

} // end while(e…

//没有在当前桶中找到

//创建条目加入

e = (entry*)malloc(sizeof (entry));

e->key = strDup(key);

e->value = strDup(value);

e->next = NULL;

ep->next = e;

}

return index;

}

哈希表中查找

因为这个哈希表中保存的是键值对,所以这个方法是从哈希表中查找key对应的value的。要注意,这里返回的是value的地址,不应该对其指向的数据进行修改,否则可能会有意外发生。

//在哈希表中查找key对应的value

//找到了返回value的地址,没找到返回NULL

const char* findValueByKey(const table* t , const char* key)

{

int index;

const entry* e;

if (t == NULL || key == NULL) {

return NULL;

}

index = keyToIndex(key);

e = &(t->bucket[index]);

if (e->key == NULL) return NULL;//这个桶还没有元素

while (e != NULL) {

if (0 == strcmp(key , e->key)) {

return e->value; //找到了,返回值

}

e = e->next;

}

return NULL;

}

哈希表元素的移除

这个函数用于将哈希表中key对应的节点移除,如果其不存在,那就返回NULL。如果存在,就返回这个节点的地址。注意,这里并没有释放节点,如果不需要了,应该手动释放它。

//在哈希表中查找key对应的entry

//找到了返回entry,并将其从哈希表中移除

//没找到返回NULL

entry* removeEntry(table* t , char* key)

{

int index;

entry* e,*ep; //查找的时候,把ep作为返回值

if (t == NULL || key == NULL) {

return NULL;

}

index = keyToIndex(key);

e = &(t->bucket[index]);

while (e != NULL) {

if (0 == strcmp(key , e->key)) {

//如果是桶的第一个

if (e == &(t->bucket[index])) {

//如果这个桶有两个或以上元素

//交换第一个和第二个,然后移除第二个

ep = e->next;

if (ep != NULL) {

entry tmp = *e; //做浅拷贝交换

*e = *ep;//相当于链表的头节点已经移除

*ep = tmp; //这就是移除下来的链表头节点

ep->next = NULL;

}

else {//这个桶只有第一个元素

ep = (entry*)malloc(sizeof(entry));

*ep = *e;

e->key = e->value = NULL;

e->next = NULL;

}

}

else {

//如果不是桶的第一个元素

//找到它的前一个(这是前面设计不佳导致的多余操作)

ep = &(t->bucket[index]);

while (ep->next != e)ep = ep->next;

//将e从中拿出来

ep->next = e->next;

e->next = NULL;

ep = e;

}

return ep;

}// end if(strcmp…

e = e->next;

}

return NULL;

}

哈希表打印

这个函数用于打印哈希表的内容的。

void printTable(table* t)

{

int i;

entry* e;

if (t == NULL)return;

for (i = 0; i

printf(“\nbucket[%d]:\n” , i);

e = &(t->bucket[i]);

while (e->key != NULL) {

printf(“\t%s\t=\t%s\n” , e->key , e->value);

if (e->next == NULL)break;

e = e->next;

}

}

}

测试一下

用于测试的数据来自于本机相关信息。

int main()

{

table t;

initHashTable(&t);

insertEntry(&t , “电脑型号” , “华硕 X550JK 笔记本电脑”);

insertEntry(&t , “操作系统” , “Windows 8.1 64位 (DirectX 11)”);

insertEntry(&t , “处理器” , “英特尔 Core i7 – 4710HQ @ 2.50GHz 四核”);

insertEntry(&t , “主板” , “华硕 X550JK(英特尔 Haswell)”);

insertEntry(&t , “内存” , “4 GB(Hynix / Hyundai)”);

insertEntry(&t , “主硬盘” , “日立 HGST HTS541010A9E680(1 TB / 5400 转 / 分)”);

insertEntry(&t , “显卡” , “NVIDIA GeForce GTX 850M (2 GB / 华硕)”);

insertEntry(&t , “显示器” , “奇美 CMN15C4(15.3 英寸)”);

insertEntry(&t , “光驱” , “松下 DVD – RAM UJ8E2 S DVD刻录机”);

insertEntry(&t , “声卡” , “Conexant SmartAudio HD @ 英特尔 Lynx Point 高保真音频”);

insertEntry(&t , “网卡” , “瑞昱 RTL8168 / 8111 / 8112 Gigabit Ethernet Controller / 华硕”);

insertEntry(&t , “主板型号” , “华硕 X550JK”);

insertEntry(&t , “芯片组” , “英特尔 Haswell”);

insertEntry(&t , “BIOS” , “X550JK.301”);

insertEntry(&t , “制造日期” , “06 / 26 / 2014”);

insertEntry(&t , “主人” , “就是我”);

insertEntry(&t , “价格” , “六十张红色毛主席”);

insertEntry(&t , “主硬盘” , “换了个120G的固态”);

entry* e = removeEntry(&t , “主板型号”);

if (e != NULL) {

puts(“找到后要释放”);

free(e->key);

free(e->value);

free(e);

e = NULL;

}

printTable(&t);

const char* keys[] = { “显示器” , “主人”,”没有” , “处理器” };

for (int i = 0; i < 4; ++i) {

const char* value = findValueByKey(&t , keys[i]);

if (value != NULL) {

printf(“find %s\t=\t%s\n” ,keys[i], value);

}

else {

printf(“not found %s\n”,keys[i]);

}

}

freeHashTable(&t);

getchar();

return 0;

}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/179192.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • archwing任务流程_机器的武器任务流程

    archwing任务流程_机器的武器任务流程有两台机器 A,B 以及 K 个任务。机器 A 有 N 种不同的模式(模式 0∼N−1),机器 B 有 M 种不同的模式(模式 0∼M−1)。两台机器最开始都处于模式 0。每个任务既可以在 A 上执行,也可以在 B 上执行。对于每个任务 i,给定两个整数 a[i] 和 b[i],表示如果该任务在 A 上执行,需要设置模式为 a[i],如果在 B 上执行,需要模式为 b[i]。任务可以以任意顺序被执行,但每台机器转换一次模式就要重启一次。求怎样分配任务并合理安排顺序,能使机器重启次数最少。输入格

  • leetcode546_leetcode 5

    leetcode546_leetcode 5DescriptionGivenacollectionofdistinctintegers,returnallpossiblepermutations.ExampleInput:[1,2,3]Output:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]…

  • VS清除缓存_vs如何恢复默认设置

    VS清除缓存_vs如何恢复默认设置VS清除缓存

  • Java集合面试题[通俗易懂]

    Java集合面试题Java集合框架的基础接口有哪些?Collection,为集合层级的根接口。一个集合代表一组对象,这些对象即为它的元素。Java平台不提供这个接口任何直接的实现。Set,是一个不能包含重复元素的集合。这个接口对数学集合抽象进行建模,被用来代表集合,就如一副牌。List,是一个有序集合,可以包含重复元素。你可以通过它的索引来访问任何元素。List更像长度动态…

  • WPF 用代码实现WrapPanel右侧自动对齐(解决多余空白问题)

    WPF 用代码实现WrapPanel右侧自动对齐(解决多余空白问题)未处理前效果:处理后效果:<BorderBackground=”{StaticResourceBorderBg}”BorderThickness=”2″BorderBrush=”{StaticResourceBorderBrush}”CornerRadius=”5″Padding=”5″x:Name=”SvKeyWords”Margi…

  • strictmode android,Android 应用性能优化-StrictMode(严格模式)

    strictmode android,Android 应用性能优化-StrictMode(严格模式)UI线程如果被阻塞5秒的话,那么应用程序此时就会弹出ANR的对话框,ANR对应用程序来说是一个很严重的问题。如何防止应用程序出现ANR,怎么分析查看导致ANR问题的原因?我们来介绍Android的严格模式。怎样开启严格模式有两种开启方式。开发者选项进入开发者选项,里面找到启用严格模式,打开。当应用主线程执行长时间操作的话会闪锁屏幕。StrictModeAPI(代码调用)可以在Activit…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号