* Introducción
* Representación mediante arrays de bits
* Representación mediante array
* Representación mediante lista enlazada

Introducción

Los conjuntos son una de las estructuras básicas de las matemáticas, y por tanto de la informática. No se va a entrar en la definición de conjuntos ni en sus propiedades. Se supondrá que el lector conoce algo de teoría de conjuntos. Con lo más básico es suficiente.

En realidad las estructuras de datos que se han implementado hasta ahora no son más que elementos diferentes entre sí (en general) en los que se ha definido una relación. Por ejemplo, en las listas ordenadas o los árboles binarios de búsqueda se tiene una serie de elementos que están ordenados entre sí. Obviando las propiedades de las estructuras, se ve que forman un conjunto, y su cardinal es el número de elementos que contenga la estructura. En los conjuntos no existen elementos repetidos, y esto se respeta en las implementaciones que se ofrecen a continuación.

Ahora bien, en esta sección se van definir unas implementaciones que permitan aplicar el álgebra de conjuntos, ya sea unión, intersección, pertenencia, etc. Se realizan tres implementaciones: array de bits, arrays y listas enlazadas.

Representación mediante arrays de bits

Ciertamente, un bit no da más que para representar dos estados diferentes. Por supuesto, pueden ser atributos muy variados, por ejemplo, ser hombre o mujer, adulto o niño, Windows o Linux, etc. También sirve para indicar si un elemento está o no dentro de un conjunto.

El array se utiliza para representar un conjunto de números naturales (u otro tipo de datos cuyos elementos se identifiquen por un número natural único mediante una correspondencia) entre 0 y N, siendo N la capacidad del array unidimensional (es decir, un vector); almacenará valores booleanos, esto es, 1 ó 0.

Por ejemplo, suponer el conjunto universal formado por los enteros entre 0 y 4: U = {0, 1, 2, 3, 4}, y el conjunto C = {1, 2}. Se representará de esta manera:

1 : indica que el elemento pertenece al conjunto.
0 : indica que el elemento no pertenece al conjunto.

Ahora bien, se ha dicho que se va a emplear un array de bits. ¿Qué se quiere decir con esto? Que no se va a emplear un array o vector como tal, sino un tipo de datos definido por el lenguaje de programación, que suele ocupar entre 8 y 64 bits, y por tanto podrá incluir hasta 64 elementos en el conjunto. Por ejemplo, en C o Pascal se define un tipo que ocupa 8 bits:

unsigned char conjunto8;
var conjunto8 : byte;

Si todos los bits de conjunto8 están a 1 entonces se tiene el conjunto: U = {0, 1, 2, 3, 4, 5, 6, 7}, y su cardinal es 8. Si todos los bits están a 0 se tiene el conjunto vacío. El bit más significativo señalará al elemento de mayor valor, el bit menos significativo al de menor valor. Ejemplos (bit más significativo a la izquierda):

11111111 -> U = {0, 1, 2, 3, 4, 5, 6, 7}
11110001 -> U = {0, 4, 5, 6, 7}
01010101 -> U = {0, 2, 4, 6}
00000000 -> U = vacío

La razón para emplear los arrays de bits es que las operaciones sobre los conjuntos se realizan de manera muy rápida y sencilla, al menos con los computadores actuales, que tienen un tamaño de palabra múltiplo de 8. Por supuesto, la ocupación en memoria está optimizada al máximo.
El inconveniente es que el rango de representación es muy limitado. Por eso su aplicación es muy restringida, y depende fuertemente del compilador y el computador sobre el que se implementan, pero es increíblemente rápida.

Nota: Pascal cuenta con un juego de instrucciones para manipular conjuntos definidos mediante arrays de bits, dando al usuario transparencia total sobre su manejo.

A continuación se implementa un TAD sobre conjuntos en C mediante array de bits.

- Tipo de datos empleado:

typedef unsigned long tconjunto;

El tipo long suele ocupar 32 bits, por tanto el rango será: [0..31].

Nota importante: en los ejemplos se muestran conjuntos que sólo tienen un máximo de 8 elementos (8 bits). Esto está puesto simplemente por aumentar la claridad, y cómo no, por ahorrar ceros.

- Definición de conjunto vacío y universal:

const tconjunto Universal = 0xFFFFFFFF;
const tconjunto vacio = 0;

Es decir, 32 bits puestos a 1 para el conjunto universal, 32 bits puestos a 0 para el conjunto vacío.

- Unión:

Se realiza mediante la operación de OR inclusivo. Ejemplo (con 8 bits en lugar de 32):

    11001100 -> A = {2,3,6,7}
Or 10010100 -> B = {2,4,7}
    ---------
    11011100 -> C = {2,3,4,6,7}

y se codifica así:

tconjunto unircjto(tconjunto A, tconjunto B)
{ return (A | B); }

- Intersección:

Se realiza mediante la operación AND. Ejemplo:

      11001100 -> A = {2,3,6,7}
And 10010100 -> B = {2,4,7}
      ---------
      10000100 -> C = {2,7}

y se codifica así:

tconjunto interseccion(tconjunto A, tconjunto B)
{ return (A & B); }

- Diferencia:

Para obtener C = A-B se invierten todos los bits de B y se hace un AND entre A y B negado. Ejemplo:

10011101 -> A = {0,2,3,4,7}
10110010 -> B = {1,4,5,7}
B negado: 01001101 -> B(negado) = {0,2,3,6}

      10011101
And 01001101
      ---------
      00001101 -> C = {0,2,3}

y se codifica así:

tconjunto diferencia2(tconjunto A, tconjunto B)
{ return (A & ~B); }

- Diferencia simétrica:

C = (A-B) Unión (B-A)
Se realiza mediante la operación de OR exclusivo (XOR) o aplicando las primitivas definidas anteriormente. Ejemplo:

     11110000 -> A = {4,5,6,7}
Xor 00011110 -> B = {1,2,3,4}
     ---------
     11101110 -> C = {1,2,3,5,6,7}

y se codifica así:

tconjunto difsim(tconjunto A, tconjunto B)
{ return (A ^ B); }

- Igualdad de conjuntos:

La implementación es directa, si todos los bits de A y B se corresponden entonces son iguales:

int iguales(tconjunto A, tconjunto B)
{ return (A == B); }

- Subconjuntos:

Si un conjunto A es subconjunto (considerando que un conjunto cualquiera es subconjunto de si mismo) de otro B entonces verifica esta relación: A intersección B = A. Notar que A es subconjunto de A, pues A intersección A = A.

Ejemplo:
A = {1,2,3,4}, B = {0,1,2,3}
C = A intersección B = {1,2,3}; C es distinto de A.

Se codifica así:

int subconjunto(tconjunto A, tconjunto B)
{ return (iguales(interseccion(A,B),A)); }

- Pertenencia:

Determinar si un elemento pertenece a un conjunto requiere efectuar una operación de desplazamiento a nivel de bits y una posterior comprobación del bit de signo resultante. Como siempre, un ejemplo o dos lo aclaran:
Sea x = 0 y A = {0,1,2,5}. Determinar si x pertecene a A.
00100111 -> A.
Primero se desplazan los bits de A tantas veces a la derecha como valga x, en el ejemplo no se desplazan; se obtiene A'. A continuación se aplica el test del bit de signo sobre A', que consiste en obtener el resto de la división entera entre dos. Si el resto es uno, entonces x pertenece a A. En caso contrario no pertenece a A. En el ejemplo: A' mod 2 = 1, luego x pertenece a A.

Otro ejemplo: x = 3, A = {0,1,2,5}.
Se desplazan los bits de A tres posiciones a la derecha:
00000100 -> A'.
Se hace el test de signo: A' mod 2 = 0. x no pertenece a A.

La codificación es la siguiente:

int pertenece(tconjunto A, int x)
{ return ((A >> x) % 2); }

- Inserción y borrado:

Para insertar un elemento x es necesario poner a 1 el bit correspondiente. Una manera sencilla de hacerlo es mediante una suma. Hay que sumar un valor que se corresponda con el bit que se quiere establecer a 1. Para hacerlo se volverá a aplicar una operación de desplazamiento, pero esta vez hacia la izquierda y aplicada sobre el número 1. Se desplazan x bits hacia la izquierda, suponiendo que el compilador llena con ceros por la derecha.

Por ejemplo, partir de A = conjunto vacío: { }.
Se quieren insertar los elementos 0,2,3 sobre A.
Insertar 0:
x = 0. p = 1, (00000001 en binario). Se desplaza p x (0) bits a la izquierda, p' = 1, y se suma a A. Queda: A <- A + p'. A = 1.

Insertar 2:
x = 2. p = 1. Se desplaza p x (2) bits a la izquierda, p' = 4 (000000100 en binario). A <- A (1) + p' (4), A = 5 (000000101).

Insertar 3:
x =3. p = 1. Se desplaza p x (3) bits a la izquierda, p' = 8. A <- A (5) + p' (8), A = 13 (00001101).

El borrado es exactamente lo mismo, pero hay que restar p en vez de sumar. Ejemplo: borrar 3 de A.
A <- A (13) - p' (8), A = 5 (00000101)

Antes de la codificación, hay que considerar otro detalle: es necesario comprobar previamente si el elemento ya está en el conjunto para evitar problemas inesperados. Por tanto, la codificación queda así para la inserción:

tconjunto insertar(tconjunto A, int x)
{
  if (pertenece(A,x)) return A;
  else return (A + ((tconjunto)1 << x));
}

y para el borrado:

tconjunto borrar(tconjunto A, int x)
{
  if (pertenece(A,x)) return A;
  else return (A - ((tconjunto)1 << x));
}

Conclusiones

Sin duda alguna, la gran ventaja de esta implementación es la rapidez de ejecución de todas las operaciones, que se ejecutan en tiempo constante: O(1). Además los elementos se encuentran empaquetados ocupando el menor espacio posible, esto es, un único bit.

La desventaja es que no admiten un rango muy amplio de representación. Aun así, para incrementar el rango basta con crear un array de tipo conjunto, por ejemplo: tconjunto superconjunto[10], y aplicar las operaciones sobre los bits en todos los elementos del array, excepto para la inserción y borrado, en cuyo caso hay que encontrar el bit exacto a manipular.

Representación mediante array

Los elementos del conjunto se guardan uno a continuación de otro empleando una lista densa representada mediante un array.

Ejemplo: Sea el conjunto C = {1, 2}. Se representará de esta manera:

y su cardinal es 2.

Esta representación no limita el rango de representación más que al tipo de datos empleado. Por supuesto, ya no puede definirse explícitamente el conjunto universal.

Por razones de eficiencia a la hora de implementar las primitivas, las estructuras se pasan por referencia. Es un detalle importante, porque C garantiza que un array se pasa siempre por referencia, pero eso no es cierto si el array se pasa como parte de una estructura.

No se implementan rutinas de control de errores ni su detección. Se produce un error cuando se tratan de añadir elementos y estos desbordan la capacidad del array.

Nota importante: los elementos dentro del array no están ordenados entre sí.

- Tipo de datos empleado:

typedef int tTipo;

typedef struct
{
  tTipo elems[MAXELEM];
  int cardinal;
} tconjunto;

- Definición de conjunto vacío:

Un conjunto está vacío si su cardinal es cero. Para inicializar un conjunto a vacío basta con una instrucción:

A->cardinal = 0

- Pertenencia:

Para determinar si un elemento x pertenece al conjunto basta con recorrer el array hasta encontrarlo. Se devuelve True si se encuentra. Codificación:

int pertenece(tconjunto *A, tTipo x)
{
  int i;
  for (i = 0; i < A->cardinal; i++)
    if (A->elems[i] == x) return 1;
  return 0;
}

- Inserción y borrado:

Para insertar un elemento, primero debe comprobarse que no está, después se inserta en la última posición, esto es, la que señale el cardinal, que se incrementa en una unidad. Codificación:

void insertar(tconjunto *A, tTipo x)
{
  if (!pertenece(A, x))
    A->elems[A->cardinal++] = x;
}

Borrar es aparentemente más complicado. No se puede eliminar el elemento y dejar un hueco, puesto que en ese caso ya no se tiene una lista. Para eliminar este problema se sustituye el elemento borrado por el último de la lista. Codificación:

void borrar(tconjunto *A, tTipo x)
{
  int i;
  for (i = 0; i < A->cardinal; i++)
    if (A->elems[i] == x) {
      A->elems[i] = A->elems[--A->cardinal]; return;
    }
}

- Unión:

Para hacer C = A Unión B, se introducen en C todos los elementos de A y todos los elementos de B que no pertenezcan a A. Codificación:

void unircjto(tconjunto *A, tconjunto *B, tconjunto *C)
{
  int i;
  *C = *A;
  for (i = 0; i < B->cardinal; i++)
    if (!pertenece(A, B->elems[i]))
      insertar(C, B->elems[i]);
}

- Intersección:

Para hacer C = A intersección B, se hace un recorrido sobre A (o B) y se insertan en C los elementos que estén en B (o A).

El pseudocódigo es:

C = vacío
para cada x elemento de A
  si x pertenece a B entonces insertar x en C.

En C:

void interseccion(tconjunto *A, tconjunto *B, tconjunto *C)
{
  int i;
  C->cardinal = 0;
  for (i = 0; i < A->cardinal; i++)
    if (pertenece(B, A->elems[i]))
      insertar(C, A->elems[i]);
}

- Diferencia:

Para hacer C = A-B, se hace un recorrido sobre A (o B) y se insertan en C los elementos que no estén en B (o A).

El pseudocódigo es:

C = vacío
para cada x elemento de A
  si x no pertenece a B entonces insertar x en C.

En C:

void diferencia(tconjunto *A, tconjunto *B, tconjunto *C)
{
  int i;
  C->cardinal = 0;
  for (i = 0; i < A->cardinal; i++)
    if (!pertenece(B, A->elems[i]))
      insertar(C, A->elems[i]);
}

- Diferencia simétrica:

Sea C = (A-B) Unión (B-A). Para obtener este resultado se puede aprovechar el código estudiado anteriormente.

El pseudocódigo es:

C = vacío
para cada x elemento de A
  si x no pertenece a B entonces insertar x en C
para cada x elemento de B
  si x no pertenece a A entonces insertar x en C

En C:

void difsim(tconjunto *A, tconjunto *B, tconjunto *C)
{
  int i;
  C->cardinal = 0;
  for (i = 0; i < A->cardinal; i++)
    if (!pertenece(B, A->elems[i]))
      insertar(C, A->elems[i]);
  for (i = 0; i < B->cardinal; i++)
    if (!pertenece(A, B->elems[i]))
      insertar(C, B->elems[i]);  
}

- Subconjuntos:

Determinar si un conjunto A es subconjunto de B se reduce a comprobar si todo elemento de A es elemento de B. Se devuelve True si A es subconjunto de B. Codificación:

int subconjunto(tconjunto *A, tconjunto *B) /
{
  int i, esta;

  esta = 1;
  for (i = 0; i < A->cardinal; i++)
    if (!pertenece(B, A->elems[i])) return 0;
  return 1;
}

- Igualdad de conjuntos:

Un conjunto A es igual a otro B si A es subconjunto de B y ambos tienen los mismos elementos. Se devuelve True si A es igual a B. Codificación:

int iguales(tconjunto *A, tconjunto *B)
{
  return (subconjunto(A,B) && A->cardinal == B->cardinal);
}

Conclusiones

La ventaja de esta implementación es que no limita el rango de representación de los elementos del conjunto, y por supuesto tampoco limita el tipo de datos, siempre y cuando se pueda deducir cuando un elemento es igual a otro o no.

La desventaja de esta implementación con respecto a la de arrays de bits es su mala eficacia con respecto al tiempo de ejecución. El coste de la inserción y borrado es O(1). Siendo |A| el cardinal de un conjunto cualquiera A las operaciones de pertenencia se ejecuta en un tiempo O(|A|). En las restantes operaciones, que implican a dos conjuntos, la complejidad es O(|A|·|B|)

El espacio que ocupa un conjunto es de O(|MAXIMO|), siendo MAXIMO el tamaño del array.

Representación mediante lista enlazada

Esta representación es muy parecida a la implementación mediante un array, pero con alguna particularidad que la hace más interesante en algunos casos. Por supuesto, los tipos de datos de los elementos que se insertan son igualmente admisibles con listas como lo eran con arrays.

Suponer que entre los elementos del conjunto se puede definir una relación de orden, es decir, que se puede determinar si un elemento es mayor que otro. En este caso se pueden insertar y borrar elementos del conjunto de forma que la lista que los mantiene esté ordenada. Esto puede resultar interesante en algunas aplicaciones.

Sea |A| y |B| el cardinal de unos conjuntos cualesquiera A y B. Aplicando la suposición anterior las operaciónes de búsqueda, inserción y borrado se ejecutan en un tiempo O(|A|).
Pero hay una gran ventaja, y es que las restantes operaciones se ejecutan en un tiempo O(|A|+|B|). ¿Cómo se consigue ésto? Aprovechando las propiedades de tener listas ordenadas basta con hacer un único recorrido sobre cada lista. Esto es posible implementando un algoritmo basado en el algoritmo de fusión de dos listas ordenadas, que obtiene una lista ordenada a partir de dos o más listas ordenadas con un único recorrido de cada lista. (Es recomendable ver primero los Algoritmos de ordenación de listas y entender el proceso de intercalación o fusión, pero NO es necesario estudiar el proceso recursivo ya que no tiene interés aquí). Las operaciones de unión, intersección, etcétera, e incluiso el determinar si un conjunto es subconjunto de otro se efectúan haciendo pequeñas variaciones sobre el algoritmo de intercalación.

Nota sobre la implementación: Al estudiar la codificación se podrá notar que los conjuntos A y B sobre los que se hacen los recorridos no se modifican sino que quedan como están. Para ganar en eficiencia se puede hacer que el nuevo conjunto C no cree su propia lista de elementos sino que simplemente aproveche los enlaces de las listas que mantienen los conjuntos A y B, deshaciendo estos. Esto es algo opcional y no se ha implementado, pero es útil si dichos conjuntos no se van a emplear más. Los punteros c1 y c2 recorren las listas que representan a los conjuntos A y B respectivamente. El puntero c3 y aux sirven para crear el nuevo conjunto C.

Definición y tipo de datos empleado:

Se empleará una lista enlazada con cabecera ficticia y centinela. La razón es que se realizarán inserciones y búsquedas sobre la lista que contiene los elementos del conjunto. Como se ha comentado anteriormente, los elementos de la lista estarán ordenados. Por tanto, para emplear esta representación los elementos deben ser ordenables. En el código propuesto, se tratarán conjuntos de números enteros.

Los tipos de datos se declaran así:

typedef struct lista
{
  int elem;
  struct lista *sig;
} lista;


typedef struct tconjunto
{
  lista *cabecera,
	    *centinela;
  int cardinal;
} tconjunto;

- Creación del conjunto vacío:

La creación de un nuevo conjunto (vacío) se realiza estableciendo a cero el número de elementos y reservando memoria para los elementos de cabecera y centinela de la lista.

void crearcjto(struct tconjunto *cjto)
{
  cjto->cabecera = (lista *) malloc(sizeof(lista));
  cjto->centinela = (lista *) malloc(sizeof(lista));
  cjto->cabecera->sig = cjto->centinela;
  cjto->centinela->sig = cjto->centinela; /* opcional, por convenio */
  cjto->cardinal = 0;
}

- Pertenencia:

Para determinar si un elemento x pertenece al conjunto basta con recorrer la lista hasta encontrarlo o llegar al final de ésta. Se devuelve True si se encuentra antes del centinela.

int pertenece(tconjunto cjto, int x)
{
  lista *actual;

  actual = cjto.cabecera->sig;
  cjto.centinela->elem = x;
  while (actual->elem != x)
    actual = actual->sig;
  if (actual == cjto.centinela)
    return 0;
  else
    return 1;
}

- Inserción y borrado:

Para insertar un elemento primero debe comprobarse que no está, después se inserta ordenadamente en la lista, y se incrementa el cardinal en una unidad.

void insertar(tconjunto *cjto, int x)
{
  lista *anterior, *actual, *nuevo;

   /* 1.- busca */
  anterior = cjto->cabecera;
  actual = cjto->cabecera->sig;
  cjto->centinela->elem = x;
  while (actual->elem < x) {
    anterior = actual;
    actual = actual->sig;
  }

  if (actual->elem != x || actual == cjto->centinela) {
     /* 2.- crea */
    nuevo = (lista *) malloc(sizeof(lista));
    nuevo->elem = x;
     /* 3.- enlaza */
    nuevo->sig = actual;
    anterior->sig = nuevo;

    cjto->cardinal++;
  }
}

Para borrar un elemento basta con localizarlo dentro de la lista y eliminarlo.

void borrar(tconjunto *cjto, int x)
{
  lista *anterior, *actual;
    /* 1.- busca */
  anterior = cjto->cabecera;
  actual = cjto->cabecera->sig;
  cjto->centinela->elem = x;
  while (actual->elem < x) {
    anterior = actual;
    actual = actual->sig;
  }
  /* 2.- borra si existe */
  if (actual != cjto->centinela && actual->elem == x) {
    anterior->sig = actual->sig;
    free(actual);
  }
}

- Unión:

A partir de los conjuntos A y B se crea un nuevo conjunto C. Se supone que el conjunto C no ha sido inicializado antes. En cada paso se añade siempre un nuevo elemento. Por último se comprueba que no queden elementos sin copiar.

void unioncjto(tconjunto A, tconjunto B, tconjunto *C)
{
  lista *c1, *c2, *c3, *aux;

  crearcjto(C);
  c3 = C->cabecera;
  c1 = A.cabecera->sig; c2 = B.cabecera->sig;
  while (c1 != A.centinela && c2 != B.centinela) {
    aux = (lista *) malloc(sizeof(lista));
    if (c1->elem < c2->elem) {
      aux->elem = c1->elem;
      c1 = c1->sig;
    }
    else if (c1->elem > c2->elem) {
      aux->elem = c2->elem;
      c2 = c2->sig;
    }
    else {
      aux->elem = c1->elem; /* tambien vale: aux->elem = c2->elem */
      c1 = c1->sig;
      c2 = c2->sig;
    }
    aux->sig = C->centinela;
    c3->sig = aux; c3 = aux;
    C->cardinal++;
  }
  /* copia los elementos restantes si los hubiera */
  if (c1 != A.centinela) {
	while (c1 != A.centinela) {
	  aux = (lista *) malloc(sizeof(lista));
	  aux->elem = c1->elem;
	  aux->sig = C->centinela;
	  c3->sig = aux; c3 = aux;
	  C->cardinal++;
	  c1 = c1->sig;
	}
  }
  else if (c2 != B.centinela) {
	while (c2 != B.centinela) {
	  aux = (lista *) malloc(sizeof(lista));
	  aux->elem = c2->elem;
	  aux->sig = C->centinela;
	  c3->sig = aux; c3 = aux;
	  C->cardinal++;
	  c2 = c2->sig;
	}
  }
}

- Intersección:

C = A Intersección B, es el nuevo conjunto que se crea. Se añade un elemento cuando coincide en ambas listas a la vez (c1->elem == c2->elem).

void interseccion(tconjunto A, tconjunto B, tconjunto *C)
{
  lista *c1, *c2, *c3, *aux;

  crearcjto(C);
  c3 = C->cabecera;
  c1 = A.cabecera->sig; c2 = B.cabecera->sig;
  while (c1 != A.centinela && c2 != B.centinela) {
    if (c1->elem < c2->elem)
      c1 = c1->sig;
    else if (c1->elem > c2->elem)
      c2 = c2->sig;
    else {
      aux = (lista *) malloc(sizeof(lista));
      aux->elem = c1->elem; /* tambien vale: aux->elem = c2->elem */
      aux->sig = C->centinela;
      c3->sig = aux; c3 = aux;
      C->cardinal++;
      c1 = c1->sig;
      c2 = c2->sig;
	}
  }
}

- Diferencia:

C = A-B. Se añade un nuevo elemento sólo cuando (c1->elem < c2->elem).

void diferencia(tconjunto A, tconjunto B, tconjunto *C)
{
  lista *c1, *c2, *c3, *aux;

  crearcjto(C);
  c3 = C->cabecera;
  c1 = A.cabecera->sig; c2 = B.cabecera->sig;
  while (c1 != A.centinela && c2 != B.centinela) {
	if (c1->elem < c2->elem) {
      aux = (lista *) malloc(sizeof(lista));
      aux->elem = c1->elem;
      aux->sig = C->centinela;
      c3->sig = aux; c3 = aux;
      C->cardinal++;
      c1 = c1->sig;
	}
    else if (c1->elem > c2->elem)
      c2 = c2->sig;
    else 
      c1 = c1->sig, 
	  c2 = c2->sig;
  }
  /* aniade lo que quede de A */
  while (c1 != A.centinela) {
	aux = (lista *) malloc(sizeof(lista));
	aux->elem = c1->elem;
	aux->sig = C->centinela;
	c3->sig = aux; c3 = aux;
	C->cardinal++;
	c1 = c1->sig;
  }
}

- Diferencia simétrica:

C = (A-B) Unión (B-A). Es decir, todos los elementos no comunes de ambos conjuntos. Se añaden elementos si (c1->elem != c2->elem).

void difsim(tconjunto A, tconjunto B, tconjunto *C)
{
  lista *c1, *c2, *c3, *aux;

  crearcjto(C);
  c3 = C->cabecera;
  c1 = A.cabecera->sig; c2 = B.cabecera->sig;
  while (c1 != A.centinela && c2 != B.centinela) {
    if (c1->elem != c2->elem) {
      aux = (lista *) malloc(sizeof(lista));
	  if (c1->elem < c2->elem) { aux->elem = c1->elem; c1 = c1->sig; }
	  else { aux->elem = c2->elem; c2 = c2->sig; }
	  
	  aux->sig = C->centinela;
	  c3->sig = aux; c3 = aux;
	  C->cardinal++;
	}
    else {
      c1 = c1->sig;
      c2 = c2->sig;
    }
  }
  /* copia los elementos restantes si los hubiera */
  if (c1 != A.centinela) {
	while (c1 != A.centinela) {
	  aux = (lista *) malloc(sizeof(lista));
	  aux->elem = c1->elem;
	  aux->sig = C->centinela;
	  c3->sig = aux; c3 = aux;
	  C->cardinal++;
	  c1 = c1->sig;
	}
  }
  else if (c2 != B.centinela) {
	while (c2 != B.centinela) {
	  aux = (lista *) malloc(sizeof(lista));
	  aux->elem = c2->elem;
	  aux->sig = C->centinela;
	  c3->sig = aux; c3 = aux;
	  C->cardinal++;
	  c2 = c2->sig;
	}
  }
}

- Subconjuntos:

Determinar si un conjunto A es subconjunto de B se reduce a comprobar si todo elemento de A es elemento de B. Se devuelve True si A es subconjunto de B. Observar que si (c1->elem < c2->elem) entonces A ya no puede ser subconjunto de B, pues implica que dicho elemento no está en B, ya que c2 representa al menor de los elementos restantes del conjunto. Por último, observar la última condición: return (essub && c1 == A.centinela);. Es decir, quedan elementos de A que no han sido recorridos, pero B ya está totalmente recorrido, luego A no es subconjunto de B. Si se da el caso de que essub = true y c1 != A.centinela entonces se puede devolver un tercer valor que indique que B es subconjunto de A.

int subconjunto(tconjunto A, tconjunto B)
{
  int essub = 1;
  lista *c1, *c2;
  
  c1 = A.cabecera->sig; c2 = B.cabecera->sig;
  while (c1 != A.centinela && c2 != B.centinela && essub) {
	if (c1->elem < c2->elem)
	  essub = 0;
	else if (c1->elem > c2->elem)
	  c2 = c2->sig;	  
	else {
	  c1 = c1->sig;
	  c2 = c2->sig;
	}
  }
  return (essub && c1 == A.centinela);
}

- Igualdad de conjuntos:

Un conjunto A es igual a otro B si ambos tienen los mismos elementos. Se devuelve True si A es igual a B. Se comprueba primero el cardinal de ambos conjuntos.

int iguales(tconjunto A, tconjunto B)
{
  int igual;
  lista *c1, *c2;

  igual = A.cardinal == B.cardinal;

  c1 = A.cabecera->sig; c2 = B.cabecera->sig;
  while (c1 != A.centinela && c2 != B.centinela && igual) {
    if (c1->elem != c2->elem)
	  igual = 0;
    c1 = c1->sig;
	c2 = c2->sig;
  }
  return (igual);
}

Programa de prueba:

int main(void)
{
  tconjunto A, B, C, p1, p2, p3, p4, p5, p6;

  crearcjto(&A);
  crearcjto(&B);
  crearcjto(&C);

  /* A = {2,3,5}
     B = {1,2,3,4,5}
     C=  {3,4,6}
  */
  insertar(&A, 2); insertar(&A, 3); insertar(&A, 5);
  insertar(&B, 1); insertar(&B, 2); insertar(&B, 3); insertar(&B, 4); insertar(&B, 5);
  insertar(&C, 3); insertar(&C, 4); insertar(&C, 6);


  if (pertenece(A, 5)) printf("5 pertenece a A");
  if (!pertenece(B, 6)) printf("\n6 no pertenece a B");

  /* p1 = {2,3,4,5,6} */
  unioncjto(A,C,&p1);  
  
  /* p2 = {3} */
  interseccion(A,C,&p2);

  /* p3 = {1,4} */
  diferencia(B,A,&p3);

  /* p4 = p6 = {2,4,5,6}, p5 = vacío */
  difsim(C,A,&p4);
  difsim(A,C,&p6);
  difsim(B,B,&p5);

  if (iguales(p4,p6)) printf("\np4 = p6");
  if (subconjunto(B,B)) printf("\nB es subconjunto de B");
  if (!subconjunto(B,C)) printf("\nB no es subconjunto de C");
  if (subconjunto(A,B)) printf("\nA es subconjunto de B");
  if (subconjunto(p5, A)) printf("\np5 es subconjunto de A");


  return 0;
}

Conclusiones

Esta implementación tampoco limita el rango de representación de los elementos del conjunto, y por supuesto tampoco limita el tipo de datos, siempre y cuando se pueda deducir cuando un elemento es igual a otro o no.

Dado un conjunto A y B, las operaciones de inserción, borrado y pertenencia se ejecutan en un tiempo de O(|A|). Las operaciones de unión, intersección, diferencia, diferencia simétrica, subconjunto e igualdad se ejecutan en un tiempo de O(|A|+|B|).

El espacio que ocupa un conjunto es de O(|A|), siendo |A| el cardinal del conjunto A. Por supuesto es proporcional al tamaño del conjunto implementado mediante array, multiplicado por una constante debido al espacio ocupado por los punteros.