c++ - 我需要帮助对这个双链表进行排序 (C++)

Question

这是我目前所拥有的:

void sort(const E &t)
{
  DNode<E> *tmp = new DNode<E>(t,NULL,NULL);


    if(size==0)
    {
        cout << "List is empty" << endl;
    }

            else if(t<=head->element)
            {
                tmp->element=t;
                head->prev = tmp;
                tmp->next=head;
                head = tmp;
            }
                    else if(t>=tail->element)
                    {
                        tmp->element=t;
                        tail->next = tmp;
                        tmp->prev=tail;
                        tail = tmp;
                    }

                         curr=tmp;
                         insert(t);
                         size++;
} 

insert() 只是我程序中的另一个函数:

 void insert(const E &t)
{
  DNode<E> *tmp = new DNode<E>(t,NULL,NULL);
  if (size == 0)
  { curr=head=tail=tmp; }
  else 
  {
    tmp->next=curr;
    tmp->prev=curr->prev;
    if (curr->prev) curr->prev->next=tmp;
    else { head=tmp; }
    curr->prev=tmp;
    curr=tmp;
  }
  size++;
}

它确实可以编译，但没有给出正确的结果。我不确定我的错误是什么，我真的需要帮助。任何帮助将不胜感激。

这是在我的主程序中:

  one.sort(10);
  one.sort(20);
  one.sort(30);
  one.sort(40);
  one.sort(50);
  one.sort(60);
  one.print();
  one.moveToEnd();
  one.prev(); 
  one.prev();
  one.remove();
  one.remove();
  one.print();

  cout<<endl;

我应该得到这个:

头==> 10 -> 20 -> 30 -> 40 -> 50 -> 60 <==尾头 ==> 10 -> 20 -> 50 -> 60 <==尾

但我得到的是:头 ==> 10 -> 20 -> 20 -> 30 -> 30 -> 40 -> 40 -> 50 -> 50 -> 60 -> 60< ==尾头==> 10 -> 20 -> 20 -> 30 -> 30 -> 40 -> 40 -> 60 -> 60 <==尾部

Answer 1

你看到的行为的原因是你错过了 else

这个:

curr=tmp;
insert(t);
size++;

无论您是否在头部或尾部添加了一些内容，都会执行。由于您提供的每个条目都将添加到尾部，因此每次都会插入两次。如果您还没有将值添加到头部或尾部，您应该只调用插入。

如果我理解正确，curr=tmp; 和 size++; 无论如何都应该运行，所以我认为只有对插入的调用应该在 else block 中。

编辑:

应该是这样的:

if(size==0)
{
    cout << "List is empty" << endl;
    //Need to insert here as well, to add the first value to the list.
    insert(t);
}

        else if(t<=head->element)
        {
            tmp->element=t;
            head->prev = tmp;
            tmp->next=head;
            head = tmp;
        }
                else if(t>=tail->element)
                {
                    tmp->element=t;
                    tail->next = tmp;
                    tmp->prev=tail;
                    tail = tmp;
                }

                else 
                {
                     insert(t);
                }
                curr=tmp;
                size++;

我(有点)维护了您对空白的使用，不过顺便说一句，我发现它有点不寻常。我通常会将相关的“if”、“else if”和“else”语句放在同一缩进级别，并进一步缩进嵌套 block 。我认为这是更标准的，但既不在这里也不在那里。