Für meine aktuelle Lernübung studiere ich verknüpfte Listen und Bäume. Ich habe kürzlich einen Vorschlag gesehen, Datenstrukturen rekursiv zu zerstören, indem jeder Knoten seine Child / Children löscht. In fast allen Beispielen, die ich gefunden habe, ist der Knoten-Destruktor jedoch leer und einige Verwaltungsklassen behandeln die Zerstörung mit einer Art von Iteration und Delete. Ist der rekursive Destruktor aus Zuverlässigkeits- und / oder Stilsicht etwas schlecht?
Was folgt ist meine Umsetzung meines Verständnisses der beiden Ansätze.
Rekursive Destruktion:
%Vor%Und hier ist meine Auffassung von der Managementklasse, die mit der Zerstörung umgeht. Angenommen, ich hätte den folgenden DTOR für Knoten definiert:
%Vor%Ich würde die folgende LinkedList-Verwaltungsklasse und nachfolgende Haupt-
definieren %Vor%Wenn ich meine Ergebnisse richtig lese, machen meine beiden Implementierungen dasselbe.
In Bezug auf mein rekursives Zerstörungsbeispiel denke ich, dass ich fast immer eine Art Verwaltungsklasse benötigen werde, die eine Kopie des Kopfes enthält, wenn ich ein echtes Problem mit Code lösche, aber die Verwaltungsklasse nur den Kopf löschen muss. Wurzelknoten, um die Zerstörung der gesamten Datenstruktur sicherzustellen. Es fühlt sich eleganter an, aber ich habe mich mit Code beschäftigt, den ich für ordentlich gehalten habe.
Sollte die leitende Klasse dafür verantwortlich sein, dass alles richtig gelöscht wird? Oder ist es besser für die zugrunde liegende Datenstruktur, sich selbst zu reinigen? Gibt es irgendwelche Fehler, die nicht offensichtlich sind?
Danke!
- Jordanien
edit: Ein Gedanke ist mir eingefallen. Wenn ich eine ungeheuer lange Kette von Knoten habe, muss ich mich im ersten Beispiel um einen Stapelüberlauf während der Zerstörung kümmern, da die Rekursion gerade im Spiel ist?
edit2: Ich nehme an, es hätte offensichtlich sein müssen. Und jetzt fühle ich mich nur ein bisschen albern. Wenn ich mehr als 64910 Knoten auf meinem Computer habe, stürze ich ab. Die Rekursion stellt also eindeutig ein Problem dar.
Wenn Sie dies für verknüpfte Listen tun, tritt ein Problem mit dem Stapelspeicherverbrauch auf. Das Zerstören einer solchen verknüpften Liste führt zu einem rekursiven Verlauf von Node , während die Rekursionstiefe linear mit der Größe der verknüpften Liste wächst.
Machen Sie einfach das Experiment: Geben Sie mehrere Millionen Knoten in Ihre Liste ein und zerstören Sie sie dann. Ich wette, Sie werden den Stack-Überlauf bekommen (es sei denn, Sie haben Ihren Thread so konfiguriert, dass er eine enorme Stack-Größe reserviert). Besonders im Debug-Build laufen Sie sehr früh außerhalb des Stacks.
OTOH macht das für Bäume ok, zumindest aus technischer Sicht. Die Baumbereinigung wird in der Regel rekursiv implementiert, selbst wenn die obige rekursive Funktion zum Baum oder Node gehört, ist dies nicht wichtig.
Die Rekursionstiefe zum Zerstören des Baumes wächst logarithmisch mit der Baumtiefe, was in Ordnung ist.
Denken Sie an die Eigentumsrechte des verknüpften Elements.
Macht es Sinn, dass ein Node-Objekt die nächste Verwandtschaft besitzt? Es macht sicher Sinn, dass ein Node die angehängten Satellitendaten besitzt, also sollten Sie dies aufräumen, wenn der Node zerstört wird.
Die LinkedList besitzt ihre Knoten, daher sollte sie dafür verantwortlich sein, sie ohne In-Memory-Reste ordnungsgemäß zu zerstören.
Das LinkedList-Objekt sollte in der Lage sein, Knoten hinzuzufügen und zu entfernen, so dass es vom Standpunkt des Besitzers aus verantwortlich ist, sie zu bereinigen, indem beispielsweise alle Knoten in der Liste entfernt werden iterativ.
Tags und Links c++ recursion coding-style destructor