Data Structures and Algorithms in C -Download - Data Structures and Algorithms in C -Quellcode herunterladen

Data Structures and Algorithms in C

Anderer Quellcode

1.0.0

Herunterladen

Datenstrukturen und Algorithmen in C implementiert

Hier finden Sie einige Datenstrukturen und Algorithmen, die in C implementiert sind. Diese Algorithmen basieren hauptsächlich auf der Einführung von Buch in Algorithmen von Thomas H. Cormen .

Anweisungen

Jedes Modul besteht aus mindestens einer Header -Datei (.H) und einer Quelldatei, die den Codekorpus (.c) enthält. Um eines dieser Module zu verwenden, empfehle ich Ihnen, die folgenden Schritte zu befolgen:

Suchen Sie die Datenstruktur oder den Algorithmus, den Sie von /modules benötigen
Laden Sie das Modulverzeichnis (zB /modules/List ) herunter, das die Quellcode .c -Datei (z. B. List.c ) enthält.
Gehen Sie zu /include/ Ordner, finden Sie die Header (.H) -Datei, die Sie möchten (z. B. List.h ) und laden Sie sie herunter.
❕ Noch nicht fertig ❕, nun gehen und überprüfen Sie die Header -Datei (.h) und laden Sie das herunter (Befehle #include "foo.h" ). Die meisten Module umfassen beispielsweise HashFunctions oder Comparators oder sogar andere Datenstrukturen. Ermitteln Sie, was benötigt wird, und laden Sie alle Dateien herunter.
Beheben Sie die Pfade zum #include "foo.h" , wenn Sie die aktuelle Ordnerstruktur ändern.
Alles ist fertig, hoffe es hat dir geholfen!

Kompilieren und Ausführung

Wenn Sie den gesamten Ordner klonen, können Sie ausführen:

make : Das kompliziert jedes Modul
make run-tests : Die jedes Modul kompiliert und alle Tests ausführt
make valgind-tests : Die jedes Modul kompiliert und alle Tests mit Valgrind ausführt

Anhang

Datenstruktur	Definition
Blütefilter	Der Bloom-Filter ist eine platzeffiziente probabilistische Datenstruktur, die 1970 von Burton Howard Bloom konzipiert wird, um zu testen, ob ein Element ein Mitglied eines Satzes ist. Falsche positive Übereinstimmungen sind möglich, aber falsche Negative sind nicht - mit anderen Worten, eine Abfrage gibt entweder "möglicherweise in Set" oder "definitiv nicht im Set" zurück. Elemente können dem Satz hinzugefügt, aber nicht entfernt werden (obwohl dies mit der Variante des Zählblütenfilters angesprochen werden kann). Je mehr Elemente hinzugefügt wurden, desto größer ist die Wahrscheinlichkeit falscher Positives.
Rotschwarzer Baum	Rot-Schwarz-Baum ist eine Art selbstausgleichender binärer Suchbaum. Jeder Knoten speichert ein zusätzliches Bit, das "Farbe" ("rot" oder "schwarz" darstellt, mit der sichergestellt wird, dass der Baum während der Insertionen und Löschungen ausgewogen bleibt. Wenn der Baum modifiziert wird, wird der neue Baum neu angeordnet und "neu gestrichen", um die Farbeigenschaften wiederherzustellen, die einschränken, wie unausgeglichene der Baum im schlimmsten Fall werden kann. Die Eigenschaften sind so konzipiert, dass diese Neuanordnung und Wiederbelebung effizient durchgeführt werden kann. Das Neuausgleich ist nicht perfekt, sondern garantiert die Suche in O (logn) , wo n die Anzahl der Knoten des Baumes ist. Die Einfügungs- und Löschvorgänge sowie die Umlagerung und Wiederbelebung von Baum werden ebenfalls in O (logn) ausgeführt.
Verlinkte Liste	Linked List ist eine lineare Sammlung von Datenelementen, deren Reihenfolge nicht durch ihre physische Platzierung im Speicher angegeben ist. Stattdessen verweist jedes Element auf das nächste. Es handelt sich um eine Datenstruktur, die aus einer Sammlung von Knoten besteht, die zusammen eine Sequenz darstellen.
Warteschlange	Die Priority -Warteschlange ist ein abstrakter Datentyp, der einer regulären Warteschlange- oder Stapeldatenstruktur ähnelt, in der jedes Element zusätzlich über eine "Priorität" zugeordnet ist. In einer vorrangigen Warteschlange wird ein Element mit hoher Priorität vor einem Element mit niedriger Priorität zugestellt.
Hashtable mit Liste	Generische Implementierung eines sehr einfachen Hashtabels mit Schlüsseln und Ketten. Keine Rekonstruktion bereitgestellt.
Hashtable mit rotem Schwarzbaum	Bestand aus einer Tabelle, in der jede Reihe auf diese Weise einen Zeiger auf einen rot-schwarzen Baum hat, was wir die oben genannten besten Komplexität erhalten und gleichzeitig zu viele Kollisionen vermeiden.
Hashtable mit Eimern bis rotschwarzer Baum	Hashtable bestand aus Eimer von Zeigern auf rote schwarze Bäume
Maxheap	Ein Max-heap ist ein vollständiger binärer Baum, bei dem der Wert in jedem internen Knoten größer oder gleich den Werten in den Kindern dieses Knotens ist. Die Zuordnung der Elemente eines Haufens in ein Array ist trivial: Wenn ein Knoten ein Index K gespeichert ist, wird sein linkes Kind unter Index 2K+1 und sein rechtes Kind bei Index 2K+2 gespeichert.
DisjointSet	Die disjunkte Datenstruktur, die auch als Gewerkschaftsfind-Datenstruktur oder Merge-Find-Set bezeichnet wird, ist eine Datenstruktur, die eine Sammlung von Disjoint (nicht überlappenden) Sätzen speichert. Äquivalent speichert es eine Partition eines Sets in disjunkte Untergruppen. Es bietet Operationen zum Hinzufügen neuer Sets, Verschmelzungssätze (ersetzt sie durch ihre Gewerkschaft) und das Finden eines repräsentativen Mitglieds eines Sets. Der letzte Vorgang ermöglicht es effizient herauszufinden, wenn sich zwei Elemente im gleichen oder unterschiedlichen Sets befinden.
Job Scheduler mit Threads	Multi-Thread-Job-Scheduler mit UNIX PThreads.

Algorithmus	Definition
Haufen	Heapsort ist ein vergleichsbasierter Sortieralgorithmus. Heapsort kann als eine verbesserte Selektionsart betrachtet werden: Wie die Selektionsart teilt Haufen seine Eingabe in eine sortierte und eine ungeortierte Region auf und schrumpft iterativ die unsortierte Region, indem sie das größte Element extrahiert und in die sortierte Region einfügt. Im Gegensatz zur Sortierung der Selektion verschwendet Heapsort keine Zeit mit einem linearen Scan des unsortierten Bereichs. Vielmehr behält die Heap -Sortierung die unsortierte Region in einer Heap -Datenstruktur bei, um schneller das größte Element in jedem Schritt zu finden.
Quicksort	Quicksort ist ein effizienter Sortieralgorithmus. Es wurde 1959 vom britischen Informatiker Tony Hoare entwickelt und 1961 veröffentlicht. Es ist immer noch ein häufig verwendeter Algorithmus für die Sortierung. Wenn es gut implementiert wird, kann es etwas schneller sein als die Zusammenführungsart und etwa zwei- oder dreimal schneller als die Haufen.

Algorithmus

Definition

Haufen

Heapsort ist ein vergleichsbasierter Sortieralgorithmus. Heapsort kann als eine verbesserte Selektionsart betrachtet werden: Wie die Selektionsart teilt Haufen seine Eingabe in eine sortierte und eine ungeortierte Region auf und schrumpft iterativ die unsortierte Region, indem sie das größte Element extrahiert und in die sortierte Region einfügt. Im Gegensatz zur Sortierung der Selektion verschwendet Heapsort keine Zeit mit einem linearen Scan des unsortierten Bereichs. Vielmehr behält die Heap -Sortierung die unsortierte Region in einer Heap -Datenstruktur bei, um schneller das größte Element in jedem Schritt zu finden.

Quicksort

Quicksort ist ein effizienter Sortieralgorithmus. Es wurde 1959 vom britischen Informatiker Tony Hoare entwickelt und 1961 veröffentlicht. Es ist immer noch ein häufig verwendeter Algorithmus für die Sortierung. Wenn es gut implementiert wird, kann es etwas schneller sein als die Zusammenführungsart und etwa zwei- oder dreimal schneller als die Haufen.