c++ - 代码在编译时产生三个错误

Question

我的任务是编写一个程序来查找从源节点开始的最长路径。我使用了 Dial 的算法，但收到了三个错误。第一个是 'this' cannot be used in a constant expression on line 58 list B[W * V + 1]; 指的是 V。第二个错误是expression did not evaluate to a constant，调用与之前相同的行。 第三个错误是 '.push_back' must have class/struct/union 调用第 60 行 B[0].push_back(src);

我对 C++ 还是很陌生，所以非常感谢任何帮助。

这是完整的代码:

#include "stdafx.h"
#include <iostream>
#include <queue>
#include <list>
# define INF 0x3f3f3f3f
using namespace std;

struct Node
{
    int key;
    struct Node* left, *right;
};

struct Node* newNode(int key)
{
    struct Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}

class Graph
{
    int V;

     list< pair<int, int> > *adj;

public:
    Graph(int V);

    void addEdge(int u, int v, int w);

    void longestPath(int s, int W);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list< pair<int, int> >[V];
}

void Graph::addEdge(int u, int v, int w)
{
     If (v < V && w < V)
     {
    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
     }
}

void Graph::longestPath(int src, int W)
{
    vector<pair<int, list<int>::iterator> > dist(V);

    for (int i = 0; i < V; i++)
    dist[i].first = INF;

    vector<list<int>> B(W * V + 1);

    B[0].push_back(src);
    dist[src].first = 0;

    int idx = 0;
    while (1)
    {
        while (B[idx].size() == 0 && idx < W*V)
            idx++;

        if (idx == W*V)
            break;

        int u = B[idx].front();
        B[idx].pop_front();

        for (auto i = adj[u].begin(); i != adj[u].end(); ++i)
        {
            int v = (*i).first;
            int weight = (*i).second;

            int du = dist[u].first;
            int dv = dist[v].first;

            if (dv > du + weight)
            {
                if (dv != INF)
                     B[dv].erase(dist[v].second);

                dist[v].first = du + weight;
                dv = dist[v].first;

                B[dv].push_front(v);

                dist[v].second = B[dv].begin();

            }

        }
    }

    printf("Longest Distance from Source\n");
    for (int = 0; I < V; ++i)
        printf("%d        &d\n", i, dist[i].first);

}



int main()
{
    struct Node* root = newNode(27);
    root->left = newNode(14);
    root->left->left = newNode(10);
    root->left->right = newNode(19);
    root->right = newNode(35);
    root->right->left = newNode(31);
    root->right->right = newNode(42);

    int V = 7;
    Graph g(V);

    g.addEdge(27, 14, 7);
    g.addEdge(27, 35, 8);
    g.addEdge(14, 10, 1);
    g.addEdge(14, 19, 3);
    g.addEdge(35, 31, 4);
    g.addEdge(35, 42, 2);

      g.longestPath(0,8);
    return 0;
}

Answer 1

您正在越界访问:

void Graph::addEdge(int u, int v, int w)
{
    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
}

这将导致未定义的行为。但我很幸运遇到了段错误。

您可以添加边界检查来修复它:

if(v < V && w < V){
    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
}

---

您的代码 compiles但对 gcc 有一些严重的警告:

这里不需要s分号:

struct Node* newNode(int key)
{
    struct Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
};
 ^^^^

这不是有效的 C++ 代码:

list<int> B[W * V + 1];

与 C 不同，C++ 中不允许使用可变长度数组，并且根据编译情况，您可能会收到错误或警告，因为某些编译器接受此类数组作为 C++ 标准的扩展。这将使您的代码不可移植。

您可以将其更改为:

vector<list<int>> B(W * V + 1);

您可以使用调试器在您的代码中找到它们。 Live debug