Ошибка сегментации (сбрасывание ядра) при удалении указателя

Я пытаюсь удалить дубликаты из связанного списка и столкнулся с проблемой, которая, вероятно, очевидна и понятна, но я не использовал C++ в течение многих лет, и я не мог узнать, что я делаю неправильно, чтение подобных вопросов на SO.

Ниже приведены части моего кода. Я удалил ненужные части (например, конструкторы, другие методы и т.д.).

template<class T>
class Node {
  Node() : data(NULL), next(NULL), prev(NULL) {}
  explicit Node(T d) : data(d), next(NULL), prev(NULL) {}
  explicit Node(T d, Node<T> *nxt, Node<T> *prv) : data(d), next(nxt),    prev(prv) {}
  ~Node() { delete next; delete prev; }

  T data;
  Node *next;
  Node *prev;
};

template<class T>
class LinkedList {
  LinkedList() : head(NULL) {}
  explicit LinkedList(Node<T> *head_node) : head(head_node) {}
  LinkedList& operator=(const LinkedList &copy_list);
  ~LinkedList(); //didn't implement this but I guess delete head is all?

  Node<T>* head;
};


template<class T>
LinkedList<T> RemoveDuplicates(const LinkedList<T> &linked_list) {
  //my = overload creates a whole new list with the same data as the original one
  LinkedList<T> result = linked_list; 

  Node<T> *cur = result.head;
  Node<T> *prev = NULL;

  while (cur) {
    if (...) { //duplicate found  
      Node<T> *temp = cur;
      prev->next = cur->next;
      cur = cur->next;
      cur->prev = prev;
      free(temp); //Here is my problem!!!
    }
    else {
      prev = cur;
      cur = cur->next;
    }
  }
  return result;
}

Итак, сначала я сделал delete temp, и я получил Segmentation fault. Тогда я понял, что вы только delete, что вы new. Достаточно справедливо, но я new вводя каждый Node при построении всего списка в main:

Node<char> *h = new Node<char>('H'); //I have a constructor to handle this
Node<char> *e = new Node<char>('E');
Node<char> *l1 = new Node<char>('L');
Node<char> *l2 = new Node<char>('L');
Node<char> *o = new Node<char>('O');

h->next = e;
h->prev = NULL;

e->next = l1;
e->prev = h;

//and so on

Итак, почему мне не разрешено delete что-то, что было new ed где-то еще? Это потому, что он был new ed за пределами текущей области?

Во-вторых, free пространство работает отлично, но, очевидно, это не так, потому что я не malloc, а new ed!

Что я делаю неправильно? Как правильно удалить удаленный файл node?

Edit1: сделал это более наглядным в соответствии с ответами на мой пост Edit2: добавлено правило из 3 методов

Ответы

Ответ 1

Это дополнение к другим ответам, которые правильно идентифицируют и решают проблему немедленного OP. Быстрая прогулка - хотя требуется объяснить, что будет дальше.

  Node<T> *temp = cur;
  prev->next = cur->next;
  cur = cur->next;
  cur->prev = prev;

В этот момент temp не был очищен, поэтому next и prev все еще указывают на два узла, которые использовали для окружения cur и теперь связаны между собой. Это вызовет серьезные проблемы, если не для:

  free(temp); //Here is my problem!!!

free терпит неудачу, потому что значение, на которое указывает temp, было назначено новым. Ответ NathanOliver охватывает это, но скрытый ниже - то, что произойдет с

delete temp;

Это вызовет деструктор для очистки как хороший маленький объект. К сожалению, деструктор Node выглядит следующим образом:

~Node() { delete next; delete prev; }

temp->next по-прежнему указывает на живой node. Таким образом, temp->prev.

Далее и prev get delete d. Который называет их деструкторы, delete соединяющих два узла, которые они касаются, и вызывает смертельный штурм, который уничтожит все Узлы в списке.

Если двойные удаления не уничтожают программу в первую очередь. Каждая связанная node будет пытаться delete node, которая просто deleted их. Нехорошо.

Коэффициенты довольно хороши, что деструктор Node должен просто следить за собой и оставить уничтожение другого Node классу LinkedList.

Ответ 2

Вы не можете использовать free(), если вы выделили память с помощью new

Вы можете использовать malloc() с free() или new с помощью delete. Вы также не должны использовать malloc() и free() с объектами, поскольку они не вызывают конструктор объектов и деструктор в отличие от new и delete

Итак, поскольку вы выделили узлы с помощью new, мы можем изменить

free(temp); //Here is my problem!!!

к

delete temp;

Ответ 3

В этом случае очень важно иметь код конструктора, а также деструктора.

По умолчанию вы должны использовать "новый" в конструкторе и "удалить" в деструкторе. Чтобы быть более конкретным, очень важно выделить все ресурсы, которые вам нужны в конструкторе, и освободить их в деструкторе, таким образом, вы убедитесь, что у вас нет утечек памяти.

free(temp);//You don't need this, also you don't need delete.

Пожалуйста, разместите свой конструктор и код деструктора.

L.E:

Я думаю, вы должны сделать что-то вроде этого:

template<class T>
class LinkedList
{
  private:
    struct Node {
        T m_data;
        Node *m_next;
        Node *m_prev;
    };
    Node* m_first;
    Node* m_last;
    int m_count;
  public:
    LinkedList();
    ~LinkedList();
    T GetFirst();
    T GetLast();
    void AddNode(T node);
    void RemoveAt(int index);
    T GetAt(int index);
    int Count();
};

//constructor
template <typename T>
LinkedList<T>::LinkedList(){
    m_count = -1;//-1 == "The list is empty!
}

template <typename T>
void LinkedList<T>::AddNode(T data){
    Node* temp = new Node; //new is called only here -> delete is called in destructor or in RemoveAt
    temp->m_data = data;
    if (m_count > -1){//If the list contains one or more items
        temp->m_next = m_first;
        temp->m_prev = m_last;
        m_last->m_next = temp;
        m_last = temp;
        m_count++;
    }
    else if (m_count == -1)
    {//If no items are present in the list
        m_first = temp;
        m_first->m_next = temp;
        m_first->m_prev = temp;
        m_last = temp;
        m_last->m_next = temp;
        m_last->m_prev = temp;
        m_count = 0;
    }
}

template <typename T>
void LinkedList<T>::RemoveAt(int index){
    if (index <= m_count)//verify this request is valid
    {
        Node* temp = m_last;
        for (int i = 0; i <= index; ++i){
            temp = temp->m_next;
        }
        temp->m_prev->m_next = temp->m_next;
        temp->m_next->m_prev = temp->m_prev;
        delete temp;
        m_count--;
    }
}

template <typename T>
T LinkedList<T>::GetAt(int index)
{
    Node* temp = m_first;
    if (index <= m_count && index > -1){
        int i = 0;
        while(i < index){
            temp = temp->m_next;
            i++;
        }
    }
    return temp->m_data;
}

template <typename T>
T LinkedList<T>::GetFirst() {
    return m_first->data;
}

template <typename T>
T LinkedList<T>::GetLast(){
    return m_last->data;
}

template <typename T>
int LinkedList<T>::Count(){
    return m_count;
}

template <typename T>
LinkedList<T>::~LinkedList(){
   while(m_count > -1){
        Node* temp = m_first;
        m_first = temp->m_next;
        delete temp;//delete in destructor
        m_count--;
    }
}

Ответ 4

Так почему я не могу удалить что-то, еще? Это потому, что оно появилось за пределами текущей области?

Вам разрешено delete вещи new ed в другом месте. Это не проблема, если вы указываете на действительный адрес. Сег-ошибка появляется, когда вы пытаетесь использовать один из указателей, указывающих на адрес теперь delete ed.

Во-вторых, освобождение пространства отлично работает, но я чувствую, что, как обман!

Использовать free следует только при использовании malloc и delete, когда вы использовали new. Вы никогда не должны смешивать их. Кроме того, после delete, привыкнуть к присваиванию переменной NULL переменной-указателю.

Потому что мне могут понадобиться вещи, которые нужно сделать для моего деструктора Node.

Класс, инкапсулирующий данные, должен также выполнять собственное управление памятью. Например, LinkedList должен управлять памятью узлов.

Это означает, что если у вас есть что-то похожее на LinkedList<T>::add(Node<T> *data), вы должны вместо этого рассмотреть что-то вроде LinkedList<T>::add(T data); то сам класс списка позаботится об обработке узлов.

В противном случае вы рискуете отправить в список new ed Node, затем список delete внутри него в какой-то момент, но где-то еще, клиент списка по-прежнему содержит ссылку на текущую версию, недействителен node. Когда клиент пытается его использовать, снова bam!: seg-fault.

Что я делаю неправильно? Как правильно удалить удаленный файл node?

Помимо смешивания new с free s, segfault, скорее всего, запускается недопустимым доступом к памяти, поэтому вы должны найти указатель, который больше не указывает на допустимую (т.е. не deleted) память.

Ответ 5

Есть много ответов о том, что new/delete и malloc()/free() всегда должны быть спарены так, но я чувствую, что нужно точно сказать, почему именно.

Как и при инициализации,

Node<char> *h = new Node<char>('H');

ключевое слово new возвращает полностью типизированный указатель объекта объекта, определенный в самом выражении, тогда как malloc() просто выделяет заданное пространство памяти без присвоения типа, и поэтому возвращает void*. Кроме того, new/delete имеет дело с памятью из Free Store, а malloc()/free() выделяет/освобождает память в куче, хотя некоторые компиляторы могут реализовать new/free в терминах malloc()/free в некоторых случаях.

Также важно, чтобы new и delete вызывали конструктор и деструктор соответственно, а malloc() и free() просто выделяли и освобождали память кучи, не обращая внимания на состояние самой памяти.