Xcode: поток 1: EXC_BAD_ACCESS (код = 1, адрес = 0x0) при создании списка смежности

Question

Я пишу программу, которая читает файл, состоящий из курсов и предварительных требований для каждого курса. Я должен распечатать заказ, в котором вы могли бы пройти все перечисленные курсы, чтобы вы не проходили никаких курсов до того, как пройдете все необходимые предварительные курсы. Для этого я создал матрицу смежности, которая использует массив связанных списков для хранения вершин. Всякий раз, когда я запускаю его, я получаю ошибку Thread 1: EXC_BAD_ACCESS (code = 1, address = 0x0). Это происходит через некоторое время после вывода количества вершин. Я играл с контрольными точками некоторое время, но я не видел никакого прогресса. Может кто-то указать мне верное направление? Полный код:

Заголовок:

#ifndef adjList3_h
#define adjList3_h
//#include <vector>
#include <string>
#include <iostream>
//#include <queue>
#include <fstream>

using namespace std;

template <class T>
class adjList
{
private:
//    class neighbor{
//    public:
//        string name;
//        neighbor * next;
//        bool mark;
//        //constructor
//        neighbor(T x)
//        {
//            name = x;
//            next = NULL;
//            mark = false;
//        }
//    };

    class vertex
    {
    public:
        T name;
        vertex * next;
        bool mark;

        vertex(T x)
        {   name = x;
            next = NULL;
            mark = false;
        }
    };

    vertex ** arr; //array of vertex objects, collection of linked lists
    int numV;//number of vertices


    vertex * findVertex(string x, int size, vertex ** arr)
    {
        for (int i = 0; i < size; i++)
        {
            if (arr[i]->name == x)
                return arr[i];
        }
        return NULL;
    }

//    neighbor * findNeighbor(string x, int size, vertex ** arr)
//    {
//        for (int i = 0; i < size; i++)
//        {
//            if(arr[i]->name == x)
//            {
//                return arr[i];
//            }
//        }
//        return NULL;
//    }


public:
    adjList(string fileName)
    {
        string adjacentVertex, firstVertex;
        ifstream inFile;

        inFile.open(fileName);
        if(!inFile)
        {
            cout << "Error opening file..." << endl;
        }

        inFile >> numV;
        arr = new vertex*[numV]; //create an array of vertices
        cout << "Number of vertices: " << numV << endl;

        for (int i = 0; i < numV; i++)
        {
            inFile >> firstVertex; //read the source vertex name
            arr[i] = new vertex(firstVertex); //add a vertex with the source name to the graph

            inFile >> adjacentVertex; //read the next adjacent's name

            //while the adjacent name isn't the -999 sentinel
            //add an edge from source->destination
            //read the next adjacent name
            while (adjacentVertex != "\n")
            {
                //add directed edge from source vertex to neihgbors (class to pre-reqs)
                addDirectedEdge(firstVertex, adjacentVertex);
                inFile >> adjacentVertex;
            }

        }
        delete [] arr;
        inFile.close();

    }

//    bool checkCopy(string name)
//    {
//        for (int i = 0; i < numV; i++)
//        {
//            if(arr[i]->name == name)
//            {
//                return true;
//            }
//        }
//        return false;
//    }
//
    //add a directed edge going from x to y (class to pre-reqs)
    void addDirectedEdge(T x, T y)
    {
        //we want to add a directed edge from the vertex to neighbors
        vertex * source = findVertex(x, numV, arr);
        vertex * destination = findVertex(y, numV, arr);

        if (source != NULL && destination != NULL)
        {
            source->next = destination;
        }
    }


};

#endif /* adjList3_h */

Main:

    #include "adjList3.h"

    int main() {

    string filename;
    cout << "What is the filename? " << endl;
    cin >> filename;

    adjList<string> G(filename);
    }

Answer 1

Проблема здесь:

    for (int i = 0; i < numV; i++)
    {
        inFile >> firstVertex; //read the source vertex name
        arr[i] = new vertex(firstVertex); //add a vertex with the source name to the graph

        inFile >> adjacentVertex; //read the next adjacent's name

        //while the adjacent name isn't the -999 sentinel
        //add an edge from source->destination
        //read the next adjacent name
        while (adjacentVertex != "\n")
        {
            //add directed edge from source vertex to neihgbors (class to pre-reqs)
            addDirectedEdge(firstVertex, adjacentVertex);
            inFile >> adjacentVertex;
        }

    }

Вы получаете имя первой вершины и создаете объект vertex для его хранения. Затем вы получаете имя следующей вершины, но фактически никогда не создаете объект vertex для его хранения. Затем вы ищете его, но там нет vertex. Кроме того, в addDirectedEdge() вы предполагаете, что размер списка равен numV, но вы еще не прочитали в numV вершины.

Я бы обязательно создал и добавил каждый vertex в список по мере их прочтения.

Так что конструктор для adjList() может выглядеть так:

adjList(string fileName)
{
    string adjacentVertex, firstVertex;
    ifstream inFile;

    inFile.open(fileName);
    if(!inFile)
    {
        cout << "Error opening file..." << endl;
    }

    inFile >> numV;
    arr = new vertex*[numV]; //create an array of vertices
    cout << "Number of vertices: " << numV << endl;

    for (int i = 0; i < numV; i++)
    {
        inFile >> firstVertex; //read the source vertex name
        arr[i] = new vertex(firstVertex); //add a vertex with the source name to the graph

        inFile >> adjacentVertex; //read the next adjacent's name

        //while the adjacent name isn't the -999 sentinel
        //add an edge from source->destination
        //read the next adjacent name
        vertex* prevVertex = arr[i];
        while (adjacentVertex != "\n")
        {
            vertex* nextVertex = new vertex(adjacentVertex);
            //add directed edge from source vertex to neihgbors (class to pre-reqs)
            prevVertex->next = nextVertex;
            prevVertex = nextVertex;

            inFile >> adjacentVertex;
        }

    }
    delete [] arr;
    inFile.close();

}