Сортированная вставка в двусвязном списке

Question

Сортированная вставка в двусвязном списке

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

Вот код для моей отсортированной вставки

void List<T>::insertSorted(T item)
{
ListItem<T> *temp, *temp2;
ListItem<T>* a=new ListItem<T>(item);   //creates a node with our input item

if(head==NULL)
{
head=a;              //if the list is empty, set head equal to the new
//node
}//Following two conditions check whether head is the sole item in the list
//(i.e head->next==NULL), and then insert our node in it accordingly.

else if(head->value > item && head->next==NULL)
{
a->next=head;
head->prev=a;
head=a;
}

else if(head->value < item  && head->next==NULL)
{
head->next=a;
a->prev=head;
}

//This piece checks whether our list has more than one nodes, and adds
//the input node accordingly.
else if(head->next!=NULL)
{
temp=head->next;   //here i'm taking two consecutive nodes
//which in the first case are head->next and head;
temp2=head;
while(temp!=NULL)
{
//if our value can be sandwiched between two nodes then do this
if(temp->value > item && temp2->value < item)
{
temp2->next=a;
a->prev=temp2;
a->next=temp;
temp->prev=a;
break;
}
//go to the next two consecutive nodes
temp=temp->next;
temp2=temp2->next;

//if one of our node is null (i.e we've reached the end of
//the list, do the following
if(temp2->value <= item && temp==NULL)
{
temp2->next=a;
a->prev=temp2;
break;
}
}

}

}

Это очевидно неправильно. Что я здесь не так делаю?

0

c++doubly-linked-list linked-list sorted

Решение

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

Других решений пока нет …

Источник

Accepted Answer

Вы не поощряете NULL next а также prev указатели нового узла a прямо в функции. Следующая модификация в функции insertSorted делает код работающим идеально для меня

 else if(head->value == item  && head->next==NULL)
{
head->next=a;
a->prev=head;
}

//This piece checks whether our list has more than one nodes, and adds
//the input node accordingly.
else if(head->next!=NULL)
{
temp=head;
temp2=head;   //keep track of previous element in the loop
while(temp!=NULL)
{
//if our value can be sandwiched between two nodes then do this
if(temp->value < item)
{
temp2 = temp;
temp = temp ->next;
}
else
{
//from temp onward all numbers will be grater than item. so inserting before item
a->next = temp;
a->prev = temp->prev;
temp->prev = a;
if (temp == head)
{
head = a;
}
else// if temp not head then there is a previous element assign previos elemnts next to a
{
temp2->next = a;
}
break;
}
}
if (temp == NULL)
{
temp2->next=a;
a->prev = temp2;
}
}

пожалуйста, проверьте

Единственная проблема, которую я обнаружил, это отсутствие проверки для этого условия if(head->value == item && head->next==NULL)

2