Shulou(Shulou.com)06/02 Report--

This article shows you how C language to achieve a general set of general data structures, the content is concise and easy to understand, can definitely brighten your eyes, through the detailed introduction of this article, I hope you can get something.

This is a collection implemented on the basis of a general linked list. For the implementation of a linked list, see: C language implements a general linked list of general data structures.

Note that only pointers are stored in the collection, not the actual data.

For new data types, you need to customize the HashCode function and the equal function.

Several common hashCode and equal functions are also given below.

(1) HashCode function

Header file

/ * * File myHashCode.h**/#ifndef MYHASHCODE_H_INCLUDED#define MYHASHCODE_H_INCLUDED# include # define HASHCODE_MULT 31 / / default hashCodeint myHashCodeDefault (void * a); / / int type hashCodeint myHashCodeInt (void * a); / / char type hashCodeint myHashCodeChar (void * a) / / hashCodeint myHashCodeString of string type (void * a); # endif / / MYHASHCODE_H_INCLUDED

Source file

/ * * File myHashCode.c**/#include "myHashCode.h" / / default hashCodeint myHashCodeDefault (void * a) {return (int) a;} / / int type hashCodeint myHashCodeInt (void * a) {int * aa = (int *) a; return * aa } / / hashCodeint myHashCodeChar (void * a) {char * aa = (char *) an of char type; hashCodeint myHashCodeString (void * a) of return * aa;} / / string type {int re = 0; char * aa = (char *) a; while (* aa) {re + = HASHCODE_MULT * * aa; aa++;} return re;}

(2) equal function

Header file

/ * * File myEqual.h**/#ifndef MYEQUAL_H_INCLUDED#define MYEQUAL_H_INCLUDED / / default equivalent method int myEqualDefault (void * a, void * b); / / int type equivalent method int myEqualInt (void * a, void * b) / / methods with equal char types int myEqualChar (void * a, void * b); / / methods with equal string types int myEqualString (void * a, void * b); # endif / / MYEQUAL_H_INCLUDED

Source file

/ * * File myEqual.c**/#include "myEqual.h" # include / / default equivalent method int myEqualDefault (void * a, void * b) {return a = = b } / / methods of equal int type int myEqualInt (void * a, void * b) {int* aa = (int*) a; int* bb = (int*) b; return * aa = = * bb;} / / methods of char type equivalent int myEqualChar (void * a, void * b) {char * aa = (char *) a; char * bb = (char *) b; return * aa = * bb } / / int myEqualString (void * a, void * b) {char * aa = (char *) a; char * bb = (char *) b; return strcmp (aa, bb) = 0;}

(3) HashSet

Header file

# ifndef MYHASHSET_H_INCLUDED#define MYHASHSET_H_INCLUDED# include "myHashMap.h" typedef struct myHashSet {int size; / / size int initialCapacity; / / initial capacity float loadFactor; / / load factor int (* hashCode) (void * data); int (* equal) (void * data1, void * data2); MyList * * dataList;} MyHashSet; typedef struct myHashSetIterator {int index; / / several linked lists MyHashSet * set; MyNode * current Int count; / / data} MyHashSetIterator; / / create HashSetMyHashSet * createMyHashSet (int (* hashCode) (void * data), int (* equal) (void * data1,void * data2)); / / use all parameters to create HashSetMyHashSet * createMyHashSetForAll (int initialCapacity,float loadFactor,int (* hashCode) (void * data), int (* equal) (void * data1,void * data2)); / / release HashSetvoid freeMyHashSet (MyHashSet * set) / / whether to include a dataint myHashSetContains (MyHashSet * const set, void * const data); / / add a piece of data to return whether int myHashSetAddData has been successfully added (MyHashSet * const set, void * const data); / / data capacity int myHashSetGetSize (const MyHashSet * const set); / / create iterator MyHashSetIterator* createMyHashSetIterator (MyHashSet * const set); / / release iterator void freeMyHashSetIterator (MyHashSetIterator* iterator); / / whether the iterator has the next int myHashSetIteratorHasNext (MyHashSetIterator* iterator) / / traversing the next element void* myHashSetIteratorNext (MyHashSetIterator* iterator); / / deleting a piece of data and returning whether the int myHashSetRemoveData (MyHashSet* const set, void* const data) has been deleted successfully; / / adding all objects of the second Set to the first and returning the increased number of int myHashSetAddAllSet (MyHashSet* set,MyHashSet * other); / / copying HashSetMyHashSet* myHashSetCopy (MyHashSet* set); / / traversing void myHashSetOutput (MyHashSet* set, void (* pt) (void*)) # endif / / MYHASHSET_H_INCLUDED

Source file

# include "myHashSet.h" # include / / create HashSetMyHashSet * 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 > hashCode; re- = hashCode; re- For (int I = 0; I

< re->

InitialCapacity; iTunes +) {re- > dataList [I] = createMySearchList (equal);} return re;} / / create HashSetMyHashSet * 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 } / / release HashSetvoid freeMyHashSet (MyHashSet * set) {for (int I = 0; I)

< set->

InitialCapacity; iTunes +) {freeMyList (set- > dataList [I]);} free (set- > dataList); free (set);} / / whether it contains a dataint myHashSetContains (MyHashSet * const set, void * const data) {int hasCode = (* (set- > hashCode)) (data); hasCode% = set- > initialCapacity; if (hasCodeinitialCapacity; 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; iTunes +) {freeMyList (set- > dataList [I]);} free (set- > dataList); set- > dataList = newdataList; set- > initialCapacity = newSize;} / / add a piece of data to return whether int myHashSetAddData (MyHashSet * const set, void * const data) {int hasCode = (* (set- > hashCode) (data); hasCode% = set- > initialCapacity; if (hasCodeinitialCapacity; 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;} / / capacity of data int myHashSetGetSize (const MyHashSet * const set) {return set- > size } / / create iterator 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;} / / release iterator void freeMyHashSetIterator (MyHashSetIterator* iterator) {free (iterator) } / / whether the iterator has a next int myHashSetIteratorHasNext (MyHashSetIterator* iterator) {return iterator- > count

< iterator->

Set- > size;} / / traverse the next element 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 } / / Delete a piece of data and return whether int myHashSetRemoveData (MyHashSet * const set, void * const data) {int hasCode = (* (set- > hashCode)) (data); hasCode% = set- > initialCapacity; if (hasCodeinitialCapacity; int re = myListRemoveDataObject (set- > dataList [hasCode], data); if (re) {(set- > size) -;} return re) } / / add all objects of the second Set to the first, and return the increased number of 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 } / / copy HashSetMyHashSet* myHashSetCopy (MyHashSet* set) {MyHashSet* re=createMyHashSetForAll (set- > initialCapacity,set- > loadFactor,set- > hashCode,set- > equal); myHashSetAddAllSet (re,set); return re;} / / traverse void myHashSetOutput (MyHashSet* set, void (* pt) (void*)) {MyHashSetIterator * it=createMyHashSetIterator (set); while (myHashSetIteratorHasNext (it) {pt (myHashSetIteratorNext (it));} freeMyHashSetIterator (it);}

(4) Test documents

/ * * File main.c*** test for MyHashSet**/#include # include # 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 () {/ / to create a collection you need to specify two functions, the hashCode function and the equal function. MyHashSet * set = createMyHashSet (myHashCodeString, myEqualString); / / insert data for (int item0; I

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.