Datestructuras
Esta biblioteca proporciona implementaciones de algoritmos clásicos y datos de datos.
Organización
El proyecto se divide en dos paquetes, algoritmos y estructura. El paquete de algoritmos contiene implementaciones de algoritmos en su mayoría independientes, mientras que el paquete de estructura contiene estructuras de datos y algoritmos que operan exclusivamente en ellos.
Algoritmos
Aquí hay una lista de algoritmos en el paquete de algoritmos:
En binarySearch.py:
- Birtura binaria estándar: la búsqueda binaria estándar. https://en.wikipedia.org/wiki/binary_search_algorithm
- Primera búsqueda Binary Search: la búsqueda binaria estándar, excepto que encuentra el primer elemento que coincide con la clave de búsqueda.
En Expression.py:
Algoritmo de patio de derivación: algoritmo de Dijkstra para convertir Infix en notación postfix. https://en.wikipedia.org/wiki/shunting-yard_algorithm
El algoritmo de dos pilas de Dijkstra: algoritmo de Dijkstra para interpretar expresiones postfix.
En Smemessolver.py:
- A* Algoritmo: un algoritmo de búsqueda de ruta. https://en.wikipedia.org/wiki/a*_search_algorithm
- A* Algoritmo adaptado al problema de 8-Puzzle: https://www.cs.princeton.edu/courses/archive/spr10/cos226/assignments/8puzzzle.html
En sort.py:
- Orden de selección: https://en.wikipedia.org/wiki/selection_sort
- Sorteo de inserción: https://en.wikipedia.org/wiki/insertion_sort
- Shell sort: https://en.wikipedia.org/wiki/shellsort
- Variaciones de la clasificación de fusión: https://en.wikipedia.org/wiki/merge_sort
- Recuento de inversión: Cuente el número de inversiones con clasificación de fusión modificada
- Variaciones de clasificación rápida: incluyendo clasificación rápida estándar, clasificación rápida de 3 vías y clasificación rápida de muestreo. https://en.wikipedia.org/wiki/quicksort
- Sort de montón: https://en.wikipedia.org/wiki/heapsort
- Seleccione KTH: Seleccione el elemento KTH en orden. Basado en la partición de clasificación rápida.
Estructura
Aquí hay una lista de estructuras de datos implementadas y algoritmos que opera en ellas:
En LinkedList.py:
- Lista vinculada: https://en.wikipedia.org/wiki/linked_list
- Pila vinculada: pila implementada con una lista vinculada.
- Cola vinculada: cola implementada con una lista vinculada.
En unionfind.py: https://en.wikipedia.org/wiki/disjoint-set_data_structure
- Findir rápido: conjunto disjunto implementado con una matriz similar a la estructura de datos. O (1) encontrar.
- Unión rápida: conjunto disjunto implementado con el árbol de enlace principal.
- Unión rápida equilibrada: conjunto disjunto implementado con el árbol de enlace parental y el equilibrio en la unión. O (log (n)) eficiencia para Find y Union.
- Unión rápida de compresión de ruta: conjunto disjunto implementado con el árbol de enlace principal y aumentado con compresión de ruta.
- Compresión de ruta equilibrada Unión rápida: conjunto disjunto implementado con el árbol de enlace principal con el equilibrio y la compresión de la ruta. casi amortizada o (1) eficiencia en el hallazgo y la unión.
En symboltable.py:
- Árbol de búsqueda binaria: BST estándar. https://en.wikipedia.org/wiki/binary_search_tree
- Árbol rojo y negro: BST equilibrado usando representación 2-3. https://en.wikipedia.org/wiki/red%E2%80%93black_tree
- Tabla hash separada: tabla hash que resuelve la colisión al encadenarlas en una lista. https://en.wikipedia.org/wiki/hash_table#separate_chaining
- Tabla de hash abierta: tabla hash que resuelve colisión con sondeo lineal. https://en.wikipedia.org/wiki/hash_table#open_addressing
En Heap.py:
- Monado binario: una implementación de una cola prioritaria con montón binario. https://en.wikipedia.org/wiki/binary_heap
En Graph.py:
- Gráfico no dirigido: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#undirected_graph
- Gráfico dirigido: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#directed_graph
- Gráfico ponderado no dirigido: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#weweet_graph
- Gráfico ponderado dirigido: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#weweet_graph
- Primera búsqueda de profundidad: https://en.wikipedia.org/wiki/depth-first_search
- Amplth Primera búsqueda: https://en.wikipedia.org/wiki/breadth-first_search
- Componentes conectados no dirigidos: https://en.wikipedia.org/wiki/Component_(graph_theory)
- Detección del ciclo no dirigida: https://en.wikipedia.org/wiki/cycle_(graph_theory)
- Detección del ciclo dirigido: https://en.wikipedia.org/wiki/cycle_(graph_theory)
- Detección de Biparte: https://en.wikipedia.org/wiki/bipartite_graph
- Ordenado topológico: https://en.wikipedia.org/wiki/topological_sorting
- Componentes fuertemente conectados (algoritmo de Kosaraju): https://en.wikipedia.org/wiki/kosaraju%27s_algorithm
- Algoritmo de Prim (perezoso): https://en.wikipedia.org/wiki/prim%27s_algorithm
- Algoritmo de Kruskal: https://en.wikipedia.org/wiki/kruskal%27s_algorithm
- La ruta más corta de Dijkstra: https://en.wikipedia.org/wiki/dijkstra%27S_Algorithm
- Camino más corto acíclico topológico: https://en.wikipedia.org/wiki/topological_sorting#application_to_shortest_path_finding
- Bellman Ford más corto Path: https://en.wikipedia.org/wiki/bellman%E2%80%93ford_algorithm
Uso
Todos los componentes se prueban. Sin embargo, no se prueban con rigurosos estándares de producción. Las estructuras de datos, como la lista vinculada y los simbolables, tienen interfaces como la lista y el diccionario estándar de Python.
