C语言如何实现通用数据结构中的通用集合

本篇文章为大家展示了C语言如何实现通用数据结构中的通用集合，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。

这是在通用链表的基础上实现的集合，关于链表的实现参见：C语言实现通用数据结构之通用链表

注意集合中只存储了指针，没有储存实际的数据。

对于新的数据类型来说，需要自定义HashCode函数和equal函数。

下面还给出了几个常见的hashCode函数和equal函数。

（1）HashCode函数

头文件

#ifndef MYHASHCODE_H_INCLUDED#define MYHASHCODE_H_INCLUDED #include <string.h> #define HASHCODE_MULT 31 //默认的hashCodeint myHashCodeDefault(void * a); //int类型hashCodeint myHashCodeInt(void * a); //char类型的hashCodeint myHashCodeChar(void * a); //string类型的hashCodeint myHashCodeString(void * a); #endif // MYHASHCODE_H_INCLUDED

源文件

#include "myHashCode.h" //默认的hashCodeint myHashCodeDefault(void * a){    return (int) a;} //int类型hashCodeint myHashCodeInt(void * a){    int * aa = (int *) a;    return *aa;} //char类型的hashCodeint myHashCodeChar(void * a){    char *aa = (char *) a;    return *aa;} //string类型的hashCodeint myHashCodeString(void * a){    int re = 0;    char *aa = (char *) a;    while (*aa)    {        re += HASHCODE_MULT * *aa;        aa++;    }    return re;}

（2）equal函数

头文件

#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

源文件

#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; //创建HashSetMyHashSet *createMyHashSet(int (*hashCode)(void *data),int (*equal)(void *data1,void *data2)); //使用全部参数创建HashSetMyHashSet *createMyHashSetForAll(int initialCapacity,float loadFactor,int (*hashCode)(void *data),int (*equal)(void *data1,void *data2)); //释放HashSetvoid freeMyHashSet(MyHashSet * set); //是否包含某个dataint 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); //复制HashSetMyHashSet* myHashSetCopy(MyHashSet * set); //遍历void myHashSetOutput(MyHashSet *set, void(*pt)(void*)); #endif // MYHASHSET_H_INCLUDED

源文件

# include "myHashSet.h"#include <stdlib.h>//创建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;    re->equal = equal;    for (int i = 0; i < re->initialCapacity; i++)    {        re->dataList[i] = createMySearchList(equal);    }    return re;} //使用全部参数创建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;} //释放HashSetvoid freeMyHashSet(MyHashSet * set){    for (int i = 0; i < set->initialCapacity; i++)    {        freeMyList(set->dataList[i]);    }    free(set->dataList);    free(set);} //是否包含某个dataint 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;} //复制HashSetMyHashSet* 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）测试文件

#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;}

上述内容就是C语言如何实现通用数据结构中的通用集合，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注编程网其他教程频道。