服务器之家

服务器之家 > 正文

C语言实现通用数据结构之通用集合(HashSet)

时间：2022-03-05 17:33     来源/作者：swwlqw

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

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

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

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

（1）HashCode函数

头文件

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*************************
*** 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

源文件

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*************************
*** 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函数

头文件

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*************************
*** 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

源文件

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*************************
*** 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

头文件

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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

源文件

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
# 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）测试文件

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*************************
*** 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;
}

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

原文链接：https://blog.csdn.net/swwlqw/article/details/22664129

标签：
集合 C语言 数据结构 

相关文章

热门资讯

2022年最旺的微信头像大全 微信头像2022年最新版图片
2022年最旺的微信头像大全 微信头像2022年最新版图片 2022-01-10
蜘蛛侠3英雄无归3正片免费播放 蜘蛛侠3在线观看免费高清完整
蜘蛛侠3英雄无归3正片免费播放 蜘蛛侠3在线观看免费高清完整 2021-08-24
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
返回顶部