Реализация функции pop () в связанном списке (C ++)
Я в целом немного смущен идеей связанных списков. Поэтому я пытаюсь реализовать некоторые функции, которые помогут мне понять.
struct Node {
string val;
Node* next;
Node* prev;
};
struct Stew {
Node* first;
Node* last;
};
Итак, здесь у Stew есть специальные указатели на передний элемент и последний элемент.
Я пытаюсь удалить первый элемент (поп).
Поэтому я попытался сделать это следующим образом, и я не могу найти, в чем ошибка:
void pop (Stew& q) {
assert (!isEmpty(q));
q.first = q.first->next;
q.first -> prev = NULL;
}
Любая помощь будет оценена, спасибо!
Кстати, я сейчас использую C ++ 98, а не C ++ 11.
Решение
Вы забыли освободить память удаленного узла с помощью delete и вы не позаботились о том, чтобы список составлял ровно один элемент. Потому что, если это так, то после
q.first = q.first->next;
q.first является NULL, Затем вы пытаетесь разыменовать q.first в следующей строке:
q.first -> prev = NULL;
Не делайте этого шага, если список был оригинальным длиной в один элемент и впоследствии пустым. Вместо этого позаботьтесь о q.last который больше не будет указывать на выделенную память:
q.first = q.first->next;
if(q.first)
q.first->prev = NULL;
else
q.last = NULL;
(Хотя в зависимости от реализации остальной части связанного списка блок else не понадобится, поскольку информация о том, является ли список пустым, полностью содержится либо в q.last или же q.first)
Также pop обычно возвращает удаленное значение. Ваш pop не делает этого
Другие решения
Я только что понял, что вы реализовали last Понтирее к твоему Stew класс, чтобы вы могли:
struct Node {
string val;
Node* next;
Node* prev;
};
struct Stew {
Node* first;
Node* last;
};typedef struct Node node_t;
typedef struct Stew stew_t;
node_t* pop(stew_t& q)
{
node_t* last = q->last;
if (q->last == q->first) // List is empty or has only one element.
{
q->first = NULL;
q->last = NULL;
}
else
{
q->last = last->prev; // Update the last pointer.
}
return last;
}