Menü

Einführung in Datenstrukturen in C ++

introduction data structures c

Versuchen Sie Unser Instrument, Um Probleme Zu Beseitigen

Ein Einführungs-Tutorial zu Datenstrukturen in C ++.

„Datenstruktur kann als organisierte Sammlung von Daten definiert werden, die einem Programm hilft, effizient und schnell auf Daten zuzugreifen, damit das gesamte Programm effizient funktionieren kann. „

Wir wissen, dass in der Programmierwelt Daten das Zentrum sind und sich alles um Daten dreht. Wir müssen alle Datenoperationen ausführen, einschließlich Speichern, Suchen, Sortieren, Organisieren und Zugreifen auf Daten, und nur dann kann unser Programm erfolgreich sein.

=> Hier finden Sie Informationen zur vollständigen Liste der C ++ - Tutorials.

Einführung in Datenstrukturen in C ++ (1)

Was du lernen wirst:

Überblick

Wir müssen den effizientesten Weg zum Speichern von Daten finden, der uns beim Erstellen dynamischer Lösungen helfen kann. Die Datenstruktur hilft uns beim Aufbau solcher Lösungen.

Beim Organisieren oder Anordnen von Daten in Strukturen müssen wir sicherstellen, dass die Anordnung nahezu ein reales Objekt darstellt. Zweitens sollte diese Anordnung so einfach sein, dass jeder leicht darauf zugreifen und sie bei Bedarf verarbeiten kann.

In dieser Reihe lernen wir sowohl grundlegende als auch erweiterte Datenstrukturen im Detail kennen. Wir werden auch im Detail verschiedene Such- und Sortiertechniken kennenlernen, die an Datenstrukturen durchgeführt werden können.

Nach dem Erlernen dieser Lernserie sollte der Leser mit jeder Datenstruktur und ihrer Programmierung vertraut sein.

Lassen Sie uns einige der Begriffe durchgehen, die wir beim Umgang mit Datenstrukturen verwenden:

Zum Beispiel,nimm einen bestimmten Schüler. Ein Schüler kann die folgenden Details haben, wie sie bildlich dargestellt sind.

Beispiel - Datenstruktur

  • Daten: Es ist der Elementarwert. In der obigen Abbildung kann die Schülerrollennummer Daten sein.
  • Gruppenelement: Dies ist das Datenelement mit mehr als einem Unterelement. In der obigen Abbildung hat Student_name Vor- und Nachnamen.
  • Aufzeichnung: Es ist eine Sammlung von Datenelementen. Im obigen Beispiel bilden Datenelemente wie Schüler-Rollennummer, Name, Klasse, Alter, Klasse usw. zusammen einen Datensatz.
  • Entität: Es ist eine Klasse von Aufzeichnungen. Im obigen Diagramm ist der Schüler eine Entität.
  • Attribut oder Feld: Eigenschaften einer Entität werden als Attribute bezeichnet und jedes Feld repräsentiert ein Attribut.
  • Datei: Eine Datei ist eine Sammlung von Datensätzen. Im obigen Beispiel kann eine studentische Entität Tausende von Datensätzen haben. Somit enthält eine Datei alle diese Datensätze.

Der Leser sollte sich all dieser Begriffe bewusst sein, da wir sie ab und zu verwenden, wenn wir verschiedene Datenstrukturen verwenden.

Datenstrukturen sind der Hauptbaustein des Programms. Als Programmierer sollten wir vorsichtig sein, welche Datenstruktur verwendet werden soll. Die genaue zu verwendende Datenstruktur ist die schwierigste Entscheidung für die Programmierung.

Lassen Sie uns die Notwendigkeit einer Datenstruktur in der Programmierung diskutieren.

Notwendigkeit einer Datenstruktur in der Programmierung

Mit zunehmender Datenmenge werden die Anwendungen immer komplexer, sodass es für den Programmierer schwierig wird, diese Daten sowie die Software zu verwalten.

In der Regel kann die Anwendung jederzeit mit den folgenden Hürden konfrontiert sein:

# 1) Durchsuchen großer Datenmengen: Da eine große Datenmenge verarbeitet und gespeichert wird, muss unser Programm möglicherweise zu einem bestimmten Zeitpunkt bestimmte Daten durchsuchen. Wenn die Daten zu groß und nicht richtig organisiert sind, dauert es sehr lange, bis die erforderlichen Daten abgerufen werden.

Wenn wir Datenstrukturen zum Speichern und Organisieren von Daten verwenden, wird das Abrufen von Daten schneller und einfacher.

# 2) Verarbeitungsgeschwindigkeit: Desorganisierte Daten können zu einer langsamen Verarbeitungsgeschwindigkeit führen, da beim Abrufen und Zugreifen auf Daten viel Zeit verschwendet wird.

Wenn wir die Daten während des Speicherns ordnungsgemäß in einer Datenstruktur organisieren, verschwenden wir keine Zeit mit Aktivitäten wie dem Abrufen und dem Organisieren jedes Mal. Stattdessen können wir uns auf die Verarbeitung von Daten konzentrieren, um die gewünschte Ausgabe zu erzielen.

# 3) Mehrere gleichzeitige Anfragen: Viele Anwendungen müssen heutzutage gleichzeitig Daten anfordern. Diese Anforderungen sollten effizient verarbeitet werden, damit Anwendungen reibungslos ausgeführt werden können.

Wenn unsere Daten nur zufällig gespeichert werden, können wir nicht alle gleichzeitigen Anforderungen gleichzeitig verarbeiten. Es ist daher eine kluge Entscheidung, Daten in einer geeigneten Datenstruktur anzuordnen, um die Bearbeitungszeit für gleichzeitige Anforderungen zu minimieren.

Datenstrukturklassifizierung

In C ++ verwendete Datenstrukturen können wie folgt klassifiziert werden.

Klassifizierung von Datenstrukturen

Eine Datenstruktur ist eine Möglichkeit, die Daten zu organisieren. So können wir Datenstrukturen wie gezeigt in primitive oder Standarddatenstrukturen und nicht primitive oder benutzerdefinierte Datenstrukturen klassifizieren.

Wir haben alle in C ++ unterstützten Datentypen gesehen. Da dies auch eine Möglichkeit zum Organisieren von Daten ist, handelt es sich um eine Standarddatenstruktur.

Die anderen Datenstrukturen sind nicht primitiv und müssen vom Benutzer definiert werden, bevor sie in einem Programm verwendet werden können. Diese benutzerdefinierten Datenstrukturen werden weiter in lineare und nichtlineare Datenstrukturen unterteilt.

Lineare Datenstruktur

Bei linearen Datenstrukturen sind alle Elemente linear oder sequentiell angeordnet. Jedes Element in einer linearen Datenstruktur hat einen Vorgänger (vorheriges Element) und einen Nachfolger (nächstes Element).

Lineare Datenstrukturen werden weiter in statische und dynamische Datenstrukturen unterteilt. Statische Datenstrukturen haben normalerweise eine feste Größe und können nach ihrer Deklaration zur Kompilierungszeit nicht mehr geändert werden. Dynamische Datenstrukturen können ihre Größe dynamisch ändern und sich anpassen.

Das beliebteste Beispiel für eine lineare statische Datenstruktur ist ein Array.

Array

Ein Array ist eine sequentielle Sammlung von Elementen desselben Typs. Auf jedes Element des Arrays kann über seine Position im Array zugegriffen werden, die als Index oder Index des Arrays bezeichnet wird. Der Name des Arrays zeigt auf das erste Element im Array.

Array

Das oben gezeigte ist ein Array 'a' von n Elementen. Die Elemente sind von 0 bis n-1 nummeriert. Die Größe des Arrays (in diesem Fall n) wird auch als Dimension des Arrays bezeichnet. Wie in der obigen Abbildung gezeigt, zeigt der Name des Arrays auf das erste Element des Arrays.

Das Array ist die einfachste Datenstruktur und effizient, da auf Elemente direkt über Indizes zugegriffen werden kann. Wenn wir auf das dritte Element im Array zugreifen wollen, müssen wir nur a (2) sagen.

Das Hinzufügen oder Löschen der Array-Elemente ist jedoch schwierig. Daher verwenden wir Arrays nur in einfachen Anwendungen oder in Anwendungen, in denen das Hinzufügen / Löschen von Elementen nicht erforderlich ist.

Beliebte lineare dynamische Datenstrukturen sind verknüpfte Listen, Stapel und Warteschlangen.

Verknüpfte Liste

Eine verknüpfte Liste ist eine Sammlung von Knoten. Jeder Knoten enthält das Datenelement und einen Zeiger auf den nächsten Knoten. Knoten können dynamisch hinzugefügt und gelöscht werden. Eine verknüpfte Liste kann eine einfach verknüpfte Liste sein, in der jeder Knoten nur einen Zeiger auf das nächste Element hat. Für das letzte Element wird der nächste Zeiger auf null gesetzt.

In der doppelt verknüpften Liste hat jeder Knoten zwei Zeiger, einen auf den vorherigen Knoten und den zweiten auf den nächsten Knoten. Für den ersten Knoten ist der vorherige Zeiger null und für den letzten Knoten ist der nächste Zeiger null.

Verknüpfte Liste

Wie in der obigen Abbildung gezeigt, wird der Anfang der Liste als Kopf und das Ende der verknüpften Liste als Schwanz bezeichnet. Wie oben gezeigt, hat jeder Knoten einen Zeiger auf das nächste Element. Wir können Elemente einfach hinzufügen oder löschen, indem wir den Zeiger auf den nächsten Knoten ändern.

Stapel

Der Stapel ist eine lineare Datenstruktur, in der die Elemente nur an einem Ende hinzugefügt oder entfernt werden können, das als 'Oberseite' des Stapels bezeichnet wird. Auf diese Weise weist der Stapel einen Speicherzugriff vom Typ LIFO (Last In, First Out) auf.

Stapel

Wie oben gezeigt, werden Elemente im Stapel immer an einem Ende hinzugefügt und auch am selben Ende entfernt. Dies wird als 'Top' des Stapels bezeichnet. Wenn ein Element hinzugefügt wird, wird es über den Stapel nach unten gedrückt und die Oberseite des Stapels wird um eine Position erhöht.

In ähnlicher Weise wird beim Entfernen eines Elements die Oberseite des Stapels dekrementiert. Wenn ein Stapel leer ist, wird die Oberseite des Stapels auf -1 gesetzt. Es gibt zwei Hauptoperationen, 'Push' und 'Pop', die auf dem Stapel ausgeführt werden.

Warteschlange

Die Warteschlange ist eine weitere lineare Datenstruktur, bei der die Elemente an einem Ende mit der Bezeichnung 'hinten' hinzugefügt und an einem anderen Ende mit der Bezeichnung 'vorne' gelöscht werden. Die Warteschlange demonstriert FIFO (First In, First Out) die Art der Speicherzugriffsmethode.

Warteschlange

Das obige Diagramm zeigt eine Warteschlange mit hinteren und vorderen Enden. Wenn die Warteschlange leer ist, stimmen der hintere und der vordere Zeiger überein.

Nichtlineare Datenstruktur

In nichtlinearen Datenstrukturen sind Daten nicht sequentiell angeordnet, sondern nichtlinear angeordnet. Elemente sind in einer nichtlinearen Anordnung miteinander verbunden.

Nichtlineare Datenstrukturen sind Bäume und Diagramme.

am besten YouTube-Video in MP3 konvertieren

Bäume

Bäume sind nichtlineare mehrstufige Datenstrukturen mit einer hierarchischen Beziehung zwischen den Elementen. Elemente des Baumes werden Knoten genannt.

Der Knoten oben wird als Wurzel des Baums bezeichnet. Die Wurzel kann einen oder mehrere untergeordnete Knoten haben. Die nachfolgenden Knoten können auch einen oder mehrere untergeordnete Knoten haben. Die Knoten, die keine untergeordneten Knoten haben, werden Blattknoten genannt.

Bäume

Im obigen Diagramm haben wir einen Baum mit 6 Knoten gezeigt. Von diesen drei Knoten sind die Blattknoten, ein oberster Knoten ist die Wurzel und die anderen sind untergeordnete Knoten. Abhängig von der Anzahl der Knoten, untergeordneten Knoten usw. oder der Beziehung zwischen den Knoten haben wir verschiedene Arten von Bäumen.

Grafiken

Das Diagramm besteht aus einer Reihe von Knoten, die aufgerufen werden Eckpunkte über die aufgerufenen Links miteinander verbunden Kanten . Graphen können einen Zyklus enthalten, d. H. Der gleiche Scheitelpunkt kann sowohl ein Startpunkt als auch der Endpunkt eines bestimmten Pfades sein. Bäume können niemals einen Zyklus haben.

Grafiken

Das obige Diagramm ist ein ungerichteter Graph. Wir können auch gerichtete Graphen haben, in denen wir die Kanten mit gerichteten Pfeilen darstellen.

Operationen zur Datenstruktur

Alle Datenstrukturen führen verschiedene Operationen an ihren Elementen aus.

Diese sind allen Datenstrukturen gemeinsam und werden wie folgt aufgelistet:

  • Suchen: Diese Operation wird ausgeführt, um nach einem bestimmten Element oder einem Schlüssel zu suchen. Die gebräuchlichsten Suchalgorithmen sind sequentielle / lineare Suche und binäre Suche.
  • Sortierung: Beim Sortieren werden die Elemente in einer Datenstruktur in aufsteigender oder absteigender Reihenfolge in einer bestimmten Reihenfolge angeordnet. Für Datenstrukturen stehen verschiedene Sortieralgorithmen zur Verfügung. Am beliebtesten unter ihnen sind Quicksort, Auswahlsortierung, Zusammenführungssortierung usw.
  • Einfügen: Die Einfügeoperation befasst sich mit dem Hinzufügen eines Elements zur Datenstruktur. Dies ist die wichtigste Operation, und durch das Hinzufügen eines Elements ändert sich die Anordnung, und wir müssen darauf achten, dass die Datenstruktur intakt bleibt.
  • Streichung: Durch das Löschen wird ein Element aus der Datenstruktur entfernt. Die gleichen Bedingungen, die beim Einfügen zu beachten sind, sind auch beim Löschen zu erfüllen.
  • Durchqueren: Wir sagen, dass wir eine Datenstruktur durchlaufen, wenn wir jedes einzelne Element in der Struktur besuchen. Das Durchlaufen ist erforderlich, um bestimmte spezifische Operationen an der Datenstruktur auszuführen.

In unseren folgenden Themen lernen wir zunächst die verschiedenen Such- und Sortiertechniken kennen, die an Datenstrukturen durchgeführt werden sollen.

Vorteile der Datenstruktur

  • Abstraktion: Datenstrukturen werden häufig als abstrakte Datentypen implementiert. Die Benutzer greifen nur auf die äußere Oberfläche zu, ohne sich um die zugrunde liegende Implementierung zu kümmern. Somit liefert die Datenstruktur eine Abstraktionsebene.
  • Effizienz: Eine ordnungsgemäße Organisation der Daten führt zu einem effizienten Zugriff auf Daten, wodurch Programme effizienter werden. Zweitens können wir abhängig von unseren Anforderungen die richtige Datenstruktur auswählen.
  • Wiederverwendbarkeit: Wir können die von uns entworfenen Datenstrukturen wiederverwenden. Sie können auch in einer Bibliothek kompiliert und an den Client verteilt werden.

Fazit

Damit schließen wir dieses Tutorial zur Einführung in Datenstrukturen ab. Wir haben jede der Datenstrukturen in diesem Tutorial kurz vorgestellt.

In unseren nachfolgenden Tutorials werden wir mehr über Datenstrukturen sowie die verschiedenen Such- und Sortiertechniken erfahren.

=> Klicken Sie hier für die Absolute C ++ - Schulungsserie.

Literatur-Empfehlungen

^