回复 2楼 mxs810
程序代码:
//下面是完整代码,我的题目是“校园导游”,要求从某一个近点出发到另一个景点,计算出它们之间经过的最短距离打印出来,并且同时也打印出来都,经过了那些景点,就是这//个功能总是出现问题,帮帮我吧!
#include<iostream>
#include<string>
using namespace std;
#define MaxVertexNum 100 /*景点个数最大50*/
#define MAXCOST 1000 /*定义路径的无穷大*/
#define T 11 /*目前景点个数*/
typedef struct
{
char name[20]; /*景点名称*/
char introduce[100]; /*景点简介*/
}Elemtype;
typedef struct
{
int num; /*顶点编号*/
Elemtype date; /*顶点信息*/
}Vertex; /*定义顶点*/
typedef struct
{
Vertex vexs[MaxVertexNum]; /*存放顶点的一维数组,数组第零个单元没有用上*/
unsigned int edges[MaxVertexNum][MaxVertexNum]; /*存放路径的长度*/
int n,e;
}MGraph;
MGraph MGr; /*全局变量,定义MGr为MGraph类型*/
int shortest[MaxVertexNum][MaxVertexNum]; /*定义全局变量存贮最小路径*/
int path[MaxVertexNum][MaxVertexNum]; /*定义存贮路径*/
void init()
{
int i,j;
MGr.vexs[1].num=1;
strcpy(MGr.vexs[1].date.name,"校门");
strcpy(MGr.vexs[1].date.introduce,"挨着阳光大街,坐良乡环城1路很方便。");
MGr.vexs[2].num=2;
strcpy(MGr.vexs[2].date.name,"体育馆");
strcpy(MGr.vexs[2].date.introduce,"集乒乓球馆、羽毛球馆、健身馆、大型校级活动场馆于一身的混合型馆。");
MGr.vexs[3].num=3;
strcpy(MGr.vexs[3].date.name,"操场");
strcpy(MGr.vexs[3].date.introduce,"上室外体育课的地方,也是运动的一个好地方。");
MGr.vexs[4].num=4;
strcpy(MGr.vexs[4].date.name,"工科实践中心");
strcpy(MGr.vexs[4].date.introduce,"一些工科实践课上课的地方,里面设备都是比较好的。");
MGr.vexs[5].num=5;
strcpy(MGr.vexs[5].date.name,"工科教学楼");
strcpy(MGr.vexs[5].date.introduce,"上课的主要地方,里面也有可以自由上机的机房。");
MGr.vexs[6].num=6;
strcpy(MGr.vexs[6].date.name,"师生服务中心");
strcpy(MGr.vexs[6].date.introduce,"这是校园区唯一一个可以吃放买东西的地方。");
MGr.vexs[7].num=7;
strcpy(MGr.vexs[7].date.name,"文科教学楼");
strcpy(MGr.vexs[7].date.introduce,"也是上课的主要地方。");
MGr.vexs[8].num=8;
strcpy(MGr.vexs[8].date.name,"报告厅");
strcpy(MGr.vexs[8].date.introduce,"主要是作报告听讲座的地方,学校的网络中心也在这里面。");
MGr.vexs[9].num=9;
strcpy(MGr.vexs[9].date.name,"图书馆");
strcpy(MGr.vexs[9].date.introduce,"分四层,里面有大量的书籍报刊供师生借阅。");
MGr.vexs[10].num=10;
strcpy(MGr.vexs[10].date.name,"钟楼");
strcpy(MGr.vexs[10].date.introduce,"学校的安保系统都在这里面。");
MGr.vexs[11].num=11;
strcpy(MGr.vexs[11].date.name,"下沉式小广场");
strcpy(MGr.vexs[11].date.introduce,"环境最令人惬意的地方,这边的大屏幕有时播放一些电视节目。");
for(i=1;i<=T;i++)
{
for(j=1;j<=T;j++)
{
MGr.edges[i][j]=MAXCOST;
}
}
for(i=1;i<=T;i++)
{
shortest[i][i]=0;
} /*初始化*/
MGr.edges[1][10]=MGr.edges[10][1]=10;
MGr.edges[1][9]=MGr.edges[9][1]=14;
MGr.edges[2][3]=MGr.edges[3][2]=22;
MGr.edges[2][10]=MGr.edges[10][2]=50;
MGr.edges[3][4]=MGr.edges[4][3]=38;
MGr.edges[3][10]=MGr.edges[10][3]=46;
MGr.edges[3][11]=MGr.edges[11][3]=87;
MGr.edges[4][5]=MGr.edges[5][4]=15;
MGr.edges[5][6]=MGr.edges[6][5]=9;
MGr.edges[5][11]=MGr.edges[11][5]=43;
MGr.edges[6][7]=MGr.edges[7][6]=73;
MGr.edges[6][11]=MGr.edges[11][6]=35;
MGr.edges[7][8]=MGr.edges[8][7]=27;
MGr.edges[7][11]=MGr.edges[11][7]=31;
MGr.edges[8][9]=MGr.edges[9][8]=20;
MGr.edges[9][10]=MGr.edges[10][9]=42;
}
void introduce()
{
int n;
cout<<"请输入查询景点编号:"<<endl;
cin>>n;
switch(n)
{
case 1:
cout<<"景点名称:"<<MGr.vexs[1].date.name<<"\n";
cout<<"景点简介:"<<MGr.vexs[1].date.introduce<<endl;
break;
case 2:
cout<<"景点名称:"<<MGr.vexs[2].date.name<<"\n";
cout<<"景点简介:"<<MGr.vexs[2].date.introduce<<endl;
break;
case 3:
cout<<"景点名称:"<<MGr.vexs[3].date.name<<"\n";
cout<<"景点简介:"<<MGr.vexs[3].date.introduce<<endl;
break;
case 4:
cout<<"景点名称:"<<MGr.vexs[4].date.name<<"\n";
cout<<"景点简介:"<<MGr.vexs[4].date.introduce<<endl;
break;
case 5:
cout<<"景点名称:"<<MGr.vexs[5].date.name<<"\n";
cout<<"景点简介:"<<MGr.vexs[5].date.introduce<<endl;
break;
case 6:
cout<<"景点名称:"<<MGr.vexs[6].date.name<<"\n";
cout<<"景点简介:"<<MGr.vexs[6].date.introduce<<endl;
break;
case 7:
cout<<"景点名称:"<<MGr.vexs[7].date.name<<"\n";
cout<<"景点简介:"<<MGr.vexs[7].date.introduce<<endl;
break;
case 8:
cout<<"景点名称:"<<MGr.vexs[8].date.name<<"\n";
cout<<"景点简介:"<<MGr.vexs[8].date.introduce<<endl;
break;
case 9:
cout<<"景点名称:"<<MGr.vexs[9].date.name<<"\n";
cout<<"景点简介:"<<MGr.vexs[9].date.introduce<<endl;
break;
case 10:
cout<<"景点名称:"<<MGr.vexs[10].date.name<<"\n";
cout<<"景点简介:"<<MGr.vexs[10].date.introduce<<endl;
break;
case 11:
cout<<"景点名称:"<<MGr.vexs[11].date.name<<"\n";
cout<<"景点简介:"<<MGr.vexs[11].date.introduce<<endl;
break;
default:
cout<<"输入序号错误。";
break;
}
}
void floyd()
{
int i,j,k;
for(i=1;i<=T;i++)
{
for(j=1;j<=T;j++)
{
shortest[i][j]=MGr.edges[i][j];
path[i][j]=0;
}
} /*初始化数组*/
for(k=1;k<=T;k++)
{
for(i=1;i<=T;i++)
{
for(j=1;j<=T;j++)
{
if(shortest[i][j]>(shortest[i][k]+shortest[k][j]))
{
shortest[i][j]=shortest[i][k]+shortest[k][j];
path[i][j]=k;
path[j][i]=k;/*记录经过的路径*/
}//end_if
}
}
}//end_for
}
void display(int i,int j)
{/* 打印两个景点的路径及最短距离 */
int a,b;
a=i;
b=j;
cout<<"\n";
cout<<"您要查询的两景点间最短路径是:\n\n";
if(shortest[i][j]!=MaxVertexNum)
{
if(i<j)
{
cout<<b;
while(path[i][j]!=0)
{/* 把i到j的路径上所有经过的景点按逆序打印出来*/
cout<<"<-"<<path[i][j];
if(i<j)
j=path[i][j];
else
i=path[j][i];
}
cout<<"<-"<<a;
cout<<"\n\n";
cout<<a<<"->"<<b<<"最短距离是"<<shortest[a][b]<<"米"<<"\n\n";
}
else
{
cout<<a;
while(path[i][j]!=0)
{/* 把i到j的路径上所有经过的景点按顺序打印出来*/
cout<<"->"<<path[i][j];
if(i<j)
j=path[i][j];
else
i=path[j][i];
}
cout<<"->"<<b;
cout<<"\n\n";
cout<<a<<"->"<<b<<"最短距离是:"<<shortest[a][b]<<"米\n\n"<<endl;
}
}
else
cout<<"输入错误!不存在此路!\n\n";
}/*display*/
int shortestdistance()
{/*要查找的两景点的最短距离*/
int i,j;
cout<<"请输入要查询的两个景点的编号(1->11的数字编号并用间隔一个空格):";
cin>>i>>j;
if(i>T||i<=0||j>T||j<0)
{
cout<<"输入信息错误!\n\n";
cout<<" 请输入要查询的两个景点的编号(1->11的数字编号并间隔一个空格):\n";
cin>>i>>j;
}
else
{
floyd();
display(i,j);
}
return 1;
}/*shortestdistance*/
void main()
{
char k;
init();
cout<<"*******************************************************************\n";
cout<<"* *\n";
cout<<"* *\n";
cout<<"* 欢迎使用校园导游咨询 *\n";
cout<<"* *\n";
cout<<"*******************************************************************\n";
while(1)
{
cout<<"校园景点及编号:\n";
cout<<" 1——校门 7——文科教学楼\n";
cout<<" 2——体育馆 8——报告厅\n";
cout<<" 3——操场 9——图书馆\n";
cout<<" 4——工科实践中心 10——钟楼\n";
cout<<" 5——工科教学楼 11——下沉式小广场\n";
cout<<" 6——师生服务中心\n";
cout<<"*******************************************************************\n";
cout<<"1.景点信息查询请按 i 键\n";
cout<<"2.景点最短路径查询请按 s 键\n";
cout<<"3.退出系统请按 e 键\n";
cout<<"请选择服务:";
cin>>k;
switch(k)
{
case 'i':
cout<<"*******************************************************************\n";
introduce();
cout<<"*******************************************************************\n";
break;
case 's':
cout<<"*******************************************************************\n";
shortestdistance();
cout<<"*******************************************************************\n";
break;
case 'e':
exit(0);
}
}
system("pause");
}