您好,登錄后才能下訂單哦!
本篇文章為大家展示了C語言如何實現(xiàn)通用數(shù)據(jù)結構中的通用集合,內容簡明扼要并且容易理解,絕對能使你眼前一亮,通過這篇文章的詳細介紹希望你能有所收獲。
這是在通用鏈表的基礎上實現(xiàn)的集合,關于鏈表的實現(xiàn)參見:C語言實現(xiàn)通用數(shù)據(jù)結構之通用鏈表
注意集合中只存儲了指針,沒有儲存實際的數(shù)據(jù)。
對于新的數(shù)據(jù)類型來說,需要自定義HashCode函數(shù)和equal函數(shù)。
下面還給出了幾個常見的hashCode函數(shù)和equal函數(shù)。
(1)HashCode函數(shù)
頭文件
/************************* *** 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函數(shù)
頭文件
/************************* *** 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; //第幾個數(shù)據(jù) } MyHashSetIterator; //創(chuàng)建HashSet MyHashSet *createMyHashSet(int (*hashCode)(void *data),int (*equal)(void *data1,void *data2)); //使用全部參數(shù)創(chuàng)建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); //增加一條數(shù)據(jù),返回是否添加成功 int myHashSetAddData(MyHashSet * const set, void * const data); //數(shù)據(jù)的容量 int myHashSetGetSize(const MyHashSet * const set); //創(chuàng)建迭代器 MyHashSetIterator* createMyHashSetIterator(MyHashSet * const set); //釋放迭代器 void freeMyHashSetIterator(MyHashSetIterator* iterator); //迭代器是否有下一個 int myHashSetIteratorHasNext(MyHashSetIterator* iterator); //遍歷下一個元素 void* myHashSetIteratorNext(MyHashSetIterator* iterator); //刪除一條數(shù)據(jù),返回是否刪除成功 int myHashSetRemoveData(MyHashSet * const set, void * const data); //將第二個Set的全部對象加入到第一個,返回增加的個數(shù) 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> //創(chuàng)建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; } //使用全部參數(shù)創(chuàng)建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; } //增加一條數(shù)據(jù),返回是否添加成功 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; } //數(shù)據(jù)的容量 int myHashSetGetSize(const MyHashSet * const set) { return set->size; } //創(chuàng)建迭代器 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; } //刪除一條數(shù)據(jù),返回是否刪除成功 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的全部對象加入到第一個,返回增加的個數(shù) 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() { //創(chuàng)建集合需要指定兩個函數(shù),hashCode函數(shù)和equal函數(shù)。 MyHashSet * set = createMyHashSet(myHashCodeString, myEqualString); //插入數(shù)據(jù) 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; }
上述內容就是C語言如何實現(xiàn)通用數(shù)據(jù)結構中的通用集合,你們學到知識或技能了嗎?如果還想學到更多技能或者豐富自己的知識儲備,歡迎關注億速云行業(yè)資訊頻道。
免責聲明:本站發(fā)布的內容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經查實,將立刻刪除涉嫌侵權內容。