華為2014上機考試樣題_高級題_地鐵換乘最短路徑_無向無權圖+鄰接表存儲+BFS廣度優先算法
/*
Copyright (c) 2013, [email protected]
華為2014上機考試樣題 高級題 地鐵換乘 最短路徑 http://www.linuxidc.com/Linux/2013-10/90916.htm
華為2014校園招聘經歷_底層軟件研發_機考 http://www.linuxidc.com/Linux/2013-10/90912.htm
華為2014機考題目_判斷if括號匹配是否合法_堆棧_簡單的方法- - http://www.linuxidc.com/Linux/2013-10/90913.htm
華為2014機考題_判斷if括號是否匹配_堆棧 http://www.linuxidc.com/Linux/2013-10/90914.htm
無向無權圖 鄰接表存儲 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;
}