精华内容
下载资源
问答
  • c语言 hash链表
    2021-02-20 14:29:38

    C语言中, 标准库没有提供哈希表, 哈希表有多种实现方式,可参考以下实现——

    以下哈希表结构为 : 指定长度的哈希表长度,冲突的节点使用延展链表存储数据(后面统一称为冲突链表)

    一、基本结构体定义

    1、存储数据的结构体

    /* 该结构体成员根据需要设定即可 */
    typedef struct tagHashData {
        int idx;
        int value;
    } HashData;

    2、哈希表数据节点的结构体

    typedef struct tagHashNode {
        HashData node;
        int valid; /* 这里判断该节点已使用 */
        struct tagHashNode *next;
    } HashNode;

    3、哈希表主体的结构体

    typedef struct tagHash {
        int length;
        HashNode **hashList;
    } Hash;

    二、哈希表基础功能的实现

    1、哈希索引计算函数

    /* 索引分布计算函数, 此处为绝对值, 一般使用CRC计算 */
    unsigned int GetHashPosition(int num)
    {
        if (num < 0) {
            return ~(--num);
        }
        return num;
    }

    2、创建哈希表

    /* 初始化指定长度大小的哈希表 */
    Hash *InitHash(int length)
    {
        /* byteLength 用于存储传入 length 的字节数, 申请哈希表堆内存使用 */
        unsigned int byteLength;
        Hash *hh = NULL;
        if (length == 0) {
            printf("parameter error!\n");
            return NULL;
        }
        hh = (Hash *)malloc(sizeof(Hash));
        if (hh == NULL) {
            return NULL;
        }
        byteLength = length * sizeof(HashNode *);
    
        /* 申请指定长度的指针数组 */
        hh->hashList = (HashNode **)malloc(byteLength);
        if (hh->hashList == NULL) {
            return NULL; 
        }
        (void)memset(hh->hashList, 0, byteLength);
        hh->length = length;
        return hh;
    }

    3、在哈希表中查找

    HashNode *HashSrch(Hash *hash, HashData *node)
    {
        unsigned int position;
        HashNode *hashNode = NULL;
        if (hash == NULL || hash->hashList == NULL) {
            printf("parameter error!\n");
            return NULL;
        }
    
        /* 使用传入节点的值作为索引 */
        position = GetHashPosition(node->value) % hash->length;
        hashNode = hash->hashList[position];
        /* 遍历冲突链表 */
        while (hashNode != NULL) {
            /* if (hashNode->valid == 1 && memcmp(&hashNode->node, node, sizeof(HashData)) == 0) */
            if (hashNode->valid == 1 && hashNode->node.value == node->value)
            {
                printf("node search value %d successfully!\n", node->value);
                return hashNode;
            }
            hashNode = hashNode->next;
        }
        printf("node search value %d doesn't exist!\n", node->value);
        return NULL;
    }

    4、插入哈希表

    int HashInst(Hash *hash, HashData *node)
    {
        unsigned int position = 0;
        HashNode *newhashNode = NULL;
    
        if (hash == NULL || node == NULL) {
            printf("parameter error!\n");
            return HAMS_ERROR;
        }
        /* 先查找节点是否存在, 不存在再插入 */
        if (HashSrch(hash, node) == NULL) {
            /* 申请新的数据节点, 并拷贝数据 */
            newhashNode = (HashNode *)malloc(sizeof(HashNode));
            if (newhashNode == NULL) {
                printf("node insert malloc fail!\n");
                return HAMS_ERROR;
            }
            memcpy(&newhashNode->node, node, sizeof(HashData));
            newhashNode->valid = 1;
            newhashNode->next = NULL;
    
            position = GetHashPosition(node->value) % hash->length;
            /* 插入第一个节点, 效率较高 */
            newhashNode->next = hash->hashList[position];
            hash->hashList[position] = newhashNode;
        }
        printf("node insert value %d successfully!\n", node->value);
        return HAMS_OK;
    }

    5、打印哈希表中的数据内容

    void PrintHash(Hash *hash)
    {
        int i;
        HashNode *hashNode = NULL;
        if (hash == NULL) {
            printf("parameter error!\n");
            return;
        }
        /* 首先遍历整个哈希表的指针数组,有数据的节点再打印冲突链表 */
        for (i = 0; i < hash->length; i++) {
            hashNode = hash->hashList[i];
            if (hashNode != NULL) {
                printf("\n[ hash idx %d nodes :\n", i);
            }
    
            while (hashNode != NULL && hashNode->valid == 1) {
                printf("val : %u, index : %u;\t", hashNode->node.value, hashNode->node.idx);
                hashNode = hashNode->next;
            }
            if (hashNode != NULL) {
                printf(" ]\n");
            }
        }
    }

    6、销毁哈希表

    void destroyHash(Hash **pHash)
    {
        int i;
        Hash *hash = NULL;
        HashNode *hashNode = NULL;
        HashNode *tempHashNode = NULL;
    
        if (pHash == NULL || *pHash == NULL) {
            printf("parameter error!\n");
            return;
        }
    
        hash = *pHash;
        /* 首先销毁冲突链表节点, 再销毁指针数组, 最后销毁哈希表 */
        if (hash->hashList != NULL) {
            for (i = 0; i < hash->length; i++) {
                hashNode = hash->hashList[i];
                while (hashNode != NULL) {
                    tempHashNode = hashNode;
                    hashNode = hashNode->next;
                    printf("free idx : %d node val : %u, index %u\n", i, tempHashNode->node.value, tempHashNode->node.idx);
                    free(tempHashNode);
                }
            }
            free(hash->hashList);
        }
        free(hash);
        /* 销毁内存后指针置NULL,防止产生悬空指针 */
        *pHash = NULL;
    }

    7、测试函数

    void TC_Hash()
    {
        int i, ret;
        HashData node[] = {
            {1, 10},
            {2, 20},
            {3, 30},
            {4, 50},
            {5, 10},
            {6, 10},
        };
        Hash *hh = NULL;
    
        hh = InitHash(100);
        for (i = 0; i < sizeof(node) / sizeof(node[0]); i++) {
            ret = HashInst(hh, &node[i]);
            printf("node[%d] insert idx : %d, value : %d, ret %d\n", i, node[i].idx, node[i].value, ret);
            (void)HashSrch(hh, &node[i]);
        }
        PrintHash(hh);
        destroyHash(&hh);
    }

     

    更多相关内容
  • C语言链表详解

    2022-06-01 22:41:56
    C语言链表详解

    链表

    链表的引入
    从数组的缺陷说起
    (1)数组有2个缺陷,一个是数组中所有元素的类型必须一致;第二个是数组的元素个数必须事先制定并且一旦指定之后不能更改。
    (2)如何解决数组的2个缺陷:数组的第一个缺陷靠结构体去解决。结构体允许其中的元素的类型不相同,因此解决了数组的第一个缺陷。所以说结构体是因为数组不能解决某些问题所以才发明的。
    (3)如何解决数组的第二个缺陷?我们希望数组的大小能够实时扩展。譬如我刚开始定了一个元素个数是10,后来程序运行时觉得不够因此动态扩展为20.普通的数组显然不行,我们可以对数组进行封装以达到这种目的;我们还可以使用一个新的数据结构来解决,这个新的数据结构就是链表。
    总结:几乎可以这样理解:链表就是一个元素个数可以实时变大/变小的数组。

    大学为什么都有新校区?
    (1)学校初建的时候(类似于变量定义并初始化时),这时候因为旁边都是荒地而没有建筑,因此学校的校园大小由自己定的;但是学校建立了之后旁边慢慢的也有了其他建筑(类似于这个变量分配了之后,内存的相邻区域又分配了其他变量与这个变量地址相连),这时候你的校园随着发展感觉不够用了想要扩展,却发现邻居已经住满了,校园的四周全部都是别人的建筑,这时候学校要扩展有2个办法:第一个是拆迁,第二个是搬迁,第三个是外部扩展。
    (2)拆迁基本行不通,因为成本太高了。
    (3)搬迁可以行的通。程序中解决数组大小扩展的一个思路就是整体搬迁。具体步骤是:先在另外的空白内存处建立一个大的数组,然后把原来的数组中的元素的值整个复制到新数组的头部,然后再释放掉原来数组的内存空间,并且把新的数组去替代原来的数组。这种可变数组在C语言中不支持,但是在更高级语言如C++、Java等里面是支持的。
    (4)外部扩展的思路是最常见的,基本可以说是最合理的。它的一个思路就是化整为零,在原来的不动的前提下去外部扩展新的分基地。外部扩展在学校的例子中就是新校区;外部扩展在编程解决数组问题的点上就是链表。

    链表是什么样的?
    (1)顾名思义,链表就是用锁链连接起来的表。这里的表指的是一个一个的节点(一个节点就是一个校区),节点中有一些内存可以用来存储数据(所以叫表,表就是数据表);这里的锁链指的是链接各个表的方法,C语言中用来连接2个表(其实就是2块内存)的方法就是指针。
    (2)链表是由若干个节点组成的(链表的各个节点结构是完全类似的),节点是由有效数据和指针组成的。有效数据区域用来存储信息完成任务的,指针区域用于指向链表的下一个节点从而构成链表。

    时刻别忘了链表是用来干嘛的
    (1)时刻谨记:链表就是用来解决数组的大小不能动态扩展的问题,所以链表其实就是当数组用的。直白点:链表能完成的任务用数组也能完成,数组能完成的任务用链表也能完成。但是灵活性不一样。
    (2)简单说:链表就是用来存储数据的。链表用来存数据相对于数组来说优点就是灵活性,需要多少个动态分配多少个,不占用额外的内存。数组的优势是使用简单(简单粗暴)。

    单链表的实现
    单链表的节点构成
    (1)链表是由节点组成的,节点中包含:有效数据和指针。
    (2)定义的struct node只是一个结构体,本身并没有变量生成,也不占用内存。结构体定义相当于为链表节点定义了一个模板,但是还没有一个节点,将来在实际创建链表时需要一个节点时用这个模板来复制一个即可。

    堆内存的申请和使用
    (1)链表的内存要求比较灵活,不能用栈,也不能用data数据段。只能用堆内存。
    (2)使用堆内存来创建一个链表节点的步骤:1、申请堆内存,大小为一个节点的大小(检查申请结果是否正确);2、清理申请到的堆内存;3、把申请到的堆内存当作一个新节点;4、填充你哦个新节点的有效数据和指针区域。

    链表的头指针
    (1)头指针并不是节点,而是一个普通指针,只占4字节。头指针的类型是struct node *类型的,所以它才能指向链表的节点。
    (2)一个典型的链表的实现就是:头指针指向链表的第1个节点,然后第1个节点中的指针指向下一个节点,然后依次类推一直到最后一个节点。这样就构成了一个链。

    实战:构建一个简单的单链表
    (1)目标:构建一个链表,然后将一些数据(譬如1,2,3三个数字)存储在链表中

    单链表的算法之插入节点
    继续上节,访问链表中各个节点的数据
    (1)只能用头指针,不能用各个节点自己的指针。因为在实际当中我们保存链表的时候是不会保存各个节点的指针的,只能通过头指针来访问链表节点。
    (2)前一个节点内部的pNext指针能帮助我们找到下一个节点。
    将创建节点的代码封装成一个函数
    (1)封装时的关键点就是函数的接口(函数参数和返回值)的设计
    从链表头部插入新节点
    从链表尾部插入新节点
    (1)尾部插入简单点,因为前面已经建立好的链表不用动。直接动最后一个就可以了。

    单链表的算法之插入节点续
    详解链表头部插入函数
    什么是头节点
    (1)问题:因为我们在insert_tail中直接默认了头指针指向的有一个节点,因此如果程序中直接定义了头指针后就直接insert_tail就会报段错误。我们不得不在定义头指针之后先create_node创建一个新节点给头指针初始化,否则不能避免这个错误;但是这样解决让程序看起来逻辑有点不太顺,因为看起来第一个节点和后面的节点的创建、添加方式有点不同。
    (2)链表还有另外一种用法,就是把头指针指向的第一个节点作为头节点使用。头节点的特点是:第一,它紧跟在头指针后面。第二,头节点的数据部分是空的(有时候不是空的,而是存储整个链表的节点数),指针部分指向下一个节点,也就是第一个节点。
    (3)这样看来,头节点确实和其他节点不同。我们在创建一个链表时添加节点的方法也不同。头节点在创建头指针时一并创建并且和头指针关联起来;后面的真正的存储数据的节点用节点添加的函数来完成,譬如insert_tail.
    (4)链表有没有头节点是不同的。体现在链表的插入节点、删除节点、遍历节点、解析链表的各个算法函数都不同。所以如果一个链表设计的时候就有头节点那么后面的所有算法都应该这样来处理;如果设计时就没有头节点,那么后面的所有算法都应该按照没有头节点来做。实际编程中两种链表都有人用,所以大家在看别人写的代码时一定要注意看它有没有头节点。


    从链表头部插入新节点
    (1)注意写代码过程中的箭头符号,和说话过程中的指针指向。这是两码事,容易搞混。箭头符号实际上是用指针方式来访问结构体,所以箭头符号的实质是访问结构体中的成员。更清楚一点说程序中的箭头和链表的连接没有任何关系;链表中的节点通过指针指向来连接,编程中表现为一个赋值语句(用=来进行连接),实质是把后一个节点的首地址,赋值给前一个节点中的pNext元素做为值。
    (2)链表可以从头部插入,也可以从尾部插入。也可以两头插入。头部插入和尾部插入对链表来说几乎没有差别。对链表本身无差别,但是有时候对业务逻辑有差别。


    单链表的算法之遍历节点
    什么是遍历
    (1)遍历就是把单链表中的各个节点挨个拿出来,就叫遍历。
    (2)遍历的要点:一是不能遗漏、二是不能重复、追求效率。
    如何遍历单链表
    (1)分析一个数据结构如何遍历,关键是分析这个数据结构本身的特点。然后根据本身特点来制定它的遍历算法。
    (2)单链表的特点就是由很多个节点组成,头指针+头节点为整个链表的起始,最后一个节点的特征是它内部的pNext指针值为NULL。从起始到结尾中间由各个节点内部的pNext指针来挂接。由起始到结尾的路径有且只有一条。单链表的这些特点就决定了它的遍历算法。
    (3)遍历方法:从头指针+头节点开始,顺着链表挂接指针依次访问链表的各个节点,取出这个节点的数据,然后再往下一个节点,直到最后一个节点,结束返回。

    编程实战
    (1)写一个链表遍历的函数,void bianli(struct node*pH);


    单链表的算法之删除节点
    为什么要删除节点
    (1)一直在强调,链表到底用来干嘛的?
    (2)有时候链表节点中的数据不想要了,因此要删掉这个节点。
    删除节点的2个步骤
    (1)第一步:找到要删除的节点;第二步:删除这个节点。
    如何找到待删除的节点
    (1)通过遍历来查找节点。从头指针+头节点开始,顺着链表依次将各个节点拿出来,按照一定的方法比对,找到我们要删除的那个节点。
    如何删除一个节点
    (1)待删除的节点不是尾节点的情况:首先把待删除的节点的前一个节点的pNext指针指向待删除的节点的后一个节点的首地址(这样就把这个节点从链表中摘出来了),然后再将这个摘出来的节点free掉接口。
    (2)待删除的节点是尾节点的情况:首先把待删除的尾节点的前一个节点的pNext指针指向null(这时候就相当于原来尾节点前面的一个节点变成了新的尾节点),然后将摘出来的节点free掉。

    注意堆内存的释放
    (1)前面几节课我们写的代码最终都没有释放堆内存。当程序都结束了的情况下那些没有free的堆内存也被释放了。
    (2)有时候我们的程序运行时间很久,这时候malloc的内存如果没有free会一直被占用直到你free释放它或者整个程序终止。

    单链表的算法之逆序
    什么是链表的逆序
    (1)链表的逆序又叫反向,意思就是把链表中所有的有效节点在链表中的顺序给反过来。

    单链表逆序算法分析
    (1)当我们对一个数据结构进行一个操作时,我们就需要一套算法。这就是数据结构和算法的关系。
    (2)我总结:算法有2个层次。第一个层次是数学和逻辑上的算法;第二次个层次是用编程语言来实现算法。
    (3)从逻辑上来讲,链表的逆序有很多种方法。这些方法都能实现最终的需要,但是效率是不一样的。彼此的可扩展性、容错性等不同。
    (4)思路:首先遍历原链表,然后将原链表中的头指针和头节点作为新链表的头指针和头节点,原链表中的有效节点挨个依次取出来,采用头插入的方法插入新链表中即可。
    (5)链表逆序 = 遍历 + 头插入

    编程实战


    双链表的引入和基本实现
    单链表的局限性
    (1)单链表是对数组的一个扩展,解决了数组的大小比较死板不容易扩展的问题。使用堆内存来存储数据,将数据分散到各个节点之间,其各个节点在内存中可以不相连,节点之间通过指针进行单向链接。链表中的各个节点内存不相连,有利于利用碎片化的内存。
    (2)单链表各个节点之间只由一个指针单向链接,这样实现有一些局限性。局限性主要体现在单链表只能经由指针单向移动(一旦指针移动过某个节点就无法再回来,如果要再次操作这个节点除非从头指针开始再次遍历一次),因此单链表的某些操作就比较麻烦(算法比较有局限)。回忆之前单链表的所有操作(插入、删除节点、 遍历、从单链表中取某个节点的数·····),因为单链表的单向移动性导致了不少麻烦。
    总结:单链表的单向移动性导致我们在操作单链表时,当前节点只能向后移动不能向前移动,因此不自由,不利于解决更复杂的算法。

    解决思路:有效数据+2个指针的节点(双链表)
    (1)单链表的节点 = 有效数据 + 指针(指针指向后一个节点)
    (2)双向链表的节点 = 有效数据 + 2个指针(一个指向后一个节点,另一个指向前一个节点)

    双链表的封装和编程实现


    双链表的算法之插入节点
    尾部插入
    头部插入


    双链表的算法之遍历节点
    (1)双链表是单链表的一个父集。双链表中如何完全无视pPrev指针,则双链表就变成了单链表。这就决定了双链表的正向遍历(后向遍历)和单链表是完全相同的。
    (2)双链表中因为多了pPrev指针,因此双链表还可以前向遍历(从链表的尾节点向前面依次遍历直到头节点)。但是前向遍历的意义并不大,主要是因为很少有当前当了尾节点需要前向遍历的情况。
    (3)总结:双链表是对单链表的一种有成本的扩展,但是这个扩展在有些时候意义不大,在另一些时候意义就比较大。因此在实践用途中要根据业务要求选择适合的链表。


    双链表的算法之删除节点

    其它数据结构:

    链表、哈希表、二叉树、图等
    链表是最重要的,链表在linux内核中使用非常多,驱动、应用编写很多时候都需要使用链表。所以对链表必须掌握,掌握到:会自己定义结构体来实现链表、会写链表的节点插入(前插、后插)、节点删除、节点查找、节点遍历等。(至于像逆序这些很少用,掌握了前面那几个这个也不难)。

    哈希表不是很常用,一般不需要自己写实现,而直接使用别人实现的哈希表比较多。对我们来说最重要的是要明白哈希表的原理、从而知道哈希表的特点,从而知道什么时候该用哈希表,当看到别人用了哈希表的时候要明白别人为什么要用哈希表、合适不合适?有没有更好的选择?

    二叉树、图等。对于这些复杂数据结构,不要太当回事。这些复杂数据结构用到的概率很小(在嵌入式开发中),其实这些数据结构被发明出来就是为了解决特定问题的,你不处理特定问题根本用不到这些,没必要去研究。

    为什么需要更复杂的数据结构
    因为现实中的实际问题是多种多样的,问题的复杂度不同,所以需要解决问题的算法和数据结构也不同。所以当你处理什么复杂度的问题,就去研究针对性解决的数据结构和算法;当你没有遇到此类问题(或者你工作的领域根本跟这个就没关系)时就不要去管了。

    数据结构和算法的关系
    数据结构的发明都是为了配合一定的算法;算法是为了处理具体问题,算法的实现依赖于相应的数据结构。
    当前我们说的算法和纯数学是不同的(算法是基于数学的,大学计算机系研究生博士生很多本科都是数学相关专业的),因为计算机算法要求以数学算法为指导,并且结合计算机本身的特点来改进,最终实现一个在计算机上可以运行的算法(意思就是用代码可以表示的算法)。

    应该怎样学习这部分?
    从上面表述大家应该明白以下事实:
    1. 数据结构和算法是相辅相成的,要一起研究。
    2. 数据结构和算法对嵌入式来说不全是重点,不要盲目的跑去研究这个。
    3. 一般在实际应用中,实现数据结构和算法的人和使用数据结构和算法的人是分开的。实际中有一部分人的工作就是研究数据结构和算法,并且试图用代码来实现这些算法(表现为库);其他做真正工作的人要做的就是理解、明白这些算法和数据结构的意义、优劣、特征,然后在合适的时候选择合适的数据结构和算法来解决自己碰到的实际问题。

    举个例子:linux内核在字符设备驱动管理时,使用了哈希表(hash table,散列表)。所以字符设备驱动的很多特点都和哈希表的特点有关。

    展开全文
  • 使用C语言,初步实现了哈希表,使用“链表”的方法,Hash函数是直接“取模”运算

    1 哈希表的特点

    结合了数组(索引快)和链表(可灵活增删结点)的优点。

    在这里插入图片描述

    2 代码实现

    2.1 链表部分

    2.1.1 链表结点的结构

    typedef struct __tag_node{
        int id;
        struct  __tag_node *pNext;
        int satellite;
    }Node;
    

    2.1.2 创建链表

    Node *LinkedList_Create(void)
    {
        Node *p = malloc(sizeof(Node));
        if(p == NULL){
            return NULL;
        }
        p->pNext = NULL;
        p->id = 0; // The total quantity of nodes
    
        return p;
    }
    

    2.1.3 销毁链表

    void LinkedList_Destroy(Node *list)
    {
        Node *p = list->pNext; // Reserved header node
        while(p){
            Node *tmp = p;
            p = p->pNext;
            free(tmp);
        }
        list->pNext = NULL;
        list->id = 0;
    }
    

    2.1.4 头插新结点

    /**
     * @brief Inserting a new node in the linked list
     * @param list, The linked list will be inserted
     * @param id, id number
     * @param the satellite value of the id
     **/
    int LinkedList_InsertHead(Node *list, int id, int dat)
    {
        Node *p = malloc(sizeof(Node *));
        if(p == NULL){
            return -1;
        }
        p->id = id;
        p->pNext = list->pNext;
        list->pNext = p;
    
        p->satellite = dat;
    
        return 1;
    }
    

    2.1.5 根据id搜索链表

    /**
     * @brief search the id
     * @param list, The hash table will be searched
     * @param key, key
     * @retval the satellite value of the id
     **/
    int LinkedList_Search(Node *list, int id)
    {
        Node *p = list->pNext;
    
        for(Node *p = list->pNext; p; p = p->pNext){
            if(id == p->id){
                return p->satellite;
            }
        }
    
        return 0;
    }
    

    2.2 Hash表部分

    2.2.1 创建Hash表

    Node **HashTable_Create(int len)
    {
        Node **p = malloc(len * sizeof(Node *));
        for(int i = 0; i < len; i++){
            p[i] = LinkedList_Create();
        }
    
        return p;
    }
    

    2.2.2 清空表中元素

    void HashTable_Clear(Node **arr, int len)
    {
        for(int i = 0; i < len; i++){
            LinkedList_Destroy(*(arr+i));
        }
    }
    

    2.2.3 摧毁整个Hash表

    void HashTable_Destroy(Node **arr, int len)
    {
        HashTable_Clear(arr, len);
        for(int i = 0; i < len; i++){
            free(arr[i]);
        }
        free(arr);
    }
    

    2.2.4 Hash函数

    int HashTable_hashFunc(int key, int len)
    {
        return key % len;
    }
    

    2.2.5 插入哈希表

    int HashTable_Insert(int key, int value, Node **table, int length)
    {
        if(LinkedList_InsertHead(table[HashTable_hashFunc(key, length)], key, value)){
            return 1;  // Success
        }else{
            return -1; // Failure
        }
    }
    

    2.2.6 根据key搜索Hash表返回数据

    /**
     * @brief search the key
     * @param table, The hash table will be searched
     * @param length, The length of the hash table
     * @retval the value of the key
     **/
    int HashTable_Search(int key, Node **table, int length)
    {
        return LinkedList_Search(table[HashTable_hashFunc(key, length)], key);
    }
    

    3 测试例程

    #define __MAX_LEN_TABLE_ 10
    
    int main(int argc, char *argv[])
    {
        Node **pHashTable;
        pHashTable = HashTable_Create(__MAX_LEN_TABLE_);
    
        if(HashTable_Insert(12, 125, pHashTable, __MAX_LEN_TABLE_)){
            printf("Insert key = 12, value = 125 successful!\r\n");
        }else{
            printf("Insert key = 12 fail!\r\n");
        }
    
        if(HashTable_Insert(22, 255, pHashTable, __MAX_LEN_TABLE_)){
            printf("Insert key = 22, value = 255 successful!\r\n");
        }else{
            printf("Insert key = 255 fail!\r\n");
        }
    
        int value = HashTable_Search(22, pHashTable, __MAX_LEN_TABLE_);
        printf("value of key=22 is %d\r\n", value);
    
        value = HashTable_Search(12, pHashTable, __MAX_LEN_TABLE_);
        printf("value of key=12 is %d\r\n", value);
    
        HashTable_Destroy(pHashTable, __MAX_LEN_TABLE_);
        
        return 0;
    }
    

    测试结果

    在这里插入图片描述

    展开全文
  • c语言 hash

    2022-07-08 16:07:19
    C语言 hash

    先存着,c语言真就啥都没有呗

    struct hashTable {
        int key;
        UT_hash_handle hh;
    };
    
    bool containsDuplicate(int* nums, int numsSize) {
        struct hashTable* set = NULL;
        for (int i = 0; i < numsSize; i++) {
            struct hashTable* tmp;
            HASH_FIND_INT(set, nums + i, tmp);
            if (tmp == NULL) {
                tmp = malloc(sizeof(struct hashTable));
                tmp->key = nums[i];
                HASH_ADD_INT(set, key, tmp);
            } else {
                return true;
            }
        }
        return false;
    }
    
    作者:LeetCode-Solution
    链接:https://leetcode.cn/problems/contains-duplicate/solution/cun-zai-zhong-fu-yuan-su-by-leetcode-sol-iedd/
    来源:力扣(LeetCode)
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    

    实现hashtable,大概写了下int类型的,,大概思路就是一个指针p指向一块内存,
    这块内存有若干指针,分别指向一个链表,链表在hash碰撞的时候增加节点,牺牲内存增加速度

    #include<stdio.h>
    #include<stdlib.h>
    #define max_len 50
    #define GET_KEY(num) (num)%max_len
    typedef struct hashnode {
    	struct hashnode* next;
    	int value;
    	int count;
    }Hashnode;
    void init(Hashnode** hashtable, int size);
    void display(Hashnode** hashtable, int size);
    void find(Hashnode** hashtable, int size, int num);
    void test_null(Hashnode* p);
    
    void main() {
    	int num[max_len * 2];
    	for (int i = 0; i < max_len * 2; i++) {
    		num[i] = i + max_len;
    		printf("%d ", num[i]);
    	}
    	printf("\n");
    	Hashnode** hashtable = (Hashnode**)malloc(max_len * 8 + 8);
    	test_null(hashtable);
    	init(hashtable, max_len);
    	num[98] = 50;
    	for (int i = 0; i < max_len * 2; i++) {
    		find(hashtable, max_len, num[i]);
    	}
    	display(hashtable, max_len);
    
    }
    
    void init(Hashnode** hashtable, int size) {
    	Hashnode** p = hashtable;
    	for (int i = 0; i < size; i++) {;
    		(*p)= (Hashnode*)malloc(16);
    		test_null(*p);
    		(*p)->next = NULL;
    		(*p)->value = -1;
    		(*p)->count = 0;
    		p++;
    	}
    }
    
    void display(Hashnode** hashtable, int size) {
    	for (int i = 0; i < size; i++) {
    		Hashnode* p = *(hashtable + i);
    		while (p) {
    			printf("%d %d ", p->value, p->count);
    			p = p->next;
    		}
    		printf("\n");
    	}
    	printf("\n\n");
    	
    }
    
    void find(Hashnode** hashtable, int size,int num) {
    	int pos = GET_KEY(num),flag=0;
    	Hashnode* p = *(hashtable + pos),*q=p;
    	while (p) {
    		if (p->value == -1) {
    			p->value = num;
    			p->count++;
    			flag = 1;
    			break;
    		}
    		if (p->value == num) {
    			p->count++;
    			flag = 1;
    			break;
    		}
    		else {
    			q = p;
    			p = p->next;
    		}
    	}
    	if (!flag) {
    		Hashnode* node = (Hashnode*)malloc(16);
    		test_null(node);
    		node->value = num;
    		node->next = NULL;
    		node->count = 1;
    		q->next = node;
    	}
    }
    //vs还是会有没检查内存的警告,不知道是这么写有问题还是vs检查不到
    void test_null(Hashnode* p) {
    	if (!p) {
    		printf("error\n");
    		exit(1);
    	}
    }
    

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • c语言实现哈希表

    千次阅读 2022-03-23 21:00:27
    c++中,我们可以直接使用map或者unordered_map来产生pair键值对,c语言中没有对应的库,所以需要自己实现一下hash表的结构。 如下图所示: hash表中保存的是哈希函数,桶结点的个数,以及二级指针:存储的是桶结点...
  • 哈希算法 C语言实现(采用链表

    千次阅读 2017-12-05 22:27:06
    Hash insert(Hash h,int x,char *s) /** 哈希链表的插入 **/ {  Hash p =h;  while(p) /**先看看是不是空指针**/  {  /**看样子是**/  if(strcmp(p->arr,s)==0) /**再看看身份证号是不是已经存在了**/ ...
  • 线性探查法 结果展示 四、总结 五、随便聊聊 前言 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的...
  • /* pointer table */ /************************************************************************/ /* hash : form hash value for string s /****************************************************************...
  • 删除排序链表中的重复元素(C语言
  • HASH表的创建
  • C语言-哈希查找(HASH)-详解(完整代码)

    千次阅读 多人点赞 2021-09-04 20:30:29
    用一个指针数组,来存储 每个链表的头节点 的首地址 如果要从 'NUM' 个数中查找数据 先对'NUM'/0.75,求得最大质数'N' //(质数:只能被1和本身整除的数) 然后创建一个有'N'个元素的'指针数组' 然后将'NUM'个数分别对...
  • 链表的增删改查: (1)录入某本图书的信息(图书信息包括的内容:ISBN号、书名、作者、出版社、出版日期、价格) (2)给定图书ISBN编号,显示、修改、删除该图书信息 (6)给定出版社名称,查找并显示该出版社的...
  • C语言hash函数

    千次阅读 2015-09-03 21:23:28
    //这里我自己设计一个hash算法来快速查找一堆数字中相等的数字,这也许是最接近原理的算法了 //一个整数整除27后的来作为hash函数 //定义一个保存实际数据的结构体节点 struct data_node { int num; int count; ...
  • C语言链表面试题复杂链表问题

    千次阅读 2017-03-22 18:04:30
    复杂链表 何为复杂链表呢? 这个问题是我在一道面试题上看到的,觉得挺难理解的,所以写一篇博客介绍一下 链表本身具有两个或多个指针,当然next指针很有规律的指向下一个结点,但是其他的指针...
  • 深度学习C语言之指针指针分析单重指针多重指针复杂指针函数指针新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格...
  • 解决频繁查找时候 速度慢的痛点,使用C语言写一个hash表模块。可以根据自己的实际情况扩展。
  • c语言实现hash map(链表散列hash

    千次阅读 2019-06-15 22:39:43
    散列(hash): 将字符串转换为固定长度的数组或索引值的方法,叫做散列法。 hashmap的底层结构 hashmap是一个链表散列的数据结构,即是数组和链表的结合体。(也可能是数组+链表+红黑树) 数组:存储空间连续,占用...
  • Hash insert(Hash h,char *s) /**哈希链表的老朋友 没有不行**/ {  Hash p=h; /**先判断是不是空**/  while(p)  {  if(strcmp(p->s,s)==0) /**不是空就看是不是相等**/  {  p->num++;  return h; ...
  • 我们学习到,hash 表其实就是通过 hash函数将输入的数据进行转换成一个相对唯一的 index, 然后将数据存在 index 号的数组中,如果发现冲突,则继续往后存储。 由于hash 函数的存在,我们查找数据时,可以很快的得到...
  • C语言实现哈希表

    千次阅读 2021-05-17 11:06:30
    C语言实现哈希表 简介:遇到散列表冲突时,采用链表分离的方式 哈希表在根据内容查找时,它的时间复杂度相对于要逐一遍历的数组或者链表要小。 散列算法:主要由md5(消息摘要算法),sha1(安全散列) ,这两者不可靠。...
  • //1:求两集合的交集(链表)。#include #include struct node{int data;struct node* next;};void push(struct node **head_ref, int new_data);//添加数据元素声明bool isPresent(struct node *head, int data);//...
  • C语言哈希表

    千次阅读 2021-11-21 10:01:06
    //线性探测法处理冲突 void collision(int &hashValue,int hashSize){ hashValue=(hashValue+1)%hashSize; } //开放定址哈希表的初始化 Status InitHash(HashTable &H,int size,int *tag,int (*hash)(KeyType,int),...
  • C语言-手写Map(数组+链表+红黑树)(全功能)
  • 1. hash key值计算,key的比较,内存分配,可以通过实现模板类重新定制 2. 实现按插入时间的先后,通过有序链表访问节点。用于按照时间先后,快速遍历... hash 实现快速存取, 链表快速实现超时hash节点的删除。
  • 数据结构之哈希链表Hashtable

    千次阅读 2020-07-11 12:32:51
    散列(Hashing)在现实中经常遇到按照给定...如图所示这就是整个hashtable的图书,其中红色部分其实是一个数组,里面存放的是链表,大家可以通过蓝色知道里面存放的是链表,绿色部分就是链表的一个结点,有数据域和...
  • 【uthash库】C语言中哈希表的使用

    千次阅读 2022-01-06 21:02:09
    文章目录前言一、哈希表是什么?... Hash表也称散列表,也有直接译作哈希表,Hash表是一种特殊的数据结构,它同数组、链表以及二叉排序树等相比较有很明显的区别,它能够快速定位到想要查找的记录,而不是与
  • 链表数组表示桶,然后用(元素值 + k)/(k+1)来定位插入哪个桶里k 个桶,最后一个桶用来放最大值,只有 k - 1 个跨度,这 k - 1 个跨度对应 k - 1 个桶。数对应的桶的下标为 (元素值 + k)/(k+1)1.遍历原始数组 arr ...
  • Hash表(C语言

    2020-03-01 12:17:40
    即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间 (3)链地址法(拉链法):将所有关键字为同义词的记录存储在同一线性链表中,产生hash冲突后在存储...
  • #define HASHSIZE 12 //set hash p #define NULLKEY -1000000 //set a impossible key //如果哈希表中有相同值,该算法找不到第二个该值,需要优化find函数 typedef struct LTable{ int id;//原数组id int elem; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,399
精华内容 7,359
关键字:

c语言 hash链表