C - Cómo implementar Establecer estructura de datos?

Question

¿Hay alguna manera complicada de implementar una estructura de datos establecida (una colección de valores únicos) en C? Todos los elementos en un conjunto serán del mismo tipo y hay una gran memoria RAM.

Como sé, para los enteros se puede hacer realmente rápido 'n'easy usando matrices de índice indexado. Pero me gustaría tener un tipo de datos Set muy general. Y sería bueno si un conjunto pudiera incluirse a sí mismo.

Answer 1

Hay múltiples formas de implementar conjunto (y el mapa) funcionalidad, por ejemplo:

• enfoque basado en el árbol (recorrido ordenado)
• enfoque basado en hash (recorrido no ordenado)

Desde ha mencionado las matrices indexadas en valores, probemos el enfoque basado en hash que se construye naturalmente en la parte superior del valor -indexed array technique.

Tenga cuidado con el advantages and disadvantages de enfoques basados ​​en hash vs. árbol.

se puede diseñar una (un caso especial de hash-tables) de hash-setde punteros a hashablePOD s, con chaining, internamente representa como una matriz de tamaño fijo de cubos de hashables, donde:

• todos hashables en un cubo tienen el mismo valor hash
• un cubo puede ser implementado como una dynamic array or linked list of hashables
• un hashable 's valor de hash se utiliza para indexar en la matriz de cubos (matriz indexada-hash-value)
• uno o más de los hashables contenida en el hash-conjunto podría ser (un puntero a) otro hash-set, o incluso al hash-set en sí mismo (es decir, auto-inclusión es posible)

Con grandes cantidades de memoria a su disposición, puede cambiar el tamaño de su arsenal de cubos con generosidad y, en combinación con un buen método de hash, reducir drásticamente la probabilidad de collision, logrando prácticamente rendimiento en tiempo constante.

Usted tendría que poner en práctica:

• la hash function para el tipo que se algoritmo hash
• una función de la igualdad para el tipo que se utiliza para probar si dos hashables son iguales o no
• el hash-set contains/insert/remove funcionalidad.

También puede usar open addressing como alternativa al mantenimiento y administración de depósitos.

Answer 2

Los juegos se implementan generalmente como una variedad de un binary tree. Red black trees tienen un buen rendimiento en el peor de los casos.

También se pueden usar para crear un map para permitir búsquedas de clave/valor.

Este enfoque requiere algún tipo de orden sobre los elementos del conjunto y los valores clave en un mapa.

No estoy seguro de cómo administraría un conjunto que posiblemente podría contener árboles binarios si limita la membresía establecida a tipos bien definidos en C ... la comparación entre tales construcciones podría ser problemática. Sin embargo, puedes hacerlo con bastante facilidad en C++.

Answer 3

Si la cantidad máxima de elementos en el conjunto (la cardinalidad del tipo de datos subyacente) es lo suficientemente pequeña, quizás desee considerar el uso de una matriz simple antigua de bits (o como los llame en su idioma favorito).

Luego tiene una simple comprobación de membresía: bit n es 1 si el elemento n está en el conjunto. Incluso podría contar miembros 'ordinarios' de 1, y solo hacer que el bit 0 sea igual a 1 si el conjunto se contiene a sí mismo. Este enfoque probablemente requerirá algún tipo de otra estructura de datos (o función) para traducir desde el tipo de datos miembro a la posición en la matriz de bits (y viceversa), pero realiza operaciones básicas (unión, intersección, membresía) prueba, diferencia, inserción, eliminación, compelment) muy, muy fácil. Y solo es adecuado para conjuntos relativamente pequeños, no querría usarlo para conjuntos de enteros de 32 bits, supongo.

Answer 4

La forma de obtener genericidad en C es por void *, por lo tanto, va a utilizar punteros de todos modos, y los punteros a diferentes objetos son únicos. Esto significa que necesita un mapa hash o árbol binario que contenga punteros, y esto funcionará para todos los objetos de datos.

El inconveniente de esto es que no puede introducir valores de forma independiente. No puede tener un conjunto que contenga el valor 5; tiene que asignar 5 a una variable, lo que significa que no coincidirá con un 5 al azar. Puede ingresarlo como (void *) 5, y para fines prácticos es probable que funcione con enteros pequeños, pero si sus enteros pueden entrar en tamaños suficientemente grandes para competir con los indicadores esto tiene una probabilidad muy pequeña de fallar.

Tampoco funciona con valores de cadena. Dado char a[] = "Hello, World!"; char b[] = "Hello, World!";, un conjunto de punteros encontraría que a y b son diferentes. Es probable que desee ajustar los valores, pero si le preocupan las colisiones hash, debe guardar la cadena en el conjunto y hacer un strncmp() para comparar la cadena almacenada con la cadena de sondeo.

(Hay problemas similares con números de punto flotante, pero tratando de representar los números de punto flotante en juegos es una mala idea en primer lugar.)

Por lo tanto, usted probablemente querrá un valor etiquetado, uno etiqueta para cualquier tipo de objeto, uno para el valor entero, y uno para el valor de cadena, y posiblemente más para diferentes tipos de valores. Es complicado, pero factible.