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

1、综合实验十二校园导游咨询一、实验目的(1) 熟练掌握图的创建及遍历基本操作算法。(2) 熟练掌握最短路径算法。(3) 利用图的遍历和最短路径求解技术，设计一个校园导游程序，为来访的客人提供各种信息查询服务。二、 实验内容【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】(1)设计你所在学校的校园平面图，所含景点不少于10个。 以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。(2)为来访客人提供图中任意景点相关信息的查询。(3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一个最短的简单路径。【测试数据

2、】由读者根据实际情况指定。【实现提示】一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。【选作内容】(1)求校园图的关节点。(2)提供图中任意景点问路查询，即求任意两个景点之间的所有路径。(3)提供校园图中多个景点的最佳访问路线查询，即求途经这多个景点的最佳(短 )路径。(4)校园导游图的景点和道路的修改扩充功能。(5)扩充道路信息，如道路类别(车道、人行道等)、沿途景色等级，以至可按客人所需分别查询人行路径或车行路径或观景路径等。(6)扩充每个景点的邻接景点的方向等信息，使得路径查询结果能提供详尽的导向信息。(7) 实现校园导游图的仿真界面。程序代码及结

3、果：#include<iostream>#include<iomanip>using namespace std;const int MaxSize=18;const int INFINITY=65535;/ 最大值无穷class direction;template <class T> class MGraph;template <class T>class VertexNode/ 定义头结点friend class MGraph<T>public:int vex;/ 顶点名称T vexname;/ 顶点名称T vexinf;/ 顶

4、点信息direction dir;/ 存放顶点方位信息的direction 类的 dir 。;class directionpublic:int ln;/ 存放在方向图中的横坐标，表示东西int col;/ 存放在方向图中的纵坐标，表示南北;template <class T>class MGraph/ 定义无向图的邻接矩阵public:MGraph();/ 构造函数，初始化具有n 个顶点的图void printvexname();/ 显示所有景点及景点代号void printvexinf(int i);/ 显示代号为i 景点的名称及信息void printroad(int i,i

5、nt j);/ 显示景点ij 的最短路径方案信息void printdir(int i,int j);/ 显示景点i 到 j 的方向信息，如“向东 100m ，向南 200m”VertexNode<T> adjlistMaxSize; / 存放景点全部信息的景点类数组int vertexNum,arcNum; / 图的顶点数和边数void Root(int p,int q);/ 递归寻找pq 间的最短路径int PathMaxSizeMaxSize,DistMaxSizeMaxSize;/ 创建 Path 和 Dist 分别存放两点间最短路径的前驱节点，两点间最短路径长度int L

6、ineMaxSize;/Line 存放路径int kkk;/Line 数组的标记private:T vertexMaxSize; / 存放图中顶点的数组int arcMaxSizeMaxSize;/ 存放图中边的数组;*【以下为类的实现即类函数的定义】*template <class T>MGraph<T>:MGraph()/a 为景点代号，b 为景点名称，c 为景点信息，d 为景点方位信息的横坐标，e 为景点方位信息的纵坐标/s 为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arcint s=0,1,0,0,2,0,0,0,2,0,0,0,2,

7、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,

8、0,0,4,4,0,0,2,0;int a=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17;char* b=" 南门 ","实验楼 ","南图 "," 大活 "," 睿思楼 ","大礼堂 ","南 4 教 ","知行楼 ","国交楼 "," 南 3 教 "," 南 2 教 ","南 1 教 ","北图 &qu

9、ot;,"北 3 教 ","北 4 教 "," 北 2 教 "," 北 1 教 ","北门 "char* c=" 南校区正门"," 物理实验楼"," 南校区图书馆","大学生活动中心","教师办公楼、医务室及留学生公寓"," 大礼堂，用于举办各种文艺演出","南校区第4 教学楼"," 实习基地，计算机房等","国际交流中心，教职

10、工餐厅"," 南校区第3 教学楼 "," 南校区第2 教学楼 ","南校区第1 教学楼""北校区图书馆","北校区第3 教学楼 ","北校区第4 教学楼 ","北校区第2 教学楼 ","北校区第1 教学楼 ","北校区正门"int d=8,6,4,4,1,0,0,1,3,4,6,8,4,3,2,3,5,8;int e=8,8,8,10,8,10,7,6,6,6,6,6,3,1,0,0,0,2;int i,j

11、;vertexNum=18;arcNum=30;for(i=0;i<vertexNum;i+)adjlisti.vex=ai;adjlisti.vexname=bi;adjlisti.vexinf=ci;adjlisti.dir.ln=di;adjlisti.dir.col=ei;for (i=0; i<vertexNum; i+)/ 初始化邻接矩阵for (j=0; j<vertexNum; j+)arcij=arc皿i=s(i*(i+1)/2+j; 根据s口的对称性，将一维数组中的数据赋给二维数组 arctemplate<class T>void MGraph

12、<T>:printvexname()int i;for(i=0;i<vertexNum;i+)cout<<adjlisti.vex<<" "<<adjlisti.vexname<<endl;template<class T>void MGraph<T>:printvexinf(int i)cout<<i<<" "<<adjlisti.vexname<<":"<<adjlisti.vexi

13、nf<<endl;template<class T>void MGraph<T>:printdir(int i,int j)int dx,nb;/ 临时存放i 与 j 之间的南北东西关系j 在 i 的哪边？dx=adjlistj.dir.col-adjlisti.dir.col;nb=adjlistj.dir.ln-adjlisti.dir.ln;if(dx>0)/ 即 j 在 i 的东边cout<<" 向东"<<dx*100<<"m， "elsecout<<&qu

14、ot; 向西"<<dx*(0-100)<<"m， "if(nb>0)/ 即 j 在 i 的南边cout<<" 向南"<<nb*100<<"m"elsecout<<" 向北"<<nb*(0-100)<<"m"template<class T>void MGraph<T>:Root(int p,int q)if (Pathpq>0)Root(p,Pathpq)

15、;Root(Pathpq,q);else(Linekkk=q;kkk+;)template<class T>void MGraph<T>:printroad(int i,int j)(int p,q,m,k,item1,item2;for(p=0;p<vertexNum;p+)for(q=0;q<vertexNum;q+)Distpq=arcpq;/ 邻接矩阵赋值for(k=0;k<vertexNum;k+)for(p=0;p<vertexNum;p+)if (Distpk>0)for(q=0;q<vertexNum;q+)if (D

16、istkq>0)if (Distpq>Distpk+Distkq)|(Distpq=0)&&(p!=q)(Distpq=Distpk+Distkq;Pathpq=k;)cout<<"n=n"cout<<"从"<<adjlisti.vexname<<"至U"<<adjlistj.vexname<<"的最短路径为："<<endl;cout<<adjlisti.vexname;kkk=2;Root(

17、i,j);item2=Line2;cout<<"->"printdir(i,item2);cout<<"->"<<adjlistitem2.vexname;for(m=3;m<=kkk-1;m+)(item1=Linem;cout<<"->"printdir(item1-1,item1);cout<<"->"<<adjlistitem1.vexname;)cout<<endl;cout<<&

18、quot;n=欢迎下载8n"*【以下为主函数】*int funcchoice()/ 系统功能选择页面 int choice;cout<<"= ="<<endl;cout<<"欢迎进入校园导游咨询平台"<<endl;cout<<" 1-cout<<" 2-cout<<" 3-cout<<" 4- cout<<"=显示校园所有景点信息"<<endl;查询校园景点信息&qu

19、ot;<<endl;问路查询系统"<<endl;退出导游资讯平台"<<endl;="<<endl;cout<<"请输入要选择的功能号："cin>>choice;return choice;) void main()MGraph<char*> mg;int funcchoice();int fc;while(1)fc=funcchoice();if(fc=1)int i;for(i=0;i<mg.vertexNum;i+)mg.printvexinf(i);

20、)else if(fc=2)int i;mg.printvexname();cout<<endl<<"请输入所要查询景点代号："cin>>i;mg.printvexinf(i);)else if(fc=3)int i,j；mg.printvexname();cout<<"请输入两景点代号(我们将把最短路线反馈予您)cin>>i>>j;mg.printroad(i,j);else if(fc=4)break;elsecout<<"输入有误，请重新输入！"<<endl;运行测试图 "CAUtenAgujib alaXUes ktoplN3JjDeb ugU期 ZDSaag*欢迎选入校国导静迎平台2一查理金用妻底信息3-回靖查询案垸4一祖由导游黄讯平台生 同 012345673 8 y L L L L L矢举斐岸'8 H 楼费，中教理型的兼善I 啊验书动公示器轮第第狮第第雪