Удаление узла из кругового двусвязного списка
Я написал код для вставки элементов в круговой двусвязный список и для отображения этих элементов. Я должен также иметь возможность удалить хвостовой узел из списка, а также искать в списке определенный элемент.
Это мой рабочий код для добавления и печати:
void Circular_DLList::add_to_tail(int a)
{
DLLNode *temp = new DLLNode;
temp->info = a;
if (is_empty()) {
tail = temp;
temp->next = tail;
temp->prev = tail;
}
else {
temp->next = tail->next;
temp->prev = tail;
tail = temp;
tail->prev->next = temp;
}
}
void Circular_DLList::print_list()
{
DLLNode *ptr;
ptr = tail->next;
do {
cout<< ptr->info << endl;
ptr = ptr->next;
}
while(ptr != tail->next);
}
Независимо от того, что я пишу для функции delete_from_tail, это вызывает ошибку сегментации: 11. Это моя попытка для функции (которая выдает ошибку).
int Circular_DLList::delete_from_tail()
{
int a = tail->info;
if(tail == tail->next) {
delete tail;
tail = NULL;
}
else {
tail = tail->prev;
delete tail->next;
tail->next = NULL;
}
return a;
}
Любой совет, как это исправить, был бы фантастическим. Я попытался отладить, но я не могу понять проблему или где именно это вообще связано.
Спасибо
Решение
Проблема довольно очевидна, если вы посмотрите на нее внимательно. Ваша функция удаления разрывает круговую цепочку списка ссылок. Как так? Смотрите вашу функцию удаления ниже:
int Circular_DLList::delete_from_tail()
{
int a = tail->info;
DLLNode *temp;
if(tail == tail->next) {
delete tail;
tail = NULL;
}
else {
tail = tail->prev;
delete tail->next;
tail->next = NULL;
}
return a;
}
в else-condition вы устанавливаете tail->next = NULL что на самом деле ошибка и, следовательно, разрывает цепь. Поэтому, когда вызывается print, предполагается, что круговая цепочка не повреждена, и, следовательно, случайно пытается получить доступ к указателю NULL, что, в свою очередь, приводит к ошибке сегментации.
Исправление очень просто, смотрите код ниже:
int Circular_DLList::delete_from_tail()
{
int a = tail->info;
if(tail == tail->next) {
delete tail;
tail = NULL;
}
else {
temp = tail;
tail = tail->prev;
tail->next = temp->next; // To maintain the circular chain
tail->next->previous = tail; // Since this element's previous also point to the node about to be deleted
delete temp;
temp = NULL;
}
return a;
}
Другие решения
Других решений пока нет …