정렬 된 삽입이 이중으로 목록

Question

내가 구조체 prev 및 next 포인터를 가지고 ListItem 및 T 형식의 값을 사용하여 이중 연결리스트를 만드는 중이를 연결

내가 바로 그 일을하고 있습니까?

주 코드를 실행하면 디스플레이에 1, 15 및 16 만 표시됩니다.

template <class T> 
void List<T>::insertSorted(T item) 
{ 
    ListItem<T> *node=new ListItem<T>(item); 
    if (head==NULL) 
    { 
     head=node; 
    }   
    else if (head!=NULL) 
    { 
     T c,d; 
     ListItem<T> *temp,*temp2; 
     temp=head; 
     c=temp->value; 
     int count=0; 
     while (temp->next!=NULL) 
     { 
       if (temp->prev!=NULL) 
       temp2=temp->prev; 

       if (c>item && item>temp2->value) 
       { 
        if (temp->prev!=NULL) 
        { 
         temp2->next=node; 
         node->prev=temp2; 
         node->next=temp; 
         temp->prev=node;  
         count++; 
        } 
        else if (temp->prev==NULL) 
        { 
         head=node; 
         head->next=temp; 
         count++; 
        }    
       } 
       temp=temp->next; 
       c=temp->value; 
     } 
     if (temp->value<item) //comparison with last temp 
     { 
      temp->next=node; 
      node->prev=temp; 
     } 
     else if (temp->value>item) 
     { 
       temp2=temp->prev; 
       temp2->next=node; 
       node->prev=temp2; 
       node->next=temp; 
       temp->prev=node; 
     } 
    }   
} 
int main() 
{ 
    List<int> Mylist; 
    for (int i=16;i>0;i--) 
    { 
     Mylist.insertSorted(i); //insertion should be in ascending order according 
            //to my fnction 
    } 
    Mylist.printList(); //prints the whole linked list 
    system("PAUSE"); 
    return 0; 
} 

Answer 1

아니, 당신이하고있는 일은 UB입니다.

else if (head!=NULL) 
{ 
     T c,d; 
     ListItem<T> *temp,*temp2; //temp2 points to nirvana 
     temp=head;    //temp is head 
     c=temp->value;    
     int count=0; 
     while (temp->next!=NULL) //head->next != NULL, so enter the loop 
     { 
      if (temp->prev!=NULL) //head->prev is NULL... 
       temp2=temp->prev; //.. so temp2 continues to point into nirvana  

      if (c>item && item>temp2->value) //take nirvana's value. OUCH! 

재구성 코드 : 당신을 의미 head != NULL 및 head->next != NULL을 감안할 때 목록에있는 두 개 이상의 항목이있다. 종이에 알고리즘을 배치하고, 목록에서 요소가 없거나, 목록에 하나의 요소가 있거나, 요소가 두 개 이상이거나, 항목이 작거나, 항목이 가장 크거나, 항목이 중간에있는 경우에해야 할 일을 살펴보십시오. 종이에 바로 써 놓았다면 코드에 적어 두십시오.

편집 : 힌트 : 목록이 이전에 정렬 된 것으로 가정합니다. 새 요소를 삽입하기 전에 어떤 요소에 목록 요소가 있어야합니까? 그리고 그것을 어떻게 찾을 수 있습니까?