C语言实现通用数据结构之通用映射(HashMap)

本文实例为大家分享了C语言实现通用数据结构之通用映射的具体代码,供大家参考,具体内容如下

这是在通用链表的基础上实现的映射,关于链表的实现参见:C语言实现通用数据结构之通用链表。

注意映射中只存储了key和value的指针,没有储存实际的数据。

对于新的key类型来说,需要自定义HashCode函数和equal函数。

在HashSet的实现中给出了几个常见的hashCode函数和equal函数。参见:c语言实现通用数据结构(四):通用集合。

头文件:myHashMap.h

#ifndef MYHASHMAP_H_INCLUDED
#define MYHASHMAP_H_INCLUDED
#include "myList.h"

#define DEFAULT_INITIAL_CAPACITY 16
#define DEFAULT_LOAD_FACTOR 0.75f

typedef struct entry
{
    void * key;
    void * value;
} Entry;

typedef struct myHashMap
{
    int size;   //大小
    int initialCapacity; //初始容量
    float loadFactor;   //加载因子
    int (*hashCode)(void *key);
    int (*equal)(void *key1,void *key2);
    MyList ** entryList;
} MyHashMap;

typedef struct myHashMapEntryIterator
{
    int index;       //第几个链表
    MyHashMap *map;
    MyNode *current;
    int count;        //第几个数据
} MyHashMapEntryIterator;

//创建HashMap
MyHashMap *createMyHashMap(int (*hashCode)(void *key),int (*equal)(void *key1,void *key2));

//使用全部参数创建HashMap
MyHashMap *createMyHashMapForAll(int initialCapacity,float loadFactor,int (*hashCode)(void *key),int (*equal)(void *key1,void *key2));

//释放HashMap
void freeMyHashMap(MyHashMap * map);

//是否包含某个key
int myHashMapContainsKey(MyHashMap *const map,void * const key);

//增加一条映射
void myHashMapPutData(MyHashMap *const map,void * const key,void * const value);

//通过key得到数据,如果没有数据则返回null
void* myHashMapGetDataByKey(MyHashMap * const map,void *const key);

//数据的容量
int myHashMapGetSize(const MyHashMap * const map);

//创建Entry迭代器
MyHashMapEntryIterator* createMyHashMapEntryIterator( MyHashMap *const map);

//释放Entry迭代器
void freeMyHashMapEntryIterator(MyHashMapEntryIterator* iterator);

//Entry迭代器是否有下一个
int myHashMapEntryIteratorHasNext(MyHashMapEntryIterator* iterator);

//遍历下一个Entry元素
Entry* myHashMapEntryIteratorNext(MyHashMapEntryIterator* iterator);

//删除一条数据,返回是否删除成功
int myHashMapRemoveDataByKey(MyHashMap *const map,void * const key);

//遍历
void myHashMapOutput(MyHashMap *map, void(*pt)(Entry*));

#endif // MYHASHMAP_H_INCLUDED

源文件:  myHashMap.c

#include "myHashMap.h"
#include <stdlib.h>

//某条Entry链表上是否包含某个key值。
Entry* listContainsEntry(MyList * list, void * key,
  int(*equal)(void *key1, void *key2)) {
 MyListIterator* it = createMyListIterator(list);
 while (myListIteratorHasNext(it)) {
  Entry * entry = (Entry *) (myListIteratorNext(it));
  if (entry->key == key || (equal != NULL && (*equal)(entry->key, key))) {
   return entry;
  }
 }
 freeMyListIterator(it);
 return NULL;
}

void rebuildMyHashMap(MyHashMap * map) {
 int newSize = map->initialCapacity * 2;
 MyList **newentryList = (MyList **) malloc(sizeof(MyList*) * newSize);
 for (int i = 0; i < newSize; i++) {
  newentryList[i] = createMyList();
 }
 MyHashMapEntryIterator* it = createMyHashMapEntryIterator(map);
 while (myHashMapEntryIteratorHasNext(it)) {
  Entry * entry = myHashMapEntryIteratorNext(it);
  int hasCode = (*(map->hashCode))(entry->key);
  hasCode %= newSize;
  if (hasCode < 0)
   hasCode += newSize;
  myListInsertDataAtLast(newentryList[hasCode], entry);
 }
 freeMyHashMapEntryIterator(it);
 for (int i = 0; i < map->initialCapacity; i++) {
  freeMyList(map->entryList[i]);
 }
 free(map->entryList);
 map->entryList = newentryList;
 map->initialCapacity = newSize;
}

//创建HashMap
MyHashMap *createMyHashMap(int(*hashCode)(void *key),
  int(*equal)(void *key1, void *key2)) {
 MyHashMap *re = (MyHashMap *) malloc(sizeof(MyHashMap));
 re->size = 0;
 re->loadFactor = DEFAULT_LOAD_FACTOR;
 re->initialCapacity = DEFAULT_INITIAL_CAPACITY;
 re->entryList = (MyList **) malloc(sizeof(MyList*) * re->initialCapacity);
 re->hashCode = hashCode;
 re->equal = equal;
 for (int i = 0; i < re->initialCapacity; i++) {
  re->entryList[i] = createMyList();
 }
 return re;
}

//使用全部参数创建HashMap
MyHashMap *createMyHashMapForAll(int initialCapacity, float loadFactor,
  int(*hashCode)(void *key), int(*equal)(void *key1, void *key2)) {
 MyHashMap *re = createMyHashMap(hashCode, equal);
 re->initialCapacity = initialCapacity;
 re->loadFactor = loadFactor;
 return re;
}

//是否包含某个key
int myHashMapContainsKey(MyHashMap * const map, void * const key) {
 int hasCode = (*(map->hashCode))(key);
 hasCode %= map->initialCapacity;
 if (hasCode < 0)
  hasCode += map->initialCapacity;
 Entry * re = listContainsEntry(map->entryList[hasCode], key, map->equal);
 return re != NULL;
}

//增加一条映射
void myHashMapPutData(MyHashMap * const map, void * const key,
  void * const value) {
 int hasCode = (*(map->hashCode))(key);
 hasCode %= map->initialCapacity;
 if (hasCode < 0)
  hasCode += map->initialCapacity;
 Entry * re = listContainsEntry(map->entryList[hasCode], key, map->equal);
 if (re == NULL) {
  Entry * entry = (Entry*) malloc(sizeof(Entry));
  entry->key = key;
  entry->value = value;
  myListInsertDataAtLast(map->entryList[hasCode], entry);
  (map->size)++;
  if (map->size > map->initialCapacity * map->loadFactor) {
   rebuildMyHashMap(map);
  }
 } else {
  re->value = value;
 }
}

//通过key得到数据,如果没有数据则返回null
void* myHashMapGetDataByKey(MyHashMap * const map, void * const key) {
 int hasCode = (*(map->hashCode))(key);
 hasCode %= map->initialCapacity;
 if (hasCode < 0)
  hasCode += map->initialCapacity;
 Entry * re = listContainsEntry(map->entryList[hasCode], key, map->equal);
 if (re == NULL) {
  return NULL;
 }
 return re->value;
}

//数据的容量
int myHashMapGetSize(const MyHashMap * const map) {
 return map->size;
}

//创建Entry迭代器
MyHashMapEntryIterator* createMyHashMapEntryIterator(MyHashMap * const map) {
 MyHashMapEntryIterator* re = (MyHashMapEntryIterator*) malloc(
   sizeof(MyHashMapEntryIterator));
 re->count = 0;
 re->index = 0;
 re->map = map;
 re->current = map->entryList[0]->first;
 return re;
}

//释放Entry迭代器
void freeMyHashMapEntryIterator(MyHashMapEntryIterator* iterator) {
 free(iterator);
}

//Entry迭代器是否有下一个
int myHashMapEntryIteratorHasNext(MyHashMapEntryIterator* iterator) {
 return iterator->count < iterator->map->size;
}

//遍历下一个Entry元素
Entry* myHashMapEntryIteratorNext(MyHashMapEntryIterator* iterator) {
 (iterator->count)++;
 while (!(iterator->current)) {
  (iterator->index)++;
  iterator->current = iterator->map->entryList[iterator->index]->first;
 }
 Entry * re = (Entry *) iterator->current->data;
 iterator->current = iterator->current->next;
 return re;
}

//删除一条数据,返回是否删除成功
int myHashMapRemoveDataByKey(MyHashMap * const map, void * const key) {
 int hasCode = (*(map->hashCode))(key);
 hasCode %= map->initialCapacity;
 if (hasCode < 0)
  hasCode += map->initialCapacity;
 MyListIterator* it = createMyListIterator(map->entryList[hasCode]);
 int re = 0;
 while (myListIteratorHasNext(it)) {
  Entry * entry = (Entry *) (myListIteratorNext(it));
  if ((*(map->equal))(entry->key, key)) {
   myListRemoveDataAt(map->entryList[hasCode], it->count - 1);
   re = 1;
   (map->size)--;
   break;
  }
 }
 freeMyListIterator(it);
 return re;
}

void myFree(Entry * p){
    free(p);
}

//释放HashMap
void freeMyHashMap(MyHashMap * map) {
 myHashMapOutput(map, myFree);
 for (int i = 0; i < map->initialCapacity; i++) {
  freeMyList(map->entryList[i]);
 }
 free(map->entryList);
 free(map);
}

//遍历
void myHashMapOutput(MyHashMap *map, void(*pt)(Entry*)) {
 MyHashMapEntryIterator* iterator = createMyHashMapEntryIterator(map);
 while (myHashMapEntryIteratorHasNext(iterator)) {
  pt(myHashMapEntryIteratorNext(iterator));
 }
 freeMyHashMapEntryIterator(iterator);
}

测试文件

/*************************
*** File main.c
*** test for MyHashMap
**************************/
#include <stdio.h>
#include <stdlib.h>
#include "myEqual.h"
#include "myHashCode.h"
#include "myHashMap.h"

#define S 10

char* strs[S]=
{
    "abc",
    "qq",
    "hello",
    "abc",
    "lmy",
    "ab",
    "qq",
    "lqw",
    "sww",
    "lqw"
};

int main()
{

    int*  data = malloc(sizeof(int)* S);
    for (int i=0; i<S; i++)
    {
        data[i]=i;
    }

    //创建映射需要指定两个函数,hashCode函数和equal函数。
    MyHashMap * map = createMyHashMap(myHashCodeString, myEqualString);

    //插入数据
    for (int i=0; i<S; i++)
    {
        myHashMapPutData(map, strs[i], &data[i]);
    }

    //输出大小
    printf("size=%d\n",myHashMapGetSize(map));

    //测试删除
    myHashMapRemoveDataByKey(map,"qq");
    myHashMapRemoveDataByKey(map,"ab");
    myHashMapRemoveDataByKey(map,"qwert");

    //输出大小
    printf("after remove size=%d\n",myHashMapGetSize(map));

    //遍历
    MyHashMapEntryIterator * it = createMyHashMapEntryIterator(map);
    while(myHashMapEntryIteratorHasNext(it))
    {
        Entry * pp= myHashMapEntryIteratorNext(it);
        char * key = pp-> key;
        int * value = pp->value;
        printf("%s(%d)\n", key, *value);
    }
    //释放遍历器
    freeMyHashMapEntryIterator(it);

    //释放映射
    freeMyHashMap(map);

    //释放数据
    free(data);
    return 0;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • C语言编程中建立和解除内存映射的方法

    C语言mmap()函数:建立内存映射 头文件: #include <unistd.h> #include <sys/mman.h> 定义函数:void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offsize); 函数说明:mmap()用来将某个文件内容映射到内存中,对该内存区域的存取即是直接对该文件内容的读写. 参数说明: 返回值:若映射成功则返回映射区的内存起始地址,否则返回MAP_

  • C语言实现大数据文件的内存映射机制

    C语言实现大数据文件的内存映射机制 摘要 本文主要讲述大量数据的文件的内存映射机制的实现. 1. 内存映射 内存映射文件,是由一个文件到一块内存的映射.Win32提供了允许应用程序把文件映射到一个进程的函数 (CreateFileMapping).内存映射文件与虚拟内存有些类似,通过内存映射文件可以保留一个地址空间的区域,同时将物理存储器提交给此区域,内存文件映射的物理存储器来自一个已经存在于磁盘上的文件,而且在对该文件进行操作之前必须首先对文件进行映射.使用内存映射文件处理存储于磁盘上的文件时

  • C语言自动生成enum值和名字映射代码

    这年头好像继续做C语言的人不多了,年轻人大多去互联网和移动应用.确实,那两个领域现在来钱快,且总是供不应求.就说刚刚在一个旧同事的微信群里,有人刚放出自己有团队可以做App几分钟,哇塞,好几个人说有项目,要求加好友私聊.我也想过转行,可惜人老珠黄,没有互联网或是应用团队愿意接收.估计再过些年,C程序世界里就只有我这样的小老头们继续自娱自乐了,羡慕死年轻人了! 平常工作中,经常要做一些打印,或是日志.而这里面,enum类型的数据就很多,如果只是打印出它的整数值,显然会让测试人员很恼火,鬼知道那数字

  • C语言实现通用数据结构之通用映射(HashMap)

    本文实例为大家分享了C语言实现通用数据结构之通用映射的具体代码,供大家参考,具体内容如下 这是在通用链表的基础上实现的映射,关于链表的实现参见:C语言实现通用数据结构之通用链表. 注意映射中只存储了key和value的指针,没有储存实际的数据. 对于新的key类型来说,需要自定义HashCode函数和equal函数. 在HashSet的实现中给出了几个常见的hashCode函数和equal函数.参见:c语言实现通用数据结构(四):通用集合. 头文件:myHashMap.h #ifndef MYH

  • C语言实现通用数据结构之通用链表

    本文实例为大家分享了c语言实现通用数据结构之通用链表的具体代码,供大家参考,具体内容如下 忽然想起来,大概在两年之前学习C语言的时候,曾经用C语言写过一些通用的数据结构.主要也就实现了链表.队列.椎.HashSet,还有HashMap.当时只是知道标准的C语言中没有这方面的类库,后来才知道有很多第三方的类似这样的类库.废话不多说,先把代码粘过来. 下面实现的是通用链表,注意链表中只存储了指针,没有储存实际的数据. 头文件 /************************* *** File m

  • C语言实现通用数据结构之通用椎栈

    本文实例为大家分享了C语言实现通用数据结构之通用椎栈的具体代码,供大家参考,具体内容如下 这是在通用链表的基础上实现的椎栈,关于链表的实现参见:C语言实现通用数据结构之通用链表 . 这里所说的椎栈就是指的栈. 注意椎栈中只存储了指针,没有储存实际的数据. 头文件: /************************* *** File myStack.h **************************/ #ifndef MYSTACK_H_INCLUDED #define MYSTACK_

  • C语言实现通用数据结构之通用集合(HashSet)

    这是在通用链表的基础上实现的集合,关于链表的实现参见:C语言实现通用数据结构之通用链表 注意集合中只存储了指针,没有储存实际的数据. 对于新的数据类型来说,需要自定义HashCode函数和equal函数. 下面还给出了几个常见的hashCode函数和equal函数. (1)HashCode函数 头文件 /************************* *** File myHashCode.h **************************/ #ifndef MYHASHCODE_H_

  • C语言 深入解读数据结构之堆的实现

    堆的概念与结构 概念:如果有一个关键码的集合K={ k0,k1 ,k2 ,-,kn-1 },把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足K i<=K 2*i+1且Ki<=K 2*i+2(K i>=K 2*i+1且Ki>=K 2*i+2) i = 0,1,2...,则称为小堆(或大堆).将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆. 性质: 堆中某个节点的值总是不大于或不小于其父节点的值: 堆总是一棵完全二叉树. 结构: 1.大堆 2

  • C语言详解数据结构与算法中枚举和模拟及排序

    目录 枚举 连号区间数 递增三元组 二分 双指针 前缀和 模拟 特别数的和 错误票据 排序 快速排序 归并排序 枚举 连号区间数 来源:第四届蓝桥杯省赛C++B组,第四届蓝桥杯省赛JAVAB组 小明这些天一直在思考这样一个奇怪而有趣的问题: 在 1∼N 的某个排列中有多少个连号区间呢? 这里所说的连号区间的定义是: 如果区间 [L,R] 里的所有元素(即此排列的第 L 个到第 R 个元素)递增排序后能得到一个长度为 R−L+1 的“连续”数列,则称这个区间连号区间. 当 N 很小的时候,小明可以

  • C语言植物大战数据结构二叉树递归

    目录 前言 一.二叉树的遍历算法 1.构造二叉树 2.前序遍历(递归图是重点.) 3.中序遍历 4.后序遍历 二.二叉树遍历算法的应用 1.求节点个数 3.求第k层节点个数 4.查找值为x的节点 5.二叉树销毁 6.前序遍历构建二叉树 7.判断二叉树是否是完全二叉树 8.求二叉树的深度 三.二叉树LeetCode题目 1.单值二叉树 2. 检查两颗树是否相同 3. 对称二叉树 4.另一颗树的子树 6.反转二叉树 " 梧桐更兼细雨,到黄昏.点点滴滴." C语言朱武大战数据结构专栏 C语言

  • C语言植物大战数据结构快速排序图文示例

    目录 快速排序 一.经典1962年Hoare法 1.单趟排序 2.递归左半区间和右半区间 3.代码实现 二.填坑法(了解) 1.单趟思路 2.代码实现 三.双指针法(最佳方法) 1.单趟排序 2.具体思路 3.代码递归图 4.代码实现 四.三数取中优化(最终方案) 1.三数取中 2.代码实现(最终代码) 五.时间复杂度(重点) 1.最好情况下 2.最坏情况下 3.空间复杂度 六.非递归写法 1.栈模拟递归快排 2.队列实现快排 浅浅总结下 “田家少闲月,五月人倍忙”“夜来南风起,小麦覆陇黄” C

  • C语言植物大战数据结构堆排序图文示例

    目录 TOP.堆排序前言 一.向下调整堆排序 1.向下调整建堆 建堆的技巧 建堆思路代码 2.向下调整排序 调整思路 排序整体代码 3.时间复杂度(难点) 向下建堆O(N) 向下调整(N*LogN) 二.向上调整堆排序 1.向上调整建堆 2.建堆代码 “大弦嘈嘈如急雨,小弦切切如私语”“嘈嘈切切错杂弹,大珠小珠落玉盘” TOP.堆排序前言 什么是堆排序?假如给你下面的代码让你完善堆排序,你会怎么写?你会怎么排? void HeapSort(int* a, int n) { } int main(

  • C语言植物大战数据结构希尔排序算法

    目录 前言 一.插入排序 1.排序思路 2.单趟排序 详细图解 3.整体代码 4.时间复杂度 (1).最坏情况下 (2).最好情况下 (3).基本有序情况下(重点) 5.算法特点 二.希尔排序 1.希尔从哪个方面优化的插入排序? 2.排序思路 3.预排序 4.正式排序 5.整体代码 6.时间复杂度 (1).while循环的复杂度 (2).每组gap的时间复杂度 结论: “至若春和景明,波澜不惊,上下天光,一碧万顷,沙鸥翔集,锦鳞游泳,岸芷汀兰,郁郁青青.” C语言朱武大战数据结构专栏 C语言植物

随机推荐