C++: doppelt frei oder Korruption (fasttop)

Question

Ich versuche, den Knoten zu finden, wo der Zyklus in der Liste beginnt. Das zurückgegebene Ergebnis ist korrekt. Jedoch ein Fehler unter Angabe * Fehler in ./Lösung: doppelt frei oder Korruption (FastTop): 0x0000000000b3e030 Abgebrochen wird angezeigt. Ich sah einige andere ähnliche Probleme, und ich denke, das Problem ist mit temp1=temp;. Aber ich weiß nicht, wie ich dieses Problem lösen soll. Wie wird es korrigiert? Auch warum tritt dieser Fehler auf?

ListNode* Solution::detectCycle(ListNode* A) { 
    ListNode* temp = A; 
    ListNode* temp1 = A; 

    while(temp->next!=NULL && temp->next->next!=A->next){ 

     temp1 = temp; 
     temp = temp->next; 
     temp1->next=A->next; 
    } 
    if(temp->next==NULL) { 
     temp->val=-1; 
     delete temp1; 
     return temp; 

    } 
    else { 
     temp= temp->next; 
     delete temp1; 

     return temp; 
    } 

} 

Vielen Dank.

Answer 1

Als direkte Antwort stürzt Ihr Code ab, weil Sie auf Knoten zugreifen, die bereits frei sind. Neben dem Zugriff löschen Sie einen Knoten, der bereits gelöscht wurde. Diese "doppelte Freiheit" wird fast immer zu einem Crash oder anderem Chaos führen. Ein starkes Verständnis der Heap-Mechanik in C/C++ wird Ihnen eine Menge Elend ersparen, es lohnt sich zu lernen.

Ich bin mir nicht sicher, was die Anforderungen sind, aber ich glaube, dass Sie versuchen, nach einer zirkulären verknüpften Liste zu suchen. Ich weiß nicht, warum Sie einen der Knoten in einer 'detect'-Methode löschen. Versuchen Sie, die Schleife zu durchbrechen? Wenn dies der Fall ist, sind alle Knoten immer noch in der Liste, so dass nichts gelöscht wird. Ändern Sie einfach den Befehl -> neben nullptr auf dem Knoten, der eine Schleife bildet.

Hier ist ein Beispielcode aus Ihrem Original. Ich habe es mit Ihrem Code als Basis erstellt und dann mit dem Debugger debugged. Ein effektiver Softwareentwickler ist ein Meister des Debuggers, umarmen Sie es. Es ist ein minimales, vollständiges und überprüfbares Beispiel, wie in den Kommentaren beschrieben.

Ich habe ein paar Tests als ein Beispiel für 'Anwendungsfälle', keine Schleife, degenerierte Schleife, längere Schleife. Als Softwareingenieure ist es ein großer Teil unserer Arbeit, über Fehlerfälle nachzudenken, die oft an den Grenzen auftreten. Es könnte andere geben, die ich nicht behandelt habe.

Wie in den Kommentaren erwähnt, zeigt die Kompilierung oder ein einzelner erfolgreicher Anwendungsfall keine fehlerfreie Software an. Strenge Tests sind notwendig, um Vertrauen zu gewinnen. Diese Art von Tests wird oft als "Unit Testing" bezeichnet. Es gibt eine große Menge an Literatur zu diesem Thema.

#include <iostream> 

struct ListNode 
{ 
    int val; 
    ListNode* next; 
}; 

//Look for a loop back to A 

ListNode* detectCycle(ListNode* A) { 
    if(A == nullptr) // can't be a loop if list is empty 
     return nullptr; 

    ListNode* temp = A; 


    while(temp->next!=NULL && temp->next !=A){ 
     temp = temp->next; 
    } 
    if(temp->next==NULL) { 
     return nullptr; // No loop 

    } 
    else { 
     return temp; // Node where loop starts, may be A itself 
    } 

} 

int main(int argc,char* arv[]) 
{ 
    ListNode *a = new ListNode; 
    ListNode *loop = nullptr; 
    loop = detectCycle(a); 
    if(loop == nullptr) 
    std::cout << "Case 1 passed" << std::endl; 
    a->next = a; 
    loop = detectCycle(a); 
    if(loop == a) 
    std::cout << "Case 2 passed" << std::endl; 
    ListNode *b = new ListNode; 
    ListNode *c = new ListNode; 
    ListNode *d = new ListNode; 
    a->next = b; 
    b->next = c; 
    c->next = d; 
    d->next = a; 
    loop = detectCycle(a); 
    if(loop == d) 
    std::cout << "Case 3 passed" << std::endl; 
    loop = detectCycle(b); 
    if(loop == a) 
    std::cout << "Case 4 passed" << std::endl; 

    return 0; 
}