Data Structures and Algorithms in C Descarga: Data Structures and Algorithms in C

Data Structures and Algorithms in C

Otro código fuente

1.0.0

Descargar

Estucturas de datos y algoritmos implementados en C

Aquí encontrará algunas estructuras de datos y algoritmos implementados en C. Estos algoritmos se basan principalmente en la introducción del libro a los algoritmos de Thomas H. Cormen .

Instrucciones

Cada módulo consta de al menos un archivo de encabezado (.h) y un archivo fuente que contiene el Código Corpus (.C). Para usar uno de estos módulos, le sugiero que siga estos pasos:

Encuentre la estructura de datos o algoritmo que necesita de /modules
Descargue el directorio del módulo ( /modules/List Ej List.c
Vaya a /include/ carpeta, busque el archivo de encabezado (.h) que desee (por ejemplo, List.h ) y descárguelo.
❕ Aún no está terminado ❕, ahora vaya y consulte el archivo de encabezado (.h) y descargue lo que está incluido (comandos #include "foo.h" ). La mayoría de los módulos incluyen, por ejemplo, HashFunctions o Comparators o incluso otras estructuras de datos. Detente lo que se necesita y descargue todos los archivos.
Arregle las rutas al #include "foo.h" si cambia la estructura de la carpeta actual.
Todo está listo, ¡espero que te haya ayudado!

Compilar y ejecución

Si clona toda la carpeta, puede ejecutar:

make : eso complica cada módulo
make run-tests : que compila cada módulo y ejecuta todas las pruebas
make valgind-tests : que compila cada módulo y ejecuta todas las pruebas usando Valgrind

Apéndice

Estructura de datos	Definición
Filtro de floración	El filtro Bloom es una estructura de datos probabilísticas de eficiencia espacial, concebida por Burton Howard Bloom en 1970, que se usa para probar si un elemento es un miembro de un conjunto. Las coincidencias falsas positivas son posibles, pero los falsos negativos no son, en otras palabras, una consulta devuelve "posiblemente en el set" o "definitivamente no en el set". Los elementos se pueden agregar al conjunto, pero no se eliminarán (aunque esto se puede abordar con la variante de filtro de floración de conteo); Cuantos más elementos se agregan, mayor será la probabilidad de falsos positivos.
Árbol rojo-negro	El árbol rojo-negro es una especie de árbol de búsqueda binario de equilibrio. Cada nodo almacena un bit adicional que representa "color" ("rojo" o "negro"), se usa para garantizar que el árbol permanezca equilibrado durante las inserciones y deleciones. Cuando se modifica el árbol, el nuevo árbol se reorganiza y se "repinte" para restaurar las propiedades de coloración que limitan cuán desequilibrado puede volverse el árbol en el peor de los casos. Las propiedades están diseñadas de tal manera que este reorganización y el recolor se pueden realizar de manera eficiente. El volver a equilibrar no es perfecto, pero garantiza buscar en el tiempo O (logn) , donde n es el número de nodos del árbol. Las operaciones de inserción y deleción, junto con el reordenamiento y la recolación del árbol, también se realizan en el tiempo O (logn) .
Lista vinculada	Linked List es una colección lineal de elementos de datos cuyo orden no está dado por su ubicación física en la memoria. En cambio, cada elemento apunta al siguiente. Es una estructura de datos que consiste en una colección de nodos que en conjunto representan una secuencia.
Cola	La cola de prioridad es un tipo de datos abstractos similar a una cola regular o una estructura de datos de pila en la que cada elemento también tiene una "prioridad" asociada. En una cola de prioridad, se sirve un elemento con alta prioridad ante un elemento con baja prioridad.
Hashtable con lista	Implementación genérica de un hashtable muy simple con claves y cadenas. No se proporciona reconstrucción.
Hashtable con árbol rojo-negro	Consistía en una tabla, en la que cada fila tiene un puntero a un árbol rojo-negro de esta manera, obtenemos las mejores complejidades anteriores y al mismo tiempo evitando demasiadas colisiones.
Hashtable con cubos a árbol rojo-negro	Hashtable consistía en cubos de punteros a árboles negros rojos
Maxheap	Un máximo-helado es un árbol binario completo en el que el valor en cada nodo interno es mayor o igual a los valores en los hijos de ese nodo. Mapear los elementos de un montón en una matriz es trivial: si un nodo se almacena un índice K, entonces su hijo izquierdo se almacena en el índice 2K+1 y su hijo derecho en el índice 2K+2.
Desarticulación	La estructura de datos del conjunto de disjunto, también llamada estructura de datos de la Unión o el conjunto de fusiones de fusión, es una estructura de datos que almacena una recopilación de conjuntos de disjuntos (no superpuestas). De manera equivalente, almacena una partición de un conjunto en subconjuntos disjuntos. Proporciona operaciones para agregar nuevos conjuntos, fusionar conjuntos (reemplazándolos por su sindicato) y encontrar un miembro representativo de un conjunto. La última operación permite averiguar de manera eficiente si dos elementos están en los mismos o diferentes conjuntos.
Programador de trabajo con hilos	Programador de trabajo de múltiples subprocesos con UNIX PTHREADS.

Algoritmo	Definición
Montaña	HeepSort es un algoritmo de clasificación basado en comparación. Se puede considerar que HeapSort es un tipo de selección mejorado: como el tipo de selección, Heapsort divide su entrada en una región ordenada y sin clasificar, y encoge iterativamente la región sin clasificar al extraer el elemento más grande de él e insertarla en la región clasificada. A diferencia del orden de selección, Heapsort no pierde el tiempo con un escaneo de tiempo lineal de la región no organizada; Más bien, Heap Sort mantiene la región sin clasificar en una estructura de datos de Heap para encontrar más rápidamente el elemento más grande en cada paso.
Acelerar	Quicksort es un algoritmo de clasificación eficiente. Desarrollado por el científico informático británico Tony Hoare en 1959 y publicado en 1961, sigue siendo un algoritmo de uso común para la clasificación. Cuando se implementa bien, puede ser algo más rápido que la clasificación de fusiones y aproximadamente dos o tres veces más rápido que Heapsort.

Algoritmo

Definición

Montaña

HeepSort es un algoritmo de clasificación basado en comparación. Se puede considerar que HeapSort es un tipo de selección mejorado: como el tipo de selección, Heapsort divide su entrada en una región ordenada y sin clasificar, y encoge iterativamente la región sin clasificar al extraer el elemento más grande de él e insertarla en la región clasificada. A diferencia del orden de selección, Heapsort no pierde el tiempo con un escaneo de tiempo lineal de la región no organizada; Más bien, Heap Sort mantiene la región sin clasificar en una estructura de datos de Heap para encontrar más rápidamente el elemento más grande en cada paso.

Acelerar

Quicksort es un algoritmo de clasificación eficiente. Desarrollado por el científico informático británico Tony Hoare en 1959 y publicado en 1961, sigue siendo un algoritmo de uso común para la clasificación. Cuando se implementa bien, puede ser algo más rápido que la clasificación de fusiones y aproximadamente dos o tres veces más rápido que Heapsort.