文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

如何用C语言写一个散列表

2023-06-22 07:47

关注

本篇文章为大家展示了如何用C语言写一个散列表,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。

一、快速理解散列表

散列表,就是下标可以为字母的数组。

假设现有一个数组int a[100],想查找其中第40个元素,则直接输入a[40]就可以了,时间复杂度为O ( 1 ) O(1)O(1)。

问题在于,当下标不是数字,而是一个字符串的时候,可能需要一个超大的空间才能将所有下标妥善地存放在特定的位置。例如,若以大小写字母作为下标索引,那么一位就需要预留52个空间,10位就需要52的10次方 这么大的空间,根本没有设备可以满足。

好在,52的10次方这么庞大的数字也超出了正常人的使用范围,无论多长的索引,我们能用上的值也绝对是有限的。

例如,现有下面三个字符串作为下标

key1 = "microcold";key2 = "tinycold";key3 = "microcool";

其实只需要选取头、尾两个字母,就能很好地区分这三个字符串,即

def hash(key):    return key[0]+key[-1]

但这种算法对索引字符的要求非常高,至少头尾不能重复。所以,现在需要能把超长字符串映射成特定短字符串而且尽量避免重复的算法。

二、散列函数

最简单的散列函数就是求余,将输入字符串按位转为整数之后求余。由于在字符串可能会转成非常大的整数,故需了解余数的性质

如何用C语言写一个散列表

(a+b)%c=(a%c+b %c)% c

相应地有:

(a*b)%c=((a%c)*(b %c))% c

用C语言实现如下:

#include <stdio.h>#define MAXHASH 100//快速取幂法,a*b^n%cint  PowerMod (int a, int b, int n, int c) {      int  ans = 1;     b = b % c;     while (n > 0) {          if(n % 2 == 1)             ans = (ans * b) % c;         n = n / 2;       //b >>= 1;        b = (b * b) % c;     }     return (a*ans)%c; } int hash(char* key, int n){    int addr = 0;    for(int i = 0; i < n; i++){        addr += PowerMod(key[i], 128, i, MAXHASH);    }    return addr%MAXHASH;}int main(){    char* str;    int i;    while(1){        gets(str);        i = 0;        while(str[i++]!='\0'){}        printf("%d\n",hash(str,i));    }    return 0;}

测试如下:

>gcc hash.c>a.exeasdf21microcold81tinycold12microcool5minicool81minicold73

三、防撞

尽管minicool和microcold撞车了,但通过100以内的位数,去表示52的9次方 的样本,也算是不错的表现了。

为了不发生撞车,则需更改数组中的元素类型&mdash;&mdash;至少得是个结构体。而防止撞车的方法很简单,如果发生撞车,那我就不散列了,直接发配到一个指定的数组中。

#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXHASH 100typedef struct HASHNODE{    char *key;    int next;} *hashNode;struct HASHNODE* hashTable[MAXHASH];struct HASHNODE* crashTable[MAXHASH];     //存储撞击之后的值int numCrash=0;                   //已有的撞击值void initTable(){    for(int i=0; i < MAXHASH; i++){        hashTable[i] = (hashNode)malloc(sizeof(struct HASHNODE));        hashTable[i]->key = NULL;        hashTable[i]->next = -1;        crashTable[i] = (hashNode)malloc(sizeof(struct HASHNODE));        crashTable[i]->key = NULL;        hashTable[i]->next = -1;    }}void insertCrash(char* str, int index, int n){    if(index == numCrash){        crashTable[numCrash]->key = (char*)malloc(sizeof(char)*n);        strcpy(crashTable[numCrash++]->key, str);  //此时新增一个节点    }    else {        if(crashTable[index]->next==-1)            crashTable[index]->next = numCrash;        insertCrash(str, hashTable[index]->next, n);    }}//n为字符串长度void insertHash(char* str, int index,int n){    if(hashTable[index]->key==NULL){        hashTable[index]->key = (char*)malloc(sizeof(char)*n);        strcpy(hashTable[index]->key, str);    }else{        if(hashTable[index]->next==-1)            hashTable[index]->next = numCrash;        insertCrash(str, hashTable[index]->next, n);    }}void printHash(){    for(int i = 0; i < MAXHASH; i++){        if(hashTable[i]->key!=NULL)            printf("hashTable[%d]:%s\n",i,hashTable[i]->key);        if(crashTable[i]->key!=NULL)            printf("crashTable[%d]:%s\n",i,crashTable[i]->key);    }}int  PowerMod (int a, int b, int n, int c) {      int  ans = 1;     b = b % c;     while (n > 0) {          if(n % 2 == 1)             ans = (ans * b) % c;         n = n / 2;       //b >>= 1;        b = (b * b) % c;     }     return (a*ans)%c; } int hash(char* key, int n){    int addr = 0;    for(int i = 0; i < n; i++){        addr += PowerMod(key[i], 128, i, MAXHASH);    }    return addr%MAXHASH;}int main(){    initTable();    char* str;    int i;    while(1){        gets(str);        if(strcmp(str,"exit")==0) break;        i = 0;        while(str[i++]!='\0'){}        insertHash(str,hash(str,i),i);        printf("%d\n",hash(str,i));    }    printHash();    return 0;}

最后得到:

>gcc hash.c>a.exeasdf21hellworld84microcold81minicool81tinycool20tinycold12weixiaoleng11exitcrashTable[0]:minicoolhashTable[11]:weixiaolenghashTable[12]:tinycoldhashTable[20]:tinycoolhashTable[21]:asdfhashTable[81]:microcoldhashTable[84]:hellworld

可见一方面的确散列了,另一方面也的确防撞了。

上述内容就是如何用C语言写一个散列表,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注编程网行业资讯频道。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯