Ошибка сегментации (ядро сброшено), когда я удаляю указатель

Question

Я пытаюсь удалить дубликаты из связанного списка и столкнулся с проблемой, которая, вероятно, очевидна и проста, но я не использовал 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Эд где-то еще? Это потому что это было newвыход за пределы текущей области?

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

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

Edit1: сделал его более информативным согласно ответам на мое сообщение. Edit2: добавлено правило 3 методов

Answer 1

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

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

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

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

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

delete temp;

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

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

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

Следующая и предыдущая deleteд. Который называет их деструкторами, deleteОбращаясь к двум узлам, к которым они прикасаются, он вызывает смертельную бурю, которая уничтожит все узлы в списке.

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

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

Answer 2

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

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

Так как вы распределили узлы с new мы можем изменить

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

в

delete temp;

Answer 3

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

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

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

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

LE:

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

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

Answer 4

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

Вам разрешено delete вещи newв другом месте Это не проблема, если вы указываете действительный адрес. Ошибка сегмента обнаруживается, когда вы затем пытаетесь использовать один из указателей, которые указывали наdeleteРед. адрес.

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

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

Потому что мне может понадобиться что-то сделать с деструктором моего Узла.

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

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

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

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

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

Answer 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() просто выделяйте и освобождайте память кучи, не обращая внимания на состояние самой памяти.