Как отсортировать двусвязный список в C ++ без обмена данными, только передачи (записей) узлов

Question

У меня проблема с методом сортировки моего связанного списка.Мне нужно отсортировать узлы в двусвязном списке путем передачи ссылок узлов (записей узлов).Метод остановлен из-за nullptr в последнем узле.

Я не знаю, как решить эту проблему.Я перепробовал много вариантов, но никто не удался.

#include "DlinkedList.h"

// Node constructor
Node::Node()
{
    this->rhetorician = NULL;
    this->prev = NULL;
    this->next = NULL;
}

// Node destructor
Node::~Node()
{
}

// List constructor
DlinkedList::DlinkedList()
{
    this->length = 0;
    this->head = NULL;
}

// Method for adding node at the end
void DlinkedList::appendNode(Rhetorician* rhetorician)
{
    if (this->head == NULL) {
        Node *new_node = new Node();
        new_node->rhetorician = rhetorician;
        this->head = new_node;
    }
    else {
        Node *last_node = NULL;
        for (Node *node_ptr = this->head; node_ptr != NULL; node_ptr = node_ptr->next)
        {
            last_node = node_ptr;
        }
        Node *new_node = new Node();
        new_node->rhetorician = rhetorician;
        last_node->next = new_node;
        new_node->prev = last_node;
    }
    this->length++;
}

// Method for printing nodes
void DlinkedList::printNodes()
{
    for (Node *node_cur = this->head; node_cur != NULL; node_cur = node_cur->next)
    {
        node_cur->rhetorician->printer();
        cout << "---------------------------------------------------------------------------------------------------" << endl;
    }
    cout << endl << "##################################################################################################\n" << endl;
}

// Method for getting length
int DlinkedList::getLenght()
{
    return this->length;
}

// Method for deleting node
void DlinkedList::remove(string name)
{
    Node* logout_node = NULL;
    for (Node* node_cur = this->head; node_cur != NULL; node_cur = node_cur->next)
    {
        if (node_cur->rhetorician->name == name)
        {
            logout_node = node_cur;
        }
    }

    if (this->head != NULL || logout_node != NULL)
    {
        if (this->head == logout_node)
        {
            this->head = logout_node->next;
        }

        if (logout_node->next != NULL)
        {
            logout_node->next->prev = logout_node->prev;
        }

        if (logout_node->prev != NULL)
        {
            logout_node->prev->next = logout_node->next;
        }

        delete logout_node->rhetorician;
        delete logout_node;
        this->length--;
    }
}

// Method for finding node
void DlinkedList::find(string name)
{
    bool ver = false;
    Node *n = NULL;

    for (Node* node_cur = this->head; node_cur != NULL; node_cur = node_cur->next)
    {
        if (node_cur->rhetorician->name == name)
        {
            ver = true;
            n = node_cur;
        }
    }

    if (ver)
    {
        n->rhetorician->printer();
    }
    else
    {
        cout << "Rhetorician was not found!";
    }
}

// Method for sorting nodes
void DlinkedList::sort()
{
    int count = this->getLenght();
    Node *tmp, *current;
    int i, j;

    for (i = 1; i < count; i++)
    {
        current = this->head;
        for (j = 0; j <= count - i - 1; j++)
        {
            Node *before, *after;
            if (current->rhetorician->coefficient > current->next->rhetorician->coefficient)
            {
                before = current->prev;
                after = current->next;
                if (before != NULL) {
                    before->next = after;
                }
                current->next = after->next;
                current->prev = after;
                after->next = current;
                after->prev = before;
            }
            tmp = current;
            current = current->next;
        }
    }
}

// List destructor
DlinkedList::~DlinkedList()
{
    Node *next_node = NULL;
    for (Node *node_cur = this->head; node_cur != NULL; node_cur = next_node)
    {
        next_node = node_cur->next;
        delete node_cur->rhetorician;
        delete node_cur;
    }

    this->head = NULL;
    this->length = 0;
}

Main:

#include <iostream>
#include "DlinkedList.h"
#include <fstream>
#include <vector>
#include <sstream>

// Namespace
using namespace std;

// Parser of line to vector array
vector<string> split(string strToSplit, char delimeter)
{
    stringstream ss(strToSplit);
    string item;
    vector<string> splittedStrings;
    while (getline(ss, item, delimeter))
    {
        splittedStrings.push_back(item);
    }
    return splittedStrings;
}

// File loader
void read_file(const char *name, DlinkedList *list)
{
    // Variable for loading line
    string line;
    {
        // Create relation
        ifstream file(name);

        // Check if file exists
        if (file)
        {
            // Check if file is empty
            if (!(file.peek() == ifstream::traits_type::eof()))
            {
                // Read data from file and put into LinkedList
                while (getline(file, line)) {
                    list->appendNode(new Rhetorician(split(line, ';')[0], split(line, ';')[1],
                        split(line, ';')[2], stoi(split(line, ';')[3])));
                }
            }
            // Close file
            file.close();
        }
    }
}

// Main method
int main() 
{
    // Create instance of doubly linked list
    DlinkedList *list = new DlinkedList();

    // Read file and push data into list
    read_file("seznam_enumat.txt", list);

    // Print all loaded rhetoricians behind added own one
    cout << "\nAll rhetoricians from file:" << endl;
    cout << "##################################################################################################\n" << endl;
    list->printNodes();

    // Append other rhetoricians
    list->appendNode(new Rhetorician("Cain", "Foster", "Structural and molecular virology", 7));
    list->appendNode(new Rhetorician("Stacy", "Algar", "Dept of microbiology and immunology", 5));
    list->appendNode(new Rhetorician("Oded", "Philander", "Experimental plasma physics", 3));
    list->appendNode(new Rhetorician("Shay", "Rimon", "Experimental plasma physics", 10));

    // Sort rhetoricians in list
    list->sort();

    // Delete rhetorician by name
    //list->remove("Stacy");

    // Finder of rhetorician
    cout << "\nFound rhetorician:" << endl;
    cout << "##################################################################################################\n" << endl;
    list->find("Shay");

    // Print all sorted rhetoricians
    cout << "\nAll rhetoricians:" << endl;
    cout << "##################################################################################################\n" << endl;
    list->printNodes();

    // Destruct list
    delete list;

    // Check if user click any key
    getchar();
    return 0;
}

Риторик:

#include "Rhetorician.h"

Rhetorician::Rhetorician(string name, string surname, string contribution, int coefficient)
{
    this->name = name;
    this->surname = surname;
    this->contribution = contribution;
    this->coefficient = coefficient;
}

void Rhetorician::printer()
{
    // Name
    cout << "Name:" << endl;
    cout << this->name << endl;

    // Surname
    cout << "Surname:" << endl;
    cout << this->surname << endl;

    // Contribution
    cout << "Contribution:" << endl;
    cout << this->contribution << endl;

    // Coefficient
    cout << "Coefficient:" << endl;
    cout << this->coefficient << endl;
}

Answer 1

Основная проблема в sort().Это неправильно обрабатывает указатели.Возьмите короткий пример, 3 -> 2 -> 1, и вы получите его.

Вот исправленный код с удаленными ненужными переменными:

void DlinkedList::sort() {
    int count = this->getLenght();
    Node *current;
    int i, j;

    for (i = 1; i < count; i++) {
        current = this->head;
        for (j = 0; j <= count - i - 1; j++) {
            Node *before, *after;
            if (current->rhetorician->coefficient > current->next->rhetorician->coefficient) {
                before = current->prev;
                after = current->next;
                if (before != nullptr) {
                    before->next = after;
                } else {
                    // if before = null, it is the head node
                    this->head = after; // In case before pointer is null, after pointer should be the new head
                }
                current->next = after->next;
                current->prev = after;

                if (after->next != nullptr) {
                    after->next->prev = current; // prev pointer of after->next should be set to current.
                }

                after->next = current;
                after->prev = before;
            } else {
                current = current->next; // Go to next node only if current->rhetorician->coefficient > current->next->rhetorician->coefficient condition is false.
            }
        }
    }
}

Answer 2

Сортированный вверх список работает супер, но когда я попытался отсортировать список вниз, изменился только символ> для <он не работает.Должны ли быть изменены до узла и после узла? </p>

        // Zero or one element, no sort required.
        if (this->head == NULL) return;
        if (this->head->next == NULL) return;

        // Force initial entry.
        int swapped = 1;
        while (swapped) {
            // Flag as last time, then do one pass.
            swapped = 0;
            this->current = this->head;
            while (this->current->next != NULL) {
                Node *before, *after;
                if (current->rhetorician->coefficient > current->next->rhetorician->coefficient) {
                    swapped = 1;
                    before = current->prev;
                    after = current->next;

                    if (before != NULL) {
                        before->next = after;
                    }
                    else {
                        // if before = null, it is the head node
                        this->head = after; // In case before pointer is null, after pointer should be the new head
                    }
                    current->next = after->next;
                    current->prev = after;

                    if (after->next != NULL) {
                        after->next->prev = current; // prev pointer of after->next should be set to current.
                    }

                    after->next = current;
                    after->prev = before;
                }
                current = current->next;
            }
        }// Zero or one element, no sort required.
        if (this->head == NULL) return;
        if (this->head->next == NULL) return;

        // Force initial entry.
        int swapped = 1;
        while (swapped) {
            // Flag as last time, then do one pass.
            swapped = 0;
            this->current = this->head;
            while (this->current->next != NULL) {
                Node *before, *after;
                if (current->rhetorician->coefficient > current->next->rhetorician->coefficient) {
                    swapped = 1;
                    before = current->prev;
                    after = current->next;

                    if (before != NULL) {
                        before->next = after;
                    }
                    else {
                        // if before = null, it is the head node
                        this->head = after; // In case before pointer is null, after pointer should be the new head
                    }
                    current->next = after->next;
                    current->prev = after;

                    if (after->next != NULL) {
                        after->next->prev = current; // prev pointer of after->next should be set to current.
                    }

                    after->next = current;
                    after->prev = before;
                }
                current = current->next;
            }
        }