Was sind Datenstrukturen in C und wie werden sie verwendet?

Einführung

Zunächst einmal ist eine Datenstruktur eine Sammlung von Datenelementen, die unter einem Namen oder einer Überschrift zusammengehalten werden, und stellt eine bestimmte Art der Speicherung und Zusammenstellung der Daten dar, damit die Daten effizient verwendet werden können.

Typen

Datenstrukturen sind weit verbreitet und werden in fast jedem Softwaresystem verwendet. Einige der häufigsten Beispiele für Datenstrukturen sind Arrays, Warteschlangen, Stapel, verknüpfte Listen und Bäume.

Anwendungen

Beim Entwerfen von Compilern, Betriebssystemen, Erstellen von Datenbanken, Anwendungen für künstliche Intelligenz und vielem mehr.

Einstufung

Datenstrukturen werden in zwei Kategorien eingeteilt: primitive Datenstrukturen und nicht-primitive Datenstrukturen.

1. Primitiv: Sie sind die grundlegenden Datentypen, die von einer Programmiersprache unterstützt werden. Ein gängiges Beispiel für diese Klassifizierung sind ganze Zahlen, Zeichen und boolesche Werte.

2. Nicht-primitiv: Diese Kategorien von Datenstrukturen werden unter Verwendung primitiver Datenstrukturen erstellt. Beispiele sind verknüpfte Stapel, verknüpfte Listen, Diagramme und Bäume.

Arrays

Ein Array ist eine einfache Sammlung von Datenelementen, die den gleichen Datentyp haben. Das bedeutet, dass ein Array vom Typ Integer nur Integer-Werte speichern kann. Ein Array vom Datentyp Float kann Werte speichern, die dem Datentyp Float entsprechen, und sonst nichts.

In einem Array gespeicherte Elemente sind linear zugänglich und befinden sich in zusammenhängenden Speicherblöcken, auf die mit einem Index verwiesen werden kann.

Deklarieren eines Arrays

In C kann ein Array wie folgt deklariert werden:

Datentyp Name[Länge];

Zum Beispiel,

int-Befehle[10];

Die obige Codezeile erstellt ein Array von 10 Speicherblöcken, in denen ein ganzzahliger Wert gespeichert werden kann. In C beginnt der Indexwert des Arrays bei 0. Die Indexwerte reichen also von 0 bis 9. Wenn wir auf einen bestimmten Wert in diesem Array zugreifen möchten, müssen wir einfach Folgendes eingeben:

printf(order[index_number]);

Eine andere Möglichkeit, ein Array zu deklarieren, ist wie folgt:

data_type array_name[size]={Liste von Werten};

Zum Beispiel,

int markiert[5]={9, 8, 7, 9, 8};

Die obige Befehlszeile erzeugt ein Array mit 5 Speicherblöcken mit festen Werten in jedem der Blöcke. Bei einem 32-Bit-Compiler beträgt der vom int-Datentyp belegte 32-Bit-Speicher 4 Byte. 5 Speicherblöcke würden also 20 Byte Speicher belegen.

Eine andere legitime Möglichkeit, Arrays zu initialisieren, ist:

int markiert [5] = {9 , 45};

Dieser Befehl erstellt ein Array aus 5 Blöcken, wobei die letzten 3 Blöcke 0 als Wert haben.

Ein anderer legitimer Weg ist:

int markiert [] = {9 , 5, 2, 1, 3,4};

Der C-Compiler versteht, dass nur 5 Blöcke erforderlich sind, um diese Daten in ein Array einzupassen. Es wird daher ein Array von Namenszeichen der Größe 5 initialisieren.

Auf ähnliche Weise kann ein 2-D-Array auf folgende Weise initialisiert werden

int Markierungen[2][3]={{9,7,7},{6, 2, 1}};

Der obige Befehl erstellt ein 2-D-Array mit 2 Zeilen und 3 Spalten.

Lesen Sie: Ideen und Themen für das Datenstrukturprojekt

Operationen

Es gibt einige Operationen, die auf Arrays ausgeführt werden können. Zum Beispiel:

1. ein Array durchlaufen
2. Einfügen eines Elements in das Array
3. Suche nach einem bestimmten Element im Array
4. Löschen eines bestimmten Elements aus dem Array
5. Zusammenführen der beiden Arrays und,
6. Sortieren des Arrays – in aufsteigender oder absteigender Reihenfolge.

Nachteile

Der dem Array zugewiesene Speicher ist fest. Das ist tatsächlich ein Problem. Angenommen, wir haben ein Array der Größe 50 erstellt und nur auf 30 Speicherblöcke zugegriffen. Die restlichen 20 Blöcke belegen Speicher ohne Nutzen. Um dieses Problem anzugehen, haben wir daher eine verknüpfte Liste.

Verknüpfte Liste

Linked List speichert Daten ähnlich wie Arrays seriell. Der Hauptunterschied besteht darin, dass nicht alles auf einmal gespeichert wird. Speichert stattdessen die Daten oder stellt bei Bedarf einen Speicherblock zur Verfügung. In einer verketteten Liste sind die Blöcke in zwei Teile geteilt. Der erste Teil enthält die eigentlichen Daten.

Der zweite Teil ist ein Zeiger, der auf den nächsten Block in einer verknüpften Liste zeigt. Der Zeiger speichert die Adresse des nächsten Blocks, der die Daten enthält. Es gibt einen weiteren Zeiger, der als Kopfzeiger bekannt ist. head zeigt auf den ersten Speicherblock in der verknüpften Liste. Es folgt die Darstellung der verknüpften Liste. Diese Blöcke werden auch als „Knoten“ bezeichnet.

Quelle

Verknüpfte Listen initialisieren

Um die Linkliste zu initialisieren, erstellen wir einen Strukturnamenknoten. Die Struktur hat zwei Dinge. 1. Die darin enthaltenen Daten und 2. Der Zeiger, der auf den nächsten Knoten zeigt. Der Datentyp des Zeigers ist der der Struktur, da er auf den Strukturknoten zeigt.

Strukturknoten

{

int-Daten;

struct node *next;

};

In einer verknüpften Liste zeigt der Zeiger des letzten Knotens auf nichts oder zeigt einfach auf null.

Lesen Sie auch: Diagramme in der Datenstruktur

Verknüpfte Liste Traversal

In einer verknüpften Liste zeigt der Zeiger des letzten Knotens auf nichts, oder er zeigt einfach auf null. Um also eine gesamte verknüpfte Liste zu durchlaufen, erstellen wir einen Dummy-Zeiger, der zunächst auf den Kopf zeigt. Und für die Länge der verknüpften Liste bewegt sich der Zeiger weiter vorwärts, bis er auf null zeigt oder den letzten Knoten der verknüpften Liste erreicht.

Hinzufügen eines Knotens

Der Algorithmus zum Hinzufügen eines Knotens vor einem bestimmten Knoten wäre wie folgt:

1. setze zwei Dummy-Zeiger (ptr und preptr), die anfangs auf Kopf zeigen
2. Verschieben Sie den ptr, bis ptr.data gleich den Daten ist, bevor wir beabsichtigen, den Knoten einzufügen. preptr wird 1 Knoten hinter ptr sein.
3. Erstellen Sie einen Knoten
4. Der Knoten, auf den der Dummy preptr zeigte, der nächste Knoten dieses Knotens wird auf diesen neuen Knoten zeigen
5. Der nächste des neuen Knotens zeigt auf den Ptr.

Der Algorithmus zum Hinzufügen eines Knotens nach bestimmten Daten würde auf ähnliche Weise erfolgen.

Vorteile der verknüpften Liste

1. Dynamische Größe im Gegensatz zu einem Array
2. Das Einfügen und Löschen ist in der verknüpften Liste einfacher als in einem Array.

Warteschlange

Die Warteschlange folgt einem First-In-First-Out- oder FIFO-System. In einer Array-Implementierung haben wir zwei Zeiger, um den Anwendungsfall von Queue zu demonstrieren.

Quelle

FIFO bedeutet im Grunde, dass der Wert, der zuerst in den Stapel eintritt, das Array zuerst verlässt. Im obigen Warteschlangendiagramm zeigt die Zeigerfront auf den Wert 7. Wenn wir den ersten Block löschen (dequeue), zeigt die Front jetzt auf den Wert 2. Ebenso, wenn wir eine Zahl eingeben (enqueue), sagen wir 3 in Position 5. Dann zeigt der hintere Zeiger auf Position 5.

Überlauf- und Unterlaufbedingungen

Trotzdem müssen wir vor dem Eingeben eines Datenwerts in die Warteschlange auf Überlaufbedingungen prüfen. Ein Überlauf tritt auf, wenn versucht wird, ein Element in eine bereits volle Warteschlange einzufügen. Eine Warteschlange wird voll, wenn hinten = max_size–1.

Ebenso sollten wir vor dem Löschen von Daten aus der Warteschlange auf Unterlaufbedingungen prüfen. Ein Unterlauf tritt auf, wenn versucht wird, ein Element aus einer bereits leeren Warteschlange zu löschen, dh wenn vorne = null und hinten = null ist, dann ist die Warteschlange leer.

Stapel

Ein Stack ist eine Datenstruktur, in der wir Elemente nur an einem Ende einfügen und löschen, das auch als oberstes Ende des Stacks bezeichnet wird. Die Stack-Implementierung wird daher als Last-In-First-Out (LIFO)-Implementierung bezeichnet. Im Gegensatz zu queue benötigen wir für den Stack nur einen Top-Zeiger.

Wenn wir Elemente in ein Array eingeben (pushen) wollen, bewegt sich der obere Zeiger nach oben oder erhöht sich um 1. Wenn wir ein Element löschen (popen) möchten, verringert sich der obere Zeiger um 1 oder geht um 1 Einheit nach unten. Ein Stack unterstützt drei grundlegende Operationen: Push, Pop und Peep. Die Peep-Operation zeigt einfach das oberste Element im Stapel an.

Quelle

Lernen Sie Softwarekurse online von den besten Universitäten der Welt. Verdienen Sie Executive PG-Programme, Advanced Certificate-Programme oder Master-Programme, um Ihre Karriere zu beschleunigen.

Fazit

In diesem Artikel haben wir über 4 Arten von Datenstrukturen gesprochen, nämlich Arrays, verknüpfte Listen, Warteschlangen und Stapel. Ich hoffe, Ihnen hat dieser Artikel gefallen und bleiben Sie dran für weitere interessante Lektüre. Bis zum nächsten Mal.

Wenn Sie mehr über Javascript und Full-Stack-Entwicklung erfahren möchten, schauen Sie sich das Executive PG-Programm in Full-Stack-Softwareentwicklung von upGrad & IIIT-B an, das für Berufstätige konzipiert ist und mehr als 500 Stunden strenge Schulungen und mehr als 9 Projekte bietet und Aufgaben, IIIT-B-Alumni-Status, praktische praktische Schlusssteinprojekte und Arbeitsunterstützung bei Top-Unternehmen.