c++中如何表示集合,并且怎么进行集合的运算

发布网友发布时间：2022-04-30 20:15

共2个回答

热心网友时间：2022-07-01 00:09

你可以使用并查集，你可以查一下怎么使用，如果了解STL，你可以使用stl中的set。而且STL提供了标准的集合的算法， set_difference,set_union,set_intersect进行并集，交集，抑或等运算。如果上述不会，你可以使用简单的链表实现。比如第一个链表代表集合A，链表2代表集合B。。。。当插入元素的时候在指导的链表中插入即可，进行运算的时候就需要二阶循环，将链表A中的元素与B中的每一个元素都进行比较，满足条件的插入到结果链表中，最后返回结果链表即可。

热心网友时间：2022-07-01 00:09

#include <iostream>
#include <string>

using namespace std;

template <typename Type>
class MySet
{
public:
MySet();
MySet(int s, const Type a[]);
MySet(const MySet<Type> &o);

void Empty();
bool IsEmpty() const;
bool IsMemberOf(const Type &m) const;
void Add(const Type &m);
Type Sub();
bool IsEqual(const MySet<Type> &o) const;
MySet<Type> operator&(const MySet<Type> &o);
MySet<Type> operator|(const MySet<Type> &o);
void Print();

private:
Type element[100];
int count;
};

template <typename Type>
MySet<Type>::MySet() : count(0)
{
}

template <typename Type>
MySet<Type>::MySet(int s, const Type a[]) : count(s)
{
for (int i = 0; i < s; ++i)
element[i] = a[i];
}

template <typename Type>
MySet<Type>::MySet(const MySet &o)
{
count = o.count;

for (int i = 0; i < count; ++i)
element[i] = o.element[i];
}

template <typename Type>
void MySet<Type>::Empty()
{
count = 0;
}

template <typename Type>
bool MySet<Type>::IsEmpty() const
{
return (count == 0);
}

template <typename Type>
bool MySet<Type>::IsEqual(const MySet<Type> &o) const
{
if ((count != o.count)
|| (IsEmpty() && !o.IsEmpty())
|| (!IsEmpty() && o.IsEmpty()))
return false;

for (int i = 0; i < count; ++i)
{
if (element[i] != o.element[i])
return false;
}

return true;
}

template <typename Type>
bool MySet<Type>::IsMemberOf(const Type &m) const
{
if (IsEmpty())
return false;

for (int i = 0; i < count; ++i)
{
if (element[i] == m)
return true;
}

return false;
}

template <typename Type>
void MySet<Type>::Add(const Type &m)
{
if (++count > 100)
return;

element[count - 1] = m;
}

template <typename Type>
Type MySet<Type>::Sub()
{
if (IsEmpty())
return 0;

Type temp = element[count];
--count;

return temp;
}

template <typename Type>
MySet<Type> MySet<Type>::operator&(const MySet<Type> &o)
{
MySet<Type> inset;

if (IsEmpty() || o.IsEmpty())
return inset;

for (int i = 0; i < count; ++i)
{
for (int j = 0; j < o.count; ++j)
if (element[i] == o.element[j] && !inset.IsMemberOf(o.element[j]))
inset.Add(element[i]);
}

return inset;
}

template <typename Type>
MySet<Type> MySet<Type>::operator|(const MySet<Type> &o)
{
MySet<Type> unset(count, element);

if (!IsEmpty() && o.IsEmpty())
return unset;

if (IsEmpty() && !o.IsEmpty())
return MySet(o);

for (int i = 0; i < count; ++i)
{
for (int j = 0; j < o.count; ++j)
if (element[i] != o.element[j] && !unset.IsMemberOf(o.element[j]))
unset.Add(o.element[j]);
}

return unset;
}

template <typename Type>
void MySet<Type>::Print()
{
for (int i = 0; i < count; ++i)
cout << element[i] << ' ';
cout << endl;
}

int main()
{
int ia[7] = { 1, 2, 3, 4, 5, 6, 7 };
MySet<int> a, b(7, ia);
a.Add(6);
a.Add(7);
a.Add(8);
a.Add(9);
a.Print();
b.Print();
MySet<int> c = a | b;
MySet<int> d = a & b;
c.Print();
d.Print();
MySet<string> str;
str.Add("Hello");
str.Add("World!");
str.Print();
return 0;
}