Estructuras de datos y algoritmos
Las estructuras de datos y los algoritmos (DSA) es uno de los temas más importantes en ciencias de la computación en el que cada estudiante de CS debe ser competente e incluso los estudiantes que no sean de CS deben tener una comprensión básica de ello. Se dice que DSA es como pan y mantequilla, necesidad de CS. Este repositorio está hecho para esos estudiantes (¿como yo?) Que están ansiosos por aprender y quieren implementar estructuras y algoritmos de datos.
¿Por qué Go/Golang y no C, C ++ o Java?
No estaría en desacuerdo con que C, C ++ o Java no serían un gran idioma para implementar DSA, ya que uno tiene que cuidar muchas cosas mientras escribe el código, como las asignaciones de memoria y las ofertas adecuadas, y al hacerlo se aprende mucho.
Sin embargo, la razón por la cual GO también sería un buen lenguaje para implementar DSA es que carece de mucha magia. No hay sobrecarga de operadores, por lo que no hay forma de ocultar una complejidad adicional. Una operación de índice es O (1), un bucle es o (n) - siempre. No hay genéricos, por lo que muchas abstracciones y ayudantes adicionales no existen, lo que en realidad es bastante bueno. No hay pereza u otra magia impulsada por el compilador que pueda alterar significativamente el tiempo de ejecución de sus algoritmos. Y GO tiene puntero y primitivas de bajo nivel para rodajas, lo que significa que es evidente cuando los datos están empaquetados o cuando los datos tienen una indirección adicional. En resumen : haga que la ejecución algorítmica real sea obvia del código, que es algo bueno para aprender algoritmos.
Conclusión : GO también sería un buen lenguaje para comenzar a implementar estructuras de datos y algoritmos.
Instrucciones
- Para comenzar, asegúrese de tener el lenguaje de programación IR instalado en su computadora. Siga cómo instalar instrucciones de las instrucciones de descarga de Golang.
- Una vez que GO se instale en su máquina, simplemente clone o descargue este repositorio.
- Ahora
cd <folder-name> en la carpeta donde se encuentra el archivo que desea ejecutar. - Ahora corre,
go run . .
Ejemplo
Supongamos que desea ejecutar archivos ubicados en el directorio graphs/directed_unweighted que la sintaxis para ejecutarlo sería:
cd graphs/directed_unweighted/
go run .
Nombres de carpetas
- Algoritmos -
- 01knapsack_dp - 0-1 problema de mochila usando programación dinámica
- A_star -
- 8_Puzzle - 8 Problema de rompecabezas usando un algoritmo *
- Directed_Graph - A * Algoritmo para el gráfico dirigido
- no dirigido_graph - A * algoritmo para un gráfico no dirigido
- Activity_Selection_GP - Selección de actividad utilizando programación codiciosa
- Assembly_line_scheduling - Algoritmo de programación de línea de ensamblaje utilizando programación dinámica
- binary_reflected_gray_codes - códigos grises reflejados binarios
- Closest_pair_problem -
- cpp_brute_force - Problema de par más cercano utilizando la técnica de fuerza bruta
- CPP_DIVIDE_CONQUER - Problema de par más cercano usando Divide and Conquer Techinque
- Combinaciones -
- with_r - con repetición de elementos
- sin_r - sin repetición de elementos
- Convex_hull -
- CH_BRUTE_FORCE - Algoritmo de casco convexo utilizando la técnica de fuerza bruta
- CH_DIVIDE_CONQUER - Algoritmo de casco convexo utilizando la técnica de división y conquistar
- Expression_Conversions -
- Infix_Postfix - Conversión de Infix a Postfix
- Infix_prefix - Infix to prefijo la conversión
- Postfix_infix - Postfix to Infix Conversion
- Postfix_prefix - Postfix a prefijo la conversión
- prefix_infix - conversión de prefijo a infijo
- prefix_postfix - conversión de prefijo a postfix
- GCD : el mayor divisor común (algoritmo de Euclides)
- Gráficos -
- articulation_point_detection - detectar puntos de articulación en un gráfico no dirigido
- Bellman_ford - Algoritmo de Bellman Ford
- Bridge_Detection : detección de puentes/detección de borde de corte en un gráfico no dirigido
- Dijkstra - Algoritmo de Dijkstra
- Floyd_warshall - Algoritmo de Floyd Warshall (todos los puntos más corto Ruta)
- Kruskals - Algoritmo de Kruskal (encontrando mST de árbol de expansión mínimo utilizando un enfoque codicioso)
- Prims - Algoritmo de Prim (encontrar mínimo MST con un enfoque codicioso)
- topological_sort - clasificación topológica
- Traversales -
- CD_DIRECTIVE_GRAPH_TRAVERSALS - Detección de ciclo en gráficos dirigidos utilizando técnicas de recorridos
- CD_UNDIRECTIVE_GRAPH_TRAVERSALS - Detección de ciclo en gráficos no dirigidos utilizando técnicas de recorrido
- TSP -
- Tsp_dynamic -
- Directed_Graph - TSP (problema de vendedor ambulante) utilizando un enfoque dinámico para el gráfico dirigido
- Undirected_Graph - TSP (problema de vendedor ambulante) utilizando un enfoque dinámico para un gráfico no dirigido
- TSP_NAIVE -
- Directed_Graph - TSP (problema de vendedor ambulante) utilizando un enfoque ingenuo para el gráfico dirigido
- Undirected_Graph - TSP (problema de vendedor ambulante) utilizando un enfoque ingenuo para un gráfico no dirigido
- Union_Find - Union Find / Disjunto se establece (detectar ciclos en un gráfico no dirigido)
- Huffman_Codes - Códigos Huffman (generando códigos de Huffman)
- JOB_SCHEDULING_GP - Algoritmo de programación de trabajo usando programación codiciosa
- LCM : múltiplo menos común (usando el algoritmo de GCD Euclid)
- LCS - Subsecuencia común más larga
- ITerative_DP - Subsecuencia común más larga utilizando programación dinámica (versión iterativa)
- LO_PERMUTACIONES - Permutaciones de pedidos lexicográficos
- Longest_palindrome_substring -
- Brute_force - Subcandring de palíndromo más largo utilizando la técnica de fuerza bruta
- Manchers - Subcandromo más largo usando el algoritmo de Mancher
- Making_Change_DP : hacer problemas de cambio usando la programación dinámica
- Order_statistics - Encontrar KTH El elemento más pequeño/más grande (estadísticas de pedido)
- Naive_approach - enfoque ingenuo usando el montón máximo - o (k + (nk)*log (k))
- Quick_select - Quick Select (Sort Quick) - O (N^2), θ (NLogn)
- peor_case_linear_time - estadísticas de pedido de tiempo lineal del peor de los casos - O (n)
- Power_set - Conjunto de potencia (conjunto de subconjuntos)
- Buscando -
- Binary_search - Binary Search - O (log n)
- Interpolation_search - Búsqueda de interpolación - O (N)
- lineal_search - búsqueda lineal - o (n)
- ternary_search - búsqueda ternaria - o (log 3 n)
- Sieve_of_eratosthenes - Sieve of Eratosthenes (primos consecutivos que no exceden n)
- clasificación -
- binary_insertion_sort - sort de inserción binaria - o (n 2 )
- Bubble_sort - Bubble Sort - O (N 2 )
- bucket_sort - sort de cubo - o (n 2 )
- Counting_sort - Sorteo de conteo - O (N + K)
- Heap_sort - Heap Sort - O (nlog (n)
- insertion_sort - sort de inserción - o (n 2 )
- Merge_sort - Merge Sort - O (nlog (n))
- Quick_sort - Sorteo rápido - θ (nlog (n))
- Radix_sort - Radix Sort - O (N+K)
- selection_sort - sort de selección - (o (n 2 ))
- shell_sort - shell sort - о (n)
- String_matching -
- Boyer_moore - Algoritmo de Boyer Moore
- Horspool - Algoritmo de Horspool de Boyer Moore
- knuth_morris_pratt - Knuth Morris Pratt
- naive_pattern_matching - coincidencia de patrones ingenuos
- Rabin_karp - Rabin Karp
- Toh - Torre de Hanoi
- Gráficos -
- Directed_Unweight - Gráfico no ponderado dirigido
- Directed_weuthing - Gráfico ponderado dirigido
- no dirigido_unweight - gráfico no ponderado no dirigido
- no dirigido_weuthing - gráfico ponderado no dirigido
- montones -
- max_binary_heap - montón binario máximo
- min_binary_heap - Min binary montón
- Linked_lists -
- Circular_doubly_ll - lista circular doblemente vinculada
- Circular_ll - Lista de vinculación circular
- Doobly_ll - Lista doblemente vinculada
- Pres_rev_single_ll - Preserve el orden durante la inserción en una sola lista vinculada e invertir una sola lista vinculada
- Single_ll - Lista de un solo vinculado
- colas -
- CdQueue - cola circular doble final
- Cocaue - cola circular
- dreue - cola de doble finalización
- priority_queue - cola prioritaria con el uso de Min Heap
- simple_queue - cola simple
- pila - pila
- árboles -
- AVL_TREE_USING_LL - Árbol AVL usando la lista vinculada con BFS y DFS (pre, in, post) Ordene los recorridos.
- BST_USING_ARR - Árbol de búsqueda binario usando matriz con BFS y DFS (pre, in, post) Traversales de orden.
- BST_USING_LL - Árbol de búsqueda binario usando la lista vinculada con BFS y DFS (pre, in, post) Traversal de orden.
- Simple_BT_USING_ARR - Árbol binario simple usando matriz con BFS y DFS (pre, in, post) Traversal de orden.
- Simple_BT_USING_LL - Árbol binario simple usando una lista vinculada con BFS y DFS (pre, in, post) Ordenar recorridos.
Nota : El puntero ": Point_left:" indica una implementación incompleta y está en la lista de TODO.
Contribución
Este repositorio es para aprender cómo implementar estructuras y algoritmos de datos, y dado que las contribuciones de los demás realmente no me enseñan cómo implementarlo por mí mismo, no aceptaré ninguna solicitud de extracción. Sin embargo, no dude en desembolsar este repositorio y modificar el código para reproducir varias estructuras y algoritmos de datos. Además, mientras juega con el código, si encuentra algo inusual o incorrecto en la implementación, agradecería encarecidamente si crea un problema en el mismo.
Licencia
Este repositorio se publica bajo la licencia MIT. En resumen, esto significa que es libre de usar este software en cualquier proyecto personal, de código abierto o comerciales. La atribución es opcional pero apreciada.
HAPPY CODING
HAPPY LEARNING
