Antwort.
Dynamische Datenstrukturen in C (z. B. verkettete Listen, Bäume) werden normalerweise manuell unter Verwendung von Zeigern und dynamischer Speicherzuweisung (malloc, calloc, free) implementiert.
Wichtige Nuancen bei der Implementierung:
- Initialisieren Sie Zeiger unbedingt: Müll in nicht initialisierten Zeigern führt zu Speicherlecks oder Segmentation Faults.
- Fehler bei der Speicherzuweisung behandeln: Überprüfen Sie das Ergebnis von malloc/calloc, sonst kann das Programm mit einem ungültigen Zeiger arbeiten.
- Speicher korrekt freigeben: Vergessen Sie nicht, free für jede zugewiesene Struktur aufzurufen, um Speicherlecks zu vermeiden.
- Vermeiden Sie „hängende“ Zeiger (setzten Sie den Zeiger nach free auf NULL).
Beispiel: Erstellung und Löschung einer einfachen einfach verketteten Liste
typedef struct Node {
int value;
struct Node* next;
} Node;
Node* create_node(int value) {
Node* n = malloc(sizeof(Node));
if (!n) return NULL;
n->value = value;
n->next = NULL;
return n;
}
void free_list(Node* head) {
while (head) {
Node* tmp = head;
head = head->next;
free(tmp);
}
}
Fangfrage.
Kann man die Speicherfreigabe der Knotenliste innerhalb einer Schleife mithilfe nur des aktuellen Zeigers durchführen?
Es ist nicht korrekt, den aktuellen Knoten ohne vorherige Speicherung des nächsten Knoten zu befreien! Nach dem Aufruf von free kann der Speicher an dieser Adresse überschrieben oder vom Betriebssystem zurückgegeben werden.
Richtiger Ansatz:
Node* curr = head;
while (curr) {
Node* next = curr->next;
free(curr);
curr = next;
}
Wenn next nicht gespeichert wird, greift man auf bereits freigegebenen (und möglicherweise nicht eigenen!) Speicher zu.
Geschichte
Weil vergessen wurde, die gesamte Liste (free) bei einem fehlerhaften Abschluss einer der Operationen freizugeben, arbeitete der Autotest bei 10000 Einfügungen/Löschungen, wodurch der Speicherbedarf allmählich stieg – der Profiler zeigte ein großes Leck.
Der Entwickler hatte einen Zeiger auf den letzten Knoten der Liste gespeichert, jedoch nicht auf NULL gesetzt, nachdem er alle Elemente gelöscht hatte, wodurch er in einer anderen Funktion auf bereits freigegebenen Speicher verwies und einen schwer fassbaren Segfault erhielt.
Bei der Arbeit mit Bäumen wurde vergessen, rekursiv alle "Teilbäume" zu löschen und nur den Wurzelknoten freizugeben. Ergebnis: Durch unvollständige Bereinigung blieb die Speicherstruktur schmutzig, was zu sporadischen Abstürzen führte.