указатели — C ++ Круговой связанный список: удалить элемент

Question

указатели — C ++ Круговой связанный список: удалить элемент

Я сделал с вставкой, поиск в круговом связанном списке, но для удаления я получаю ошибки компилятора …

Следующее — моя структура для узлов.

 struct node
{
int               p_data;
struct node*   p_next;

node(node* head, int data)
{
p_next = head;
p_data = data;
}

explicit node(int data)
{
p_next = nullptr;
p_data = data;
}
};node* remove_circular(node* head, node* target)
{
if (head == target->p_next)
{
delete head;
return nullptr;
}

auto next_pointer = target->p_next;
target->p_data = next_pointer->p_data;
target->p_next = next_pointer->p_next;

delete target->p_next;
return target;
}

и в основной функции я звоню

 head = remove_circular(head, head);
head = remove_circular(head, temp);

это удалить элемент head и другой элемент, на который указывает temp.
Но я получаю ошибки

У кого-нибудь есть идея удалить один элемент из кругового списка?

Я изменил его, чтобы удалить target-> p_next;
но теперь он удаляет все в списке.
Любая идея???

1

c++circular-list linked-list pointers

Решение

Другие решения

Вот как работает круговой связанный список:

пример связанного списка

Каждый узел указывает на следующий в строке, а хвост списка указывает на узел заголовка. В этом отличие от circular linked list к regular linked list (что, в случае выше, сделало бы 37 указывать на терминатор null).

В случае если в вашем списке только один объект, он должен выглядеть примерно так:

только ситуация узла

Итак, как вы можете видеть, нет объекта, указывающего на null в любом месте, но это происходит в вашем коде с вашим explicit конструктор (который будет работать, если я напишу node n = node(12)).

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

4

Как только вы исправите ошибку компилятора, у вас по-прежнему будут возникать алгоритмические проблемы. Я предлагаю вам нарисовать круговой список на бумаге и подумать о шагах, необходимых для удаления элемента. Рассмотрим все случаи, например: пустой список, список из 1 элемента, элемент не в списке и т. Д.

2

Источник

Accepted Answer

Вы должны рассмотреть несколько вещей.

1.) случай пустого списка

  if(head == nullptr){//Empty list case
return nullptr;
}

2.) Цель, которая будет удалена, является головным узлом, и это единственный узел в списке.

  if (head == target && target->p_next == head){
create a temp node with the data value of target
target = nullptr;//Since nothing points to target now it is for all intents and purposes deleted from the list but the data is still there so you can do something with it. I assume this is necessary because you return a node *.
return the temp node
}

3.) Создайте цикл, который перебирает весь список. У вас есть что-то, что удалит только следующий узел, который работает, если у вас есть список из двух элементов, а целью был второй элемент.

  auto next_pointer = head->p_next;//could not be target->p_next as this assumed
while (next_pointer->p_next != target){//This while loop traverses the list rather than just deleting the next entry.

4.) Внутри вашего цикла добавьте проверку, чтобы увидеть, был ли пройден список и цель не была найдена.

   if (next_pointer->p_next == head){
return nullptr;
}//end IF

5.) Внутри цикла добавьте регистр else, который означает, что цель была в произвольном месте в списке. Так как я дал тебе остальное, я оставлю тебя, чтобы получить эту часть. Это не сложно, всего на несколько строк длиннее, чем приведенные выше заявления.

1