在双向链表中排序插入

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; 
      } 
     } 

    } 

} 

这显然是错误的代码。我在这里做错了什么？

Answer 1

您不是初始化到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)