华为2014上机考试样题

华为2014上机考试样题_高级题_地铁换乘最短路径_无向无权图+邻接表存储+BFS广度优先算法

/*
Copyright (c) 2013, binzhouweichao@163.com

华为2014上机考试样题 高级题 地铁换乘 最短路径

华为2014校园招聘经历_底层软件研发_机考

华为2014机考题目_判断if括号匹配是否合法_堆栈_简单的方法- -

华为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 |
-----------------------------------------------------------------------------------------------------------------------------------------------

参考:

*/

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/a352ada98ba312afc72cd823d342aa9b.html