Wie lösche ich Knoten einer verknüpften Liste in C++ richtig?

Lesezeit: 5 Minuten

Ich habe das Gefühl, dass ich den Knoten nicht wirklich lösche und Speicher freigebe. Ich glaube, ich bewege nur Zeiger herum, also wenn ich die verknüpfte Liste drucke, druckt die Liste nicht das Element, das ich gelöscht habe. Meine Frage ist also, lösche ich den Knoten tatsächlich oder ordne ich einfach die Zeiger neu an, sodass es so aussieht, als würde ich die Knoten löschen (im Wesentlichen nur die Links unterbrechen, aber den Knoten nicht löschen)? Vielen Dank für jede Hilfe.

void SLL::deleteNode(int target){
Node *current = new Node;
Node *previous = new Node;

for (current = front->next, previous = front; current != NULL; current = current->next, previous=previous->next){
    if (previous->data == target && previous == front){
        front = previous->next;
        delete[] previous;
        return;
    //This if statement deletes the element if its the front
    }

    else {

        if (previous->data == target && previous->next == NULL){
            previous = NULL;
            delete[] current;
            return;
        //This if statement deletes the node if it is the back
        }


        else if (current->data==target)
        {
            previous->next = current->next;
            delete[] current;
            return;
        //This if statement deletes a node if it is in the middle
        }
    }
    }

    delete[] current;
    delete[] previous;
}

  • Warum verwenden Sie das Array löschen (delete [])-Version, wenn Sie erklären current und previous als Einzelinstanz?

    – Mathematiker1975

    1. März 2014 um 22:35 Uhr


  • Beginnen Sie Ihren Aufzählungsalgorithmus mit front->next ist besorgniserregend. Bitte Teilen Sie uns mit, dass Sie keinen vorab zugewiesenen „Kopf“-Knoten verwenden, der eigentlich keine Daten enthält. Es wird nicht benötigt. Und es sei denn, Sie haben Ihren Knoten mit zugewiesen new Node[n]du verwendest das falsche delete Operator.

    – WhozCraig

    1. März 2014 um 22:36 Uhr


  • Ich weiß nicht. Ich habe das versucht, es hat funktioniert. Bitte beantworten Sie die Frage.

    – WombatCombat

    1. März 2014 um 22:56 Uhr

  • Weiß nicht was ? Ob Ihr vorderer Zeiger ein Sentinel-Knoten ist? Ob Ihre Knoten mit Vektor-new ? Du hast den Code geschrieben, richtig? Und übrigens, die beiden Knoten, die Sie am Kopf dieser Funktion zuweisen, werden sofort durchgesickert, sodass ich Ihnen versichern kann, dass am Ende kein Speicher wiederhergestellt wird, unabhängig davon, ob Sie einen Zielknoten gelöscht haben oder nicht.

    – WhozCraig

    1. März 2014 um 23:09 Uhr


  • Sie delete[] ein Nullvektor in Ihrem zweiten Block, aber ich glaube nicht, dass die Kontrolle jemals in diesen Block gelangen kann, also denke ich, dass es strittig ist.

    – Beta

    1. März 2014 um 23:14 Uhr

Wie losche ich Knoten einer verknupften Liste in C richtig
Spock77

Node *current  = new Node;
Node *previous = new Node;

Dieser Code verursacht Speicherlecks – Sie löschen diesen Speicher niemals. Sie können Zeiger ohne Speicherzuordnung deklarieren:

Node *current  = nullptr;
Node *previous = nullptr;

delete löscht den Speicher des Zeigers, sodass Sie tatsächlich Knoten löschen. Aber mit löschen[] für die Node* ist falsches sollte nur für Arrays verwendet werden – der zugewiesene Speicher new[]. Unsachgemäße Verwendung führt zu undefiniertem Verhalten. Um also Knoten richtig zu löschen, löschen Sie sie mit dem Operator löschen.

Verwenden Sie Tools zur Erkennung von Speicherlecks, um festzustellen, ob es Speicherlecks in Ihrem Programm gibt.

Der Code zum Löschen eines Listenelements: Sagen wir, wir haben pHead, der auf den Kopf der Liste zeigt (aber es würde Ihnen viel mehr bringen, wenn Sie solche Dinge selbst schreiben):

Node* pCur  = pHead;
Node* pPrev = pCur;

while (pCur && pCur->data != target) {
    pPrev = pCur;
    pCur  = pCur->next;
}

if (pCur==nullptr)  // not found
   return NOT_FOUND;

if (pCur == pHead) {   // first element matches
    pHead = pCur->next;
} else {
    pPrev->next = pCur->next;
}

// pCur now is excluded from the list

delete pCur;     // deallocate its memory

Alternative Verwendung von Pointer To Pointer (Community-Zusatz)

Das Obige kann ein neues Licht annehmen, wenn Sie die tatsächlichen Zeiger verwenden in die Liste, um die Aufzählung durchzuführen. Das Folgende beginnt mit pp zugewiesen werden die Adresse des Kopfzeigers (nicht der Knoten, auf den er zeigt; der eigentliche Zeiger selbst). Wir gehen die Liste durch bis pp Halten Sie die Adresse eines Zeigers, der auf einen Knoten mit dem zu löschenden Ziel zeigt (könnte der Kopfzeiger sein, könnte ein next Zeiger in einem Knoten, macht keinen Unterschied). Der adressierte Zeiger wird auf seinen eigenen Knoten gesetzt next Wert, dann wird der Zielknoten entfernt.

Dies sollte wirklich in einem Debugger beobachtet werden, um zu sehen, wie es funktioniert, aber der Algorithmus ist bemerkenswert einfach, wenn man bedenkt, was wirklich vor sich geht:

Node **pp = &pHead;
while (*pp && (*pp)->data != target)
    pp = &(*pp)->next;

if (*pp)
{
    Node *victim = *pp;
    *pp = victim->next;
    delete victim;
}

Das ist alle davon. Und Sie erhalten die Entfernung von Kopfknoten, ohne dass Sie dies kostenlos tun müssen. Hoffe das hilft auch.

  • Danke. Ich werde ab diesem Zeitpunkt keine neuen mehr für sie verwenden. Obwohl meine Frage immer noch bleibt, wie lösche ich meinen Zielknoten? Ich weiß, dass Sie es angesprochen haben, aber können Sie es vielleicht etwas genauer erklären.

    – WombatCombat

    2. März 2014 um 0:17 Uhr

  • @ user3291106 – Ich stelle einen Beispielcode bereit. Aber es wäre viel nützlicher für Sie, es selbst zu schreiben. Probieren Sie jetzt die doppelt verknüpfte Liste aus und suchen Sie beispielsweise vom Ende aus.

    – Spock77

    2. März 2014 um 1:06 Uhr

  • @Alex Wie endet das wann pHead zeigt auf den zu löschenden Knoten? Folgen: Die While-Schleife wird übersprungen und tut nichts. pHead->next wird effektiv sich selbst zugewiesen, weil pPrev, pCurund pHead alle zeigen auf denselben Knoten. Der Kopfknoten wird dann mit zerstört delete pCur;, wodurch der gesamte Rest der Liste verwaist wird und alle drei Zeiger eine ungültige, unbestimmte Adresse enthalten. In einem Wort, Autsch.

    – WhozCraig

    2. März 2014 um 3:55 Uhr


  • @WhozCraig Vielen Dank für die Korrektur! Repariert. Obwohl mir das lieber wäre Benutzer3291106 erzähl mir davon 🙂 Ich brauche mich mit Code-Posts nicht zu beeilen, stimme zu.

    – Spock77

    2. März 2014 um 4:35 Uhr

  • @Alex Kein Problem. werfen Sie einen Blick auf den Nachtrag. Ich bin mir nicht sicher, ob Sie es schon einmal gesehen haben, aber es verdient einen Blick. Und +1 für das Festhalten an der Antwort.

    – WhozCraig

    2. März 2014 um 4:49 Uhr


989000cookie-checkWie lösche ich Knoten einer verknüpften Liste in C++ richtig?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy