Я уже сделал односвязный циклический список, который работал нормально, но в этом случае я сталкиваюсь с такой проблемой, что если я хочу удалить хвост, он удалит его, если узел был вставлен как хвост, но победил т, если он был вставлен в качестве головы. Я предполагаю, что проблема заключается в соединении inserthead-inserttail или удалении функции tail, но не может найти его. Я буду благодарен за вашу помощь.
Состав:
struct Element{
int value;
Element *prev, *next;
};
struct List2W{
Element *tail;
};
Код:
void insertHead(List2W& l, int x){
Element *new_head = new Element;
new_head->value=x;
if(isEmpty(l))
{
new_head->next=new_head;
new_head->prev=new_head;
l.tail=new_head;
}
else
{
new_head->next=l.tail->next;
new_head->prev=l.tail;
l.tail->next=new_head;
}
}
void insertTail(List2W& l, int x){
Element *new_tail = new Element;
new_tail->value=x;
if(isEmpty(l))
{
new_tail->next=new_tail;
new_tail->prev=new_tail;
}
else
{
new_tail->next=l.tail->next;
new_tail->prev=l.tail;
l.tail->next=new_tail;
}
l.tail=new_tail;
}
bool deleteTail(List2W& l, int &value){
if(isEmpty(l))
return false;
else if(l.tail->next==l.tail)
{
value=l.tail->value;
l.tail=NULL;
}
else
{
value=l.tail->value;
(l.tail->prev)->next=l.tail->next;
(l.tail->next)->prev=l.tail->prev;
l.tail=l.tail->prev;
}
return true;}
Итак, моя функция вставки пропустила строку, которая должна соединить предыдущую заголовок с new_head:
else
{
(l.tail->next)->prev=new_head; // here
new_head->next=l.tail->next;
new_head->prev=l.tail;
l.tail->next=new_head;
}
Спасибо @nariuji, вы заставили меня повторно проанализировать эту функцию, и спасибо за ваш интерес. Кроме этого, мне просто нужно позаботиться об удалении хвоста, чтобы освободить память, и все должно быть в порядке.
void insertTail(List2W& l, int x) {
// a part is omitted
new_tail->next = l.tail->next;
new_tail->prev = l.tail;
l.tail->next = new_tail;
(l.tail->next)->prev = new_tail; // is this unnecessary?
}