526互联

数据结构---集合

发布时间 2023-12-30 00:01:44作者: Kroner

前言

集合是不同的对象的（或者称成员）的无序集合，由于成员直接存在关联，可以理解为归聚在一起的成员组合。集合有两种重要的特点：

  1. 成员是无序
  2. 每个集合的中的成员不重复

这是集合中成员的重要特征。

集合的介绍和基本知识

集合的介绍的定义

集合是相关有关联的无序组合，每个成员在一个集合中只出现一次，在数学中我们可以使用集合论有关的定义在定义集合的概念。

  1. 没有包含任何成员的集合我们称之为空集。集合的所有可能成员构成的集合称之为全集（全域），使用集合的表示可以写成\(S=U\)表示全集，使用\(S = \emptyset\) 表示空集。
  2. 如果两个集合中所包含的集合是一样的，则可以称这两个集合相等。例如\(S1=\{1,2,3\}\) ,\(S2=\{1,2,3\}\)这两个集合中成员是相同所\(S1 = S2\)。
  3. 如果两个集合中\(S2\)包含另一个集合\(S1\)集合的所有成员，称\(S1\)是\(S2\)的子集。记为则\(S1\in S2\)

集合的性质

集合的基本操作我们常用的有三种，分别是集合的交集，并集和差集操作当然还存在其他的集合操作，但是这三种是最为主要的集合操作了。

  1. 两个集合的\(S1\)和\(S2\)的并集也是一个集合，记为\(S{_m}\)，它包含了S1和S2中的全部成员，这种运算称之为集合的并集，数学表达为\(S1\cup S2 = S{_m}\)。
  2. 两个集合的\(S1\)和\(S2\)的交集也是一个集合，记为\(S{_i}\)，它包含了S1和S2中的共有成员，这种运算称之为集合的并集，数学表达为\(S1\cap S2 = S{_i}\)。
  3. 两个集合的\(S1\)和\(S2\)的差集也是一个集合，记为\(S{_d}\)，它包含了只存在\(S1\)的元素而不在\(S2\)中的元素，这种运算称之为集合的差集，数学表达为\(S1 \setminus S2 = S{_d}\)，有的教材也写为 \(S1 - S2 = S{_d}\)。

以上是集合一些基础概念，如果关心编程的话，了解一下即可。

集合的抽象数据结构实现的方法

在这篇文章中，我们使用Set来表示集合这个数据结构。实现集合的方式中是采用链表。简单的一种思路就是将链表中List重定义为Set但是Set和链表又有不同的地方，链表可以存储相同的成员，但是集合不同，集合中的每一个元素都是独一无二的。所以在使用链表的方式插入元素时候必须先对链表进行遍历，判断是否已经存在相同的成员。这部分的对于程序的性能是一个很大的影响，尤其当集合的长度很大时候，这样对于每个新插入的成员的遍历时间也变长，后面在讲到Hash的时候，可以使用Hash表对集合进行优化大大的提高集合的操作速度。

集合的接口定义

在实现集合前先对集合对一些公共的接口定义：

  • void set_init(Set* set, int(*match)(const void* key1, const void* key2), void (*destory)(void* data));

    • 描述：由于这里实现set的本质是一个链表，所以直接使用链表对set进行初始化，但是这个成员的重复的函数这个是list所没有的，所以要自己这个判断函数，这样提高了C语言的灵活性。
    • 时间复杂度；和链表的初始化函数一致，这个也是\(O(1)\)的时间复杂度。

  • int set_insert(Set *set, const void *data)

    • 和链表的实现方式是一致
    • 时间复杂度：和链表的时间复杂度一致，和成员的数量有关\(O(n)\)。

  • int set_remove(Set* set, void** data);

    • 描述：int set_remove(Set* set, void** data);利用list_next来遍历集合，根据match函数来检查数据是否匹配。prev是记录要移除的前一个元素的信息，这是因为使用的函数的list_rem_next()是移除后一个元素。
    • 时间复杂度：\(O(n)\) 在最糟糕的情况下 必须对集合的每一个元素进行遍历 ，这就导致必须执行n个\(O(1)\)的操作。

  • int set_union(Set* setu, const Set *set1, const Set *set2);

    • 描述：set_union是建立一个并集，记为setu，这个是由参数set1和参数set2组成的并集，思路是先把集合set1的中成员加入setu中然后，再加集合set2，不过在加入set2的时候要对set2中的每一成员进行判断。判断函数程序中为set_is_member。
    • 时间复杂度：\(O(mn)\) m为集合set1中的成员数量，n是集合set2中的成员数量，在将集合set1加入集合setu中的时间复杂度是\(O(m)\) 这个时候setu中的成员为m个，在执行加入第二个set2时，在加入集合还需要对集合进行遍历判断n所以第二次操作的时间复杂度为\(O(mn)\)两次操作是顺序，所以最大的时间复杂度为\(O(mn)\)。

  • int set_intersection(Set *seti, const Set *set1, const Set* Set2);

    • 描述：set_intersection就求解两个集合的交集
    • 时间复杂：和交集的分析一样也是\(O(mn)\)

  • ``int set_difference(Set* setd, const Set* set1, const Set* set2);`

    • 描述：set_intersection就求解两个集合的差集
    • 时间复杂：和交集的分析一样也是\(O(mn)\)

  • int set_is_member(const Set *set,void *data);

    • 描述：判断成员是否在集合中出现过，出现过返回1，没出现过返回0
    • 时间复杂：在最糟糕的情况下，必须对集合的全部成员遍历所以时间复杂度为\(O(n)\)

int set_is_subset(const Set* set1, const Set* set2);

  • 描述：判断集合set1是否是set2的子集

  • 时间复杂度：\(O(mn)\) 假设集合set1中的成员数为m 集合set2的成员数为n 要对于集合set1中每一个成员都要在set2中进行遍历匹配，所以最糟糕的情况下要遍历\(mn\)次。

  • int set_is_equel(const Set* set1, const Set* set2);

    • 描述：判断集合set1是否是相等于集合set2
    • 时间复杂度：\(O(mn)\)

代码实现

头文件

#pragma once
#ifndef SET_H
#define SET_H

#include <stdio.h>
#include "list.h"

// 使用链表的方式实现集合
typedef List Set;

// 公共接口
void set_init(Set* set, int(*match)(const void* key1, const void* key2), void (*destory)(void* data));

#define set_destory  list_destory
int set_insert(Set *set, const void *data);
int set_remove(Set* set, void** data);
int set_union(Set* setu, const Set *set1, const Set *set2);
int set_intersection(Set *seti, const Set *set1, const Set* Set2);
int set_difference(Set* setd, const Set* set1, const Set* set2);
int set_is_member(const Set *set,void *data);
int set_is_subset(const Set* set1, const Set* set2);
int set_is_equel(const Set* set1, const Set* set2);

#define set_size(set)  ((set)->size)


#endif // !SET_H

实现文件

#include <stdio.h>
#include <stdlib.h>

#include "list.h"
#include "set.h"

/*set_init 集合初始化函数*/
void set_init(Set* set, int(*match)(const void* key1, const void* key2), void (*destory)(void* data))
{
	list_init(set, destory);
	set->match = match;
	return;
}

/*set_insert 集合插入成员*/
int set_insert(Set* set, const void* data) 
{   
	// 检查是否已存在成员在集合中
	if (set_is_member(set,data)) 
	{
		return 1;
	}
	// 不存在就把成员插入链表尾部
	return list_ins_next(set, list_tail(set), data);
}
/*set_remove 集合删除成员*/
int set_remove(Set* set, void** data) 
{
	ListElement* member, *prev;
	// 寻找成员的位置
	prev = NULL;
	for (member = list_head(set);member != NULL; member = list_next(member))
	{
		if (set->match(*data, list_data(member)))
			break;
		prev = member;
	}
	// 如果成员不在集合中
	if (member == NULL)
	{
		return -1;
	}
	return list_rem_next(set, prev, data);
}

/*set_union 集合的交集*/
int set_union(Set* setu, const Set* set1, const Set* set2) 
{
	ListElement* member;

	// 初始化这个交集的集合
	set_init(setu, set1->match, NULL);
	// 插入这个第一个集合
	for (member = list_head(set1); member != NULL; member = list_next(member)) 
	{   
		// 失败要回滚
		if (list_ins_next(setu, list_tail(setu), list_data(member)) != 0) 
		{
			set_destory(setu);
			return -1;
		}
	}
	// 插入第二个集合
	for (member = list_head(set2); member != NULL; member = list_next(member)) 
	{
		// 防止同样的成员插入
		if (set_is_member(setu, list_data(member))) 
		{
			continue;
		}
		else 
		{
			if (list_ins_next(setu, list_tail(setu), list_data(member)) != 0)
			{
				set_destory(setu);
				return -1;
			}
		}
	}
	return 0;
}

/*set_intersection 集合交集*/
int set_intersection(Set* seti, const Set* set1, const Set* set2) 
{
	ListElement* member;

	// 初始化交集的集合
	set_init(seti, set1->match, NULL);
	// 插入这个第一个集合
	for (member = list_head(set1); member != NULL; member = list_next(member))
	{    
		// 这个数据两个集合都存在
		if (set_is_member(set2, list_data(member))) 
		{
			if (list_ins_next(seti, list_tail(seti), list_data(member)) != 0) 
			{
				set_destory(seti);
				return -1;
			}
		}
	}
	return 0;
}

/*set_difference 集合差集*/
int set_difference(Set* setd, const Set* set1, const Set* set2) 
{
	ListElement* member;
    // 差集初始化
	set_init(setd,set1->match,NULL);
	// 将集合1插入差集
	for (member = list_head(set1); member != NULL; member = list_next(member))
	{
		if (!set_is_member(set2, list_data(member)))
		{
			set_destory(setd);
			return -1;
		}
	}
	return 0;
}
/*set_is_member 判断成员是否在集合里*/
int set_is_member(const Set* set, void* data) 
{   
	ListElement* member;
	for (member = list_head(set); member != NULL; member = list_next(member))
	{
		if (set->match(data,list_data(member)))
		{
			return 1;
		}
	}
	return 0;
}
/*set_is_subset 判断set1是否set2的子集*/
int set_is_subset(const Set* set1, const Set* set2)
{   
	ListElement* member;
	if (set_size(set1)>set_size(set2))
	{
		return 0;
	}
	for (member = list_head(set1); member != NULL; member = list_next(member))
	{
		if (!set_is_member(set1, set2)) 
		{
			return 0;
		}
	}
	return 1;
}

/*set_is_equel 判断set1相等set2*/
int set_is_equel(const Set* set1, const Set* set2)
{
	ListElement* member;
	if (set_size(set1) != set_size(set2)) 
	{
		return 0;
	}
	for (member = list_head(set1); member != NULL; member = list_next(member))
	{
		if (!set_is_member(set1, set2))
		{
			return 0;
		}
	}
	return 1;

}

集合覆盖问题

有空补充