Un Conjunto es una colección de elementos distintos. Los elementos no se pueden modificar una vez agregados. Hay varias operaciones asociadas con conjuntos, como unión, intersección, conjunto de potencia, producto cartesiano, diferencia de conjunto, complemento e igualdad.
Métodos de conjunto:
- add(data) – Agrega ‘datos’ al conjunto
- unionSet(s) – Devuelve la unión del conjunto con el conjunto ‘s’
- intersecciónSet(s) – Devuelve el conjunto de intersección con el conjunto ‘s’
- complementSet(U) – Devuelve el complemento del conjunto con Universal Set ‘U’
- operador -(s) – Devuelve la diferencia del conjunto y el conjunto ‘s’
- operador ==(s) – Devuelve si el conjunto es igual al conjunto ‘s’
- displayProduct(s) – Imprime el producto cartesiano de set y set ‘s’ en la consola
- displayPowerSet(): imprime el conjunto de potencia del conjunto en la consola
- toArray(): devuelve el conjunto como una array de sus elementos
- contiene(s) – Devuelve si el conjunto contiene el elemento ‘s’
- displaySet() – Imprime el conjunto en la consola
- getSize() – Devuelve el tamaño del conjunto
A continuación se muestra una implementación de un conjunto que utiliza Binary Search Tree :
C++
// C++ implementation of the approach
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stack>
#include <string>
using namespace std;
// Structure to implement a node of a BST
template <typename T>
struct Node {
// The data content of the node
T data;
// Link to the left child
Node* left;
// Link to the right child
Node* right;
public:
// Function to print the inorder
// traversal of the BST
void inorder(Node* r)
{
if (r == NULL) {
return;
}
inorder(r->left);
cout << r->data << " ";
inorder(r->right);
}
/*
Function to check if BST contains a node
with the given data
@param r pointer to the root node
@param d the data to search
@return 1 if the node is present else 0
*/
int containsNode(Node* r, T d)
{
if (r == NULL) {
return 0;
}
int x = r->data == d ? 1 : 0;
return x | containsNode(r->left, d) | containsNode(r->right, d);
}
/*
Function to insert a node with
given data into the BST
@param r pointer to the root node
@param d the data to insert
@return pointer to the root of the resultant BST
*/
Node* insert(Node* r, T d)
{
// Add the node when NULL node is encountered
if (r == NULL) {
Node<T>* tmp = new Node<T>;
tmp->data = d;
tmp->left = tmp->right = NULL;
return tmp;
}
// Traverse the left subtree if data
// is less than the current node
if (d < r->data) {
r->left = insert(r->left, d);
return r;
}
// Traverse the right subtree if data
// is greater than the current node
else if (d > r->data) {
r->right = insert(r->right, d);
return r;
}
else
return r;
}
};
// Class to implement a Set using BST
template <typename T>
class Set {
// Pointer to the root of the
// BST storing the set data
Node<T>* root;
// The number of elements in the set
int size;
public:
// Default constructor
Set()
{
root = NULL;
size = 0;
}
// Copy constructor
Set(const Set& s)
{
root = s.root;
size = s.size;
}
/*
Function to Add an element to the set
@param data the element to add to the set
*/
void add(const T data)
{
if (!root->containsNode(root, data)) {
root = root->insert(root, data);
size++;
}
}
/*
Function to compute the union of two sets
@param s set to find union with
@return the union set
*/
Set unionSet(Set& s)
{
Set<T> res;
// Second set is returned
// if first set is empty
if (root == NULL)
return res;
// First set is returned
// if second set is empty
if (s.root == NULL)
return *this;
// The elements of the first set
// are added to the resultant set
stack<Node<T>*> nodeStack;
nodeStack.push(root);
// Preorder traversal of the BST
while (!nodeStack.empty()) {
Node<T>* node;
node = nodeStack.top();
nodeStack.pop();
// The data is added to the resultant set
res.add(node->data);
if (node->right)
nodeStack.push(node->right);
if (node->left)
nodeStack.push(node->left);
}
// The elements of the second set
// are added to the resultant set
stack<Node<T>*> nodeStack1;
nodeStack1.push(s.root);
while (!nodeStack1.empty()) {
Node<T>* node;
node = nodeStack1.top();
nodeStack1.pop();
res.add(node->data);
if (node->right)
nodeStack1.push(node->right);
if (node->left)
nodeStack1.push(node->left);
}
return res;
}
/**
Computes the intersection of two sets
@param s the set to find intersection with
@return the intersection set
*/
Set intersectionSet(Set& s)
{
Set<T> res;
stack<Node<T>*> nodeStack;
nodeStack.push(root);
while (!nodeStack.empty()) {
Node<T>* node;
node = nodeStack.top();
nodeStack.pop();
if (s.contains(node->data)) {
res.add(node->data);
}
if (node->right)
nodeStack.push(node->right);
if (node->left)
nodeStack.push(node->left);
}
return res;
}
/*
Function to compute the complement of the set
@param U the universal set
@return the complement set
*/
Set complementSet(Set& U)
{
return (U - *this);
}
/*
Function to compute the difference of two sets
@param s the set to be subtracted
@return the difference set
*/
Set operator-(Set& s)
{
Set<T> res;
stack<Node<T>*> nodeStack;
nodeStack.push(this->root);
while (!nodeStack.empty()) {
Node<T>* node;
node = nodeStack.top();
nodeStack.pop();
if (!s.contains(node->data)) {
res.add(node->data);
}
if (node->right)
nodeStack.push(node->right);
if (node->left)
nodeStack.push(node->left);
}
return res;
}
/*
Function that checks equality of two sets
@param s set to check equality with
@return boolean value denoting result of check
*/
bool operator==(Set& s)
{
if (s.getSize() != size) {
return false;
}
stack<Node<T>*> nodeStack;
nodeStack.push(this->root);
while (!nodeStack.empty()) {
Node<T>* node;
node = nodeStack.top();
nodeStack.pop();
if (!s.contains(node->data)) {
return false;
}
if (node->right)
nodeStack.push(node->right);
if (node->left)
nodeStack.push(node->left);
}
return true;
}
/*
Function to print the cartesian product of two sets
@param s the set to find product with
*/
void displayProduct(Set& s)
{
int i, j, n2 = s.getSize();
T* A = toArray();
T* B = s.toArray();
i = 0;
cout << "{ ";
for (i = 0; i < size; i++) {
for (j = 0; j < n2; j++) {
cout << "{ " << A[i] << " " << B[j] << " } ";
}
}
cout << "}" << endl;
}
// Function to print power set of the set
void displayPowerSet()
{
int n = pow(2, size);
T* A = toArray();
int i;
while (n-- > 0) {
cout << "{ ";
for (int i = 0; i < size; i++) {
if ((n & (1 << i)) == 0) {
cout << A[i] << " ";
}
}
cout << "}" << endl;
}
}
/*
Function to convert the set into an array
@return array of set elements
*/
T* toArray()
{
T* A = new T[size];
int i = 0;
stack<Node<T>*> nodeStack;
nodeStack.push(this->root);
while (!nodeStack.empty()) {
Node<T>* node;
node = nodeStack.top();
nodeStack.pop();
A[i++] = node->data;
if (node->right)
nodeStack.push(node->right);
if (node->left)
nodeStack.push(node->left);
}
return A;
}
/*
Function to check whether the set contains an element
@param data the element to search
@return relut of check
*/
bool contains(T data)
{
return root->containsNode(root, data) ? true : false;
}
// Function to print the contents of the set
void displaySet()
{
cout << "{ ";
root->inorder(root);
cout << "}" << endl;
}
/*
Function to return the current size of the Set
@return size of set
*/
int getSize()
{
return size;
}
};
// Driver code
int main()
{
// Create Set A
Set<int> A;
// Add elements to Set A
A.add(1);
A.add(2);
A.add(3);
A.add(2);
// Display the contents of Set A
cout << "A = ";
A.displaySet();
cout << "P(A) = " << endl;
A.displayPowerSet();
// Check if Set A contains some elements
cout << "A " << (A.contains(3) ? "contains"
: "does not contain")
<< " 3" << endl;
cout << "A " << (A.contains(4) ? "contains"
: "does not contain")
<< " 4" << endl;
cout << endl;
// Create Set B
Set<int> B;
// Insert elements to Set B
B.add(1);
B.add(2);
B.add(4);
// Display the contents of Set B
cout << "B = ";
B.displaySet();
cout << "P(B) = " << endl;
B.displayPowerSet();
cout << endl;
// Create Set C
Set<int> C;
C.add(1);
C.add(2);
C.add(4);
// Display the contents of Set C
cout << "C = ";
C.displaySet();
cout << endl;
// Set F contains the difference
// of the Sets A and B
Set<int> F = A - B;
cout << "A - B = ";
F.displaySet();
cout << endl;
// Set D contains the union
// of the Sets A and B
Set<int> D = A.unionSet(B);
cout << "A union B = ";
D.displaySet();
cout << endl;
// Set E contains the intersection
// of the Sets A and B
Set<int> E = A.intersectionSet(B);
cout << "A intersection B = ";
E.displaySet();
cout << endl;
// Display the product
cout << "A x B = ";
A.displayProduct(B);
cout << endl;
// Equality tests
cout << "Equality of Sets:" << endl;
cout << "A "
<< ((A == B) ? "" : "!") << "= B"
<< endl;
cout << "B "
<< ((B == C) ? "" : "!") << "= C"
<< endl;
cout << "A "
<< ((A == C) ? "" : "!") << "= C"
<< endl;
cout << endl;
Set<int> U;
U.add(1);
U.add(2);
U.add(3);
U.add(4);
U.add(5);
U.add(6);
U.add(7);
// Complements of the respective Sets
Set<int> A1 = A.complementSet(U);
Set<int> B1 = B.complementSet(U);
Set<int> C1 = C.complementSet(U);
cout << "A' = ";
A1.displaySet();
cout << "B' = ";
B1.displaySet();
cout << "C' = ";
C1.displaySet();
return 0;
}
Producción:
A = { 1 2 3 }
P(A) =
{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
{ 1 3 }
{ 2 3 }
{ 1 2 3 }
A contains 3
A does not contain 4
B = { 1 2 4 }
P(B) =
{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 4 }
{ 1 4 }
{ 2 4 }
{ 1 2 4 }
C = { 1 2 4 }
A - B = { 3 }
A union B = { 1 2 3 4 }
A intersection B = { 1 2 }
A x B = { { 1 1 } { 1 2 } { 1 4 } { 2 1 } { 2 2 } { 2 4 } { 3 1 } { 3 2 } { 3 4 } }
Equality of Sets:
A != B
B = C
A != C
A' = { 4 5 6 7 }
B' = { 3 5 6 7 }
C' = { 3 5 6 7 }
Se puede usar AVL Tree o Red-Black Tree en lugar de BST simple para hacer que la inserción y la búsqueda de O(log(n)) sean más complejas.
Para usar el conjunto STL, consulte este artículo Establecer en la biblioteca de plantillas estándar (STL) de C++ .