输入两个站点后，有的能正常运行，有的却运行不了，不输出卡着不动
bus_line.txt文件
375 陈渔路口 环线路口 杉树坡子 洪山桥 长沙大学 兑泽街 南湖大市场 省血液中心 朝阳村 月湖大市场 #
132 九尾冲 德雅路口 洪山桥 长沙大学 月湖公园北 洪山路 山月路口 月湖公园 广电中心 世界之窗 #
901 王家垅 九尾冲 洪山桥 长沙大学 月湖公园北 洪西村 三字墙 特立路口 #
807 环线路口 长大附中 福元路山月路口 洪西村 #
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <stdlib.h>
#define MAX_LENGTH 30
#define LINE_LENGTH 1000
using namespace std;
// 线路部分需要的数据结构
struct Bus_point { // 公交车站点信息
int sta_num = 0; // 站点号码
string sta_name; // 站点名称
vector<string> bus_num; // 公交车号
};
struct Road_line {
struct Bus_point Left, Right; // 一条线路的左右段的站点
int cost = 1; // 这条路线的长度
int road_num = 0; // 路线编号
};
struct Bus_line { // 路线信息
string sta_name; // 经过站点名称
int sta_num = 0; // 站点号码
};
struct node {
int u = 0, step = 0;
node() {}
node(int a, int sp)
{
u = a; step = sp;
}
//重载了符号 < ：若本站的step>输入站的a.step 则返回true
bool operator < (const node& a)const {
return step > a.step;
}
};
struct Short_trasfer { // 最短换乘需要存储的信息 !!!!!
int bp = 0; // 当前所在的站点是什么
vector <int> bus_proccess; // 到达这个站点需要做什么车以及之前坐的车
vector <int> bus_line;
int trasfer = 0; // 到达这个站点需要换乘几次
};
const int inf = INT32_MAX;
// 公交部分的数据结构
vector <Bus_point> bus_point; // 存储公交车站信息
vector <Bus_line> bus_line[10000]; // 存储公交线路
vector <Road_line> road_line; // 存储路段信息
map <int, string> name_hash; // 存储下标与公交车线路的关系
queue <Short_trasfer> q; // 存储最短换乘临时容器
int mp[10000][10000]; // 地图
int dist[10000], flag[10000], pre[10000]; // 从起点到任意点的最小距离, 是否到过该点, 走过点的前缀
int num_of_sta = 0, line_of_bus = 0; // 站点个数, 公交线路个数
// 公交线路管理函数
void input_file(); // 写入文件操作
int add_new_point(string line_name, string add_name, int cnt, string pre_sta);
int check_point_exist(string s); // 检查站点是否存在
void build_sta(); // 建站
void build_line(); // 建公交线路
void init_map(); // 初始化图
void build_map(); // 建图
void add_line(); // 添加线路 !!!!!!!!!
void shortest_transfer(string start, string end);
int main(string arg[]) {
string start, end;
add_line();
printf("请输入起点位置: ");
cin >> start;
printf("请输入终点位置: ");
cin >> end;
shortest_transfer(start, end);
system("pause");
return 0;
}
void input_file() { // 写入文件操作
FILE* fp;
fp = fopen("bus_sta.txt", "w+"); // 以重写车站信息的文件
if (fp != NULL) {
for (int i = 0; i < int(bus_point.size()); i++) {
fprintf(fp, "%s ", bus_point[i].sta_name.c_str());
for (int j = 0; j < int(bus_point[i].bus_num.size()); j++) {
if (i == int(bus_point.size()) - 1 && j == int(bus_point[i].bus_num.size()) - 1) fprintf(fp, "%s", bus_point[i].bus_num[j].c_str());
else if (j == int(bus_point[i].bus_num.size()) - 1) fprintf(fp, "%s\n", bus_point[i].bus_num[j].c_str());
else fprintf(fp, "%s ", bus_point[i].bus_num[j].c_str());
}
}
}
else printf("车站信息文件打开失败！\n");
if (fp) {
fclose(fp);
}
fp = fopen("road.txt", "w+"); //写每个站点之间的路径长度
if (fp != NULL) {
for (int i = 0; i < int(road_line.size()); i++) {
if (i == int(road_line.size()) - 1) fprintf(fp, "%d %d %d", road_line[i].Left.sta_num, road_line[i].Right.sta_num, road_line[i].cost);
else fprintf(fp, "%d %d %d\n", road_line[i].Left.sta_num, road_line[i].Right.sta_num, road_line[i].cost);
}
}
else printf("道路信息文件打开失败！\n");
if (fp) {
fclose(fp);
}
/***************道路信息***************/
printf("公交系统信息更新成功!\n");
}
int check_point_exist(string s) { // 检查站点是否存在
for (int i = 0; i < int(bus_point.size()); i++) {
if (s == bus_point[i].sta_name) return 1; // 如果传入的与存在的的相符合,证明该站点存在
}
return 0;
}
void build_sta() { // 建站
struct Bus_point bp;
FILE* fp;
char s[MAX_LENGTH] = { '\0' };
fp = fopen("bus_sta.txt", "r");
bool t = 0;
if (fp != NULL) {
while (!feof(fp)) { // 直到读到文件末尾
fscanf_s(fp, "%s", s, MAX_LENGTH); // 字符串读取
if (strlen(s) < 4) { // 字符串长度小于4的按照公交车线路名称处理
bp.bus_num.push_back(s);
}
else { // 否则按照站点名称处理
num_of_sta++; // 站点总数++
if (t) bus_point.push_back(bp);
t = 1;
bp.bus_num.clear(); // 清空结构体进行下一次的存储
bp.sta_name = s;
}
}
bus_point.push_back(bp); // 特殊处理最后一次站点加入
}
else {
printf("文件打开失败!\n");
}
for (int i = 0; i < int(bus_point.size()); i++) {
bus_point[i].sta_num = i; // 给每个站点编号，方便进行下一步操作
}
}
void build_line() { // 建公交线路
struct Bus_line bl; // 定义存储道路信息的结构体
char s[MAX_LENGTH] = { '\0' };
FILE* fp;
fp = fopen("bus_line.txt", "r");
if (fp != NULL) {
while (!feof(fp)) {
fscanf_s(fp, "%s", s, MAX_LENGTH);
if (strlen(s) < 4) { // 如果长度小于4 按照线路名称处理
line_of_bus++; // 线路名称会放在各个站点最前面 所以遇到后需要将总线路++
name_hash[line_of_bus] = s;
}
else { // 否则就是站点名称
bl.sta_name = s;
for (int i = 0; i < int(bus_point.size()); i++) { // 寻找该站点的编号
if (bus_point[i].sta_name == s) {
bl.sta_num = bus_point[i].sta_num;
break;
}
}
bus_line[line_of_bus].push_back(bl); // 将这个线路加入到链表中
}
}
}
else {
printf("文件打开失败!\n");
}
}
void init_map() { // 初始化图
for (int i = 0; i < 10000; i++) { // 初始化将每个点之间的路初始化为无穷大
for (int j = 0; j < 10000; j++) {
mp[i][j] = inf;
}
}
for (int i = 0; i < int(road_line.size()); i++) { // 从道路信息中将站点编号和道路长度提取出来，加入数组中
mp[road_line[i].Left.sta_num][road_line[i].Right.sta_num] = road_line[i].cost;
mp[road_line[i].Right.sta_num][road_line[i].Left.sta_num] = road_line[i].cost;
}
}
void build_map() { // 建图
struct Bus_point bp;
struct Road_line rl;
FILE* fp;
int a, b, c;
// 建立线路关系
fp = fopen("road.txt", "r");
if (fp != NULL) {
while (!feof(fp)) {
fscanf_s(fp, "%d %d %d", &a, &b, &c);
rl.Left = bus_point[a]; // 该条路左边的站点
rl.Right = bus_point[b]; // 该条路右边的站点
rl.cost = c; // 该条路的长度
road_line.push_back(rl); // 将路段信息加入链表
}
}
else {
printf("文件打开失败!\n");
}
for (int i = 0; i < int(road_line.size()); i++) { // 将每条路段编号
road_line[i].road_num = i;
}
init_map(); // 建图
}
void add_line() { // 添加线路 重点！！！
FILE* fp;
string pre_sta;
char new_line[LINE_LENGTH] = { '\0' }, new_sta[LINE_LENGTH] = { '\0' };
int new_sta_num = 0, pre_sta_num = 0;
struct Bus_line bl;
struct Road_line rl;
int cnt;
fp = fopen("bus_line.txt", "r");
if (fp != NULL) {
while (!feof(fp)) {
fscanf_s(fp, "%s", new_line, LINE_LENGTH);
name_hash[++line_of_bus] = new_line;
cnt = 0;
while (strcmp(new_sta, "#") != 0) {
cnt++;
fscanf_s(fp, "%s", new_sta, LINE_LENGTH);
if (strcmp(new_sta, "#") == 0) {
strcpy(new_sta, "");
break;
}
/***************公交车站点信息更新***************/
int t = check_point_exist(new_sta);
if (!t) {
//printf("抱歉, 不支持增加不存在的站点,请重新输入\n");
pre_sta_num = add_new_point(new_line, new_sta, cnt, pre_sta);
pre_sta = new_sta;
continue;
}
for (int i = 0; i < int(bus_point.size()); i++) {
if (strcmp(bus_point[i].sta_name.c_str(), new_sta) == 0) {
bus_point[i].bus_num.push_back(new_line);
new_sta_num = i;
break;
}
}
bl.sta_name = new_sta;
bl.sta_num = cnt - 1;
bus_line[line_of_bus].insert(bus_line[line_of_bus].end(), bl);
/***************道路信息更新***************/
if (cnt == 1) {
pre_sta = new_sta;
pre_sta_num = new_sta_num;
}
else {
bool exit_road = 0;
for (int i = 0; i < int(road_line.size()); i++) {
if ((pre_sta == road_line[i].Left.sta_name && new_sta == road_line[i].Right.sta_name) || (pre_sta == road_line[i].Right.sta_name && new_sta == road_line[i].Left.sta_name)) {
//printf("此站与前一个站已经存在路程,因此不再添加\n");
exit_road = 1;
break;
}
}
if (!exit_road) {
int len;
//cout << "未检测到 " << pre_sta << "站 与 " << new_sta << "站 有路程,已添加！" << endl;
len = 1;
rl.Left = bus_point[pre_sta_num];
rl.Right = bus_point[new_sta_num];
rl.cost = len;
road_line.push_back(rl);
}
pre_sta = new_sta;
pre_sta_num = new_sta_num;
}
}
// 重新建图
}
}
init_map();
input_file();
}
int add_new_point(string line_name, string add_name, int cnt, string pre_sta)
{
int i;
int line_num = 0, pos;
struct Bus_line bl; // 存储公交线路
struct Bus_point bp; // 存储站点信息
struct Road_line rl; // 存储线路信息
for (i = 1; i <= line_of_bus; i++)
{
if (name_hash[i] == line_name) //找某条公交车线路的下标
{
line_num = i;
break;
}
}
pos = cnt - 1;
bl.sta_name = add_name;
bl.sta_num = pos;
bus_line[line_num].insert(bus_line[line_num].end(), bl);
//添加进入站点
bp.sta_name = add_name;
bp.bus_num.push_back(line_name);
bp.sta_num = num_of_sta++;
bus_point.push_back(bp);
//添加进入道路
string point_name;
string point_name_left, point_name_right;
int Left = 0, Right = 0;
bool exit1 = 0, exit2 = 0;
Right = bp.sta_num;
if (cnt != 1)
{
exit1 = 1;
rl.Right = bp; //当前站点就为右端
Right = bp.sta_num; //当前站点右端的序号
point_name_left = pre_sta; //记录上一个站点名称 把它当作道路的左端
for (int i = 0; i < int(bus_point.size()); i++)
{
if (bus_point[i].sta_name == point_name_left) //找到左端站点的那个站点对象
{
rl.Left = bus_point[i]; //找到左端站点后 赋给rl
Left = bus_point[i].sta_num; //赋给left左端站点的序号值
break;
}
}
rl.cost = 1; //路程长度永远为1
rl.road_num = (int)road_line.size();
road_line.push_back(rl);
mp[Left][Right] = rl.cost;
mp[Right][Left] = rl.cost;
}
return Right;
}
void bfs(int end_num) { // 最短换乘
while (!q.empty()) {
int cnt = 0;
struct Short_trasfer st, t;
st = q.front();
q.pop();
if (st.bp == end_num) {
printf("最少需要换乘%d次\n", st.trasfer);
cout << bus_point[st.bus_proccess[0]].sta_name;
for (int i = 1; i < int(st.bus_proccess.size()) - 1; i++) {
cout << " -" << name_hash[st.bus_line[cnt++]] << "路- " << bus_point[st.bus_proccess[i]].sta_name;
}
cout << " -" << name_hash[st.bus_line[cnt++]] << "路- " << bus_point[st.bus_proccess[int(st.bus_proccess.size()) - 1]].sta_name << endl;
return;
}
else {
for (int i = 0; i < int(bus_point[st.bp].bus_num.size()); i++) { // 遍历此站公交车可以到达各个线路
string line_name = bus_point[st.bp].bus_num[i]; // 807
int line_name_num = 0;
for (int j = 1; j <= line_of_bus; j++) { // 寻找公交线路的编号
if (name_hash[j] == line_name) {
line_name_num = j;
break;
}
}
for (int j = 0; j < int(bus_line[line_name_num].size()); j++) { // 寻找这路公交车可以到达的站点
t.bp = bus_line[line_name_num][j].sta_num;
t.trasfer = st.trasfer + 1;
t.bus_proccess = st.bus_proccess;
t.bus_proccess.push_back(t.bp);
t.bus_line = st.bus_line;
t.bus_line.push_back(line_name_num);
q.push(t);
}
}
}
}
}
void shortest_transfer(string start, string end) { // 最短换乘
int start_num = 0, end_num = 0,x = 0,y = 0;
// printf("公交站的总个数个数为: %d\n", num_of_sta);
for (int i = 0; i < int(bus_point.size()); i++) {
if (bus_point[i].sta_name == start) {
start_num = bus_point[i].sta_num;
break;
}
}
for (int i = 0; i < int(bus_point.size()); i++) {
if (bus_point[i].sta_name == end) {
end_num = bus_point[i].sta_num;
break;
}
}
/*for (int j = 0; j < int(bus_point[x].bus_num.size()); j++) {
for (int k = 0; k < int(bus_point[y].bus_num.size()); k++) {
if (bus_point[y].bus_num[k] == bus_point[y].bus_num[j]) {
printf("0");
break;
goto here;
}
}
}
here:*/
while (!q.empty()) q.pop();
struct Short_trasfer st;
st.bp = start_num;
st.trasfer = -1;
st.bus_proccess.push_back(start_num);
q.push(st);
bfs(end_num);
}
最好把源代码贴出来，这样还能调试一下。这么看代码，而且不是简单编程错误的话，太难了
你这寻找公交线路的for循环，不一定就能找到站点名称啊。如果没找到站点名称，那么line_name_num就不知道是什么值了，后续的循环直接就拿着line_name_num用了，是不是会有问题呢