综合实验十二 校园导游咨询

综合实验十二校园导游咨询一、实验目的（1）熟练掌握图的创建及遍历基本操作算法。（2）熟练掌握最短路径算法。（3）利用图的遍历和最短路径求解技术，设计一个校园导游程序，为来访的客人提供各种信息查询服务。二、实验内容【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】(1)设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。(2)为来访客人提供图中任意景点相关信息的查询。(3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一个最短的简单路径。【测试数据】由读者根据实际情况指定。【实现提示】一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。【选作内容】(1)求校园图的关节点。(2)提供图中任意景点问路查询，即求任意两个景点之间的所有路径。(3)提供校园图中多个景点的最佳访问路线查询，即求途经这多个景点的最佳(短)路径。(4)校园导游图的景点和道路的修改扩充功能。(5)扩充道路信息，如道路类别(车道、人行道等)、沿途景色等级，以至可按客人所需分别查询人行路径或车行路径或观景路径等。(6)扩充每个景点的邻接景点的方向等信息，使得路径查询结果能提供详尽的导向信息。(7)实现校园导游图的仿真界面。程序代码及结果：#includeiostream#includeiomanipusingnamespacestd;constintMaxSize=18;constintINFINITY=65535;//最大值无穷classdirection;templateclassTclassMGraph;templateclassTclassVertexNode//定义头结点{friendclassMGraphT;public:intvex;//顶点名称Tvexname;//顶点名称Tvexinf;//顶点信息directiondir;//存放顶点方位信息的direction类的dir。};classdirection{public:intln;//存放在方向图中的横坐标，表示东西intcol;//存放在方向图中的纵坐标，表示南北};templateclassTclassMGraph//定义无向图的邻接矩阵{public:MGraph();//构造函数，初始化具有n个顶点的图voidprintvexname();//显示所有景点及景点代号voidprintvexinf(inti);//显示代号为i景点的名称及信息voidprintroad(inti,intj);//显示景点i~j的最短路径方案信息voidprintdir(inti,intj);//显示景点i到j的方向信息，如“向东100m，向南200m”VertexNodeTadjlist[MaxSize];//存放景点全部信息的景点类数组intvertexNum,arcNum;//图的顶点数和边数voidRoot(intp,intq);//递归寻找pq间的最短路径intPath[MaxSize][MaxSize],Dist[MaxSize][MaxSize];//创建Path和Dist分别存放两点间最短路径的前驱节点，两点间最短路径长度intLine[MaxSize];//Line存放路径intkkk;//Line[]数组的标记private:Tvertex[MaxSize];//存放图中顶点的数组intarc[MaxSize][MaxSize];//存放图中边的数组};*************************【以下为类的实现即类函数的定义】***********************************templateclassTMGraphT::MGraph()//a[]为景点代号，b[]为景点名称，c[]为景点信息，d[]为景点方位信息的横坐标，e[]为景点方位信息的纵坐标//s[]为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arc[][]{ints[]={0,1,0,0,2,0,0,0,2,0,0,0,2,3,0,0,0,0,4,2,0,0,0,0,0,2,3,0,0,0,0,0,2,3,1,0,0,0,2,0,2,0,0,2,0,4,0,2,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,2,0,1,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,4,4,0,0,2,0};inta[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};char*b[]={南门,实验楼,南图,大活,睿思楼,大礼堂,南4教,知行楼,国交楼,南3教,南2教,南1教,北图,北3教,北4教,北2教,北1教,北门};char*c[]={南校区正门,物理实验楼,南校区图书馆,大学生活动中心,教师办公楼、医务室及留学生公寓,大礼堂，用于举办各种文艺演出,南校区第4教学楼,实习基地，计算机房等,国际交流中心，教职工餐厅,南校区第3教学楼,南校区第2教学楼,南校区第1教学楼,北校区图书馆,北校区第3教学楼,北校区第4教学楼,北校区第2教学楼,北校区第1教学楼,北校区正门};intd[]={8,6,4,4,1,0,0,1,3,4,6,8,4,3,2,3,5,8};inte[]={8,8,8,10,8,10,7,6,6,6,6,6,3,1,0,0,0,2};inti,j;vertexNum=18;arcNum=30;for(i=0;ivertexNum;i++){adjlist[i].vex=a[i];adjlist[i].vexname=b[i];adjlist[i].vexinf=c[i];adjlist[i].dir.ln=d[i];adjlist[i].dir.col=e[i];}for(i=0;ivertexNum;i++)//初始化邻接矩阵for(j=0;jvertexNum;j++)arc[i][j]=arc[j][i]=s[(i*(i+1))/2+j];//根据s[]的对称性，将一维数组中的数据赋给二维数组arc[][]}templateclassTvoidMGraphT::printvexname(){inti;for(i=0;ivertexNum;i++)coutadjlist[i].vexadjlist[i].vexnameendl;;}templateclassTvoidMGraphT::printvexinf(inti){coutiadjlist[i].vexname:adjlist[i].vexinfendl;}templateclassTvoidMGraphT::printdir(inti,intj){intdx,nb;//临时存放i与j之间的南北东西关系j在i的哪边？？dx=adjlist[j].dir.col-adjlist[i].dir.col;nb=adjlist[j].dir.ln-adjlist[i].dir.ln;if(dx0)//即j在i的东边cout向东dx*100m，;elsecout向西dx*(0-100)m，;if(nb0)//即j在i的南边cout向南nb*100m;elsecout向北nb*(0-100)m;}templateclassTvoidMGraphT::Root(intp,intq){if(Path[p][q]0){Root(p,Path[p][q]);Root(Path[p][q],q);}else{Line[kkk]=q;kkk++;}}templateclassTvoidMGraphT::printroad(inti,intj){intp,q,m,k,item1,item2;for(p=0;pvertexNum;p++)for(q=0;qvertexNum;q++)Dist[p][q]=arc[p][q];//邻接矩阵赋值for(k=0;kvertexNum;k++)for(p=0;pvertexNum;p++)if(Dist[p][k]0)for(q=0;qvertexNum;q++)if(Dist[k][q]0)if(((Dist[p][q]Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q)){Dist[p][q]=Dist[p][k]+Dist[k][q];Path[p][q]=k;}cout\n=====================================================\n;cout从adjlist[i].vexname到adjlist[j].vexname的最短路径为：endl;coutadjlist[i].vexname;kkk=2;Root(i,j);item2=Line[2];cout--;printdir(i,item2);cout--adjlist[item2].vexname;for(m=3;m=kkk-1;m++){item1=Line[m];cout--;printdir(item1-1,item1);cout--adjlist[item1].vexname;}coutendl;cout\n=====================================================\n;}*****************************【以下为主函数】**************************************intfuncchoice()//系统功能选择页面{intchoice;cout==============================================================endl;cout欢迎进入校园导游咨询平台endl;cout1--显示校园所有景点信息endl;cout2--查询校园景点信息endl;cout3--问路查询系统endl;cout4--退出导游资讯平台endl;cout==============================================================endl;cout请输入要选择的功能号：;cinchoice;returnchoice;}voidmain(){MGraphchar*mg;intfuncchoice();intfc;while(1){fc=funcchoice();if(fc==1){inti;for(i=0;img.vertexNum;i++)mg.printvexinf(i);}elseif(fc==2){inti;mg.printvexname();coutendl请输入所要查询景点代号：;cini;mg.printvexinf(i);}elseif(fc==3){inti,j;mg.printvexname();cout请输入两景点代号（我们将把最短路线反馈予您）：;cinij;mg.printroad(i,j);}else