双链表C++上的插入排序

Question

我目前正在学习许多不同的数据排序方法。我正在尝试使用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循环似乎循环了不确定的次数。

请帮忙。

Answer 1

它永远运行，因为你的指针都搞砸了。假设您从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。

"请帮忙"是相当模糊的，所以我只是帮你确定了实际的行为。在未来，我鼓励你用笔和纸(或类似的东西(写下测试用例的预期结果，然后在你逐步完成代码时写下实际结果。