华为2014上机考试样题_高级题_地铁换乘最短路径_无向无权图+邻接表存储+BFS广度优先算法
/*
Copyright (c) 2013, binzhouweichao@163.com
华为2014机考题目_判断if括号匹配是否合法_堆栈_简单的方法- -
无向无权图 邻接表存储 BFS广度优先算法搜索
涉及：图 链表 队列 指针 数组 字符串 类型转换
供参考
*/
/*
A10-----A11-----A12-----A13
| |
B1--B2--B3--B4--B5--T1--B6--B7--B8--B9--B10--T2--B11--B12--B13--B14--B15
| |
A9 A14
| |
A8 A15
| |
A7 A16
| |
A6 A17
| |
A5---A4---A3---A2---A1---A18
*/
#include <iostream>
#include <string> //用到字符串操作
#include <sstream> //int转string，用到流操作
using namespace std; //标准库命名空间
#define DEBUG //是否为调试模式
#define VerNum 35 //定义顶点数为35 = 18(A) + 15(B) + 2(T)
#define NULL 0 //定义空指针
typedef int Boolean; //定义布尔类型，为int类型别名，适用于访问标志visited
#define TRUE 1 //定义TRUE为1
#define FALSE 0 //定义FALSE为0
/*********************字符串数组与编号映射*************************************
A
data: A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 A16 A17 A18
index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
B
data: B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 B15
index: 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
T
data: T1 T2
index: 33 34
*/
string Data[VerNum]; //字符串数组，用于存储输入的字符串，数据和下标构成上述映射关系
//全局变量。。
string intToString(int index) //int转string，用于下述initD()的字符串序号
{
stringstream str1;
string str2;
str1 << index;
str1 >> str2;
return str2;
}
void InitData() //初始化字符串数组，完成映射
{
int index;
//A1-A18, index 0-17
for(index=0; index<18; index++)
{
Data[index] = "A" + intToString(index+1);
}
//B1-B15, index 18-32
for(index=18; index<33; index++)
{
Data[index] = "B" + intToString(index-18+1);
}
//T1-T2, index 33-34
Data[33] = "T1";
Data[34] = "T2";
}
/*********************************************************************************************/
int dataToIndex(string str) //查找输入字符串的相应index
{
int index;
for(index=0; index<VerNum; index++)
{
if(strcmp(str.c_str(), Data[index].c_str()) == 0) //比较输入字符串str与数据数组Data[]的各元素，相等则返回该元素下标index
break;
}
return index;
}
/**************************************************************邻接表存储图信息******************************
Data index 顶点表GraphList 第一边表e1[35] 第二边表e2[33] 第三边表e3[2] 第四边表e4[2]
verIndex firstedge eVerIndex nextEdge eVerIndex nextEdge eVerIndex nextEdge eVerIndex nextEdge
-----------------------------------------------------------------------------------------------------------------------------------------------
A1 0 | 0 --> |e1[0] 1 --> |e2[0] 17 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A2 1 | 1 --> | 2 --> | 0 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A3 2 | 2 --> | 3 --> | 1 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A4 3 | 3 --> | 4 --> | 2 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A5 4 | 4 --> | 5 --> | 3 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A6 5 | 5 --> | 6 --> | 4 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A7 6 | 6 --> | 7 --> | 5 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A8 7 | 7 --> | 8 --> | 6 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A9 8 | 8 --> | 32(T1) --> | 7 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A10 9 | 9 --> | 10 --> | 33(T1) -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A11 10 | 10 --> | 11 --> | 9 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A12 11 | 11 --> | 12 --> | 10 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A13 12 | 12 --> | 34(T2) --> | 11 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A14 13 | 13 --> | 14 --> | 34(T2) -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A15 14 | 14 --> | 15 --> | 13 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A16 15 | 15 --> | 16 --> | 14 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A17 16 | 16 --> | 17 --> | 15 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
A18 17 | 17 --> | 0 --> |e2[17] 16 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
B1 18 | 18 --> | 19 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
B2 19 | 19 --> | 20 --> |e2[18] 18 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
B3 20 | 20 --> | 21 --> | 19 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
B4 21 | 21 --> | 22 --> | 20 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
B5 22 | 22 --> | 33(T1) --> | 21 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
B6 23 | 23 --> | 24 --> | 33(T1) -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
B7 24 | 24 --> | 25 --> | 23 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
B8 25 | 25 --> | 26 --> | 24 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
B9 26 | 26 --> | 27 --> | 25 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
B10 27 | 27 --> | 34(T2) --> | 26 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
B11 28 | 28 --> | 29 --> | 34(T2) -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
B12 29 | 29 --> | 30 --> | 28 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
B13 30 | 30 --> | 31 --> | 29 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
B14 31 | 31 --> | 32 --> |e2[30] 30 -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
B15 32 | 32 --> | 31(B14) -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
T1 33 | 33 --> |e1[33] 9(A10) --> |e2[31] 8(A9) --> |e3[0] 23(B6) --> |e4[0] 22(B5) -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
T2 34 | 34 --> |e1[34] 13(A14) --> |e2[32] 12(A14) --> |e3[1] 28(B11) --> |e4[1] 27(B10) -->NULL |
-----------------------------------------------------------------------------------------------------------------------------------------------
*/