Implementación de Conjuntos en C/C++

Presentamos ahora la implementación de conjuntos en el lenguaje C/C++, el cual no cuenta con un tipo de datos específico, tal como el SET de Pascal, por lo que hemos recurrido a los operadores lógicos binarios, ya descritos en anteriores entradas (1)(2). 

Cada elemento de un conjunto de éstos está representado por un bit, y solamente permite datos de tipo base enteros, concretamente unsigned char. Se agrupan hasta 128 datos almacenados en un arreglo de 16 elementos. Veamos el código:

//Conjuntos.Cpp

#include "stdio.h"
#include "conio.h"
#include "alloc.h"

/* Definiciones */

#define M 128   // Elementos del conjunto
#define N 16     // Elementos del arreglo. M /8

unsigned char A[N], B[N], *C;
unsigned char x, y;

/* Prototipos de funciones */
void Iniciar (unsigned char C[]);
unsigned char byte (unsigned char x);
unsigned char bit (unsigned char x);
unsigned char Pertenece (unsigned char x, unsigned char C[]);
void Incluir (unsigned char x, unsigned char C[]);
void Excluir (unsigned char x, unsigned char C[]);
unsigned char *Union(unsigned char A[], unsigned char B[]);
unsigned char *Interseccion (unsigned char A[], unsigned char B[]);
unsigned char *Diferencia(unsigned char A[], unsigned char B[]);
unsigned char *Complemento (unsigned char A[]);
unsigned char Iguales(unsigned char A[], unsigned char B[]);
void Escribir (unsigned char C[]);
void Listar (unsigned char C[]);

void main() {
    // Iniciamos los conjuntos A y B
    Iniciar(A); Iniciar(B);
  
    // Agregamos algunos elementos al conjunto A
    for (x = 1; x < M; x *= 2)           // Potencias de 2
       Incluir(x, A);
    printf("A = "); Escribir(A);
  
    // Agregamos al conjunto B los multiplos de 20
    for (x = 20; x < M; x += 20)
        Incluir(x, B);
    printf("B = "); Escribir(B);

    // Hallamos la union de A y B en C
    C = Union(A, B);
    printf("Union de A y B = "); Escribir(C);

    // Hallamos la interseccion de A y B en C
    C = Interseccion(A, B);
    printf("Interseccion de A y B = "); Escribir(C);

    // Hallamos la diferencia de A y B en C
    C = Diferencia(A, B);
    printf("Diferencia de A y B = "); Escribir(C);

    // Hallamos complemento del conjunto A
    C = Complemento(A);
    printf("Complemento de A = "); Escribir(C);

    // Determinamos si los conjuntos A y B son iguales o diferentes
    if (Iguales(A, B))
        printf("\nA y B son iguales. \n");
    else
        printf("\nA y B son diferentes. \n");
    printf("\nA = "); Escribir(A);
    printf("\nB = "); Escribir(B);

    // Determinamos si los conjuntos A y C son iguales o diferentes
    C = A;
    if (Iguales(A, C))
        printf("\nA y C son iguales. \n");
    else
        printf("\nA y C son diferentes. \n");
    printf("\nA = "); Escribir(A);
    printf("\nC = "); Escribir(C);

    // Eliminamos algunos elementos del conjunto A
    Excluir(8, A); Excluir(32, A);
    printf("Despues de eliminar 8 y 32 de A.\n");
    printf("\nA = "); Escribir(A);
    getch();
}

/* ************************************************ */

/* Iniciar el conjunto */
void Iniciar (unsigned char C[])  {
    unsigned char i;
    for (i = 0; i < N; i++)
        C[i] = 0;
}

/* Determinar byte que ocupa el elemento x */
unsigned char byte (unsigned char x)  {
    return (x / 8);
}

/* Determinar el bit del byte que ocupa el elemento */
unsigned char bit (unsigned char x) {
    return (x % 8);
}

/* Incluir un elemento al conjunto */
void Incluir (unsigned char x, unsigned char C[]) {
    C[byte(x)] |= (1 << bit(x));
}

/* Excluir un elemento del conjunto */
void Excluir (unsigned char x, unsigned char C[]) {
    C[byte(x)] &= (255 - (1 << bit(x)));
}

/* Determinar si un elemento pertenece al conjunto */
unsigned char Pertenece (unsigned char x, unsigned char C[]) {
    if (C[byte(x)] & (1 << bit(x)))  return 1;
    else return 0;
}

/* Unión de dos conjuntos */
unsigned char *Union(unsigned char A[], unsigned char B[]) {
unsigned char i, *C, *D;
    C = (unsigned char *)malloc(N);
    D = C;
    for (i = 0; i < N; i++)  {
        *C = A[i] | B[i];
        C++;
    }
    return D;
}

/* Intersección de dos conjuntos */
unsigned char *Interseccion (unsigned char A[], unsigned char B[]) {
unsigned char i, *C, *D;
    C = (unsigned char *) malloc(N);
    D = C;
    for (i = 0; i < N; i++)  {
        *C = A[i] & B[i];
        C++;
    }
    return D;
}

/* Diferencia entre dos conjuntos */
unsigned char *Diferencia(unsigned char A[], unsigned char B[]) {
unsigned char i, *C, *D;
    C = (unsigned char *)malloc(N);
    D = C;
    for (i = 0; i < N; i++ )  {
        *C = A[i] & ~B[i];
        C++;
    }
    return D;
}

/* Hallar el complemento de un conjunto */
unsigned char *Complemento (unsigned char A[]) {
unsigned char i, *C, *D;
    C = (unsigned char *) malloc(N);
    D = C;
    for (i = 0; i < N; i++)  {
        *C = ~A[i];
        C++;
    }
    return D;
}

/* Determinar si dos conjuntos son iguales */
unsigned char Iguales(unsigned char A[], unsigned char B[]) {
unsigned char i;
    for (i = 0; i < N; i++)
        if (A[i] != B[i])  return 0;
    return 1;
}

// Determinar si un conjunto esta vacio
unsigned char Vacio(unsigned char C[]) {
unsigned char x;
    for (x = 0; x < N; x++)
        if (C[x] != 0)  return 0;
    return 1;
}

/* Escribir conjunto */
void Escribir (unsigned char C[]) {
unsigned char x;
    if  (!Vacio(C))  {
        printf("{ ");
        for (x = 0; x < M; x++)
            if (Pertenece(x, C))  printf("%u, ", x);
        printf("\b\b }"); // Borra la coma y el espacio anteriores
    }
    else  printf("{ }");
    printf("\n\n");
}