本文实例为大家分享了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);
}测试文件
#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;
}以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持编程网。
