C++에서 재귀 메서드를 사용할 때 double free 또는 corruption (fasttop)

Stack 클래스를 구현하고 해당 클래스를 사용하여 하노이 문제를 해결하려고했습니다.C++에서 재귀 메서드를 사용할 때 double free 또는 corruption (fasttop)

template<class Datatype> 
class Node 
{ 
    public: 
     Node() 
     { 
      next = NULL; 
      prev = NULL; 
     } 
     Node* getNext() 
     { 
      return next; 
     } 
     Node* getPrev() 
     { 
      return prev; 
     } 
     Datatype* getData() 
     { 
      return &data; 
     } 
     void changeNext() 
     { 
      next = NULL; 
     } 
     void changeNext(Node& nextNode) 
     { 
      next = &nextNode; 
     } 
     void changePrev() 
     { 
      prev = NULL; 
     } 
     void changePrev(Node& prevNode) 
     { 
      prev = &prevNode; 
     } 
     Node* addNext(Node &); 
     Node* addPrev(Node &); 
     void nodeDel(); 
     void addData(Datatype &); 
    private: 
     Node* next; 
     Node* prev; 
     Datatype data; 
}; 

template<class Datatype> 
class Stack 
{ 
    public: 
     Stack() : head(NULL) 
     { 

     } 
     virtual ~Stack() 
     { 
      Datatype temp; 
      while (pop(temp)); 
      cout << "Stack released all spaces" << endl; 
     } 
    public: 
     virtual int push(Datatype &); 
     virtual int pop(Datatype &); 
     virtual Datatype* peek(); 
    protected: 
     Node<Datatype> *head; 
}; 
template <class Datatype> 
int Stack<Datatype>::push(Datatype &new_data) 
{ 
    Node<Datatype> *pt_node = new Node<Datatype>; 
    if (pt_node == NULL) 
     return -1; 

    pt_node -> addData(new_data); 

    if (head == NULL) 
     head = pt_node; 
    else 
    { 
     pt_node -> addPrev(*head); 
     head = pt_node; 
    } 

    //cout << *(head -> getData()) << endl; 

    return 0; 
} 

template <class Datatype> 
int Stack<Datatype>::pop(Datatype &pop_data) 
{ 
    if (head == NULL) 
     return 0; 

    pop_data = *(head -> getData()); 

    if (head -> getNext() == NULL) 
    { 
     delete head; 
     head = NULL; 
    } 
    else 
    { 
     Node<Datatype>* temp = head; 
     head = head -> getNext(); 
     delete temp; 
    } 

    return 1; 
}

위 Stack class을 선언하고 또한 pop() 및 push() 기능을 구현 : 여기 내 코드입니다. 이제 하노이 클래스를 선언하고 함수를 구현합니다.

int main() 
{ 
    Hanoi test(STACK_DEEP); 
    test.workdone(STACK_DEEP, test.a_tower, test.b_tower, test.c_tower); 
    test.showret(); 

    return 0; 
}

출력은 다음과 같습니다 : 여기

class Hanoi 
{ 
    public: 
     Hanoi(int num) : a_tower(), b_tower(), c_tower() 
     { 
      deep = num; 
      int i; 
      for (i = num; i != 0; i --) 
       a_tower.push(i); 
     } 
    public: 
     void workdone(int, Stack<int>&, Stack<int>&, Stack<int>&); 
     void showret(); 
    public: 
     Stack<int> a_tower; 
     Stack<int> b_tower; 
     Stack<int> c_tower; 
     int deep; 
}; 

void Hanoi::workdone(int deep_num, Stack<int>& A, Stack<int>& B, Stack<int>& C) 
{ 
    int temp; 
    if (deep_num == 1) 
    { 
     A.pop(temp); 
     C.push(temp); 
    }  
    else 
    { 
     Hanoi::workdone(deep_num - 1, A, C, B); 
     A.pop(temp); 
     C.push(temp); 
     Hanoi::workdone(deep_num - 1, B, A, C); 
    } 
} 

void Hanoi::showret() 
{ 
    int temp; 
    while (c_tower.pop(temp) != 0) 
     cout << temp << endl; 
}

내 테스트 코드입니다

*** glibc detected *** ./3_4: double free or corruption (fasttop): 0x090c0038 ***

나는 하노이가 호출 될 때 ~이 문제가 발생 생각하지만, 난 정말 이유를 알고하지 않습니다 이것은 일어날 것입니다. my_node.h

#include <iostream> 

using namespace std; 

template<class Datatype> 
class Node 
{ 
    public: 
     Node() 
     { 
      next = NULL; 
      prev = NULL; 
     } 
     Node* getNext() 
     { 
      return next; 
     } 
     Node* getPrev() 
     { 
      return prev; 
     } 
     Datatype* getData() 
     { 
      return &data; 
     } 
     void changeNext() 
     { 
      next = NULL; 
     } 
     void changeNext(Node& nextNode) 
     { 
      next = &nextNode; 
     } 
     void changePrev() 
     { 
      prev = NULL; 
     } 
     void changePrev(Node& prevNode) 
     { 
      prev = &prevNode; 
     } 
     Node* addNext(Node &); 
     Node* addPrev(Node &); 
     void nodeDel(); 
     void addData(Datatype &); 
    private: 
     Node* next; 
     Node* prev; 
     Datatype data; 
}; 

template<class Datatype> 
class Stack 
{ 
    public: 
     Stack() : head(NULL) 
     { 

     } 
     virtual ~Stack() 
     { 
      Datatype temp; 
      while (pop(temp)); 
      cout << "Stack released all spaces" << endl; 
     } 
    public: 
     virtual int push(Datatype &); 
     virtual int pop(Datatype &); 
     virtual Datatype* peek(); 
    protected: 
     Node<Datatype> *head; 
}; 

template <class Datatype> 
Node<Datatype>* Node<Datatype>::addNext(Node<Datatype>& exi_node) 
{ 
    if (exi_node.getNext() == NULL) 
    { 
     changePrev(exi_node); 
     exi_node.changeNext(*this); 
    } 
    else 
    { 
     Node* next = exi_node.getNext(); 
     changePrev(exi_node); 
     changeNext(*next); 
     exi_node.changeNext(*this); 
     next -> changePrev(*this); 
    } 
    return &exi_node; 
} 

template <class Datatype> 
Node<Datatype>* Node<Datatype>::addPrev(Node<Datatype>& exi_node) 
{ 
    if (exi_node.getPrev() == NULL) 
    { 
     changeNext(exi_node); 
     exi_node.changePrev(*this); 
    } 
    else 
    { 
     Node* prev = exi_node.getPrev(); 
     changePrev(*prev); 
     changeNext(exi_node); 
     exi_node.changePrev(*this); 
     prev -> changeNext(*this); 
    } 
    return &exi_node; 
} 

template<class Datatype> 
void Node<Datatype>::nodeDel() 
{ 
    if (prev == NULL && next == NULL) 
     ; 
    else if (prev == NULL) 
    { 
     Node* next = getNext(); 
     next -> changePrev(); 
    } 
    else if (next == NULL) 
    { 
     Node* prev = getPrev(); 
     prev -> changeNext(); 
    } 
    else 
    { 
     Node* next = getNext(); 
     Node* prev = getPrev(); 
     next -> changePrev(*prev); 
     prev -> changeNext(*next); 
    } 
    delete this; 
    return; 
} 

template <class Datatype> 
void Node<Datatype>::addData(Datatype &new_data) 
{ 
    data = new_data; 
} 

template <class Datatype> 
int Stack<Datatype>::push(Datatype &new_data) 
{ 
    Node<Datatype> *pt_node = new Node<Datatype>; 
    if (pt_node == NULL) 
     return -1; 

    pt_node -> addData(new_data); 

    if (head == NULL) 
     head = pt_node; 
    else 
    { 
     pt_node -> addPrev(*head); 
     head = pt_node; 
    } 

    //cout << *(head -> getData()) << endl; 

    return 0; 
} 

template <class Datatype> 
int Stack<Datatype>::pop(Datatype &pop_data) 
{ 
    if (head == NULL) 
     return 0; 

    pop_data = *(head -> getData()); 

    if (head -> getNext() == NULL) 
    { 
     delete head; 
     head = NULL; 
    } 
    else 
    { 
     Node<Datatype>* temp = head; 
     head = head -> getNext(); 
     delete temp; 
    } 

    return 1; 
} 

template <class Datatype> 
Datatype* Stack<Datatype>::peek() 
{ 
    if (head == NULL) 
     return NULL; 
    return (this->head)->getData(); 
}

3_4.h

#include <iostream> 
#include "my_node.h" 

using namespace std; 

class Hanoi 
{ 
    public: 
     Hanoi(int num) : a_tower(), b_tower(), c_tower() 
     { 
      deep = num; 
      int i; 
      for (i = num; i != 0; i --) 
       a_tower.push(i); 
     } 
    public: 
     void workdone(int, Stack<int>&, Stack<int>&, Stack<int>&); 
     void showret(); 
    public: 
     Stack<int> a_tower; 
     Stack<int> b_tower; 
     Stack<int> c_tower; 
     int deep; 
}; 

void Hanoi::workdone(int deep_num, Stack<int>& A, Stack<int>& B, Stack<int>& C) 
{ 
    int temp; 
    if (deep_num == 1) 
    { 
     A.pop(temp); 
     C.push(temp); 
    }  
    else 
    { 
     Hanoi::workdone(deep_num - 1, A, C, B); 
     A.pop(temp); 
     C.push(temp); 
     Hanoi::workdone(deep_num - 1, B, A, C); 
    } 
} 

void Hanoi::showret() 
{ 
    int temp; 
    while (c_tower.pop(temp) != 0) 
     cout << temp << endl; 
}

3_4.cpp

#include <iostream> 
#include "3_4.h" 

using namespace std; 

#define STACK_DEEP 4 

int main() 
{ 
    Hanoi test(STACK_DEEP); 
    test.workdone(STACK_DEEP, test.a_tower, test.b_tower, test.c_tower); 
    test.showret(); 

    return 0; 
}

명령 : 여기

는,이 결과를 얻을 수있는 전체 코드를 게시 나는 다음을 사용한다 :

,269,945,

출처

2014-03-04 Shanpei Zhou

'Node' 클래스가 아직 없습니다. 질문에 정의를 삽입하거나 오류를 복제 한 실제 예제 링크를 제공하십시오. – Tim

나는 재 편집했다. 귀하의 조언에 감사드립니다. –

요즘 누구도 디버거를 사용하는 방법을 모르는 사람입니까? – hildensia

는 코드은 필요 이상으로 더 복잡한 (혼란)이지만, 오류가 노드 :: addPrev 최소한의 수정이 함수의 구현을 변경하는 것입니다

의 잘못된 구현으로 요약된다 :

template <class Datatype> 
    Node<Datatype>* Node<Datatype>::addPrev(Node<Datatype>& exi_node) 
    { 
     exi_node.prev = this; 
     this->next = &exi_node; 
     return &exi_node; 
    }

적절한 수정 간단한 구현 스택 및 노드 클래스를 변경 포함 할 것이다 - 이전 덧글이 언급 한 것처럼, 그것은 이중 연결리스트 일 필요는 없습니다.

출처

2014-03-04 23:04:42 ganz

C++에서 재귀 메서드를 사용할 때 double free 또는 corruption (fasttop)

답변

관련 문제