c++ - 双链表出现错误 'pointer being freed was not allocated'

Question

我创建了一个双链表类，并试图将它与我创建的 Vector 类一起使用，以便制作一个链表 vector ，但是在程序结束时，我似乎遇到了一个错误malloc:对象 0x100100be0 的 *** 错误:未分配正在释放的指针我假设这与析构函数有关，这也是 Xcode 指向我的地方。我该如何规避这个？我认为我的析构函数工作正常，但我想我错了。

测试文件:

#include <iostream>
#include <string>
#include "Vector.h"
#include "doubleLL.h"

using namespace std;

int main (int argc, const char * argv[])
{

    Vector<double_llist<string> > listWords(27);
    double_llist<string> numbers;
    numbers.push_back("one");
    numbers.push_back("two");
    numbers.push_back("three");
    listWords[0] = numbers;
    listWords[0].print();
}

doubleLL.h:

#ifndef DOUBLELL_H
#define DOUBLELL_H
#include <iostream>
using namespace std;

template <class T>
class double_llist {
private:
    struct node {
        T data;
        node* prev;
        node* next;
        node(T t, node* p, node* n) : data(t), prev(p), next(n) {}
        int count;
    };
    node* head;
    node* tail;

public:
    double_llist() : head( NULL ), tail ( NULL ) {}
    template<int N>
    double_llist( T (&arr) [N]) : head( NULL ), tail ( NULL )
    {
        for( int i(0); i != N; ++i)
            push_back(arr[i]);
    }
    bool empty() const { return ( !head || !tail ); }
    operator bool() const { return !empty(); } 
    void push_back(T);
    void push_front(T);
    T pop_back();
    void removeNode(node *);
    void print();

    node* search(T data) {
        node *tempNode;
        if (head == NULL) {
            // List is empty
            return NULL;
        } else {
            tempNode = head;
            while (tempNode != NULL) {
                if (tempNode->data == data) {
                    tempNode->count += 1;
                    if (tempNode->count >= 4) {
                        // Push tempNode to front of linked list
                        push_front(tempNode->data);
                        head->count = tempNode->count;
                        removeNode(tempNode);
                    }
                    return tempNode;
                } else {
                    tempNode = tempNode->next;
                }
            }
        }
        return NULL;
    }

    ~double_llist()
    {
        while(head)
        {
            node *temp(head);
            head = head->next;
            delete temp;
        }
    }

    double_llist& operator = ( const double_llist& other )
    {
        if (this == &other) {
            return *this;
        }
        while (!empty()) {
            pop_back();
        }
        for (node *itr = other.head->next; itr != other.tail; ++itr) {
            tail = new node(other.head->data, itr, NULL);
        }
        return *this;

    }


    double_llist(const double_llist& other)
    {
        head = new node;
        tail = new node;
        head->tail = tail;
        tail->prev = head;
        *this = other;
    }
};

template <class T>
void double_llist<T>::push_back(T data)
{
    tail = new node(data, tail, NULL);
    if( tail->prev )
        tail->prev->next = tail;

    if( empty() )
        head = tail;
}

template <class T>
void double_llist<T>::push_front(T data) {
    head = new node(data, NULL, head);
    if( head->next )
        head->next->prev = head;

    if( empty() )
        tail = head;
}


template <class T>
T double_llist<T>::pop_back()
{
    node* temp(tail);
    T data( tail->data );
    tail = tail->prev ;

    if( tail )
        tail->next = NULL;
    else
        head = NULL ;

    delete temp;
    return data;
}

template <class T>
void double_llist<T>::removeNode(node *n) {
    if(n == this->head) {
        this->head=this->head->next;
        this->head->prev = NULL;
    } else if (n==this->tail) {
        this->tail=this->tail->prev;
        this->tail->next = NULL ;
    } else {
        n->prev->next = n->next;
        n->next->prev = n->prev;
    }
}

template <class T>
void double_llist<T>::print() {
    node* temp;
    temp = this->head;
    int i = 0;
    while(temp != NULL)
    {
        if (i < 3) {
            cout << temp->data << endl;
            temp=temp->next;
            ++i;
        } else {
            return;
        }
    }
    cout << endl;
    return;
}

#endif

错误似乎来自 doubleLL，因此未包含 Vector.h。如果需要帮助我指明正确的方向，请告诉我。

谢谢!

Answer 1

你没有遵守规则 3:如果你实现了析构函数、复制构造函数或赋值运算符，你应该实现所有这三个。我单步执行了你的代码，出现了是创建了很多对象拷贝然后又销毁了，但是由于复制不正确，已经销毁的内存又被删除了。

正确执行这些，问题就没有了。

编辑:

我刚刚完成了这些的基本实现:

double_llist& operator = ( const double_llist& other )
{
   head = NULL;
   tail = NULL;
   return *this;
}
double_llist(const double_llist& other)
{
   head = NULL;
   tail = NULL;
}

代码不再崩溃。

第二次编辑:

double_llist& operator = ( const double_llist& other )
{
   head = NULL;
   tail = NULL;
   node* otherNode = other.head;
   while ( otherNode )
   {
  push_back(otherNode->data);
  if ( otherNode == other.tail )
     break;
  otherNode = otherNode->next;
   }
   return *this;
}
double_llist(const double_llist& other)
{
   head = NULL;
   tail = NULL;
   node* otherNode = other.head;
   while ( otherNode )
   {
  push_back(otherNode->data);
  if ( otherNode == other.tail )
     break;
  otherNode = otherNode->next;
   }
}