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 {
InitQueue(&q); //初始化队列q，每个新的起点都重置一下队列
Boolean visited[VerNum] = {FALSE}; //定义各顶点访问标志，并初始化为FALSE

/*
设置一个层次标志
BFS算法是把图从一个顶点转化为树，并按照距离的远近设置树的层次，
处于同一层次的叶结点与根结点的距离相同
而且根结点与页结点的距离，就是层次数
*/
int level[VerNum][VerNum]; //树的最大度为VerNum（第一个），每层中最大叶结点为VerNum（第二个）
//此数组用于保存每层的各叶子结点
int r1, r2; //数组横下标为r1，纵下标r2
for(r1=0; r1 {
for(r2=0; 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 {
cout << i <<"：";
for(int j=0; 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 {
for(int d2=0; 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] <

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

return 0;
}