时间戳

首页 > 解决方案 > 双向链表 C++ 上的插入排序

c++ - 双向链表 C++ 上的插入排序

问题描述

我目前正在学习许多不同的数据排序方式。我正在尝试使用 C++ 在双向链表上实现插入排序。我理解在数组上使用它的概念。但是，我很难弄清楚为什么我的“while”循环会无限循环。

这是我的代码：

template <class T>
class Node
{
protected:
  T item;
  Node<T>* prev;
  Node<T>* next;

public :
  Node()
  {
    prev=nullptr;
    next=nullptr;
  }
};

//InsertionSort
void insertionSort()
{
    Node<T>* current = head->next;
    int count = 1;

    for(current; current != nullptr; current=current->next)
    {

        Node<T>* j = current;
        Node<T>* bj = j->prev;

        while(j != nullptr && j->item < bj->item)
        {
            cout << count++ <<  "Hi" << endl;
            Node<T>* temp = j->next;

            j->next = bj;
            bj->prev = j;

            bj->next = temp;
            temp->prev = bj;
        }
    }
}

我添加了 int count 来查看我的循环发生了多少次。我的 for 循环应该发生 920 次，它确实发生了。但是，我的 while 循环似乎无限次循环。

请帮忙。

标签： c++sortinglinked-listdoubly-linked-listinsertion

解决方案

它永远运行，因为你的指针都搞砸了。假设您从 bj、j 和某个节点 a 和 b 开始：

NULL <--- NodeA <---> Bj <---> J <---> NodeB ---> NULL

在单个 while 循环迭代结束时，您的节点处于以下状态：

NodeA:          NULL <--- NodeA ---> Bj
Bj:             j    <---   Bj  ---> NodeB
J:              Bj   <---   J   ---> Bj
NodeB:          Bj   <--- NodeB ---> NULL

如您所见，j 现在在两个方向上都指向 bj，并且在 NodeA 处没有“prev”点。

在第二次迭代（以及所有后续无限次迭代）之后，您的节点将如下所示：

NodeA:          NULL <--- NodeA ---> Bj
Bj:             Bj   <---   Bj  ---> Bj
J:              Bj   <---   J   ---> Bj
NodeB:          Bj   <--- NodeB ---> NULL

正如您现在所看到的，j 和 bj 都指向 bj 在两个方向上。

“请帮助”相当模糊，所以我只是帮助您确定实际行为。将来，我鼓励您用纸笔（或类似的东西）写下测试用例的预期结果，然后在逐步执行代码时写下实际结果。

推荐阅读