本文實(shí)例為大家分享了C語言實(shí)現(xiàn)通用數(shù)據(jù)結(jié)構(gòu)之通用映射的具體代碼，供大家參考，具體內(nèi)容如下
這是在通用鏈表的基礎(chǔ)上實(shí)現(xiàn)的映射，關(guān)于鏈表的實(shí)現(xiàn)參見：C語言實(shí)現(xiàn)通用數(shù)據(jù)結(jié)構(gòu)之通用鏈表。
注意映射中只存儲(chǔ)了key和value的指針，沒有儲(chǔ)存實(shí)際的數(shù)據(jù)。
對于新的key類型來說，需要自定義HashCode函數(shù)和equal函數(shù)。
在HashSet的實(shí)現(xiàn)中給出了幾個(gè)常見的hashCode函數(shù)和equal函數(shù)。參見：c語言實(shí)現(xiàn)通用數(shù)據(jù)結(jié)構(gòu)（四）：通用集合。
頭文件：myHashMap.h
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#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)建HashMapMyHashMap *createMyHashMap(int (*hashCode)(void *key),int (*equal)(void *key1,void *key2)); //使用全部參數(shù)創(chuàng)建HashMapMyHashMap *createMyHashMapForAll(int initialCapacity,float loadFactor,int (*hashCode)(void *key),int (*equal)(void *key1,void *key2)); //釋放HashMapvoid freeMyHashMap(MyHashMap * map); //是否包含某個(gè)keyint myHashMapContainsKey(MyHashMap *const map,void * const key); //增加一條映射void myHashMapPutData(MyHashMap *const map,void * const key,void * const value); //通過key得到數(shù)據(jù)，如果沒有數(shù)據(jù)則返回nullvoid* 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
#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)建HashMapMyHashMap *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)建HashMapMyHashMap *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è)keyint 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得到數(shù)據(jù)，如果沒有數(shù)據(jù)則返回nullvoid* 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);} //釋放HashMapvoid 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);} |
測試文件
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
/**************************** 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)); //測試刪除 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;} |
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://blog.csdn.net/swwlqw/article/details/22666705
