Сортировка вставок со связанным списком

Question

Я пытался заставить сортировку вставок работать со связанными списками. Я потратил последние три дня на алгоритм и даже попытался связаться с 4 разными репетиторами, которые не помогли. Когда я запускаю программу, она читает из файла .csv, печатает, затем сортирует список и печатает снова. Существует проблема с самой сортировкой, так как программа вылетает. Я использую связанные списки только неделю, и буду признателен за любую помощь в выяснении причины проблемы.

#include "pch.h"
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>

using namespace std;

// struct containing node data
struct node {
    string firstName;
    string lastName;
    string country;
    string phone;
    double contribution;
    int id;
    node * next;
};

// list class
class list {
private:
    node *head, *tail;
public:
    list() {
        head = nullptr;
        tail = nullptr;
    }

    // CREATE node with arguments taken from input file
    void createNode(string FirstName, string LastName, string Country, string Phone, double Contribution, int ID) {
        node *temp = new node;                  // create empty node
        temp->firstName = FirstName;
        temp->lastName = LastName;
        temp->country = Country;
        temp->phone = Phone;
        temp->contribution = Contribution;
        temp->id = ID;
        temp->next = nullptr;

        if (head == nullptr) {                  // if first node
            head = temp;
            tail = temp;
            temp = nullptr;
        }
        else {
            tail->next = temp;
            tail = temp;
        }
    }

    // PRINT
    void print() {
        node *temp = new node;                  // create empty node
        temp = head;
        // until end of list
        while (temp != nullptr) {
            cout << temp->lastName << ", " << temp->firstName << '\t'
                << temp->country << '\t' << temp->phone << '\t'
                << temp->contribution << '\t' << temp->id << endl;
            temp = temp->next;
        }
    }

    void insertionSort()
    {

        node *sortNode = new node;  // EMPTY NODE to sort into
        node *temp = new node;      // temp node is to traverse
        temp = head;            // set traversal node

        while (temp != nullptr) {
            node *nextNode = temp->next;

            // sort
            node *current = new node;
            if(sortNode == nullptr || strcmp(temp->firstName.c_str(), nextNode->firstName.c_str()) > 0) {
                temp->next = sortNode;
                sortNode = temp;

            }
            else {

                current = sortNode;
                while ((current->next != nullptr) && strcmp(current->next->firstName.c_str(), temp->firstName.c_str()) > 0)
                {
                    current = current->next;
                }
                temp->next = current->next;
                current->next = temp;
            }
            temp = nextNode;    // go to next node

        }
        head = sortNode;       
    }




    void pop() {
        node *curr = new node;
        node *previous = new node;
        curr = head;
        // find end of node
        while (curr->next != nullptr) {
            previous = curr;
            curr = curr->next;
        }
        previous->next = curr->next;
    }



};

int main()
{
    string firstName;
    string lastName;
    string country;
    string phone;
    double contribution;
    int id;
    string temp;    // store int/double as string, convert

    string line;

    list List;

    ifstream inFile("contributors.csv");
    if (!inFile) {
        cerr << "File failed to open.\n";
    }

    // read data from file by line
    while (getline(inFile, line)) {
        stringstream ss(line);                  // parse line
        getline(ss, firstName, ',');
        getline(ss, lastName, ',');
        getline(ss, country, ',');
        getline(ss, phone, ',');
        getline(ss, temp, ',');
        contribution = stod(temp);
        getline(ss, temp, ',');
        id = stoi(temp);

        // create a node
        List.createNode(firstName, lastName, country, phone, contribution, id);
    }

    List.print();
    cout << endl;
    List.insertionSort();
    cout << endl;
    List.print();


}

.csv файл для справки - https://pastebin.com/p9VTazC8

Answer 1

node *temp = new node;                  // create empty node
temp = head;

Не связано с проблемой, но вы выделяете память для нового указателя temp, затем temp, назначенного другому указателю.Это ничего не дает, кроме утечки памяти.Измените на:

node *temp = head;

В функции insertionSort у вас есть

if(sortNode == nullptr || strcmp(temp->firstName.c_str(), nextNode->firstName.c_str()) > 0)

Вы не проверяете, является ли nextNode nullptr.Бывает, что в некоторых случаях nextNode равен NULL, а затем вы пытаетесь получить доступ к nextNode.firstName.Вот почему программа вылетает.

Вы должны научиться отлаживать программу.В Visual Studio нажмите кнопку отладки.Когда программа аварийно завершает работу, перейдите в «окно стека» (Control + Alt + C), это покажет вам строку кода в коде.

Во-вторых, у вас уже есть список, затем вы пытаетесь вставитьв новый список.Вы должны добавить новую функцию для вставки отсортированных в первом запуске:

struct node 
{
    node() 
    { 
        next = nullptr; 
    }

    node(const string& fn, const string& ln, const string& cn, const string& ph, 
        double contrib, int i)
    {
        next = nullptr;
        firstName = fn;
        lastName = ln;
        country = cn;
        phone = ph;
        contribution = contrib;
        id = i;
    }

    string firstName;
    string lastName;
    string country;
    string phone;
    double contribution;
    int id;
    node *next;

    friend ostream& operator<<(ostream& os, const node& n)
    {
        os  << n.lastName << ", " << n.firstName << '\t' << n.country << '\t' 
            << n.phone << '\t' << n.contribution << '\t' << n.id << endl;
        return os;
    }
};

class list 
{
private:
    node *head, *tail;
public:
    list() 
    {
        head = nullptr;
        tail = nullptr;
    }

    void append(const string& fn, const string& ln, const string& cn, 
        const string& ph, double contrib, int i)
    {
        node *ptr = new node(fn, ln, cn, ph, contrib, i);
        if(head == nullptr)
        {
            head = ptr;
            tail = ptr;
        }
        else
        {
            tail->next = ptr;
            tail = ptr;
        }
    }

    void insert_sorted(const string& fn, const string& ln, const string& cn, 
        const string& ph, double contrib, int i)
    {
        node *ptr = new node(fn, ln, cn, ph, contrib, i);

        if(head == nullptr)
        {
            head = ptr;
            tail = ptr;
        }
        else
        {
            bool inserted = false;
            node *walk = head;
            node *prev = nullptr;
            while(walk)
            {
                if(ptr->firstName < walk->firstName)
                {
                    //2 cases, inserting at the start or middle
                    if(walk == head)
                    {
                        //start
                        ptr->next = head;
                        head = ptr;
                    }
                    else
                    {
                        //middle
                        prev->next = ptr;
                        ptr->next = walk;
                    }

                    inserted = true;
                    break;
                }
                prev = walk;
                walk = walk->next;
            }

            if(!inserted)
            {
                tail->next = ptr;
                tail = ptr;
            }
        }
    }

    void print() 
    {
        node *ptr = head;
        while(ptr) 
        {
            cout << *ptr;
            ptr = ptr->next;
        }
    }
};

int main()
{
    string firstName;
    string lastName;
    string country;
    string phone;
    double contribution;
    int id;
    string temp;    
    string line;
    list List;
    ifstream inFile("contributors.csv");
    if(!inFile) 
        cerr << "File failed to open.\n";

    // read data from file by line
    while(getline(inFile, line)) 
    {
        stringstream ss(line);                  // parse line
        getline(ss, firstName, ',');
        getline(ss, lastName, ',');
        getline(ss, country, ',');
        getline(ss, phone, ',');
        getline(ss, temp, ',');
        contribution = stod(temp);
        getline(ss, temp, ',');
        id = stoi(temp);

        //List.append(firstName, lastName, country, phone, contribution, id);
        List.insert_sorted(firstName, lastName, country, phone, contribution, id);
    }

    List.print();

    return 0;
}

В качестве альтернативы вы можете создать несортированный список с помощью createNode, а затем использовать функцию сортировки для сортировки списка.

Чтобы сделать это по-другому, создайте новый список temp_list, затем вставьте отсортированный temp_list.insert_sorted(...), затем удалите элементы в List, скопируйте temp_list в List (но это не очень эффективно)