华为2014上机考试样题_高级题

华为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://blog.chinaunix.net/uid-26548237-id-3483650.html

*/

//邻接表相关
//边表结构
typedef struct edgeNode
{
 int eVerIndex; //边表的顶点号
 struct edgeNode *nextEdge; //指向下一边表的指针
}edgeNode; //struct edgeNode的别名为edgeNode，方便调用

//顶点表结构
typedef struct vertexNode
{
 int verIndex; //顶点表的顶点号
 edgeNode *firstEdge; //指向第一边表的指针
}vertexNode;

//顶点表构成的图的邻接表
typedef struct
{
 vertexNode adjList[VerNum]; //顶点表结构数组，总数为顶点的数目
}graphList; //将此结构体别名定义为GraphList

//建图，确立顶点表和边表的关系，完善各表的数据域和指针域
void CreateGraph(graphList *g) //指针形参，对g指向的内容的操作在函数结束后仍然有效
{
 /**************边表************************/
 //边表和顶点表的填充过程参考上面的邻接表图

 edgeNode *e1[35]; //第一边表
 edgeNode *e2[33]; //第二边表
 edgeNode *e3[2]; //第三边表
 edgeNode *e4[2]; //第四边表

 int i;
 for(i=0; i<35; i++) //第一边表初始化，分配内存
 {
  e1[i] = new edgeNode;
 }
 for(i=0; i<33; i++) //第二边表初始化，分配内存
 {
  e2[i] = new edgeNode;
 }
 for(i=0; i<2; i++) //第三、四边表初始化，分配内存
 {
  e3[i] = new edgeNode;
  e4[i] = new edgeNode;
 }

 //第一边表数据域，即第一边表顶点号
  //A
 for(i=0; i<18; i++)
 {
  e1[i]->eVerIndex = i+1;
 }
  //修正A
 e1[8]->eVerIndex = 33; //A9-->T1
 e1[12]->eVerIndex = 34; //A13-->T2
 e1[17]->eVerIndex = 0; //A18-->A1
 
  //B
 for(i=18; i<18+15; i++)
 {
  e1[i]->eVerIndex = i+1;
 }
  //修正B
 e1[22]->eVerIndex = 33; //B5-->T1
 e1[27]->eVerIndex = 34; //B10-->T2
 e1[32]->eVerIndex = 31; //B15-->B14

  //T1 T2
 e1[33]->eVerIndex = 9; //T1-->A9
 e1[34]->eVerIndex = 13; //T2-->A14

 //第二边表数据域，即第二边表顶点号
  //A
 for(i=0; i<18; i++)
 {
  e2[i]->eVerIndex = i-1;
 }
  //修正A
 e2[0]->eVerIndex = 17; //A1-->A18
 e2[9]->eVerIndex = 33; //A10-->T1
 e2[13]->eVerIndex = 34; //A14-->T2

  //B
 for(i=18; i<31; i++)
 {
  e2[i]->eVerIndex = i;
 }
  //修正B
 e2[22]->eVerIndex = 33; //B6-->T1
 e2[27]->eVerIndex = 34; //B11-->T2

  //T1 T2
 e2[31]->eVerIndex = 8; //T1-->A9
 e2[32]->eVerIndex = 12; //T2-->A13

 //第三边表数据域，即第三边表顶点号
  //T1 T2
 e3[0]->eVerIndex = 23; //T1-->B6
 e3[1]->eVerIndex = 28; //T2-->B11

 //第四边表数据域，即第四边表顶点号
 e4[0]->eVerIndex = 22; //T1-->B5
 e4[1]->eVerIndex = 27; //T2-->B10

 //第一边表指针域
 for(i=0; i<18; i++)
 {
  e1[i]->nextEdge = e2[i];
 }
 e1[18]->nextEdge = NULL;
 for(i=19; i<32; i++)
 {
  e1[i]->nextEdge = e2[i-1];
 }
 e1[32]->nextEdge = NULL;

 e1[33]->nextEdge = e2[31];
 e1[34]->nextEdge = e2[32];

 //第二边表指针域
 for(i=0; i<33; i++)
 {
  e2[i]->nextEdge = NULL;
 }
 e2[31]->nextEdge = e3[0];
 e2[32]->nextEdge = e3[1];

 //第三边表指针域
 e3[0]->nextEdge = e4[0];
 e3[1]->nextEdge = e4[1];

 //第四边表指针域
 e4[0]->nextEdge = NULL;
 e4[1]->nextEdge = NULL;

/*************************************************************/

 /***完善顶点表数据域和指针域，关联顶点表与第一边表****/

 for(i=0; i<VerNum; i++)
 {
  g->adjList[i].verIndex = i; //顶点表数据域
  g->adjList[i].firstEdge = e1[i]; //顶点表指针域
 }

/***********************************************************/

}

/***打印邻接表信息*******/
#ifdef DEBUG //只在DEBUG模式下打印
void printGraph(graphList *g)
{
 int i;
 edgeNode *p;

 for(i=0; i<VerNum; i++)
 {
  cout << "顶点号：" << i << " 边号：";
  p = g->adjList[i].firstEdge;

  while(p)
  {
   cout << p->eVerIndex << " ";
   p = p->nextEdge;
  }
  cout << endl;
 }
}
#endif

/***************************************************/

/****BFS广度优先搜索邻接表，找出最短路径***********
参考：
http://blog.163.com/zhoumhan_0351/blog/static/3995422720098711040303/
******************************************************/

//队列链表结点结构，单向链表
typedef struct qNode
{
 int qVerIndex; //队列数据域，结点存储的顶点号
 struct qNode *nextQNode; //队列指针域，结点指向的下一个队列结点
}qNode; //队列链表结点结构别名为qNode

//队列链表
typedef struct
{
 qNode *front; //队列头，删除
 qNode *rear; //队列尾，添加
}queue; //队列链表别名queue

//初始化队列，新建队列
void InitQueue(queue *q)
{
 
 q->rear = new qNode; //新建队列结点，赋予队尾
 q->front = q->rear;  //空队列的队头与队尾为同一单元
 /*
 if(q->front == NULL) //分配单元失败
 {
  cout << "InitQueue Error!" << endl;
  exit(1);
 }
 */
 q->front->nextQNode = NULL; //队头的指向下一结点的指针为空
 //因为队首队尾为同一单元，则队尾结点的下一结点指针也为空，即q->rear->nextQNode == NULL
}

//入队，队尾添加
void EnQueue(queue *q, int e) //形参为队列q地址，要添加的新的队列结点的数据域
{
 qNode *p = new qNode; //新建结点，并分配内存
 
 /*if(p == NULL ) //若分配内存失败则退出
 {
  cout << "EnQueue Error!" << endl;
  exit(1);
 }
 */
 p->qVerIndex = e; //新结点的数据域为传入的参数
 p->nextQNode = NULL;  //新结点指针域为空
 
 q->rear->nextQNode = p; //原队尾指向下一结点的指针指向p
 //因为空队的队首与队尾单元相同，则若为空队时，q->front->nexQNode = p
 //即空队的 队头的指向下一结点的指针 指向新结点
 //若非空队，则对队首不影响
 q->rear = p; //p成为新的队尾
 //这时，队首q->front仍为第一次初始化时的单元，而队尾则成了新加的结点单元
 //队尾的指向下一结点的指针永远指向NULL
}

int QueueEmpty(queue *q) //判断队列是否为空，空则返回1，非空为0
{
 return(q->front == q->rear ? 1:0); //判断条件为，队头与队尾为同一单元
}

//出队，队首删除
void DeQueue(queue *q, int *m) //队列q指针传参，m为指针形参，用于保存删除的结点的数据域
{
 qNode *p = new qNode; //新建队列结点，用于缓存
 if(QueueEmpty(q)) //若为空队列，则报错退出
 {
  cout << "DeQueue Error!" << endl;
  exit(1);
 }
 p = q->front->nextQNode; //要删除的结点缓存为p
 *m = p->qVerIndex; //要删除的结点的数据域放入m所指单元
 q->front->nextQNode = p->nextQNode; //队头指向下一结点的指针指向要删除的结点的下一个结点
 if(q->front->nextQNode == NULL) //判断是否已经清空队列
 {
  q->rear = q->front; //若队首指向下一个结点的指针为空，则表明队列已经清空，队首队尾为同一单元
  //注：不能写反了
 }
 free(p); //释放缓存
}

//BFS广度优先搜索
void BFSTraverse(graphList *g, int dist[VerNum][VerNum]) //数组形参，传址，所做修改在函数结束时仍然有效
{
 queue q; //定义队列

 edgeNode *p = new edgeNode; //定义边表结点类型指针，下面访问各个结点的边表时用到

 int index;
 /*
 此处使用循环来得到所有点相对其他点的最短路径，
 若图有未达到的点，需要再设置一个循环来达到遍历所有点的目的，
 因为此题中任何点均可以达到其他所有点，不必再设下一循环
 */
 for(index=0; index<VerNum; index++) 
 {
  InitQueue(&q); //初始化队列q，每个新的起点都重置一下队列
  Boolean visited[VerNum] = {FALSE}; //定义各顶点访问标志，并初始化为FALSE
 
  /*
  设置一个层次标志
  BFS算法是把图从一个顶点转化为树，并按照距离的远近设置树的层次，
  处于同一层次的叶结点与根结点的距离相同
  而且根结点与页结点的距离，就是层次数
  */
  int level[VerNum][VerNum]; //树的最大度为VerNum（第一个），每层中最大叶结点为VerNum（第二个）
  //此数组用于保存每层的各叶子结点
  int r1, r2; //数组横下标为r1，纵下标r2
  for(r1=0; r1<VerNum; r1++) //初始化层次数组
  {
   for(r2=0; r2<VerNum; r2++)
   {
    level[r1][r2] = VerNum; //因为没有VerNum序号的结点，用于判断是否赋值，或作其他用途
   }
  }

  EnQueue(&q, index); //顶点入队
  visited[index] = TRUE; //入队表示已访问
  r1 = 0;
  r2 = 0;
  level[0][0] = index; //树的根节点存放的顶点号
  //r1表示层次数，r2表示本层的第几个叶结点
  dist[index][index] = r1 ; //表示该顶点到自身的距离为0

  while(!QueueEmpty(&q)) //队列非空，则一直访问，直至访问完所有结点
  {
   int m;
   DeQueue(&q, &m); //队首出队
   if(m == level[r1][0]) //若出队的顶点号与第r1层的第一个结点的顶点号相同
   //即：出队的顶点号是某层第一个入队的结点，那么说明该层已经访问结束，进入下一层访问
   {
    r1 += 1; //进入下一层
    r2 = 0;  //下一层起点
   }

   p = g->adjList[m].firstEdge; //按照邻接表各顶点边表的顺序访问每个顶点
   while(p)
   {
    if(!visited[p->eVerIndex])
    {
     EnQueue(&q, p->eVerIndex); //未访问的入队
     visited[p->eVerIndex] = TRUE; //入队表示已访问

     level[r1][r2] = p->eVerIndex; //r1层r2叶结点的顶点号为当前访问的边表顶点号
     dist[index][p->eVerIndex] = r1; //根顶点与当前访问的顶点的距离，为当前访问的点所在的层次数
     r2 += 1; //该层访问结点数递增
    }
    p = p->nextEdge; //循环控制，指向下一个边表
   }
  }
 }
}

#ifdef DEBUG
void printBFS(int dist[VerNum][VerNum])
{
 cout << endl;
 for(int i=0; i<VerNum; i++)
 {
  cout << i <<"：";
  for(int j=0; j<VerNum; j++)
  {
   cout << dist[i][j] << " ";
  }
  cout << endl;
 }
}
#endif

int main()
{
 InitData(); //初始化字符串数组，Data[]数组已经设置成了全局变量。。也可以设置在此处数组传参

 graphList g; //建图
 CreateGraph(&g); //完善图的所有结点

#ifdef DEBUG //调试用，打印图
 printGraph(&g);
#endif

 int dist[VerNum][VerNum]; //定义各顶点间距离数组
 for(int d1=0; d1<VerNum; d1++) //初始化距离数组
 {
  for(int d2=0; d2<VerNum; d2++)
  {
   dist[d1][d2] = 0; //表示顶点d1到顶点d2的距离
   //最大距离不会是VerNum，表示无法到达或有其他用途
  }
 }

 BFSTraverse(&g, dist); //BFS搜索，保存各点最短路径

#ifdef DEBUG
 printBFS(dist); //打印各点间最短路径
#endif

 string str1, str2; //用于保存两个输入的字符串
#ifdef DEBUG
 cout << "请输入两个站点：" << endl;
#endif
 cin >> str1 >> str2; //输入两个字符串，没有设置冗余，对于不符合规范的输入，只取前两个

 int index1, index2; //用于保存将两个输入的字符串转换后的顶点号
 index1 = dataToIndex(str1); //将str1转换成相应顶点号
 index2 = dataToIndex(str2); //将str2转换成相应顶点号

 //两点index1和index2间的距离即为dist[index1][index2]，无向，则也等于dist[index2][index1]
#ifdef DEBUG
 cout << "两点间站点数为：" << endl;
#endif
 cout << dist[index1][index2] <<endl;

#ifdef DEBUG
 system("pause"); //暂停，以查看输出
#endif

 return 0;
}