链表中的add_sorted函数

Question

目前，我正在尝试使用一个函数创建一个链接列表，该函数可以添加排序到列表中的整数，同时使用我所做的一些函数，但我的代码遇到了问题：

void list::add_sorted(int el)
    {
      if (empty()) add_first(el);
      else if (el<=head->data) add_first(el);
      else if (el >= tail->data) add_last(el);
    }

我想知道为什么我的代码中的输出:3

在主要功能中，我写道：

list t1;
t1.add_sorted(5);
t1.add_sorted(3);
t1.add_sorted(9);
t1.print();

下面是add_first(int )、add_last(int )和空()的实现：

list::list()
{
  head = tail = 0;

}
bool list::empty()
{
  return (head == 0);

}
void list::add_first(int el)
{
    if (empty()) head = tail = new node(el);
    else
     head = new node(el);

}
void list::add_last(int el)
{
    if (empty()) head = tail = new node(el);
    else
     tail=tail->next = new node(el);

}

提前谢谢。

Answer 1

您在void list::add_first(int el)方法中做了一个小错误。由于您没有添加所有代码，所以我已经修改了您的代码，如下所示。请比较以下代码以了解您的错误，特别是比较方法void list::add_first(int el)。希望这能帮上忙。

结构节点{ public: int data；节点*next；节点(Int val):data(val)，next(NULL){ }；

    class list
    {
      private:
         node *head,*tail, *temp;
      public:
         list();
         bool empty();
         void add_sorted(int el);
         void add_first(int el);
         void add_last(int el);
         void print();
    };

    list::list()
    {
      head = tail = 0;

    }
    void list::add_sorted(int el)
    {
       if (empty()) add_first(el);
       else if (el<=head->data) add_first(el);
       else if (el >= tail->data) add_last(el);
    }
    bool list::empty()
    {
      return (head == 0);

    }
    void list::add_first(int el)
    {
        if (empty()) head = tail = new node(el);
        else
        {
         //here temp is pointing to the first node of the list
         temp = head;
         head = new node(el); //now head is pointing to a new node
         head->next = temp; // and that new node is added to the list and finally head is pointing to the first node of the final list
        }

    }
    void list::add_last(int el)
    {
        if (empty()) head = tail = new node(el);//here I dont think this condition will ever satisfied
        else
         tail->next = new node(el);
         tail = tail->next;//more clearity

    }
    void list::print()
    {
      temp = head;
      while(temp)
      {
        std::cout<<temp->data<<", ";
        temp = temp->next;
      }
      std::cout<<std::endl;
    }
    int main()
    {
      list t1;
      t1.add_sorted(5);
      t1.add_sorted(3);
      t1.add_sorted(9);
      t1.print();
      return 0;
    }

Answer 2

我对插入排序链接列表的理解是保持列表排序。

这意味着您需要搜索列表以找到添加新元素的适当位置：

void addSorted(int value)
{
  node * new_element = new node(el);
  new_element->next = nullptr;
  if (head == nullptr)
  {
    head = new_element;
    tail = head;
  }
  else
  {
     node * p = head;
     node * previous = head;
     while (p != nullptr)
     {
       if (el > p.value)
       {
          new_element->next = p;
          previous->next = new_element;
          break;
       }
     }
     if (p == nullptr)
     {
        previous.next = new_element;
     }
  }
}

这里的想法是，您需要搜索列表中的插入点，然后添加新元素。有角的情况，例如当head为null时。