在雙向鏈表中排序插入

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)