Удаление узлов в двусвязном списке (C ++)

Question

У меня проблемы с пониманием, почему при создании двух или более узлов (как показано ниже) функция void del_end() удаляет только char name[20], а не весь узел.Как я могу исправить эту проблему без утечки памяти?

#include <iostream>
using namespace std;

struct node
{
    char name[20];
    char profession[20];
    int age;
    node *nxt;
    node *prv;
};

node *start_ptr = NULL;

void del_end()
{
    node *temp, *temp2;
    temp = start_ptr;
    if (start_ptr == NULL)
        cout << "Can't delete: there are no nodes" << endl;
    else if (start_ptr != NULL && start_ptr->nxt == NULL)
    {start_ptr=NULL;}
    else
    {
    while (temp->nxt != NULL)
    {
        temp = temp->nxt;
    }
    temp2=temp->prv;
    delete temp;
    temp->nxt= NULL;
    }
}

Answer 1

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

while (temp->nxt != NULL) 
{ 
    temp = temp->nxt; 
} 
temp2=temp->prv; 
delete temp2; 
temp->nxt= NULL; 

Это ваша проблема.Измените это на это:

while (temp->nxt != NULL) 
{ 
    temp = temp->nxt; 
} 
temp2=temp->prv; 
delete temp; 
temp2->nxt= NULL;

И я верю, что это будет работать так, как задумано.Это сохраняет следующий за последним узлом, удаляет конец и затем устанавливает нулевой указатель рядом с последним узлом в ноль, делая его последним.

Answer 2

У вашего кода есть некоторые проблемы, наихудшее из них:

temp2=temp->prv;
delete temp2;
temp->nxt= NULL;

Вы удаляете следующий за последним узел, оставляя любые указатели на него висящими, и теряете последний узел.*

Но если вы отправите больше реального кода, мы расскажем вам больше.

РЕДАКТИРОВАТЬ:
Вот слегка исправленная версия del_end (иесть еще много возможностей для улучшения).

void del_end()
{
  if (start_ptr == NULL)
  {
    cout << "Can't delete: there are no nodes" << endl;
    return;
  }

  if (start_ptr->nxt == NULL)
  {
    delete start_ptr;
    start_ptr = NULL;
    return;
  }

  node *nextToLast = start_ptr;
  node *last = start_ptr->nxt;

  while(last->nxt != NULL)
  {
    nextToLast = last;
    last = last->nxt;
  }

  delete last;
  nextToLast->nxt = NULL;

  return;
}

Обратите внимание, что это не предполагает, что ссылки prev правильные, что здесь представляется разумным.

Answer 3

Если вас беспокоит память, я настоятельно рекомендую научиться работать с Valgrind http://valgrind.org/. Это отличный инструмент.Valgrind делит утечки памяти на 3 категории:

• «определенно потерян» - указатель на динамически распределенную память потерян, и нет никакого способа восстановить ее
• «возможно потерян» - указатель надинамически распределенная память указывает на внутреннюю часть блока и может быть не связана
• «все еще достижимо» - указатель на динамически распределенную память все еще существует, но память никогда не освобождалась в конце выполнения программ

Запуск Valgrind также очень прост.Вот ссылка на руководство пользователя http://valgrind.org/docs/manual/manual.html. Некоторые полезные флаги при запуске valgrind:

• --leak-check=<no|summary|yes|full>
• --show-reachable=<no|yes>

Теперь я бы удалил узел из двусвязного списка:

// if the node to be removed is the head node
if (nodeToRemove->prev == NULL) {
    // reassign the head node pointer
    start_ptr = nodeToRemove->next;
} else {
    // correct previous node pointer
    nodeToRemove->prev->next = nodeToRemove->next;
}

// if the node to be removed node is the tail node
if (nodeToRemove->next == NULL) {
    // reassign the tail node pointer
    end_ptr = nodeToRemove->prev;
} else {
    // correct next node pointer
    nodeToRemove->next->prev = nodeToRemove->prev;
}

// deallocate memory
delete(nodeToRemove);
nodeToRemove = NULL;

Просто объявите node *end_ptr = NULL; после того, как вы объявите start_ptr и когда вы добавите узел в список, убедитесь, чтоend_ptr всегда указывает на конец списка ... и если вы добавляете в конец списка, это легко ... просто укажите end_ptr на добавляемый узел.

Вы также можете оставить указатель на хвост, если вам всегда нужно удалить последний узел.Поэтому, когда у вас есть узел, который вы хотите удалить, я просто проверяю, является ли он узлом head / tail, переназначаю указатели next / prev и освобождаю память.

Кстати ... Я взял это из моего Cреализации, поэтому, если синтаксис выключен, я прошу прощения ... но логика есть.

Надеюсь, что помогает.

Answer 4

delete temp2;

БУДЕТ удалить весь узел.