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)