c++ - 在 for 循环中索引向量
问题描述
这是Returning name of最低节点的后续,只是现在有了更多的进展和更少的错误。
和上次一样,这是针对大学课程的,所以复制粘贴对我来说并不是最有利的,即使它确实有效。
我现在遇到的问题与 LeastDistance 函数中向量的索引有关,因为当代码在调试器内外运行时会生成运行时异常,并显示向量下标超出范围的消息。如果有人比我更熟悉向量库,相关行是 1804。这是在同一个函数中访问 for 循环时触发的。
for (int j = 0; j < hnode[i].nodes.size(); j++)
到目前为止,我已经编写了一个小的帮助函数 GetIndex,但我不确定它的代码是否正确,以及如何在 LeastDistance 函数本身中实现它。下面是完整的代码(为粗制滥造的格式道歉,这里的编辑让我有些悲伤)。
#include "stdafx.h"
#include<iostream>
#include<vector>
#define INF = 9999;
using namespace std;
struct Node
{
char nodeLink; //adjacent link
int cost; //cost of a link
}; //to use in Dijkstra algorithm
class HeadNode
{
public:
char Name;
bool Visited;
vector<Node> nodes;
HeadNode(char x) { Name = x; Visited = false; }
};
class Graph
{
char Start = 'A';
char StartNode;
char CurrentNode;
char Destination;
int TotalCost = 0;
vector<HeadNode> hnode;
vector<char> path;
vector<int> weight;
public:
Graph();
void createHeadNode(char X);
void createAdjMatrix();
char LeastDistance(char node);
void printAdjMatrix();
void Dijkstra(char StartNode, char Destination);
void DestinationChangeCaller();
char GetStartNode();
int GetIndex(char CurrentNode);
};
int main()
{
Graph graph;
graph.createHeadNode('A');
graph.createHeadNode('B');
graph.createHeadNode('C');
graph.createHeadNode('D');
graph.createHeadNode('E');
graph.createAdjMatrix();
graph.GetStartNode();
graph.DestinationChangeCaller();
system("pause");
return 0;
}
void Graph::DestinationChangeCaller()
{
for (Destination = 'A'; Destination <= 'E'; Destination++)
{
Dijkstra(StartNode, Destination);
}
}
Graph::Graph()
{
}
int Graph::GetIndex(char node)
{
return(node - 'A');
}
void Graph::createHeadNode(char x)
{
hnode.push_back(x);
}
char Graph::GetStartNode() // elementary get function with no error correction.
{
char got;
cout << "Please enter a node from A-E to start from: ";
cin >> got;
cout << endl;
return got;
}
void Graph::createAdjMatrix()
{
hnode[0].nodes.push_back({ 'B', 4 });
hnode[0].nodes.push_back({ 'C', 1 });
hnode[1].nodes.push_back({ 'A', 4 });
hnode[1].nodes.push_back({ 'C', 2 });
hnode[1].nodes.push_back({ 'D', 1 });
hnode[2].nodes.push_back({ 'A', 1 });
hnode[2].nodes.push_back({ 'B', 2 });
hnode[2].nodes.push_back({ 'D', 3 });
hnode[2].nodes.push_back({ 'E', 1 });
hnode[3].nodes.push_back({ 'B', 1 });
hnode[3].nodes.push_back({ 'C', 3 });
hnode[3].nodes.push_back({ 'E', 1 });
hnode[4].nodes.push_back({ 'C', 1 });
hnode[4].nodes.push_back({ 'D', 1 });
}
void Graph::printAdjMatrix()
{
cout << "The adjacency list that represents the graph is :";
for (int i = 0; i < hnode.size(); i++)
{
cout << endl;
cout << hnode[i].Name << " -> ";
for (int j = 0; j < hnode[i].nodes.size(); ++j)
{
cout << hnode[i].nodes[j].nodeLink << ", " << hnode[i].nodes[j].cost << ", ";
}
}
cout << endl;
cout << endl;
cout << endl;
for (int i = 0; i < hnode.size(); i++)
{
cout << "Shortest distance from node " << Start << " to node " << hnode[i].Name << " is:" << weight[i] << endl;
cout << "Shortest path is : ";
for (int j = 0; j < path.size(); j++)
{
cout << path[j] << endl;
}
}
}
char Graph::LeastDistance(char node)
{
int smallest = 9999;
char smallestNode = node;
int idx = 0;
int i = GetIndex(node);
for (int j = 0; j < hnode[i].nodes.size(); j++)
{
if ((node == hnode[i].Name) && (hnode[i].nodes[j].cost <= smallest) && (hnode[i].Visited == false))
{
smallest = hnode[i].nodes[j].cost;
smallestNode = hnode[i].nodes[j].nodeLink;
idx = i;
}
}
hnode[idx].Visited = true;
TotalCost = TotalCost + smallest;
return(smallestNode);
}
void Graph::Dijkstra(char StartNode, char Destination)
{
CurrentNode = StartNode;
if (CurrentNode == Destination)
{
cout << "the start is the destination, therefore the cost will be 0." << endl;
}
else
{
cout << StartNode << "->";
while (true)
{
if (CurrentNode != Destination)
{
CurrentNode = LeastDistance(CurrentNode);
cout << CurrentNode << "->";
}
else if (CurrentNode == Destination)
{
cout << endl;
cout << "The total cost of this path is:" << TotalCost;
cout << endl;
TotalCost = 0;//reset cost
break;
}
}
}
}
编辑:我从顶部更改了以下几行,错误已修复,但输出仍不符合预期。
class Graph
{
char Start;
char StartNode;
char CurrentNode;
char Destination;
int TotalCost = 0;
vector<HeadNode> hnode;
vector<char> path;
vector<int> weight;
public:
Graph();
void createHeadNode(char X);
void createAdjMatrix();
char LeastDistance(char node);
void printAdjMatrix();
void Dijkstra(char StartNode, char Destination);
void DestinationChangeCaller(char Start);
char GetStartNode();
int GetIndex(char CurrentNode);
};
int main()
{
Graph graph;
graph.createHeadNode('A');
graph.createHeadNode('B');
graph.createHeadNode('C');
graph.createHeadNode('D');
graph.createHeadNode('E');
graph.createAdjMatrix();
graph.GetStartNode();
graph.DestinationChangeCaller(graph.GetStartNode());
system("pause");
return 0;
}
void Graph::DestinationChangeCaller(char Start)
{
for (Destination = 'A'; Destination <= 'E'; Destination++)
{
Dijkstra(Start, Destination);
}
}
解决方案
可能还有其他问题,但这里有一个:
char Graph::GetStartNode() // elementary get function with no error correction.
{
char got;
cout << "Please enter a node from A-E to start from: ";
cin >> got;
cout << endl;
return got;
}
因此 GetStartNode 返回用户输入。它不会更新成员变量 StartNode
当您调用 from 时,您不使用返回值main
:
graph.createAdjMatrix();
graph.GetStartNode(); // <----- The return value isn't used
graph.DestinationChangeCaller();
所以在这里:
void Graph::DestinationChangeCaller()
{
for (Destination = 'A'; Destination <= 'E'; Destination++)
{
Dijkstra(StartNode, Destination);
^^^^^^^^^
}
}
StartNode 未初始化。
推荐阅读
- visual-studio - 更改主帐户别名后,如何连接到我的 Teamproject?
- javascript - 如何读取刚刚使用 yeoman 编写的文件?
- .net-core - 更新到 .NET Core 2.1.401 后,Web.config 转换失败
- reactjs - 无法在 Reactjs 项目中导入 font-awesome
- ios - 来自后台的请求超时
- angular - Angular 5 将@Input 发送到一组组件
- python - 按指标反转元素列表
- powershell - 不能用存储在变量中的另一个字符串替换一个字符串
- java - 在网络级别在 AWS 和 localstack 之间切换
- python - Django师生模型过滤数据