C語(yǔ)言實(shí)現(xiàn)通用數(shù)據(jù)結(jié)構(gòu)之通用映射(HashMap)
本文實(shí)例為大家分享了C語(yǔ)言實(shí)現(xiàn)通用數(shù)據(jù)結(jié)構(gòu)之通用映射的具體代碼,供大家參考,具體內(nèi)容如下
這是在通用鏈表的基礎(chǔ)上實(shí)現(xiàn)的映射,關(guān)于鏈表的實(shí)現(xiàn)參見(jiàn):C語(yǔ)言實(shí)現(xiàn)通用數(shù)據(jù)結(jié)構(gòu)之通用鏈表。
注意映射中只存儲(chǔ)了key和value的指針,沒(méi)有儲(chǔ)存實(shí)際的數(shù)據(jù)。
對(duì)于新的key類型來(lái)說(shuō),需要自定義HashCode函數(shù)和equal函數(shù)。
在HashSet的實(shí)現(xiàn)中給出了幾個(gè)常見(jiàn)的hashCode函數(shù)和equal函數(shù)。參見(jiàn):c語(yǔ)言實(shí)現(xiàn)通用數(shù)據(jù)結(jié)構(gòu)(四):通用集合。
頭文件: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; //第幾個(gè)鏈表 MyHashMap *map; MyNode *current; int count; //第幾個(gè)數(shù)據(jù) } MyHashMapEntryIterator; //創(chuàng)建HashMap MyHashMap *createMyHashMap(int (*hashCode)(void *key),int (*equal)(void *key1,void *key2)); //使用全部參數(shù)創(chuàng)建HashMap MyHashMap *createMyHashMapForAll(int initialCapacity,float loadFactor,int (*hashCode)(void *key),int (*equal)(void *key1,void *key2)); //釋放HashMap void freeMyHashMap(MyHashMap * map); //是否包含某個(gè)key int myHashMapContainsKey(MyHashMap *const map,void * const key); //增加一條映射 void myHashMapPutData(MyHashMap *const map,void * const key,void * const value); //通過(guò)key得到數(shù)據(jù),如果沒(méi)有數(shù)據(jù)則返回null void* myHashMapGetDataByKey(MyHashMap * const map,void *const key); //數(shù)據(jù)的容量 int myHashMapGetSize(const MyHashMap * const map); //創(chuàng)建Entry迭代器 MyHashMapEntryIterator* createMyHashMapEntryIterator( MyHashMap *const map); //釋放Entry迭代器 void freeMyHashMapEntryIterator(MyHashMapEntryIterator* iterator); //Entry迭代器是否有下一個(gè) int myHashMapEntryIteratorHasNext(MyHashMapEntryIterator* iterator); //遍歷下一個(gè)Entry元素 Entry* myHashMapEntryIteratorNext(MyHashMapEntryIterator* iterator); //刪除一條數(shù)據(jù),返回是否刪除成功 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鏈表上是否包含某個(gè)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; } //創(chuàng)建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; } //使用全部參數(shù)創(chuàng)建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; } //是否包含某個(gè)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; } } //通過(guò)key得到數(shù)據(jù),如果沒(méi)有數(shù)據(jù)則返回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; } //數(shù)據(jù)的容量 int myHashMapGetSize(const MyHashMap * const map) { return map->size; } //創(chuàng)建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迭代器是否有下一個(gè) int myHashMapEntryIteratorHasNext(MyHashMapEntryIterator* iterator) { return iterator->count < iterator->map->size; } //遍歷下一個(gè)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; } //刪除一條數(shù)據(jù),返回是否刪除成功 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); }
測(cè)試文件
/************************* *** 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; } //創(chuàng)建映射需要指定兩個(gè)函數(shù),hashCode函數(shù)和equal函數(shù)。 MyHashMap * map = createMyHashMap(myHashCodeString, myEqualString); //插入數(shù)據(jù) for (int i=0; i<S; i++) { myHashMapPutData(map, strs[i], &data[i]); } //輸出大小 printf("size=%d\n",myHashMapGetSize(map)); //測(cè)試刪除 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); //釋放數(shù)據(jù) free(data); return 0; }
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
利用Debug調(diào)試代碼解決0xC0000005:?讀取位置?0x0000000000000000?時(shí)發(fā)生訪問(wèn)沖突問(wèn)
這篇文章主要介紹了利用Debug調(diào)試代碼解決0xC0000005:?讀取位置?0x0000000000000000?時(shí)發(fā)生訪問(wèn)沖突,本文給大家分享完美解決方案,需要的朋友可以參考下2023-03-03OpenCV利用高斯模糊實(shí)現(xiàn)簡(jiǎn)單的磨皮美顏效果
這篇文章主要介紹了通過(guò)OpenCV中的高斯模糊以及雙邊模糊來(lái)實(shí)現(xiàn)一個(gè)簡(jiǎn)單的磨皮美顏效果,文中的講解很詳細(xì),感興趣的同學(xué)可以學(xué)習(xí)一下2021-12-12C語(yǔ)言結(jié)構(gòu)數(shù)組實(shí)現(xiàn)貪吃蛇小游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言結(jié)構(gòu)數(shù)組實(shí)現(xiàn)貪吃蛇小游戲,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-10-10C語(yǔ)言中g(shù)etchar()的原理以及易錯(cuò)點(diǎn)解析
用getchar()函數(shù)讀取字符串時(shí),字符串會(huì)存儲(chǔ)在輸入緩沖區(qū)中,包括輸入的回車字符,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言中g(shù)etchar()的原理以及易錯(cuò)點(diǎn)解析的相關(guān)資料,需要的朋友可以參考下2022-03-03c語(yǔ)言 數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)之字符串
這篇文章主要介紹了c語(yǔ)言 數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)之字符串的相關(guān)資料,需要的朋友可以參考下2017-05-05C語(yǔ)言中函數(shù)與指針的應(yīng)用總結(jié)
本篇文章是對(duì)C語(yǔ)言中函數(shù)與指針的應(yīng)用進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05opencv3/C++ 實(shí)現(xiàn)SURF特征檢測(cè)
今天小編就為大家分享一篇opencv3/C++ 實(shí)現(xiàn)SURF特征檢測(cè),具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-12-12