Structures de données et algorithmes
Les structures de données et les algorithmes (DSA) sont l'un des sujets les plus importants en informatique dans lequel chaque étudiant CS doit être compétent et même les étudiants non-CS doivent avoir une compréhension de base de l'informatique. On dit que la DSA est comme le pain et le beurre, la nécessité de CS. Ce référentiel est conçu pour ces étudiants (comme moi?) Qui sont impatients d'apprendre et veulent implémenter des structures de données et des algorithmes.
Pourquoi aller / golang et non c, c ++ ou java?
Je ne serais pas en désaccord que C, C ++ ou Java ne seraient pas un excellent langage pour implémenter la DSA car il faut s'occuper de beaucoup de choses tout en écrivant le code comme les allocations de mémoire et les deralocations appropriées et, ce faisant, l'on apprend beaucoup.
Cependant, la raison pour laquelle GO serait également une bonne langue pour implémenter la DSA est qu'il manque beaucoup de magie. Il n'y a pas de surcharge d'opérateur, donc aucun moyen de masquer une complexité supplémentaire. Une opération d'index est O (1), une boucle est o (n) - toujours. Il n'y a pas de génériques, donc beaucoup d'abstractions et d'aides supplémentaires n'existent pas, ce qui est en fait assez génial. Il n'y a pas de paresse ou autre magie motivée par le compilateur qui pourrait modifier considérablement l'exécution de vos algorithmes. Et Go a un pointeur et des primitives de bas niveau pour les tranches, ce qui signifie qu'elle est apparente lorsque les données sont emballées ou lorsque les données ont une indirection supplémentaire. En bref : allez rendre l'exécution algorithmique réelle évidente à partir du code, ce qui est une bonne chose pour apprendre les algorithmes.
Conclusion : GO serait également une bonne langue pour commencer par la mise en œuvre des structures de données et des algorithmes.
Instructions
- Pour commencer, assurez-vous que le langage de programmation est installé sur votre ordinateur. Suivez comment installer les instructions à partir des instructions de téléchargement de Golang.
- Une fois que GO est installé sur votre machine, il suffit de clone ou de télécharger ce référentiel.
- Maintenant,
cd <folder-name> dans le dossier où se trouve le fichier que vous souhaitez exécuter. - Maintenant, exécutez-
go run . .
Exemple
Supposons que vous souhaitez exécuter des fichiers situés dans graphs/directed_unweighted puis la syntaxe pour l'exécuter serait:
cd graphs/directed_unweighted/
go run .
Noms de dossiers
- Algorithmes -
- 01KNAPSACK_DP - 0-1 Problème de sac à dos Utilisation de la programmation dynamique
- a_star -
- 8_puzzle - 8 Problème de puzzle à l'aide d'un algorithme *
- Directed_graph - A * Algorithme pour le graphique dirigé
- nondirecd_graph - A * Algorithme pour graphique non dirigée
- Activity_selection_gp - Sélection d'activité à l'aide de programmation gourmand
- assembly_line_scheduling - algorithme de planification des lignes de montage utilisant la programmation dynamique
- binary_reflect_gray_codes - codes gris réfléchis binaires
- Closest_pair_problem -
- CPP_BRUE_FORCE - Problème de paire le plus proche en utilisant la technique de force brute
- CPP_DIVIDE_CONQUER - Problème de paire le plus proche à l'aide de Divide et de conquérir Techinque
- combinaisons -
- avec_r - avec répétition d'éléments
- sans_r - sans répétition d'éléments
- convex_hull -
- CH_BRUTE_FORCE - Algorithme convexe de coque en utilisant la technique de force brute
- CH_DIVIDE_CONQUER - Algorithme convexe de la coque en utilisant la technique Divide and Conquer
- expression_conversions -
- infix_postfix - Infixer à la conversion post-fixe
- infix_prefix - Infixer pour préfixer la conversion
- Postfix_infix - Postfix to infixer la conversion
- PostFix_prefix - Postfix to Prefix Conversion
- prefix_infix - préfixe à infixer la conversion
- prefix_postfix - Conversion préfixe de postfix
- GCD - plus grand diviseur commun (algorithme d'Euclid)
- graphiques -
- articulation_point_dection - détection des points d'articulation dans un graphique non dirigé
- Bellman_ford - Algorithme Bellman Ford
- Bridge_dection - détection de pont / détection de bord de coupe dans un graphique non dirigé
- Dijkstra - algorithme de Dijkstra
- FLOYD_WARSHALL - Algorithme Floyd Warshall (chemin le plus court tous les points)
- Kruskals - Algorithme de Kruskal (trouver un arbre couvrant minimum MST en utilisant une approche gourmand)
- Prims - Algorithme de Prim (trouver un minimum Spanning Tree MST en utilisant une approche gourmand)
- Topological_sort - Sort topologique
- Traverses -
- cd_directed_graph_traversals - Détection du cycle dans des graphiques dirigés à l'aide de techniques de traversée
- CD_UNDIRECT_GRAPH_TRAVERSALS - Détection du cycle dans des graphiques non dirigés à l'aide de techniques de traversée
- TSP -
- TSP_DYNAMIC -
- Directed_graph - TSP (Problème du vendeur itinérant) Utilisation d'approche dynamique pour graphique dirigé
- Underected_graph - TSP (Problème du vendeur itinérant) Utilisation d'approche dynamique pour graphique non dirigé
- tsp_naive -
- Directed_graph - TSP (Problème du vendeur itinérant) Utilisation d'approche naïve pour graphique dirigé
- Underected_graph - TSP (Problème du vendeur itinérant) Utilisation d'approche naïve pour graphique non dirigé
- Union_Find - ensembles de recherche / disjoint Union (détection des cycles dans un graphique non dirigé)
- Huffman_codes - Codes Huffman (génération de codes Huffman)
- job_scheduling_gp - Algorithme de planification de l'emploi utilisant la programmation gourmand
- LCM - Multiple le moins commun (en utilisant l'algorithme de GCD Euclid)
- LCS - la plus longue subséquence commune
- iterative_dp - la plus longue subséquence courante utilisant la programmation dynamique (version itérative)
- LO_PERMUTATIONS - Permutations d'ordre lexicographique
- LONGEST_PALINDROME_SUBSTRING -
- Brute_Force - Sous-chaîne Palindrome la plus longue utilisant une technique de force brute
- Manchers - Sous-chaîne Palindrome la plus longue utilisant l'algorithme de Mancher
- Make_change_dp - faire du changement de problème en utilisant la programmation dynamique
- ORDER_STATISTISTIQUE - Trouver le Kth le plus petit / le plus grand élément (statistiques de commande)
- Naive_approach - Approche naïve en utilisant max tas - o (k + (nk) * log (k))
- Quick_Select - Quick Select (Sorme rapide) - O (n ^ 2), θ (nlogn)
- PIRS_CASE_LINEAR_TIME - Pire Cas Statistiques de l'ordre de temps linéaire - O (n)
- Power_Set - Set Power (ensemble de sous-ensembles)
- Recherche -
- Binary_Search - Recherche binaire - O (log n)
- Interpolation_search - Recherche d'interpolation - O (n)
- linear_search - Recherche linéaire - O (n)
- Ternary_Search - Recherche ternaire - O (log 3 n)
- sieve_of_eratosthenes - tamis d'eratosthènes (nombres premiers consécutifs ne dépassent pas n)
- tri -
- binary_insertion_sort - Tri d'insertion binaire - O (n 2 )
- bubble_sort - Bubble Sort - O (n 2 )
- Bucket_Sort - Sort de seau - O (n 2 )
- comptage_sort - Sort de comptage - o (n + k)
- heap_sort - theap sort - o (nlog (n)
- insertion_sort - Tri d'insertion - O (n 2 )
- Merge_sort - Merge Sort - O (nlog (n))
- Quick_sort - Sort rapide - θ (nlog (n))
- radix_sort - Radix Sort - O (n + k)
- SELECTION_SORT - SORT SELECTION - (O (N 2 ))
- shell_sort - Shell Sort - о (n)
- String_matching -
- boyer_moore - algorithme de boyer moore
- Horspool - Boyer Moore Horspool Algorithme
- knuth_morris_pratt - Knuth Morris Pratt
- naïve_pattern_matching - correspondance de motifs naïfs
- Rabin_Karp - Rabin Karp
- Toh - Tour de Hanoi
- graphiques -
- Directed_unweyped - Graphique non pondéré
- Directed_weeep - graphique pondéré réalisé
- non dirigée_unweyped - graphique non pondéré
- non dirigée_weeep - graphique pondéré non dirigée
- tas -
- max_binary_heap - tas binaire max
- min_binary_heap - tas binaire min
- Linked_lists -
- circulaire_doubly_ll - Liste circulaire doublement liée
- Circular_ll - Liste liée à la circulaire
- Double_ll - Liste doublement liée
- Pres_rev_single_ll - Conserver la commande pendant l'insertion sur la liste liée unique et l'inversion de la liste liée unique
- Single_ll - Liste liée unique
- files d'attente -
- CDQueue - file d'attente circulaire à double fin
- Cqueue - Fitre circulaire
- Dqueue - file d'attente à double fin
- priority_queue - Fitre prioritaire avec l'utilisation de Min tas
- Simple_queue - File simple
- pile - pile
- arbres -
- AVL_TREE_USING_LL - AVL Tree Utilisation de la liste Linked avec BFS et DFS (pré, dans, post) Traversals de commande.
- BST_USING_ARR - Arborescence de recherche binaire utilisant un tableau avec BFS et DFS (pré, dans, post) Traversals de commande.
- BST_USING_LL - Arborescence de recherche binaire utilisant la liste liée avec BFS et DFS (pré, dans, post) Traversals de commande.
- Simple_BT_USING_ARR - Arbre binaire simple à l'aide du tableau avec BFS et DFS (pré, dans, post) Traversals de commande.
- Simple_BT_USING_LL - Arbre binaire simple à l'aide de la liste liée avec BFS et DFS (pré, dans, post) Traversals de commande.
Remarque : le pointeur ": point_left:" indique une implémentation incomplète et est dans la liste TODO.
Contribution
Ce référentiel est pour apprendre à mettre en œuvre des structures de données et des algorithmes, et comme les contributions d'autres ne m'apprendront pas vraiment à la mettre en œuvre par moi-même, je n'accepterai aucune demande de traction. Cependant, n'hésitez pas à alimenter ce dépôt et à modifier le code pour jouer autour de diverses structures de données et algorithmes. De plus, tout en jouant autour du code, si vous trouvez quelque chose d'inhabituel ou de mal dans l'implémentation, j'apprécierais fortement si vous créez un problème sur le même.
Licence
Ce référentiel est publié sous la licence MIT. En bref, cela signifie que vous êtes libre d'utiliser ce logiciel dans des projets personnels, open-source ou commerciaux. L'attribution est facultative mais appréciée.
HAPPY CODING
HAPPY LEARNING
