在C++中使用递归方法时发生双重空闲或损坏（fasttop）

我实现了一个Stack类，并试图利用该类来解决河内问题。这里是我的代码：在C++中使用递归方法时发生双重空闲或损坏（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()功能。现在，我宣布我的河内班级和实施职能。

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; 
}

这里是我的测试代码：

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

    return 0; 
}

输出是：

*** 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; 
}

命令我用：

g++ -Wall 3_4.cpp -o 3_4

来源

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++中使用递归方法时发生双重空闲或损坏（fasttop）

回答

相关问题