golang data structures algorithms

Datenstrukturen und Algorithmen

Datenstrukturen und Algorithmen (DSA) sind eines der wichtigsten Themen in der Informatik, das jeder CS-Student in der Lage sein muss, und sogar nicht-CS-Schüler das grundlegende Verständnis dafür haben. Es wird gesagt, dass DSA wie Brot und Butter, die Notwendigkeit von CS ist. Dieses Repository wird für diejenigen Schüler (wie ich?) Erstellt, die darauf bedacht sind, Datenstrukturen und Algorithmen zu lernen und zu implementieren.

Warum Go/Golang und nicht C, C ++ oder Java?

Ich würde nicht einverstanden sein, dass C, C ++ oder Java keine großartige Sprache sein würden, um DSA zu implementieren, da man sich um viele Dinge kümmern muss, während man den Code wie Speicherzuweisungen und ordnungsgemäße Deals und damit viel lernt.

Der Grund, warum GO auch eine gute Sprache sein würde, um DSA zu implementieren, ist, dass es viel Magie fehlt. Es gibt keine Überlastung des Bedieners, daher keine Möglichkeit, zusätzliche Komplexität zu verbergen. Eine Indexoperation ist o (1), eine Schleife ist o (n) - immer. Es gibt keine Generika, daher gibt es nicht viele zusätzliche Abstraktionen und Helfer, was eigentlich ziemlich großartig ist. Es gibt keine Faulheit oder andere Compiler-gesteuerte Magie, die die Laufzeit Ihrer Algorithmen erheblich verändern könnte. Und Go hat Zeiger- und niedrige Primitive für Scheiben, was bedeutet, dass es sichtbar ist, wenn Daten gepackt sind oder wenn Daten eine zusätzliche Indirektion haben. Kurz gesagt : Machen Sie die tatsächliche algorithmische Ausführung aus dem Code offensichtlich, was eine gute Sache ist, um Algorithmen zu lernen.

Schlussfolgerung : GO wäre auch eine gute Sprache, um mit der Implementierung von Datenstrukturen und Algorithmen zu beginnen.

Anweisungen

1. Stellen Sie zu Beginn sicher, dass Sie die Programmiersprache auf Ihrem Computer installiert haben. Befolgen Sie, wie Sie Anweisungen von Golang Download -Anweisungen installieren.
2. Sobald Go auf Ihrem Computer installiert ist, klonen Sie einfach oder laden Sie dieses Repository herunter.
3. Jetzt cd <folder-name> in den Ordner, in dem sich die Datei ausführen, die Sie ausführen möchten.
4. Jetzt go run . .

Beispiel

Nehmen wir an, Sie möchten Dateien ausführen, die sich in graphs/directed_unweighted -Verzeichnis befinden, dann die Syntax, die es ausführen soll, wäre:

 cd graphs/directed_unweighted/

go run .

Ordnernamen

1. Algorithmen -
   • 01Knapsack_dp - 0-1 Knapsack -Problem mithilfe der dynamischen Programmierung
   • a_star -
     • 8_puzzle - 8 Puzzle -Problem mit einem ^* Algorithmus
     • DEECTED_GRAPH - A ^* ALGORITHUM FÜR DERECTTE GRAPE
     • Unirected_Graph - A ^* -Algorithmus für undirected Graph
   • Activity_Selection_GP - Aktivitätsauswahl unter Verwendung einer gierigen Programmierung
   • Assembly_line_Scheduling - Planungsalgorithmus für Montagelinien mithilfe der dynamischen Programmierung
   • Binary_Reflected_Gray_Codes - Binary Reflected Grey Codes
   • CEHST_PAIR_PROBLEM -
     • CPP_BRUTE_FORCE - nächstliches Paarproblem mit Brute Force -Technik
     • CPP_DIVIDE_CONQUER - Das engste Paarproblem mit Divide- und Eroberer -Techinque
   • Kombinationen -
     • With_R - mit Wiederholung von Elementen
     • ohne Elemente ohne Wiederholung
   • konvexe_hull -
     • CH_BRUTE_FORCE - Konvexer Rumpfalgorithmus mit Brute -Force -Technik
     • CH_DIVIDE_CONQUER - Konvexer Rumpfalgorithmus mithilfe der Divide- und Eroberungstechnik
   • Expression_Conversions -
     • INFIX_POSTFIX - Infix -to -Postfix -Konvertierung
     • Infix_Prefix - Infix zum Präfixkonvertieren
     • Postfix_infix - Postfix -to -Infix -Konvertierung
     • postfix_prefix - postfix zum Präfixkonvertieren
     • Präfix_Infix - Präfix zur Infix -Konvertierung
     • Präfix_Postfix - Präfix zur Postfix -Konvertierung
   • GCD - größter gemeinsamer Divisor (Euklid -Algorithmus)
   • Grafiken -
     • articulation_point_detektion - Artikulationspunkte in einem ungerichteten Diagramm erkennen
     • Bellman_ford - Bellman Ford Algorithmus
     • Bridge_Detektion - Erkennung/Schnittkantenerkennung in einem ungerichteten Diagramm
     • Dijkstra - Dijkstra -Algorithmus
     • Floyd_warshall - Floyd Warshall -Algorithmus (alle Punkte kürzester Pfad)
     • Krukals - Kruskals Algorithmus (Finden Sie Mindestspannungsbaum MST unter Verwendung eines gierigen Ansatzes)
     • Prims - Prims Algorithmus (Finden von minimalem Spanning Tree MST unter Verwendung eines gierigen Ansatzes)
     • topological_sort - topologische Sortierung
     • Traverals -
       • CD_Directed_Graph_Traversa - Zykluserkennung in gerichteten Diagramme unter Verwendung von Traversal -Techniken
       • CD_undirected_Graph_Traversa - Zykluserkennung in undirected Graphen unter Verwendung von Traversal -Techniken
     • TSP -
       • tsp_dynamic -
         1. DECECTED_GRAPH - TSP (Travel Salesman Problem) Verwenden dynamischer Ansatz für gerichtete Graphen
         2. UNDIRECTECECTE_GRAPH - TSP (Travel Salesman -Problem) Verwenden dynamischer Ansatz für ungerichtete Graphen
       • TSP_NAIVE -
         1. Direkted_Graph - TSP (Trails -Verkäuferproblem) Verwenden naiver Ansatz für Regiegrafiken
         2. UNDIRECTECECTE_GRAPH - TSP (Travel Salesman Problem) Verwenden naiver Ansatz für ungerichtete Graphen
     • Union_find - Union Find / Disjoint -Sätze (Erkennung von Zyklen in einem ungerichteten Diagramm)
   • Huffman_Codes - Huffman -Codes (generieren Huffman -Codes)
   • Job_Scheduling_gp - Jobplanungsalgorithmus mit gieriger Programmierung
   • LCM - am wenigsten gemeinsames Multiple (mit dem Algorithmus von GCD Euclid)
   • LCS - Längste gemeinsame Subsequenz
     • iterative_dp - Längste gemeinsame Subsequenz mit dynamischer Programmierung (iterative Version)
   • lo_permutations - Lexikografische Auftragsdurchlässen
   • längst_palindrome_substring -
     • Brute_Force - Längste Palindrome -Substring mit Brute Force -Technik
     • MANCHERS - Längste Palindrome -Substring mit Manchers Algorithmus
   • make_change_dp - Problem mithilfe der dynamischen Programmierung ändern
   • Order_Statistics - KTH kleinste/größte Element finden (Bestellstatistik)
     • NAIVE_ACKROACH - NAIVER -Ansatz mit maximalem Heap - O (K + (NK)*log (k))
     • Quick_Select - Quick Select (Quick Sort) - O (n^2), θ (nLogn)
     • Worst_Case_Linear_time - Worst Case Linear Time Order Statistics - O (n)
   • power_set - power set (set of subsets)
   • Suche -
     • Binary_Search - Binärsuche - O (log n)
     • Interpolation_search - Interpolationsuche - O (n)
     • linear_search - lineare Suche - o (n)
     • ternary_search - ternärische Suche - o (log ₃ n)
   • Sieb_of_eratosthenes - Sieb von Eratosthenes (aufeinanderfolgende Primzahlen, die nicht überschreiten)
   • Sortierung -
     • Binary_insertion_sort - Binäreinfügungssortier - o (n ² )
     • Bubble_Sort - Blasensortierung - O (n ² )
     • Bucket_Sort - Bucket Sort - o (n ² )
     • counting_sort - zählende Sortierung - o (n + k)
     • Heap_Sort - Heap -Sortierung - O (NLOG (N)
     • Insertion_Sort - Insertion -Sortierung - O (n ² )
     • merge_sort - merge sort - o (nLog (n))
     • Quick_Sort - Quick Sortieren - θ (nLog (n))
     • radix_sort - radix sortieren - o (n+k)
     • Selection_Sort - Auswahlsortierung - (o (n ² ))
     • Shell_sort - Shell -Sortierung - о (n)
   • String_matching -
     • Boyer_moore - Boyer Moore -Algorithmus
     • Horspool - Boyer Moore Horspool -Algorithmus
     • Knuth_Morris_pratt - Knuth Morris Pratt
     • NAIVE_PATTERN_MATCHING - NAIVE -Muster -Matching
     • Rabin_Karp - Rabin Karp
   • Toh - Turm von Hanoi
2. Grafiken -
   • Directed_Unwished - Directed Ungewissed Graph
   • DECECTED_WILLEDED - DECECTED WOLDED GRAPH
   • ungerichtet_ungewicht - ungerichtete, ungewichtete Graphen
   • UNDIRECTED_WEIGHTED - UNDIRECTED WOLDED GRAPH
3. Haufen -
   • max_binary_heap - Max -Binärhaufen
   • min_binary_heap - min binärer Haufen
4. linked_lists -
   • circular_doubly_ll - circular doppelt verknüpfte Liste
   • circular_ll - circular verknüpfte Liste
   • doppelt_ll - doppelt verknüpfte Liste
   • pres_rev_single_ll - Bestellung während des Einsetzens in einzelnen verknüpften Liste und Umkehrung der einzelnen verknüpften Liste erhalten
   • Single_ll - Single -verknüpfte Liste
5. Warteschlangen - Warteschlangen -
   • CDQueue - kreisförmige Doppel -Warteschlange
   • Cqueue - Rundwarteschlange
   • DQUEUE - Doppelende Warteschlange
   • Priority_queue - Prioritätswarteschlange mit der Verwendung von min Haufen
   • Simple_queue - einfache Warteschlange
6. Stack - Stack
7. Bäume -
   • avl_tree_using_ll - AVL -Baum mit verknüpfter Liste mit BFS und DFS (PRE, IN, POST) Order Traverals.
   • BST_USUS_arr - Binärer Suchbaum mit Array mit BFS und DFS (PRE, IN, POST) Order Traverals.
   • BST_USUS_LL - Binärer Suchbaum mit verknüpfter Liste mit BFS und DFS (PRE, IN, POST) Order Traverals.
   • Simple_BT_USING_arr - Einfacher Binärbaum mit Array mit BFS und DFS (Pre, In, Post) Order Traverals.
   • Simple_BT_USION_LL - Einfacher binärer Baum mit verknüpfter Liste mit BFS und DFS (PRE, IN, POST) Order Traverals.

Hinweis : Der Zeiger ": point_left:" Zeigt eine unvollständige Implementierung an und befindet sich in der Todo -Liste.

Beitrag

Dieses Repository dient zum Lernen, wie Datenstrukturen und Algorithmen implementiert werden können. Da die Beiträge anderer nicht wirklich beibringen, wie ich sie selbst implementieren kann, werde ich keine Pull -Anfragen annehmen. Fühlen Sie sich jedoch frei, dieses Repo zu geben und den Code so zu ändern, dass verschiedene Datenstrukturen und Algorithmen umgespielt werden. Während Sie beim Spielen im Code etwas Ungewöhnliches oder Unrecht in der Implemetation finden, würde ich mich sehr sehr freuen, wenn Sie ein Problem auf dasselbe erstellen.

Lizenz

Dieses Repository wird unter der MIT -Lizenz veröffentlicht. Kurz gesagt, dies bedeutet, dass Sie diese Software frei in persönlichen, offenen oder kommerziellen Projekten verwenden können. Die Zuordnung ist optional, aber geschätzt.

 HAPPY CODING 
HAPPY LEARNING