c++ - ソート済み 二重連結リストへの挿入

Question

ポインターと T 型の値を持つListItem構造体を使用して、二重にリンクされたリストを作成しています。prevnext

私はそれを正しくやっていますか？

メイン コードを実行すると、ディスプレイに 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;
}

Answer 1

いいえ、あなたがしているのはUBです。head != NULLとが与えられhead->next != NULLた場合、リストに少なくとも 2 つの項目があることを意味します。

 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!

コードを再構築します。紙の上にアルゴリズムをレイアウトし、さまざまな場合 (リストに要素がない、リストに 1 つの要素、2 つ以上の要素、アイテムが小さい、アイテムが最大、またはアイテムがその中間) で何をすべきかを調べます。紙の上で正しく理解できたら、コードに書き留めてください。

編集：ヒント：リストは前にソートされていると思います。新しいアイテムを挿入する前に、リスト要素にどのプロパティを持たせる必要がありますか? そして、どうやってそれを見つけることができますか？