Antwoord.
Dynamische datastructuren in C (bijvoorbeeld gekoppelde lijsten, bomen) worden meestal handmatig geïmplementeerd met behulp van pointers en dynamische geheugenallocatie (malloc, calloc, free).
Belangrijke nuances bij de implementatie:
- Initialiseer pointers altijd: rommel in niet-geinitialiseerde pointers leidt tot geheugenlekken of segmentation faults.
- Verwerk geheugenallocatiefouten: controleer het resultaat van malloc/calloc, anders kan het programma werken met een ongeldige pointer.
- Bevrijd geheugen correct: vergeet niet free aan te roepen voor elke gealloceerde structuur om te voorkomen dat er geheugenlekken ontstaan.
- Vermijd dangling pointers (zet de pointer op null na free).
Voorbeeld: creëren en verwijderen van een eenvoudige enkelvoudige gekoppelde lijst
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);
}
}
Misleidende vraag.
Is het mogelijk om de geheugen vrij te geven van de lijstknopen binnen een loop door alleen de huidige pointer te gebruiken?
Het is niet correct om de huidige knoop vrij te geven zonder eerst de volgende te bewaren! Na het aanroepen van free kan het geheugen op dat adres worden herschreven of teruggegeven aan het besturingssysteem.
Juiste benadering:
Node* curr = head;
while (curr) {
Node* next = curr->next;
free(curr);
curr = next;
}
Als je next niet bewaart, ontstaat er een toegang tot al vrijgegeven (en potentieel niet van jou!) geheugen.
Geschiedenis
Doordat de gebruiker vergat om de hele lijst (free) te wissen bij een foutieve voltooiing van een van de bewerkingen, werkte de autotester op 10.000 toevoegings-/verwijderingsoperaties, waardoor het geheugengebruik geleidelijk toenam — de profiler toonde een grote lek.
De ontwikkelaar hield een pointer bij naar de laatste knoop van de lijst, maar zerode deze niet na het verwijderen van alle elementen, waardoor in een andere functie, verwijzend naar al vrijgegeven geheugen, een moeilijk te traceren segfault ontstond.
Bij het werken met bomen vergaten ze om alle "subbomen" recursief te verwijderen, en bevrijdden alleen de wortelknoop. Het resultaat: door onvolledige opruiming bleef de geheugenstructuur vervuild, wat leidde tot periodieke crashes.