Estruturas de dados e algoritmos
Estruturas de dados e algoritmos (DSA) é um dos tópicos mais importantes da ciência da computação em que todo aluno de CS deve ser proficiente e até mesmo os alunos que não são do CS devem ter uma compreensão básica disso. Dizem que o DSA é como pão e manteiga, necessidade de CS. Este repositório é feito para os alunos (como eu?) Que estão ansiosos para aprender e querem implementar estruturas e algoritmos de dados.
Por que ir/Golang e não C, C ++ ou Java?
Eu não discordaria que C, C ++ ou Java não seriam um ótimo idioma para implementar o DSA, pois é preciso cuidar de muitas coisas enquanto escrevia o código, como alocações de memória e desalocassas adequadas e, ao fazê -lo, aprende muito.
No entanto, a razão pela qual ir também seria uma boa linguagem para implementar o DSA é que ele não tem muita mágica. Não há sobrecarga do operador, portanto, não há como ocultar a complexidade extra. Uma operação de índice é O (1), um loop é O (n) - sempre. Não há genéricos, então muitas abstrações e ajudantes extras não existem, o que é realmente ótimo. Não há preguiça ou outra magia acionada pelo compilador que possa alterar significativamente o tempo de execução de seus algoritmos. E GO possui ponteiro e primitivos de baixo nível para fatias, o que significa que é aparente quando os dados são embalados ou quando os dados têm uma indiretção extra. Em resumo : vá tornar a execução algorítmica real óbvia do código, o que é uma coisa boa de aprender algoritmos.
Conclusão : O GO também seria um bom idioma para começar a implementar estruturas e algoritmos de dados.
Instruções
- Para começar, certifique -se de que você tenha a linguagem de programação instalada no seu computador. Siga como instalar instruções do Golang Download Instruções.
- Depois que Go estiver instalado em sua máquina, basta clonar ou baixar este repositório.
- Agora,
cd <folder-name> na pasta onde o arquivo que você deseja executar está localizado. - Agora corra
go run . .
Exemplo
Vamos supor que você deseja executar arquivos localizados em graphs/directed_unweighted e, em seguida, a sintaxe para executá -lo seria:
cd graphs/directed_unweighted/
go run .
Nomes de pastas
- Algoritmos -
- 01KNAPSACK_DP - 0-1 KAPSACK PROBLEMA usando programação dinâmica
- a_star -
- 8_Puzzle - 8 problemas de quebra -cabeça usando um * algoritmo
- dirigido_graph - A * algoritmo para gráfico direcionado
- UND -INDECED_GRAPH - A * algoritmo para gráfico não direcionado
- Activity_selection_GP - Seleção de atividades usando programação gananciosa
- Assembly_line_scheduling - Algoritmo de agendamento de linha de montagem usando programação dinâmica
- binário_refleted_gray_codes - códigos cinzentos refletidos binários
- CHOSTest_pair_problem -
- CPP_BRUTE_FORCE - Problema de par mais próximo usando a técnica de força bruta
- CPP_Divide_Conquer - Problema de par mais próximo usando a divisão e conquista Techinque
- Combinações -
- with_r - com repetição de elementos
- sem_r - sem repetição de elementos
- Convex_hull -
- CH_BRUTE_FORCE - Algoritmo convexo do casco usando a técnica de força bruta
- CH_DIVIDE_CONQUER - Algoritmo convexo do casco usando a técnica de divisão e conquista
- Expression_Conversions -
- infix_postfix - Infix para pós -fix Conversão
- Infix_prefix - Infix para prefixar a conversão
- Postfix_infix - Postfix para Conversão de Infix
- Postfix_prefix - Postfix para conversão de prefixo
- prefix_infix - prefixo para conversão de infix
- prefix_postfix - prefixo para pós -fix Conversão
- GCD - Maior divisor comum (algoritmo de Euclides)
- Gráficos -
- articulação_point_detection - Detectando pontos de articulação em um gráfico não direcionado
- Bellman_ford - Algoritmo Bellman Ford
- Bridge_detection - Detecção de ponte/detecção de borda de corte em um gráfico não direcionado
- Dijkstra - Algoritmo de Dijkstra
- Floyd_warshall - Algoritmo Floyd Warshall (todos os pontos mais curtos)
- Kruskals - Algoritmo de Kruskal (encontrando a árvore de abrangência mínima MST usando a abordagem gananciosa)
- Prims - Algoritmo de Prim (Encontrando MST mínimo de abordagem usando a abordagem gananciosa)
- topological_sort - tipo topológico
- Traversals -
- CD_DIRECTED_GRAPH_TRAVERSALS - Detecção de ciclo em gráficos direcionados usando técnicas de Traversals
- CD_UNDIRECTED_GRAPH_TRAVERSALS - Detecção de ciclo em gráficos não direcionados usando técnicas de Traversals
- TSP -
- tsp_dynamic -
- Direcida_graph - TSP (Problema de Vendas Viajantes) usando abordagem dinâmica para gráfico direcionado
- Und -directed_graph - TSP (Problema de Vendas Viajantes) usando abordagem dinâmica para gráfico não direcionado
- tsp_naive -
- Direcida_graph - TSP (Problema de Vendas Viajantes) usando abordagem ingênua para gráfico direcionado
- Und -directed_graph - TSP (Problema de Vendas Viajantes) usando abordagem ingênua para gráfico não direcionado
- Union_find - Conjuntos de Localização / Disjunta da União (detectando ciclos em um gráfico não direcionado)
- Huffman_codes - Códigos Huffman (gerando códigos de Huffman)
- Job_scheduling_GP - Algoritmo de agendamento de tarefas usando programação gananciosa
- LCM - múltiplo menos comum (usando o algoritmo do GCD Euclides)
- LCS - subsequência comum mais longa
- iterative_dp - subseqüência comum mais longa usando programação dinâmica (versão iterativa)
- LO_PERMUTAÇÕES - Permutações de ordem lexicográfica
- Longest_palindrome_substring -
- BRUTE_FORCE - Substring de palíndroma mais longa usando a técnica de força bruta
- Manchers - Substring Palíndrome mais longa usando o algoritmo de Mancher
- Making_change_dp - fazendo problemas de mudança usando a programação dinâmica
- Order_statistics - Encontrando Kth Menor/Maior Elemento (Estatística de Ordem)
- ingening_apaproach - abordagem ingênua usando max heap - o (k + (nk)*log (k))
- Quick_Select - Selecione Quick (Classificação rápida) - O (n^2), θ (nLogn)
- pior_case_linear_time - pior caso estatísticas de ordem linear - o (n)
- Power_set - conjunto de energia (conjunto de subconjuntos)
- Pesquisando -
- Binário_search - Pesquisa binária - O (log n)
- Interpolation_search - Pesquisa de interpolação - O (n)
- linear_search - pesquisa linear - o (n)
- ternário_search - pesquisa ternária - o (log 3 n)
- sieve_of_eratóstenes - peneira de eratóstenes (primos consecutivos que não excedem n)
- classificação -
- binário_insertion_sort - Criação de inserção binária - O (n 2 )
- Bubble_sort - Bubble Sort - O (n 2 )
- Bucket_sort - Corrente do balde - O (n 2 )
- conting_sort - contagem de classificação - o (n + k)
- HEAP_SORT - CORREÇÃO HEAP - O (nlog (n)
- Inserção_sort - Classificação de inserção - O (n 2 )
- Merge_sort - Merge Sort - O (nlog (n))
- Quick_sort - Classificação rápida - θ (nlog (n))
- radix_sort - Radix Sort - O (n+k)
- Seleção_sort - Centro de seleção - (O (n 2 ))
- shell_sort - Classificação de shell - o (n)
- String_matching -
- Boyer_moore - Algoritmo Boyer Moore
- Horspool - Algoritmo de Boyer Moore Horspool
- knuth_morris_pratt - Knuth Morris Pratt
- inen_pattern_matching - correspondência de padrão ingênuo
- Rabin_karp - Rabin Karp
- Toh - Torre de Hanói
- Gráficos -
- Directed_unweighted - Gráfico não ponderado direcionado
- Directed_weighted - Gráfico ponderado direcionado
- não direcionado_unweighted - gráfico não polido não direcionado
- não direcionado_elefado - gráfico pesado não direcionado
- pilhas -
- max_binary_heap - heap binário máximo
- min_binary_heap - Min binário heap
- Linked_lists -
- Circular_doubly_ll - Lista duplamente vinculada circular
- Circular_ll - Lista ligada circular
- Doubly_ll - Lista duplamente vinculada
- pres_rev_single_ll - preservar a ordem durante a inserção em uma única lista vinculada e reversão da lista vinculada
- single_ll - lista vinculada única
- filas -
- CDQUEUE - Fila circular dupla
- Cqueue - fila circular
- Dqueue - fila de ponta dupla
- Priority_queue - fila de prioridade com o uso de miço min
- simples_queue - fila simples
- Stack - Stack
- Árvores -
- AVL_TREE_USING_LL - Árvore AVL usando a lista vinculada com Traversals de ordem BFS e DFS (PRE, IN, POST).
- BST_USING_ARR - Árvore de pesquisa binária usando o Array com BFS e DFS (PRAVERSALES DE ORDEM DO POSTO DA, PRE, IN, POST).
- BST_USING_LL - Árvore de pesquisa binária usando a lista vinculada com Traversals de pedidos BFS e DFS (Pre, IN, Post).
- Simple_bt_using_arr - Árvore binária simples usando a matriz com travessias de ordem BFS e DFS (pré, in, post).
- Simple_bt_using_ll - Árvore binária simples usando a lista vinculada com travessias de ordem BFS e DFS (pré, in, post).
Nota : O ponteiro ": Point_Left:" Indica implementação incompleta e está na lista de TODO.
Contribuição
Esse repositório é para aprender a implementar estruturas e algoritmos de dados e, como as contribuições de outras pessoas não me ensinam como implementá -lo sozinho, não aceitarei solicitações de tração. No entanto, sinta -se à vontade para gastar este repositório e modificar o código para jogar em torno de várias estruturas e algoritmos de dados. Além disso, enquanto brincava ao redor do código, se você achar algo incomum ou errado na implementação, eu apreciaria se você criar um problema no mesmo.
Licença
Este repositório é liberado sob a licença do MIT. Em suma, isso significa que você é livre para usar este software em projetos pessoais, de código aberto ou comerciais. A atribuição é opcional, mas apreciada.
HAPPY CODING
HAPPY LEARNING
