data-structures Tutorial
Erste Schritte mit Datenstrukturen
Suche…
Bemerkungen
In diesem Abschnitt erhalten Sie einen Überblick über die Datenstrukturen und warum ein Entwickler sie verwenden möchte.
Es sollte auch alle großen Themen in den Datenstrukturen erwähnen und auf die verwandten Themen verweisen. Da die Dokumentation für Datenstrukturen neu ist, müssen Sie möglicherweise erste Versionen dieser verwandten Themen erstellen.
Einführung in Datenstrukturen
Eine Datenstruktur ist eine Möglichkeit, Informationen zu organisieren und zu speichern.
Lass ein "Hallo, Welt!" string sind die Informationen, die wir organisieren und im byteadressierbaren Speicher speichern müssen.
Jedes ASCII-Zeichen benötigt 7 Bit Speicherplatz. Die meisten Systeme reservieren 8 Bits (1 Byte) für jedes Zeichen, sodass jedes Zeichen in "Hallo, Welt!" wird nacheinander in einer einzelnen bytegroßen Speichereinheit gespeichert.
Wir benötigen einen einzelnen Verweis auf unsere Zeichenfolge, obwohl sie mehrere Speicheradressen umfasst. Daher verwenden wir die Adresse des ersten Zeichens in der Zeichenfolge "H". Auf jedes andere Zeichen kann unter der Adresse 'H' + dem Index dieses Zeichens mit null indizierten Zeichen zugegriffen werden.
Wir möchten unseren String "Hallo, Welt!" Ausdrucken. Wir kennen die Adresse im Speicher, die wir für die Druckfunktion bereitstellen, aber woher weiß die Druckfunktion, um den Druck aufeinander folgender Speicherplätze zu stoppen? Ein allgemeiner Ansatz ist das Anhängen des Nullzeichens '\ 0' an den String. Wenn die Druckfunktion auf das Nullzeichen stößt, weiß sie, dass das Ende der Zeichenfolge erreicht ist.
Wir haben eine Methode zum Organisieren und Speichern unserer Zeichenfolge definiert, dh eine Datenstruktur! Diese sehr einfache Datenstruktur ist ein nullterminiertes Zeichenarray. Dies ist eine Möglichkeit zum Organisieren und Speichern einer Zeichenfolge.
Array: Eine einfache Datenstruktur
Eine Array-Datenstruktur wird zum Speichern ähnlicher Objekte (oder Datenwerte) in einem zusammenhängenden Speicherblock verwendet. Die Array-Datenstruktur hat eine feste Größe, die die Anzahl der Datenwerte bestimmt, die darin gespeichert werden können.
Array: Der C ++ - Weg
In der Programmiersprache C ++ können wir ein statisches Array wie folgt deklarieren
int arrayName[100];
Hier haben wir ein Array mit dem Namen "arrayName" deklariert, das bis zu 100 Werte speichern kann, die alle vom selben Typ sind, also eine Ganzzahl.
Nun werden einige Vor- und Nachteile dieser Datenstruktur diskutiert
- Wir können auf in Array gespeicherte Datenwerte in konstanter Zeit zugreifen, das heißt, die Zeitkomplexität ist O (1) . Wenn wir also auf den Datenwert zugreifen möchten, der an der i-ten Position gespeichert ist, müssen wir nicht von der Startposition aus starten und zur i-ten Position vorrücken, sondern können direkt zur i-ten Position springen, wodurch Rechenzeit eingespart wird.
- Das Einfügen eines Elements in die Mitte eines Arrays ist keine effiziente Aufgabe. Angenommen, wir möchten an der i-ten Position ein neues Element in das Array einfügen. Dann müssen wir zunächst alle Elemente an die Position (i-th) und (i + 1) bewegen, um Platz für das neue Element zu schaffen. Beispiel:
1 4 2 0ist ein Array mit 4 Elementen. Jetzt wollen wir 3 an der zweiten Position einfügen. Dann müssen wir 4,2 und 0 um eine Position weiter verschieben, um Platz für 3 zu schaffen.
1 3 4 2 0
- Ähnlich wie beim Einfügen des Elements ist auch das Löschen eines Elements von einer i-ten Position in einem Array nicht effizient, da alle Elemente vor dem gelöschten Element um einen Block verschoben werden müssen, um den durch das gelöschte leeren Platz zu füllen Element.
Dies sind drei einfache Merkmale eines Arrays. Hier könnte man glauben, dass ein Array keine effiziente Datenstruktur ist, aber in der Praxis kann der Vorteil eines Arrays seine Nachteile überwiegen. Dies hängt weitgehend von dem Zweck ab, den Sie erfüllen möchten. Möglicherweise möchten Sie das Element nicht so oft einfügen oder löschen, wie Sie möchten, und in diesem Fall ist ein Array eine absolut perfekte Datenstruktur.
Der einzige Zweck der Einführung dieser Datenstruktur besteht darin, sicherzustellen, dass Sie Datenstruktur nicht aufgrund der Anzahl von Vor- und Nachteilen auswählen, sondern Sie sollten immer versuchen, die Wichtigkeit der Datenstruktur zu analysieren, indem Sie Ihr Problem im Auge behalten. Wenn Sie viel Zeit darauf verwenden, auf Datenwerte zuzugreifen, anstatt sie einzufügen oder zu löschen, müssen wir in diesem Fall der Benachteiligung mehr Gewicht einräumen.