Datastrukturen
Diese Bibliothek bietet Implementierungen klassischer Algorithmen und Datenbüsten.
Organisation
Das Projekt ist in zwei Pakete, Algorithmen und Struktur unterteilt. Das Algorithmenpaket enthält Implementierungen meist eigenständiger Algorithmen, während das Strukturpaket Datenstrukturen und Algorithmen enthält, die ausschließlich darauf betrieben werden.
Algorithmen
Hier ist eine Liste von Algorithmen unter dem Algorithmenpaket:
In Binarysearch.py:
- Standard -Binärsuche: Die Standard -Binärsuche. https://en.wikipedia.org/wiki/bary_search_algorithmus
- Erster Ereignis binärer Suchen: Die Standard -Binärsuche, außer dass sie das erste Element findet, das mit dem Suchschlüssel übereinstimmt.
In Expression.py:
Shunting Yard -Algorithmus: Dijkstra -Algorithmus zur Konvertierung von Infix in Postfix -Notation. https://en.wikipedia.org/wiki/shunting-yard_algorithmus
Dijkstra zwei Stackalgorithmus: Dijkstra -Algorithmus zur Interpretation von Postfix -Ausdrücken.
In Problemsolver.py:
- A* Algorithmus: Ein Pfad -Finding -Algorithmus. https://en.wikipedia.org/wiki/a*_search_algorithmus
- A* Algorithmus, das an das 8-Puzz-Problem angepasst wurde: https://www.cs.princeton.edu/courses/archive/spr10/cos226/asssignments/8puzzle.html
In sort.py:
- Auswahlsortierung: https://en.wikipedia.org/wiki/selection_sort
- Insertion -Sortierung: https://en.wikipedia.org/wiki/insertion_sort
- Shell -Sortierung: https://en.wikipedia.org/wiki/shellsort
- Variationen der Zusammenführungssorte: https://en.wikipedia.org/wiki/merge_sort
- Inversion Count: Zählen Sie die Anzahl der Inversionen mit modifizierter Zusammenführungssorte
- Variationen der schnellen Sortierung: einschließlich Standard-Schnellsorten, 3-Wege-Schnellsorten und Schnellsorten. https://en.wikipedia.org/wiki/quicksort
- Heap -Sortierung: https://en.wikipedia.org/wiki/heapsort
- Wählen Sie KTH: Wählen Sie das KTH -Element in der Reihenfolge. Basierend auf der Schnellstufe.
Struktur
Hier finden Sie eine Liste der implementierten Datenstrukturen und Algorithmen, die darauf arbeiten:
In linkedList.py:
- Verlinkte Liste: https://en.wikipedia.org/wiki/linked_list
- Linked Stack: Stack mit einer verknüpften Liste implementiert.
- Linked Queue: Warteschlange mit einer verknüpften Liste implementiert.
In Unionfind.py: https://en.wikipedia.org/wiki/disjoint-set_data_structure
- Schnellfind: Disjoint -Set implementiert mit Array -ähnlicher Datenstruktur. O (1) finden.
- Quick Union: Disjoint -Set mit übergeordnetem Linkbaum implementiert.
- Ausgewogene Schnellgewerkschaft: Disjoint -Set mit dem Elternverbesser und dem Ausgleich auf Union. O (log (n)) Effizienz für Find und Gewerkschaft.
- Pfadkomprimierung Schnellgewerkschaft: Disjoint -Set mit übergeordnetem Linkbaum implementiert und mit Pfadkomprimierung erweitert.
- Ausgewogene Pfadkomprimierung Schnellvereinigung: Disjoint -Set mit einem übergeordneten Linkbaum mit Ausgleich und Pfadkomprimierung implementiert. Fast amortisiert O (1) Effizienz bei Find und Union.
In symboltable.py:
- Binärer Suchbaum: Standard BST. https://en.wikipedia.org/wiki/binary_search_tree
- Rot & Schwarzer Baum: Ausgewogene BST mit 2-3 Darstellung. https://en.wikipedia.org/wiki/red%E2%80%93Black_tree
- Separate Kettenhash -Tabelle: Hash -Tabelle, die die Kollision auflöst, indem sie in einer Liste verkettet werden. https://en.wikipedia.org/wiki/hash_table#separate_chaining
- Offene Adresshash -Tabelle: Hash -Tabelle, die die Kollision mit linearer Prüfung auflösen. https://en.wikipedia.org/wiki/hash_table#open_addressing
In Heap.py:
- Binärhaufen: Eine Implementierung einer vorrangigen Warteschlange mit Binärhaufen. https://en.wikipedia.org/wiki/BINY_HEAP
In graph.py:
- UNDERRECTED Graph: https://en.wikipedia.org/wiki/graph_(discrete_mathematics) #undirected_graph
- Regie Graph: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#directed_graph
- UNDRECTECECTED WOLDED Graph: https://en.wikipedia.org/wiki/graph_(discrete_mathematics) #gewichteded_graph
- Regie gewichtete Grafik: https://en.wikipedia.org/wiki/graph_(discrete_mathematics)#weighted_graph
- Tiefe erste Suche: https://en.wikipedia.org/wiki/depth-first_search
- Breite erste Suche: https://en.wikipedia.org/wiki/breadth-first_search
- Unbekannte verbundene Komponenten: https://en.wikipedia.org/wiki/Component_(graph_theory)
- Unbekannte Zykluserkennung: https://en.wikipedia.org/wiki/cycle_(graph_theory)
- Richtungszykluserkennung: https://en.wikipedia.org/wiki/cycle_(graph_theory)
- Biparte -Erkennung: https://en.wikipedia.org/wiki/bipartite_graph
- Topologische Ordnung: https://en.wikipedia.org/wiki/topological_sorting
- Stark verbundene Komponenten (Kosaraju -Algorithmus): https://en.wikipedia.org/wiki/Kosaraju%27S_Algorithmus
- Prims Algorithmus (faul): https://en.wikipedia.org/wiki/prim%27S_Algorithmus
- Krukal's Algorithmus: https://en.wikipedia.org/wiki/kruskal%27S_Algorithmus
- Dijkstra kürzester Weg: https://en.wikipedia.org/wiki/dijkstra%27S_Algorithmus
- Topologischer acyclisch kürzester Weg: https://en.wikipedia.org/wiki/topological_sorting#application_to_shortest_path_finding
- Bellman Ford kürzester Pfad: https://en.wikipedia.org/wiki/Bellman%E2%80%93ford_algorithmus
Verwendung
Alle Komponenten werden getestet. Sie werden jedoch nicht auf strenge Produktionsstandards getestet. Datenstrukturen wie die verknüpfte Liste und die Symbollablemente haben Schnittstellen wie die Standard -Python -Liste und das Wörterbuch.
