0

整数変数を含むノードを、既にソートされているか、要素が含まれていない双方向リンクリストに挿入するコードを実装しようとしています。コードが機能するかどうかをテストするためのファイルが提供されています。私のコードは問題なくコンパイルされています。テストが毎回私のコードに失敗するだけです。

これが私のソートされた挿入のコードです

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

    }

}

これは明らかに間違っています。ここで何が間違っていますか？

4

1 に答える 1

2

関数内で直接、新しいノードNULLのnextとポインタを初期化するのではありません。insertSorted関数を変更すると、コードが完全に機能するようになりますpreva

 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)

于 2013-02-15T08:31:19.183 に答える