服务器之家：专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C语言实现通用数据结构之通用集合(HashSet)

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

2022-03-05 17:33swwlqw C/C++

这篇文章主要为大家详细介绍了C语言实现通用数据结构之通用集合，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

这是在通用链表的基础上实现的集合，关于链表的实现参见：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语言
  • 集合
  • 数据结构

    • 延伸 · 阅读

    精彩推荐
    最近更新
    编辑推荐
    阅读排行
    热门标签
    1015 　 CEF2623 　 地址参数 　 多继承法 　 ZOJ 　 Fishing 　 同名 　 libfreetype 　 Simulink 　 数据滚动 　 右值引用 　 NSString 　 消息传递 　 平滑处理 　 Visual C++ 　 栈区 　 堆区 　 素数交换 　 内存错误 　 对象模型 　 颜色加亮 　 程序内部 　 strcat 　 WinExec 　 打开程序 　 错误调试 　 C++教程 　 tinyxml 　 XML解析器 　 静态存储区 　
    © 2019-2023 服务器之家(www.zzvips.com) 版权所有关于我们联系我们版权申明网站地图