lundi 25 novembre 2019

C++ Sort Segmentation Fault

I am working on a coding project for a class where I am given a list of randomly chosen last names, first names, and ssns (randomly generated) and need to sort it as quickly as possible. The teacher provided some code that we cannot change, and we are supposed to just fill in the sorting function. I have taken the linked-list that was created, converted it to an array, and am trying to use the C++ std::sortc++ function. Provided is my code, notice the array is initialized with 1010001 spaces because that is just larger than the actual dataset will be.

While performing the sort, I get a segmentation fault. I believe it has to do with overshooting the position in the array somehow, but I can't seem to find the actual end that I should be using.

Code:

#include <iostream>
#include <fstream>
#include <sstream>
#include <list>
#include <vector>
#include <string>
#include <algorithm>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <array>

using namespace std;

// A simple class; each object holds four public fields
class Data {
public:
    string lastName;
    string firstName;
    string ssn;
};

// Load the data from a specified input file
void loadDataList(list<Data*>& l, const string& filename) {

    ifstream input(filename);
    if (!input) {
        cerr << "Error: could not open " << filename << "\n";
        exit(1);
    }

    // The first line indicates the size
    string line;
    getline(input, line);
    stringstream ss(line);
    int size;
    ss >> size;

    // Load the data
    for (int i = 0; i < size; i++) {
        getline(input, line);
        stringstream ss2(line);
        Data* pData = new Data();
        ss2 >> pData->lastName >> pData->firstName >> pData->ssn;
        l.push_back(pData);
    }

    input.close();
}

// Output the data to a specified output file
void writeDataList(const list<Data*>& l, const string& filename) {

    ofstream output(filename);
    if (!output) {
        cerr << "Error: could not open " << filename << "\n";
        exit(1);
    }

    // Write the size first
    int size = l.size();
    output << size << "\n";

    // Write the data
    for (auto pData : l) {
        output << pData->lastName << " "
            << pData->firstName << " "
            << pData->ssn << "\n";
    }

    output.close();
}

// Sort the data according to a specified field
// (Implementation of this function will be later in this file)
void sortDataList(list<Data*>&);

// The main function calls routines to get the data, sort the data,
// and output the data. The sort is timed according to CPU time.
int main() {
    string filename;
    cout << "Enter name of input file: ";
    cin >> filename;
    list<Data*> theList;
    loadDataList(theList, filename);

    cout << "Data loaded.\n";

    cout << "Executing sort...\n";
    clock_t t1 = clock();
    sortDataList(theList);
    clock_t t2 = clock();
    double timeDiff = ((double)(t2 - t1)) / CLOCKS_PER_SEC;

    cout << "Sort finished. CPU time was " << timeDiff << " seconds.\n";

    cout << "Enter name of output file: ";
    cin >> filename;
    writeDataList(theList, filename);

    return 0;
}

// -------------------------------------------------
// YOU MAY NOT CHANGE OR ADD ANY CODE ABOVE HERE !!!
// -------------------------------------------------

// You may add global variables, functions, and/or
// class defintions here if you wish.


class T1Member {
public:
    Data* pointer;
    const char* lName;
    const char* fName;
    const char* ssn;
    char lNamefl, lNamesl, fNamefl, fNamesl; // lastname first letter, second letter, first name first letter, second letter
    T1Member(Data* d, const char* lN, const char* fN, const char* ssnum, char lNfl, char lNsl, char fNfl, char fNsl) :
        pointer(d), lName(lN), fName(fN), ssn(ssnum), lNamefl(lNfl), lNamesl(lNsl), fNamefl(fNfl), fNamesl(fNsl) {}
    T1Member() {};
};

array<T1Member*, 1010001> T1pt;

bool compare(T1Member* (x), T1Member* (y)) {
    if (x->lNamefl == y->lNamefl) {
        if (x->lNamesl == y->lNamesl) {
            if (strcmp(x->lName, y->lName) == 0) {
                if (x->fNamefl == y->fNamefl) {
                    if (x->fNamesl == y->fNamesl) {
                        if (strcmp(x->fName, y->fName) == 0) {
                            return (strcmp(x->ssn, y->ssn) < 0);
                        }
                        else {
                            return (strcmp(x->fName, y->fName) < 0);
                        }
                    }
                    else {
                        return (x->fNamesl < y->fNamesl);
                    }
                }
                else {
                    return (x->fNamefl < y->fNamefl);
                }
            }
            else {
                return (strcmp(x->lName, y->lName) < 0); // <0 if x->lName is smaller than y->lName
            }
        }
        else (x->lNamesl < y->lNamesl);
    }
    else {
        return (x->lNamefl < y->lNamefl);
    }
}

void sortDataList(list<Data*>& l) {
    int j = 0, n = 0, m = 0;

    // copying linked list into an array
    for (auto i = l.begin(); i != l.end(); i++, j++) {
        auto tmp = new T1Member((*i), ((*i)->lastName.data()), ((*i)->firstName.data()),
            ((*i)->ssn.data()), (*i)->lastName[0], (*i)->lastName[1], (*i)->firstName[0], (*i)->firstName[1]);
        T1pt[j] = tmp;
    }

    int diff = T1pt.size() - l.size();

    sort(T1pt.begin(), (T1pt.end() - diff - 1), compare);

    // sorting the linked list
    for (auto p = l.begin(); p != l.end(); p++, m++) {
        (*p) = (*T1pt[m]).pointer;
    }
}

Link to sample data set I am using to test: https://gofile.io/?c=ggL1RE

Aucun commentaire:

Enregistrer un commentaire