Пузырьковая сортировка по перемещению узлов в связанном списке (C ++) - PullRequest
Новая
       5

Пузырьковая сортировка по перемещению узлов в связанном списке (C ++)

0 голосов
/ 29 марта 2020

Я делаю пузырьковую сортировку в связанном списке, сравнивая значения в узлах, а затем перемещая узлы, но в моей функции есть проблема. Когда я запускаю свой код, он прекрасно создает узлы, но когда запускается функция 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");
}

1 Ответ

1 голос
/ 29 марта 2020

У вас есть много плохих методов кодирования, таких как 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;
        }
    }
}
...