Двойной связанный список получает ошибку «указатель на освобождение не был выделен» - PullRequest
Новая
       8

Двойной связанный список получает ошибку «указатель на освобождение не был выделен»

0 голосов
/ 30 ноября 2011

Я создал класс двойных связанных списков и пытаюсь использовать его с классом Vector, который я создал, чтобы создать вектор связанных списков, однако в конце программы кажется, что я получаю сообщение об ошибке malloc: *** error for object 0x100100be0: pointer being freed was not allocated Я предполагаю, что это связано с деструктором, и именно на это 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 не был включен.Если это необходимо, чтобы указать мне правильное направление, дайте мне знать.

Спасибо!

1 Ответ

8 голосов
/ 30 ноября 2011

Вы не подчиняетесь правилу 3: If you have either of a destructor, a copy constructor or an assignment operator implemented, you should implement all three. Я прошелся по вашему коду, и, похоже, было создано множество копий объектов, а затем уничтожено, но, поскольку копирование выполняется неправильно, уже уничтоженная память снова удаляется..

Правильно выполните их, и проблема больше не будет.

РЕДАКТИРОВАТЬ:

Я только что закончил базовую реализацию этих: 

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