通过移动链接列表（C ++）中的节点进行冒泡排序

Question

我正在通过比较节点中的值然后移动节点来对链表进行冒泡排序，但是我的函数存在问题。当我运行我的代码时，它会很好地创建节点，但是当bubblesort（）函数运行时，它会引发异常，并显示“ p2 was nullptr”。我不知道我的代码有什么问题，我们将不胜感激。

这是我的代码：

#include <iostream>
#include <stdlib.h>
using namespace std;

class Node {
public:
    int number;
    Node* next;
};

class LinkedList {
    Node* head;
    Node* tail;
public:
    LinkedList() {
        head = NULL;
        tail = NULL;
    }
    void createnode(int num) {
        Node* temp = new Node;
        temp->number = num;
        temp->next = NULL;
        if (head == NULL) {
            head = temp;
            tail = temp;
        }
        else {
            tail->next = temp;
            tail = temp;
        }
    }
    void bubblesort(int size) {
        Node* temp;
        int i, j, swapped;
        for (i = 0; i <= size; i++){
            temp = head;
            swapped = 0;
            for (j = 0; j < size - i - 1; j++){
                Node* p1 = temp;
                Node* p2 = p1->next;
                if (p1->number > p2->number){
                    Node* temp1 = p2->next;
                    p2->next = p1;
                    p1->next = temp1;
                    temp = p2;
                    swapped = 1;
                }
                temp = temp->next;
            }
            if (swapped == 0)
                break;
        }
    }
    void displaynodes() {
        Node* temp;
        temp = head;
        while (temp != NULL) {
            cout << temp->number << "  ";
            temp = temp->next;
        }
        cout << endl;
    }
};

int main() {
    LinkedList l;
    int size, num;
    cout << "How many Numbers Do You Want to Store: ";
    cin >> size;
    for (int i = 0; i < size; i++) {
        cout << "Enter Number " << i+1 << ": ";
        cin >> num;
        l.createnode(num);
    }
    system("CLS");
    cout << "Data Of Nodes Before Bubble Sort: " << endl;
    l.displaynodes();
    l.bubblesort(size);
    cout << "Data Of Nodes After Bubble Sort: " << endl;
    l.displaynodes();
    system("pause");
}

Answer 1

您有许多不良的编码习惯，例如using namespace std;，不良的命名方式以及使用Null而不是nullptr。

但是错误在于排序摘要。您正在尝试交换节点，但是如果不使用当前节点之前的节点或使用双向链表，就无法做到这一点。因此，在下面的代码中，我交换了数字而不是节点。

void bubblesort(int size) {
    int i, j, swapped = 1;
    for (i = 0; swapped && i < size; i++){
        swapped = 0;
        Node* temp = head;
        for (j = 0; j < size - i - 1; j++){

            if (temp->number > temp -> next ->number){
                int tempNumber = temp -> number;
                temp -> number = temp -> next -> number;
                temp -> next -> number = tempNumber;
                swapped = 1;
            }
            temp = temp->next;
        }
    }
}