在双链接列表上插入排序有什么问题？

Question

我得到一些随机结果。我已经经历了流动，并确实跑了几次，但无法确切地弄清楚代码出了什么问题。

程序流： 链接列表：5 4 3 2 1

1. 电流位于第二位置，即4，也将此值存储到可变温度。
2. 上一个位置是第1位，即
3. 第1个位置，循环运行直到电流变为null。
4. 第二个嵌套时，循环从电流的前身到头部节点以及条件tempdata。 如果条件为真，则将温度移至正确的位置。
5. 最后重复第一个循环。

#include <iostream>
using namespace std;
​
class Node {
public:
    int data;
    Node *next;
    Node *prev;
​
    Node(int data) {
    this->data = data;
    next = NULL;
    prev = NULL;
    }
};
​
void insert(Node *&head, Node *&tail, int data) {
    if (head == NULL) {
    Node *temp = new Node(data);
    temp->next = temp;
    head = temp;
    tail = temp;
    } else {
    Node *temp = new Node(data);
    tail->next = temp;
    temp->prev = tail;
    tail = temp;
    }
}
​
void display(Node *head) {
    Node *temp = head;
    while (temp != NULL) {
    cout << temp->data << " ";
    temp = temp->next;
    }
    cout << endl;
}
​
void insertionSort(Node *&head, int size) {
    Node *current = head->next;
    Node *previous; 
    while (current!= NULL) { 
    int temp = current->data;     
    previous = current->prev; 
    while (previous != head && temp < previous->data) { 
        previous->next->data = previous->data; 
        previous = previous->prev;             
    }
    previous->data = temp;   
    current = current->next; 
    }
}
​
int main() {
    Node *head = NULL;
    Node *tail = NULL;
    int size;
    int data;
    cout << "Linked-List Size: ";
    cin >> size;
    cout << "Enter Elements: ";
    for (int i = 0; i < size; i++) {
    cin >> data;
    insert(head, tail, data);
    }
    display(head);
    insertionSort(head, size);
    display(head);
}

Answer 1

在绘制发生的事情时，通过手动跟踪您的代码：

开始时您

temp = 4     
previous = current->prev

5 -> 4 -> 3 -> 2 -> 1
^    ^
p    c

现在有上一个！= head是错误的，因此未输入循环，而您

previous->data = temp
current = current->next

4 -> 4 -> 3 -> 2 -> 1
^         ^
p         c

这看起来开始看起来不好 - 5已经消失了...

下一个迭代：

temp = 3     
previous = current->prev
    
4 -> 4 -> 3 -> 2 -> 1
     ^    ^
     p    c

上一遍！= head＆amp;＆amp;温度＆lt;上一个＆gt; data是正确的，因此请输入循环：

previous->next->data = previous->data;

4 -> 4 -> 4 -> 2 -> 1
     ^    ^
     p    c

previous = previous->prev;

4 -> 4 -> 4 -> 2 -> 1
^         ^
p         c

现在上一个！= head是错误的，退出循环。

previous->data = temp
current = current->next

3 -> 4 -> 4 -> 2 -> 1
^              ^
p              c

等等。

要解决此问题，请绘制您的列表以及在编写任何代码之前需要发生的事情。
（并且不要忘记处理空列表。）