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和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)

于 2013-02-15T08:31:19.183 回答