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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。