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

《综合实验十二校园导游咨询.doc》由会员分享，可在线阅读，更多相关《综合实验十二校园导游咨询.doc（9页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

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

3、。程序代码及结果：#include#includeusing namespace std;const int MaxSize=18;const int INFINITY=65535;/最大值无穷class direction;template class MGraph;template class VertexNode/定义头结点friend class MGraph; public:int vex;/顶点名称T vexname;/顶点名称T vexinf;/顶点信息direction dir;/存放顶点方位信息的direction类的dir。;class directionpublic:in

4、t ln;/存放在方向图中的横坐标，表示东西int col;/存放在方向图中的纵坐标，表示南北;template class MGraph/定义无向图的邻接矩阵public:MGraph(); /构造函数，初始化具有n个顶点的图void printvexname();/显示所有景点及景点代号void printvexinf(int i);/显示代号为i景点的名称及信息void printroad(int i,int j);/显示景点ij的最短路径方案信息void printdir(int i,int j);/显示景点i到j的方向信息，如“向东100m，向南200m”VertexNode adj

5、listMaxSize; /存放景点全部信息的 景点类数组int vertexNum,arcNum; /图的顶点数和边数void Root(int p,int q);/递归寻找pq间的最短路径int PathMaxSizeMaxSize,DistMaxSizeMaxSize;/创建Path和Dist分别存放两点间最短路径的前驱节点，两点间最短路径长度int LineMaxSize;/Line存放路径int kkk;/Line数组的标记private:T vertexMaxSize; /存放图中顶点的数组int arcMaxSizeMaxSize;/存放图中边的数组;*【以下为类的实现 即类函数

6、的定义】*template MGraph:MGraph()/a为景点代号，b为景点名称，c为景点信息，d为景点方位信息的横坐标，e为景点方位信息的纵坐标/s为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arcint s=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,

7、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;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教,北图,北3教,北4教,北2教,北1教,北门;char* c=南校区

8、正门,物理实验楼,南校区图书馆,大学生活动中心,教师办公楼、医务室及留学生公寓,大礼堂，用于举办各种文艺演出,南校区第4教学楼,实习基地，计算机房等,国际交流中心，教职工餐厅,南校区第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;vertexNum=18;arcNum=30; for(i=0;ivertexNum

9、;i+)adjlisti.vex=ai;adjlisti.vexname=bi;adjlisti.vexinf=ci;adjlisti.dir.ln=di;adjlisti.dir.col=ei;for (i=0; ivertexNum; i+)/初始化邻接矩阵for (j=0; jvertexNum; j+)arcij=arcji=s(i*(i+1)/2+j; /根据s的对称性，将一维数组中的数据赋给二维数组arc templatevoid MGraph:printvexname()int i;for(i=0;ivertexNum;i+)coutadjlisti.vex adjlisti.v

10、exnameendl;templatevoid MGraph:printvexinf(int i)couti adjlisti.vexname:adjlisti.vexinfendl;templatevoid MGraph: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(dx0)/即j在i的东边cout向东dx*100m，;elsecout向西dx*(0-100)0)/即j在i的南边

11、cout向南nb*100m;elsecout向北nb*(0-100)m;templatevoid MGraph:Root(int p,int q) if (Pathpq0) Root(p,Pathpq); Root(Pathpq,q); else Linekkk=q; kkk+; templatevoid MGraph:printroad(int i,int j)int p,q,m,k,item1,item2;for(p=0;pvertexNum;p+)for(q=0;qvertexNum;q+)Distpq=arcpq;/邻接矩阵赋值for(k=0;kvertexNum;k+) for(p=

12、0;p0) for(q=0;q0) if (DistpqDistpk+Distkq)|(Distpq=0)&(p!=q) Distpq=Distpk+Distkq; Pathpq=k; coutn=n;cout从adjlisti.vexname到adjlistj.vexname的最短路径为：endl;coutadjlisti.vexname;kkk=2;Root(i,j);item2=Line2;cout;printdir(i,item2);coutadjlistitem2.vexname;for(m=3;m=kkk-1;m+)item1=Linem;cout;printdir(item1-1

13、,item1);coutadjlistitem1.vexname;coutendl;coutn=n;*【以下为主函数】*int funcchoice()/系统功能选择页面int choice;cout=endl;cout 欢迎进入校园导游咨询平台endl;cout 1-显示校园所有景点信息endl;cout 2-查询校园景点信息endl;cout 3-问路查询系统endl;cout 4-退出导游资讯平台endl;cout=endl;coutchoice;return choice;void main()MGraph mg;int funcchoice();int fc;while(1)fc=funcchoice();if(fc=1)int i;for(i=0;img.vertexNum;i+)mg.printvexinf(i);else if(fc=2)int i;mg.printvexname();coutendli;mg.printvexinf(i);else if(fc=3)int i,j;mg.printvexname();coutij;mg.printroad(i,j);else if(fc=4)break;elsecout输入有误，请重新输入！endl;运行测试图