1

ListItem我正在使用具有指针和 T 类型值的prev结构制作双向链表。next

我做对了吗？

当我运行主代码时，我只能在显示中看到 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;
}
4

1 回答 1

2

不，你正在做的是UB。给定head != NULLand head->next != NULL，意味着您在列表中至少有两个项目：

 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!

重构你的代码。在纸上列出你的算法，看看它在不同情况下应该做什么（列表中没有元素，列表中有一个元素，两个或更多元素，项目较小，项目最大，或者项目介于两者之间）。如果你在纸上做对了，就把它写在代码中。

编辑：提示：我想列表是之前排序的。列表元素应该有什么属性，你想在它之前插入新项目？你怎么能找到它？

于 2013-02-15T09:24:01.797 回答