10 Beste Datenstrukturen und Algorithmen C ++ - Grundlagen

Inhaltsverzeichnis:

Anonim

Datenstrukturen und Algorithmen C ++

Datenstrukturen und Algorithmen C ++ - bedeutet, die Elemente auf eine bestimmte Weise anzuordnen oder zu organisieren. Wenn wir sagen, wir müssen Elemente anordnen, können diese Elemente in verschiedenen Formen organisiert werden. Zum Beispiel können Socken auf verschiedene Arten angeordnet werden. Sie können es einfach in Ihrem Schrank verstauen. Oder Sie können es ordentlich gefaltet halten. Der beste Weg kann sein, sie farblich zu falten und anzuordnen. Für die Suche nach einem bestimmten Paar Socken ist die dritte Anordnung perfekt.

In einer ähnlichen Art der Organisation von Socken können Daten auch auf verschiedene Arten oder Formen organisiert werden. Diese verschiedenen Arten der Datenorganisation werden als Datenstruktur bezeichnet. Sehen wir uns eine formale Definition einer Datenstruktur und die Grundlagen zu Datenstrukturen und Algorithmen an.

Datenstrukturen und Algorithmen C ++:

Das logische oder mathematische Modell einer bestimmten Datenorganisation.

ODER

Auf diese Weise können Daten in einem Computer so organisiert werden, dass sie verwendet werden können.

Ähnlich wie bei Socken; Unterschiedliche Organisation von Listendatenstrukturen und Algorithmen C ++ verfügbar ist -

  1. Array
  2. Verknüpfte Liste
  3. Stapel
  4. Warteschlange
  5. Baum
  6. Graph
  7. Hash-tabelle
  8. Haufen
  9. Aufzeichnungen
  10. Tabellen

Diese Datenstrukturen und Algorithmen von C ++ sind beim Programmieren sehr wichtig. Ein guter Programmierer legt immer mehr Wert auf die Datenstruktur als auf den Code. Jede Programmiersprache arbeitet in C ++ mit verschiedenen Datenstrukturen und Algorithmen. Folgende Datenstrukturen stehen in C ++ zur Verfügung.

  1. Array
  2. Verknüpfte Liste
  3. Stapel
  4. Warteschlange
  5. Baum
  6. Graph
  7. Hash-tabelle
  8. Haufen

Lassen Sie uns dies einzeln diskutieren:

# 1 Array

Array ist eine einfachste Art von Datenstrukturen und Algorithmen C ++. Das Array ist als sequentielle Sammlung von Datenelementen desselben Datentyps mit fester Größe definiert. ZB a0 = 12, a1 = 21, a2 = 14, a3 = 15 … Wir können ein eindimensionales Array darstellen, wie in Abbildung gezeigt:

Wo

0, 1, 2, 3… ..n heißt tiefgestellt oder Index

a (1), a (2), … a (n) heißt tiefgestellte Variable

Es kann eindimensional, zweidimensional, dreidimensional usw. mehrdimensional sein.

In einem Speicherarray werden sie in zusammenhängenden Speicherorten gespeichert.

Die niedrigste Adresse entspricht dem ersten Element

Die höchste Adresse entspricht dem letzten Element

Wir können ein eindimensionales Array in C ++ wie folgt deklarieren

dataType arrayName (arraySize);

ZB int num (5);

Array wird in C ++ initialisiert

num = (23, 10, 12, 3, 6);

Wir können Deklaration und Initialisierung wie folgt in einer einzigen Anweisung kombinieren.

int num = (23, 10, 12, 3, 6);

Wenn wir die Größe eines Arrays dynamisch zuweisen möchten, sollten wir den Operator new wie folgt eingeben

int * a = new int (Größe);

Der Nachteil des Arrays ist, dass das Einfügen und Löschen von Elementen langsam ist, wie bei einem geordneten Array und dessen Speicher mit fester Größe.

# 2 Verknüpfte Liste

Liste bezieht sich auf eine lineare Sammlung von Elementen. Eine verknüpfte Liste besteht aus einer Reihe verbundener Knoten (Datenelement), wie in Abbildung 3 dargestellt. Der Kopfknoten zeigt auf den ersten Knoten der Liste und der letzte Knoten auf NULL (gekennzeichnet durch Æ). Da jeder Knoten mindestens enthält.

  1. Ein Datenelement (beliebiger Typ)
  2. Zeiger auf den nächsten Knoten in der Liste

Die verknüpfte Liste wird im Speicher mit zwei Arrays dargestellt. In einem Array werden Informationen gespeichert, die als Informationen bezeichnet werden, dh zu speichernde Daten, und in einem anderen Array wird das als LINK bezeichnete Feld für den nächsten Zeiger gespeichert, bei dem es sich um eine Adresse des nächsten Knotens handelt.

Ein Vorteil einer verknüpften Liste gegenüber einem Array:

Sowohl ein Array als auch eine verknüpfte Liste sind Darstellungen einer Liste von Elementen im Speicher. Der wichtige Unterschied ist die Art und Weise, in der die Elemente miteinander verknüpft sind. Die Hauptbeschränkung des Arrays ist das Einfügen von Elementen in das Array und das Löschen von Elementen aus dem geordneten Array sind schwierig, da die restlichen Elemente verschoben werden müssen. Das Einfügen und Löschen von Elementen aus einer verknüpften Liste ist sehr einfach.

Hinweis: Werden Sie C ++ - Entwickler
Erfahren Sie, wie Sie Programme für verschiedene Plattformen entwerfen und anpassen. Codieren, testen, debuggen und implementieren Sie Softwareanwendungen. Entwickeln Sie Fähigkeiten, um sicherzustellen, dass Anwendungen reibungslos ausgeführt werden.

Typen von verknüpften Listen sind:

1. Einfach verknüpfte Liste : Enthält nur ein verknüpftes Feld, das die Adresse des nächsten Knotens in der Liste enthält, und das Feld info, das die zu speichernden Informationen enthält.

2. Single Circular Linked List ist nur eine einzelne Liste, aber der letzte Knoten der Liste enthält die Adresse des ersten Knotens anstelle von Null. Das heißt Inhalt von Kopf und nächstes Feld des letzten Knotens sind gleich.

3. Die doppelt verknüpfte Liste enthält zwei verknüpfte Felder vor und nach. Ein zuvor verknüpftes Feld, das eine Adresse des vorherigen Knotens in der Liste und das nächste verknüpfte Feld enthält, enthält die Adresse des nächsten Knotens in der Liste, und die hinterlegten Informationen enthalten die Informationen, um ein Geschäft zu sein.

4. Double Circular Linked List ist eine doppelt verknüpfte Liste, aber das nächste Feld des letzten Knotens enthält die Adresse des ersten Knotens anstelle von Null.

Empfohlene Kurse

  • Kurs auf VB.NET
  • Data Science Programmiertraining
  • Online ISTQB Kurs
  • Kali Linux Schulung

Die Implementierung einer verknüpften Liste in C ++ umfasst das Erstellen eines Knotens, das Löschen eines Knotens aus der Liste, das Einfügen eines neu erstellten Knotens in die Liste und das Suchen eines Knotens mit einem bestimmten Schlüssel.

Der Code zum Erstellen des Knotens lautet wie folgt:

Das Einfügen eines Knotens in die Liste umfasst drei Fälle

1. Einfügen eines Knotens am Anfang bedeutet das Einfügen des neu erstellten Knotens als Startknoten. Um einen Knoten am Anfang einzufügen, müssen Sie zunächst einen neuen Knoten erstellen und den neuen Knoten auf den alten Start verweisen lassen. Anschließend müssen Sie den Start aktualisieren, um auf den neuen Knoten zu verweisen, wie in der folgenden Abbildung dargestellt:

Code zum Einfügen eines Knotens am Anfang:

2. Einfügen eines Knotens am Ende bedeutet das Einfügen des neu erstellten Knotens als letzten Knoten. Um den Knoten als Endknoten einzufügen, müssen Sie einen neuen Knoten erstellen und den alten letzten Knoten auf den neuen Knoten verweisen lassen. Anschließend müssen Sie den Endknoten aktualisieren, um auf den neuen Knoten zu verweisen.

3. Beim Einfügen eines Knotens an einer bestimmten Position wird ein neuer temporärer Knoten erstellt. Anschließend muss die Einfügeposition des neu erstellten Knotens ermittelt werden.

Code zum Einfügen des Knotens an einer bestimmten Position:

Beim Löschen eines Knotens aus der Liste wird ein Knoten aus der vorhandenen Liste entfernt. Das Löschen des Knotens aus der Linkliste ist einfacher als das Einfügen eines Knotens in die Liste. In C ++ wird Code zum Löschen des Knotens wie folgt angegeben:

Durch Durchlaufen eines Knotens mit einem bestimmten Schlüssel (Wert) aus einer Liste wird ein Knoten aus der Liste gesucht, dessen Informationen mit dem Schlüssel eines bestimmten Knotens übereinstimmen. Der folgende C ++ - Code durchläuft eine Liste. Datenstrukturen und Algorithmen C ++

Stapel # 3

Ein Stapel ist eine Liste von Elementen, in die ein Element nur an einem Ende eingefügt oder gelöscht werden kann, das als oberster Teil des Stapels bezeichnet wird. Betrachten Sie das Beispiel eines Turms von Hanoi. Wenn wir eine Disc einlegen müssen, müssen wir sie nur von oben einlegen, und in ähnlicher Weise erfolgt das Entfernen der Disc nur von oben.

Stack verwendet das LIFO-Prinzip, dh es funktioniert in der Reihenfolge Last in First Out. Dies ist das letzte Element, das dem Stapel hinzugefügt wird, und das erste Element, das entfernt wird. Es gibt also vier grundlegende Operationen, die auf dem Stapel ausgeführt werden können:

  • Isempty: Diese Operation prüft, ob der Stack leer ist.
  • Push : Diese Operation fügt einen neuen Gegenstand zum Stapeln hinzu.
  • Pop: Dieser Vorgang entfernt ein Element aus dem Stapelelement, das zuletzt hinzugefügt wurde.
  • Oben: Dieser Vorgang gibt das zuletzt zum Stapel hinzugefügte Element zurück.

Die folgende Abbildung zeigt ein Beispiel des Stapels, in dem das Einfügen in den Stapel und das Entfernen des Gegenstands von einem Stapel von oben und nirgendwo anders erfolgt.

Paketüberfluss

Die Bedingung, die sich aus dem Versuch ergibt, ein Element auf einen vollständigen Stapel zu schieben.

Stack underflow

Die Bedingung, die sich aus dem Versuch ergibt, einen leeren Stapel abzulegen.

Hier haben wir einige Push- und Pop-Operationen auf dem Stack gezeigt. Angenommen, der Stapel ist anfangs leer, dann haben wir F, A, M, R, N hinzugefügt. Dann pop zweimal und drücke N, H, B, T, K, O, P.

Implementierung von Stack:

Sie kann mithilfe eines Arrays oder einer verknüpften Liste implementiert werden.

Der folgende Code zeigt, wie der Stack mit Class in C ++ implementiert wird. Hier haben Sie eine Klasse als Stack definiert, in der ein Array mit dem Namen Stick mit dynamischer Größe und zwei Hauptfunktionen (Push und Pop) erstellt wurde.

Stapelüberlauf: Wenn oben> = Größe-1

Stapelunterlauf: Wenn oben <0

In Verbindung stehende Artikel:-

Hier sind einige Artikel, die sich auf die Datenstrukturen und Algorithmen C ++ beziehen, die Ihnen helfen, mehr Details über die Algorithmen C ++ und die Datenstrukturen und Algorithmen zu erhalten. Wenn Ihnen die Datenstrukturen und Algorithmen des Artikels in C ++ gefallen, geben Sie uns Ihren wertvollen Kommentar.

  1. Spickzettel für C ++ Programming Language
  2. Linux vs Ubuntu
  3. Fragen zum C ++ - Interview, die Sie kennen müssen
  4. Im Vorstellungsgespräch bei Data Structures And Algorithms | Am besten brauchbar
  5. Der beste Artikel für Algorithmen und Kryptographie (Beispiele)
  6. 8 Awesome Algorithm Interview Fragen und Antworten
  7. Erstaunlicher Leitfaden für Kali Linux vs Ubuntu
  8. C ++ Vector vs Array: Was sind die besten Funktionen