某数据结构课程设计公园导游图.doc

实验四:图(内容:某公园导游图)一、问题描述:公园导游系统:给出一张某公园的导游图,游客通过终端询问可知︰从某一景到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。二、设计描述:(存储方法).本程序特地设计函数voidinitgraph()用于实现键盘输入图的结构;(GraphMatrixgraph)用于实现访问任一景点的信息;。利用floyd算法-实现每一对景点间的最短路径。并利用voidoutgraph()函数实现显示起始点和终点间的最短路径和其长度;三、程序清单:#include<iostream>usingnamespacestd;#include<>#defineMAXVEX100#defineMAX999typedefcharVexType;typedeffloatAdjType;typedefstruct//定义图结构{intn;/*图的顶点个数*/VexTypevexs[MAXVEX];/*顶点信息*/AdjTypearcs[MAXVEX][MAXVEX];/*边信息*/}GraphMatrix;GraphMatrixgraph;//定义一个图graphtypedefstruct//定义最短路径ShortPath结构{AdjTypea[MAXVEX][MAXVEX];/*关系矩阵A,存放每对顶点间最短路径长度*/intnextvex[MAXVEX][MAXVEX];/*nextvex[i][j]存放vi到vj最短路径上vi的后继顶点的下标值*/}ShortPath;ShortPathpath;//定义路径pathvoidfloyd(GraphMatrix*pgraph,ShortPath*ppath)//floyd算法-用于实现每一对景点间的最短路径{inti,j,k;for(i=0;i<pgraph->n;i++)for(j=0;j<pgraph->n;j++){if(pgraph->arcs[i][j]!=MAX)ppath->nextvex[i][j]=j;elseppath->nextvex[i][j]=-1;ppath->a[i][j]=pgraph->arcs[i][j];}for(k=0;k<pgraph->n;k++)for(i=0;i<pgraph->n;i++)for(j=0;j<pgraph->n;j++){if(ppath->a[i][k]>=MAX||ppath->a[k][j]>=MAX)continue;if(ppath->a[i][j]>ppath->a[i][k]+ppath->a[k][j]){ppath->a[i][j]=ppath->a[i][k]+ppath->a[k][j];ppath->nextvex[i][j]=ppath->nextvex[i][k];}}}voidoutgraph()//out()函数用于实现显示起始点和终点间的最短路径和其长度{intc,b,i;cout<<endl;cout<<"请输入想查找起始点和终点:";//输入要查找起始点和终点(本程序限于编号(int型))cout<<endl;cin>>c;cin>>b;i=[c][b];//[c][b]把路径长度赋给icout<<"该路径总长为:";cout<<i<<endl;//输出路径长度cout<<"所得路径顺序为";cout<<c;//此处输出路径的第一个编号c=[c][b];for(;c!=b;c=[c][b])//循环顺序输出路径始点和终点之间的景点编号cout<<","<<c;cout<<","<<b;//再输出路径的最后一个编号cout<<endl;}voidinitgraph()//该函数用于实现键盘输入图的结构{inti,m,j;printf("请输入公园景点的个数:");//("%d",&m);=m;for(i=0;i<;i++)//循环输入结点顶点信息{printf("请输入第%i个景点信息:",i);//为了简明起见此程序结点顶点信息限于字符型cin>>[i];}printf("请输入公园的邻接矩阵的信息\n");//循环输入图的邻接矩阵信息(也就是输入一个二维数组)for(i=0;i<;i++)for(j=0;j<;j++){printf("请输入第%d行,第%d列的元素:",i