2

我在编写程序后尝试调试我的程序，但遇到了这个错误：

在此处输入图像描述

这是我的代码：

#include<fstream>
#include <iostream>
#include <vector>
#include <string>
#define MAXINT 2147483647

using namespace std;

struct Edge
{
int id, weight;

Edge(int y, int w)
{
    id = y;
    weight = w;
}
};

struct Node
{
vector <Edge *> Edges;
};

struct Graph
{
vector < Node *> vertices;
vector < int > indices;

void Resize(int x)
{
    if (vertices.capacity() < x)
        vertices.resize(x);
}

void InsertEdge(int x, int y, int weight)
{
    Resize(((x > y) ? x : y) + 1);
    InsertVertex(x);
    InsertVertex(y);
    vertices[x]->Edges.push_back(new Edge(y, weight));
}

void InsertVertex(int x)
{
    if (vertices[x] == NULL)
    {
        Node *t = new Node;
        vertices[x] = t;
        indices.push_back(x);
    }
}
};



void Dij(Graph const &g, int start)
{
Node *temp;
vector<bool> check;
vector<int>  distance, prev;
int v, w, weight, dist;

for (int i = 0; i <= g.indices.size(); i++)
{
    check.push_back(false);
    distance.push_back(MAXINT);
    prev.push_back(-1);
}

v = start;
distance[v] = 0;

while (!check[v])
{
    check[v] = true;
    temp = g.vertices[v];


    for (int i = 0; i < temp->Edges.size(); i++)
    {
        w = temp->Edges[i]->id;
        weight = temp->Edges[i]->weight;

        if (distance[w] > (distance[v] + weight))
        {
            distance[w] = distance[v] + weight;
            prev[w] = v;
        }
    }

    v = 1;
    dist = MAXINT;

    for (int x = 0; x < g.indices.size(); x++)
    {
        int i = g.indices[x];

        if (!check[i] && dist > distance[i])
        {
            dist = distance[i];
            v = i;
        }
    }
}
}

int main()
{
int startNode, nodeOne, nodeTwo, number;
Graph g;
ifstream myReadFile;
myReadFile.open("P:\\Documents\\New Folder\\Test\\src\\Read.txt");
while (!myReadFile.eof()) 
{
    myReadFile >> nodeOne;
    myReadFile >> nodeTwo;
    myReadFile >> number;
    g.InsertEdge(nodeOne, nodeTwo, number);
}

cout<< "Enter the starting node: ";
cin >> startNode;

Dij(g, startNode);

return 0;
}

我为烦人的格式道歉=/。它在 dij 方法的最后一个 for 循环中中断。有人知道我可能会省略什么吗？

4

2 回答 2

8

稻田是对的！

但作为一个建议，不要使用vector<bool>...

看，C++ 大神想要创建一个节省空间的存储结构来存储bools. 为了节省空间，他们使用了bits. 因为 C++ 中没有bits单位：他们被迫使用chars. 但是一个字符是8位！C++ 之神想出了一个独特的解决方案：他们制作了一种特殊的成员类型：reference访问布尔值。您不能以boolean任何其他方式访问这些值。从技术上讲，vector<bool>它甚至不是一个容器：由于元素是chars，因此无法取消引用迭代器。

存储位的更好和更清洁的方法是使用bitset类。

于 2013-10-31T00:57:36.967 回答
4

我认为您将错误数量的元素预先填充到这些向量中。您正在迭代g.indices.size()，它应该在哪里g.vertices.size()。

您的其余代码知道它indices可以比vertices. check您使用从中提取的值对、distance和prev向量进行索引indices。您得到的运行时错误可能是由于调试模式下的迭代器边界检查。

这应该可以解决您的问题：

for (int i = 0; i <= g.vertices.size(); i++)  // <-- notice the change here
{
    check.push_back(false);
    distance.push_back(MAXINT);
    prev.push_back(-1);
}
于 2013-10-31T00:52:50.260 回答