向双向链表中插入数据并对数据进行排序

Question

我想在一个排序的链表中以排序的方式插入数据。我能够插入数据，但它没有排序。谁能帮我解决我做错了什么？这是我的功能：

typename SortedList<T>::iterator SortedList<T>::insert(const T& data) {


if (data < front_->data_) {
    Node* n = new Node(data, front_, nullptr);

    //if empty
    if (front_ == nullptr) {
        //make back pt to node
        back_ = n;
    }
    else {
        //make front's previous point to node
        front_->prev_ = n;
    }
    //make front point at node
    front_ = n;
    return SortedList<T>::iterator(n);
}
else {
    Node* nn = new Node(data, nullptr, back_);

    //if empty
    if (front_ == nullptr) {
        //make front_ pt to node
        front_ = nn;
    }
    else {
        //make back's next point to node
        back_->next_ = nn;
    }
    //make back point at node
    back_ = nn;
    return SortedList<T>::iterator(nn);
}

这是我的 class

class SortedList{

struct Node {
    T data_;
    Node* next_;
    Node* prev_;
    Node(const T& data = T{}, Node* nx = nullptr, Node* pr = nullptr) {
        data_ = data;
        next_ = nx;
        prev_ = pr;
    }
};

Node* front_;
Node* back_;
int sizelist;

}

Answer 1

您在访问 front_->data 之前没有检查 front_ 是否有 nullptr。

但更重要的是，您没有尝试将数据插入任何类型的排序位置。您仅在列表的最前面或最后面插入。要在中间插入，您必须扫描列表以查找要插入的正确位置。

尝试更像这样的东西：

class SortedList{

    struct Node {
        T data_;
        Node* prev_;
        Node* next_;

        Node(const T& data = T{}, Node* pr = nullptr, Node* nx = nullptr)
            : data_(data), prev_(pr), next_(nx)
        {
        }
    };

    Node* front_;
    Node* back_;
    int size_;

    ...

    iterator insert(const T& data);
};

typename SortedList<T>::iterator SortedList<T>::insert(const T& data)
{
    Node *nn = front_;
    while ((nn) && (data >= nn->data_)) {
        nn = nn->next_;
    }

    Node *n = new Node(data);
    if (nn)
    {
        n->prev_ = nn->prev_;
        n->next_ = nn;
        if (nn->prev_) nn->prev_->next = n;
        nn->prev = n;
    }
    else
    {
        n->prev_ = back_;
        if (back_) back_->next_ = n;
        back_ = n;
    }

    if (front_ == nn) front_ = n;

    ++size_;

    return iterator(n);
}

Answer 2

我没有看到任何搜索列表以查找元素插入位置的代码。您没有指定您希望拥有的元素数量；线性插入排序列表的性能平均为 O(n/2)，这导致您总体上将拥有 O(n^2/2) [即 n 平方超过 2] 的结论如果 n 是 10,000 是无法容忍的，如果 n < 10 则无关紧要。20 年前，我在 8088 上遇到过这个问题，n > 200。有一个大约为 O(log2(n)) 的解决方案，但不知道n 不相关的我不想花时间去解释

Answer 3

您的代码表明您的思路不够清晰。

您必须处理以下情况：

列表为空。
新数据小于列表中所有项目的值。
新数据大于列表中所有项目的值。
新数据介于列表中项目的最低值和最高值之间。

此外，您对 "prev" 和 "next" 的使用对我来说似乎有点奇怪。当我想到双向链表时，我认为它是：

          front -> next -> next -> next -> nullptr
nullptr <- prev <- prev <- prev <- back

您似乎在使用：

          front -> prev -> prev -> prev -> nullptr
nullptr <- next <- next <- next <- back

我的回答符合我认为你使用的第二个版本。如果那不正确，"next" 和 "prev" 的用法需要在几个地方更新。

案例一

在函数开头添加以下内容：

if ( front_ == nullptr )
{
   Node* n = new Node(data, nullptr, nullptr);
   front_ = n;
   back_ = n;
   return SortedList<T>::iterator(n);
}

案例二

你需要：

if ( data < front_->data_ )
{
   Node* n = new Node(data, front_, nullptr);
   front_->prev_ = n;
   return SortedList<T>::iterator(n);
}

案例三

你需要：

if ( data > back_->data_ )
{
   Node* n = new Node(data, nullptr, back_);
   back_->next_ = n;
   return SortedList<T>::iterator(n);
}

案例4

你需要：

// Find the place where to insert the new Node.
Node* iter = front_;
for ( ; iter != nullptr && data < iter->data_; iter = iter->prev_ );

// Insert the new Node.
Node* prev = iter->prev_
Node* n = new Node(data, iter, prev);
prev->next_ = n;
iter->prev_ = n;
return SortedList<T>::iterator(n);

放在一起：

typename SortedList<T>::iterator SortedList<T>::insert(const T& data)
{
   // Case 1
   if ( front_ == nullptr )
   {
      Node* n = new Node(data, nullptr, nullptr);
      front_ = n;
      back_ = n;
      return SortedList<T>::iterator(n);
   }

   // Case 2
   if ( data < front_->data_ )
   {
      Node* n = new Node(data, front_, nullptr);
      front_->prev_ = n;
      return SortedList<T>::iterator(n);
   }

   // Case 3
   if ( data > back_->data_ )
   {
      Node* n = new Node(data, nullptr, back_);
      back_->next_ = n;
      return SortedList<T>::iterator(n);
   }

   // Case 4

   // Find the place where to insert the new Node.
   Node* iter = front_;
   for ( ; iter != nullptr && data < iter->data_; iter = iter->prev_ );

   // Insert the new Node.
   Node* prev = iter->prev_
   Node* n = new Node(data, iter, prev);
   prev->next_ = n;
   iter->prev_ = n;
   return SortedList<T>::iterator(n);
}

向双向链表中插入数据并对数据进行排序

Inserting data into a double linked list and sorting the data

c++

sorting

iterator

sortedlist

doubly-linked-list

案例一

案例二

案例三

案例4

放在一起：