C語言實現通用數據結構之通用集合(HashSet)
這是在通用鏈表的基礎上實現的集合,關於鏈表的實現參見:C語言實現通用數據結構之通用鏈表
註意集合中隻存儲瞭指針,沒有儲存實際的數據。
對於新的數據類型來說,需要自定義HashCode函數和equal函數。
下面還給出瞭幾個常見的hashCode函數和equal函數。
(1)HashCode函數
頭文件
/************************* *** File myHashCode.h **************************/ #ifndef MYHASHCODE_H_INCLUDED #define MYHASHCODE_H_INCLUDED #include <string.h> #define HASHCODE_MULT 31 //默認的hashCode int myHashCodeDefault(void * a); //int類型hashCode int myHashCodeInt(void * a); //char類型的hashCode int myHashCodeChar(void * a); //string類型的hashCode int myHashCodeString(void * a); #endif // MYHASHCODE_H_INCLUDED
源文件
/************************* *** File myHashCode.c **************************/ #include "myHashCode.h" //默認的hashCode int myHashCodeDefault(void * a) { return (int) a; } //int類型hashCode int myHashCodeInt(void * a) { int * aa = (int *) a; return *aa; } //char類型的hashCode int myHashCodeChar(void * a) { char *aa = (char *) a; return *aa; } //string類型的hashCode int myHashCodeString(void * a) { int re = 0; char *aa = (char *) a; while (*aa) { re += HASHCODE_MULT * *aa; aa++; } return re; }
(2)equal函數
頭文件
/************************* *** File myEqual.h **************************/ #ifndef MYEQUAL_H_INCLUDED #define MYEQUAL_H_INCLUDED //默認的相等的方法 int myEqualDefault(void * a, void *b); //int類型相等的方法 int myEqualInt(void * a, void *b); //char類型相等的方法 int myEqualChar(void * a, void *b); //string類型相等的方法 int myEqualString(void * a, void *b); #endif // MYEQUAL_H_INCLUDED
源文件
/************************* *** File myEqual.c **************************/ #include "myEqual.h" #include <string.h> //默認的相等的方法 int myEqualDefault(void * a, void *b) { return a == b; } //int類型相等的方法 int myEqualInt(void * a, void *b) { int *aa = (int*) a; int *bb = (int *) b; return *aa == *bb; } //char類型相等的方法 int myEqualChar(void * a, void *b) { char *aa = (char *) a; char *bb = (char *) b; return *aa = *bb; } //string類型相等的方法 int myEqualString(void * a, void *b) { char *aa = (char *) a; char *bb = (char *) b; return strcmp(aa, bb)==0; }
(3)HashSet
頭文件
#ifndef MYHASHSET_H_INCLUDED #define MYHASHSET_H_INCLUDED # include "myHashMap.h" typedef struct myHashSet { int size; //大小 int initialCapacity; //初始容量 float loadFactor; //加載因子 int (*hashCode)(void *data); int (*equal)(void *data1, void *data2); MyList ** dataList; } MyHashSet; typedef struct myHashSetIterator { int index; //第幾個鏈表 MyHashSet *set; MyNode *current; int count; //第幾個數據 } MyHashSetIterator; //創建HashSet MyHashSet *createMyHashSet(int (*hashCode)(void *data),int (*equal)(void *data1,void *data2)); //使用全部參數創建HashSet MyHashSet *createMyHashSetForAll(int initialCapacity,float loadFactor,int (*hashCode)(void *data),int (*equal)(void *data1,void *data2)); //釋放HashSet void freeMyHashSet(MyHashSet * set); //是否包含某個data int myHashSetContains(MyHashSet * const set, void * const data); //增加一條數據,返回是否添加成功 int myHashSetAddData(MyHashSet * const set, void * const data); //數據的容量 int myHashSetGetSize(const MyHashSet * const set); //創建迭代器 MyHashSetIterator* createMyHashSetIterator(MyHashSet * const set); //釋放迭代器 void freeMyHashSetIterator(MyHashSetIterator* iterator); //迭代器是否有下一個 int myHashSetIteratorHasNext(MyHashSetIterator* iterator); //遍歷下一個元素 void* myHashSetIteratorNext(MyHashSetIterator* iterator); //刪除一條數據,返回是否刪除成功 int myHashSetRemoveData(MyHashSet * const set, void * const data); //將第二個Set的全部對象加入到第一個,返回增加的個數 int myHashSetAddAllSet(MyHashSet * set,MyHashSet *other); //復制HashSet MyHashSet* myHashSetCopy(MyHashSet * set); //遍歷 void myHashSetOutput(MyHashSet *set, void(*pt)(void*)); #endif // MYHASHSET_H_INCLUDED
源文件
# include "myHashSet.h" #include <stdlib.h> //創建HashSet MyHashSet *createMyHashSet(int(*hashCode)(void *data), int(*equal)(void *data1, void *data2)) { MyHashSet *re = malloc(sizeof(MyHashSet)); re->size = 0; re->loadFactor = DEFAULT_LOAD_FACTOR; re->initialCapacity = DEFAULT_INITIAL_CAPACITY; re->dataList = (MyList **) malloc(sizeof(MyList*) * re->initialCapacity); re->hashCode = hashCode; re->equal = equal; for (int i = 0; i < re->initialCapacity; i++) { re->dataList[i] = createMySearchList(equal); } return re; } //使用全部參數創建HashSet MyHashSet *createMyHashSetForAll(int initialCapacity, float loadFactor, int(*hashCode)(void *data), int(*equal)(void *data1, void *data2)) { MyHashSet *re = createMyHashSet(hashCode, equal); re->initialCapacity = initialCapacity; re->loadFactor = loadFactor; return re; } //釋放HashSet void freeMyHashSet(MyHashSet * set) { for (int i = 0; i < set->initialCapacity; i++) { freeMyList(set->dataList[i]); } free(set->dataList); free(set); } //是否包含某個data int myHashSetContains(MyHashSet * const set, void * const data) { int hasCode = (*(set->hashCode))(data); hasCode %= set->initialCapacity; if (hasCode<0) hasCode+=set->initialCapacity; int re = myListFindDataIndex(set->dataList[hasCode], data); return re > -1; } void rebuildMyHashSet(MyHashSet * set) { int newSize = set->initialCapacity * 2; MyList **newdataList = (MyList **) malloc(sizeof(MyList*) * newSize); for (int i = 0; i < newSize; i++) { newdataList[i] = createMyList(); } MyHashSetIterator* it = createMyHashSetIterator(set); while (myHashSetIteratorHasNext(it)) { void * data = myHashSetIteratorNext(it); int hasCode = (*(set->hashCode))(data); hasCode %= newSize; myListInsertDataAtLast(newdataList[hasCode], data); } freeMyHashSetIterator(it); for (int i = 0; i < set->initialCapacity; i++) { freeMyList(set->dataList[i]); } free(set->dataList); set->dataList = newdataList; set->initialCapacity = newSize; } //增加一條數據,返回是否添加成功 int myHashSetAddData(MyHashSet * const set, void * const data) { int hasCode = (*(set->hashCode))(data); hasCode %= set->initialCapacity; if (hasCode<0) hasCode+=set->initialCapacity; int re = myListFindDataIndex(set->dataList[hasCode], data); if (re == -1) { myListInsertDataAtLast(set->dataList[hasCode], data); (set->size)++; if (set->size > set->initialCapacity * set->loadFactor) { rebuildMyHashSet(set); } return 1; } return 0; } //數據的容量 int myHashSetGetSize(const MyHashSet * const set) { return set->size; } //創建迭代器 MyHashSetIterator* createMyHashSetIterator(MyHashSet * const set) { MyHashSetIterator* re = (MyHashSetIterator*) malloc( sizeof(MyHashSetIterator)); re->count = 0; re->index = 0; re->set = set; re->current = set->dataList[0]->first; return re; } //釋放迭代器 void freeMyHashSetIterator(MyHashSetIterator* iterator) { free(iterator); } //迭代器是否有下一個 int myHashSetIteratorHasNext(MyHashSetIterator* iterator) { return iterator->count < iterator->set->size; } //遍歷下一個元素 void* myHashSetIteratorNext(MyHashSetIterator* iterator) { (iterator->count)++; while (!(iterator->current)) { (iterator->index)++; iterator->current = iterator->set->dataList[iterator->index]->first; } void * re = iterator->current->data; iterator->current = iterator->current->next; return re; } //刪除一條數據,返回是否刪除成功 int myHashSetRemoveData(MyHashSet * const set, void * const data) { int hasCode = (*(set->hashCode))(data); hasCode %= set->initialCapacity; if (hasCode<0) hasCode+=set->initialCapacity; int re = myListRemoveDataObject(set->dataList[hasCode], data); if (re) { (set->size)--; } return re; } //將第二個Set的全部對象加入到第一個,返回增加的個數 int myHashSetAddAllSet(MyHashSet * set,MyHashSet *other) { int ssize=set->size; MyHashSetIterator * it=createMyHashSetIterator(other); while (myHashSetIteratorHasNext(it)) { myHashSetAddData(set,myHashSetIteratorNext(it)); } freeMyHashSetIterator(it); int re=set->size-ssize; return re; } //復制HashSet MyHashSet* myHashSetCopy(MyHashSet * set) { MyHashSet* re=createMyHashSetForAll(set->initialCapacity,set->loadFactor,set->hashCode,set->equal); myHashSetAddAllSet(re,set); return re; } //遍歷 void myHashSetOutput(MyHashSet *set, void(*pt)(void*)) { MyHashSetIterator * it=createMyHashSetIterator(set); while (myHashSetIteratorHasNext(it)) { pt(myHashSetIteratorNext(it)); } freeMyHashSetIterator(it); }
(4)測試文件
/************************* *** File main.c *** test for MyHashSet **************************/ #include <stdio.h> #include <stdlib.h> #include "myEqual.h" #include "myHashCode.h" #include "myHashSet.h" #define S 10 char* strs[S]= { "abc", "qq", "hello", "abc", "lmy", "ab", "qq", "lqw", "sww", "lqw" }; int main() { //創建集合需要指定兩個函數,hashCode函數和equal函數。 MyHashSet * set = createMyHashSet(myHashCodeString, myEqualString); //插入數據 for (int i=0; i<S; i++) { myHashSetAddData(set, strs[i]); } //輸出大小 printf("size=%d\n",myHashSetGetSize(set)); //測試刪除 myHashSetRemoveData(set,"qq"); myHashSetRemoveData(set,"ab"); myHashSetRemoveData(set,"qwert"); //輸出大小 printf("after remove size=%d\n",myHashSetGetSize(set)); //遍歷 MyHashSetIterator * it = createMyHashSetIterator(set); while(myHashSetIteratorHasNext(it)) { char * pp= myHashSetIteratorNext(it); puts(pp); } //釋放遍歷器 freeMyHashSetIterator(it); //釋放集合 freeMyHashSet(set); return 0; }
以上就是本文的全部內容,希望對大傢的學習有所幫助,也希望大傢多多支持WalkonNet。
推薦閱讀:
- C語言實現通用數據結構之通用映射(HashMap)
- Java數據結構之HashMap和HashSet
- C語言實現通用數據結構之通用鏈表
- Go語言題解LeetCode705設計哈希集合
- Java HashSet添加 遍歷元素源碼分析