Grundlegende Konzepte der Datenstruktur
Bevor Sie formell verschiedene Datenstrukturen erlernen, müssen Sie die Klassifizierungsmethoden von Datenstrukturen und das Konzept abstrakter Datentypen beherrschen und die Kernwissenspunkte der Sprache C wiederholen, die eng mit Datenstrukturen zusammenhängen.
Klassifizierung von Datenstrukturen
Datenstrukturen können aus zwei Dimensionen klassifiziert werden: logische Struktur und Speichermethode. Das Verständnis dieser beiden Klassifizierungsmethoden hilft Ihnen, schnell zu bestimmen, welcher Typ von Datenstruktur bei spezifischen Problemen gewählt werden sollte.
Die obige Abbildung zeigt das vollständige Klassifizierungssystem der Datenstrukturen, das unten einzeln erklärt wird.
Klassifizierung nach logischer Struktur
Die logische Struktur beschreibt die abstrakten Beziehungen zwischen Datenelementen, ohne die tatsächliche Speichermethode der Daten im Speicher einzubeziehen.
| Type | Elementbeziehung | Typisches Beispiel | Anwendungsfall |
|---|---|---|---|
| Lineare Struktur | Sequenzielle Eins-zu-eins-Beziehung | Arrays, verkettete Listen, Stacks, Warteschlangen | Daten haben eine offensichtliche Reihenfolge, wie To-do-Listen und Browserverlauf |
| Baumstruktur | Hierarchische Eins-zu-viele-Beziehung | Binärbäume, BST, Heaps | Daten haben eine hierarchische Zuordnung, wie Dateisystemverzeichnisse und Organisationsstrukturen |
| Graphstruktur | Viele-zu-viele-Netzwerkbeziehung | Gerichtete Graphen, ungerichtete Graphen, gewichtete Graphen | Beziehungen zwischen Daten sind komplex, wie soziale Netzwerke und Kartennavigation |
Klassifizierung nach Speichermethode
Die Speichermethode beschreibt die tatsächliche Organisation der Daten im Speicher.
| Type | Eigenschaften | Typisches Beispiel | Kompromiss |
|---|---|---|---|
| Sequenzielle Speicherung | Elemente werden nacheinander in zusammenhängendem Speicherbereich gespeichert | Arrays, Stapel/Warteschlangen, die mit Arrays implementiert sind | Schneller Zugriff (O(1)), aber langsames Einfügen und Löschen, feste Größe |
| Verkettete Speicherung | Elemente können verstreut gespeichert werden, verbunden über Zeiger | Verkettete Listen, Bäume, Graphen (Adjazenzliste) | Schnelles Einfügen und Löschen, aber keine Unterstützung für wahlfreien Zugriff, zusätzlicher Zeiger-Overhead |
| Indexierte Speicherung | Eine zusätzliche Indextabelle anlegen, um Daten zu lokalisieren | Hash-Tabellen (über Hash-Funktionen indiziert) | Extrem schnelles Nachschlagen, erfordert jedoch zusätzlichen Speicherplatz zum Speichern der Indexstruktur |
Dieselbe logische Struktur kann mit unterschiedlichen Speichermethoden implementiert werden. Beispielsweise kann ein Stack (logisch eine lineare Struktur) entweder mit einem Array (sequentielle Speicherung) oder einer verketteten Liste (verkettete Speicherung) implementiert werden. Welche Implementierung gewählt wird, hängt von den Anforderungen der jeweiligen Anwendung an Zugriffsgeschwindigkeit, Effizienz beim Einfügen/Löschen und Speicherverbrauch ab.
Abstrakter Datentyp (ADT)
Abstrakter Datentyp (ADT)ist ein Kernkonzept beim Studium von Datenstrukturen.
Er bezieht sich auf eine abstrakte Beschreibung einer Datenmenge und einer Menge von Operationen, die auf diesen Daten definiert sind, und betrachtet nur "was zu tun ist", nicht "wie es zu tun ist".
Nehmen Sie "Stack" als Beispiel, um ADT zu verstehen:
| ADT-Ebene (was zu tun ist) | Implementierungsebene (wie es zu tun ist) |
|---|---|
| Operationen definieren: push, pop, peek | Mit Array implementieren: ein Array + Top-Zeiger verwalten |
| Verhalten definieren: Last In, First Out (LIFO) | Mit verketteter Liste implementieren: den Kopf der verketteten Liste als oberstes Ende des Stapels verwenden |
| Einschränkungen festlegen: Operationen können nur an einem Ende ausgeführt werden | Beide Implementierungen erfüllen die ADT-Definition, haben aber unterschiedliche Leistungsmerkmale |
Diese Idee der "Trennung von Schnittstelle und Implementierung" ist der Eckpfeiler des modularen Designs in der modernen Softwaretechnik.
Wenn Sie einen Stapel verwenden, müssen Sie nur wissen, wie man Operationen wie push und pop benutzt, ohne sich darum kümmern zu müssen, ob die zugrunde liegende Implementierung ein Array oder eine verkettete Liste ist – genau das ist der Wert von ADT.
Wiederholung der C-Grundlagen
Bevor Sie Datenstrukturen lernen, müssen Sie die folgenden drei zentralen Wissenspunkte der Sprache C beherrschen, die in fast allen Kapiteln dieses Tutorials vorkommen.
Zeiger
Ein Zeiger ist eines der wichtigsten und flexibelsten Merkmale in C. Er speichert die Speicheradresse einer anderen Variablen und ermöglicht den indirekten Zugriff und die Manipulation der Zielvariablen.
Beispiel
int main() {
int num = 42; /* gewöhnliche Integer-Variable */
int *ptr = # /* ptr ist ein Zeiger auf int und speichert die Adresse von num */
printf("num-Wert: %d\n", num); /* Ausgabe: 42 */
printf("Adresse von num: %p\n", &num); /* Ausgabe: 0x16d2f2f38 (Beispieladresse) */
printf("in ptr gespeicherte Adresse: %p\n", ptr); /* Ausgabe: wie oben */
printf("durch *ptr dereferenzierter Wert: %d\n", *ptr); /* Ausgabe: 42, * ist der Dereferenzierungsoperator */
*ptr = 100; /* Wert von num über den Zeiger ändern */
printf("nach der Änderung, num = %d\n", num); /* Ausgabe: 100 */
return 0;
}
Zentrale Verwendungen von Zeigern in Datenstrukturen:
| Verwenden Sie | Beispiel |
|---|---|
| Verbindungen zwischen dynamischen Knoten herstellen | In Knoten verketteter Listen,nextZeiger; in Baumknoten,left/rightZeiger |
| Indirekt auf Daten zugreifen und sie ändern | Verwenden Sie Zeigerparameter, damit Funktionen die Werte externer Variablen ändern können |
| Dynamische Speicherverwaltung | mallocGibt die Startadresse des zugewiesenen Speichers zurück, die mit einem Zeiger entgegengenommen werden muss |
| Vermeiden Sie das Kopieren großer Datenmengen | Wenn große Strukturen an Funktionen übergeben werden, ist das Übergeben von Zeigern effizienter als die Übergabe als Wert |
Was Anfänger am leichtesten verwechseln, ist
*und&die Verwendung von * und &: in Deklarationen,int *p* zeigt an, dass p ein Zeigertyp ist; bei der Verwendung,*p* zeigt das Dereferenzieren an (den Wert abrufen);&x& zeigt die Adressbildung an. Dies sind zwei völlig unterschiedliche Operatoren, und das Verständnis dieses Unterschieds ist die Voraussetzung für die gute Verwendung von Zeigern.
Struktur (struct)
Ein struct ermöglicht es, mehrere Daten unterschiedlichen Typs zu einem benutzerdefinierten Typ zusammenzufassen, und ist die Grundeinheit für den Aufbau zusammengesetzter Datenstrukturen wie Listenknoten und Baumknoten.
Beispiel
#include <string.h> /* Header-Datei für strcpy */
/* Struktur für Knoten einer verketteten Liste definieren */
struct Node {
int data; /* Datenfeld: speichert die tatsächlichen Daten */
struct Node* next; /* Zeigerfeld: zeigt auf den nächsten Knoten */
};
/* Struktur für Studenteninformationen definieren */
struct Student {
int id; /* Studenten-ID */
char name[50]; /* Name, Zeichenarray */
float score; /* Punktzahl */
};
int main() {
/* Knoten erstellen */
struct Node node1;
node1.data = 10;
node1.next = NULL; /* NULL bedeutet, dass derzeit kein nächster Knoten vorhanden ist */
printf("node1.data = %d\n", node1.data); /* Ausgabe: 10 */
/* Studentendatensatz erstellen */
struct Student stu;
stu.id = 1001;
strcpy(stu.name, "EXAMPLE"); /* strcpy: Zeichenkette in Zeichenarray kopieren */
stu.score = 95.5;
printf("ID: %d, Name: %s, Score: %.1f\n",
stu.id, stu.name, stu.score);
/* Ausgabe: ID: 1001, Name: EXAMPLE, Score: 95.5 */
return 0;
}
Strukturen in Kombination mit Zeigern ermöglichen flexible dynamische Datenstrukturen. Beispielsweise ist die selbstreferenzielle Struktur eines Knotens einer verketteten Liste (struct Node* nextzeigt auf den nächsten Knoten desselben Typs) genau die Implementierungsgrundlage von verketteten Listen.
Dynamische Speicherzuweisung
Dynamische Speicherzuweisung ermöglicht es einem Programm, zur Laufzeit nach Bedarf Heap-Speicher anzufordern und freizugeben, und ist der Schlüssel zum Aufbau von Datenstrukturen mit variabler Größe (wie verkettete Listen und Bäume).
C bietet vier Kernfunktionen:
| Funktion | Funktionalität | Beispiel |
|---|---|---|
| malloc | Speicher der angegebenen Byte-Größe zuweisen, Inhalt uninitialisiert | int* p = malloc(10 * sizeof(int)); |
| calloc | Speicher zuweisen und auf null initialisieren | int* p = calloc(10, sizeof(int)); |
| realloc | Größe von bereits zugewiesenem Speicher ändern | p = realloc(p, 20 * sizeof(int)); |
| free | Zugewiesenen Speicher freigeben und an das System zurückgeben | free(p); |
Beispiel
#include <stdlib.h> /* Header-Datei für malloc, free */
int main() {
int n = 5;
/* malloc: zusammenhängenden Speicher für n ints auf dem Heap reservieren */
int* arr = (int*)malloc(n * sizeof(int));
/* Prüfen, ob die Allokation erfolgreich war; malloc gibt bei einem Fehler NULL zurück */
if (arr == NULL) {
printf("Speicherzuweisung fehlgeschlagen!\n");
return 1; /* Abnormales Beenden */
}
/* Dynamisch zugewiesenen Speicher wie ein normales Array verwenden */
for (int i = 0; i < n; i++) {
arr[i] = (i + 1) * 10; /* Zuweisen: 10, 20, 30, 40, 50 */
}
printf("Inhalt des dynamischen Arrays: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n"); /* Ausgabe: Inhalt des dynamischen Arrays: 10 20 30 40 50 */
free(arr); /* Speicher freigeben, um Speicherlecks zu vermeiden */
arr = NULL; /* Gute Praxis: Setzen Sie den Zeiger auf NULL, um wilde Zeiger zu vermeiden */
return 0;
}
Weitere ErweiterungenDie Programmiersprache C gibt dynamisch zugewiesenen Speicher nicht automatisch frei. Jedes Mal
malloc(odercalloc) muss ein entsprechendes habenfree, andernfalls verursacht es Speicherlecks. In realen Projekten erschöpfen Speicherlecks allmählich die Systemressourcen und führen schließlich zum Absturz des Programms. Dies ist einer der häufigsten Fehler von C-Anfängern.