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

数据结构实验报告班级：06软件工程姓名：周邓雄学号：06517037实验四：图（内容：某公园导游图）一、问题描述：公园导游系统：给出一张某公园的导游图，游客通过终端询问可知︰从某一景到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。二、设计描述：1.输入导游图的算法（存储方法）.本程序特地设计函数voidinitgraph()用于实现键盘输入图的结构；2.可访问导游图中任一景点的算法.为此设计了函数voidvist(GraphMatrixgraph)用于实现访问任一景点的信息；3.最短路径从一景点到另一景点的算法。利用floyd算法-实现每一对景点间的最短路径。并利用voidoutgraph()函数实现显示起始点和终点间的最短路径和其长度；三、程序清单：#includeiostreamusingnamespacestd;#includestdio.h#defineMAXVEX100#defineMAX999typedefcharVexType;数据结构实验报告班级：06软件工程姓名：周邓雄学号：06517037typedeffloatAdjType;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;ipgraph-n;i++)for(j=0;jpgraph-n;j++){if(pgraph-arcs[i][j]!=MAX)ppath-nextvex[i][j]=j;数据结构实验报告班级：06软件工程姓名：周邓雄学号：06517037elseppath-nextvex[i][j]=-1;ppath-a[i][j]=pgraph-arcs[i][j];}for(k=0;kpgraph-n;k++)for(i=0;ipgraph-n;i++)for(j=0;jpgraph-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;coutendl;cout请输入想查找起始点和终点:;//输入要查找起始点和终点（本程序限于编号（int型））coutendl;cinc;cinb;i=path.a[c][b];//通过path.a[c][b]把路径长度赋给i数据结构实验报告班级：06软件工程姓名：周邓雄学号：06517037cout该路径总长为:;coutiendl;//输出路径长度cout所得路径顺序为;coutc;//此处输出路径的第一个编号c=path.nextvex[c][b];for(;c!=b;c=path.nextvex[c][b])//循环顺序输出路径始点和终点之间的景点编号cout,c;cout,b;//再输出路径的最后一个编号coutendl;}voidinitgraph()//该函数用于实现键盘输入图的结构{inti,m,j;printf(请输入公园景点的个数：);//图结点的个数赋给graph.nscanf(%d,&m);graph.n=m;for(i=0;igraph.n;i++)//循环输入结点顶点信息{printf(请输入第%i个景点信息:,i);//为了简明起见此程序结点顶点信息限于字符型cingraph.vexs[i];}printf(请输入公园的邻接矩阵的信息\n);//循环输入图的邻接矩阵信息（也就是输入一个二维数组）for(i=0;igraph.n;i++)数据结构实验报告班级：06软件工程姓名：周邓雄学号：06517037for(j=0;jgraph.n;j++){printf(请输入第%d行，第%d列的元素:,i+1,j+1);cingraph.arcs[i][j];}}voidvist(GraphMatrixgraph)//函数用于实现访问任一景点的信息{inti;coutendl;cout你想知道哪个景点的信息：;//注意输入的是景点的编号cini;coutendl;cout景点信息查询结果为：;coutgraph.vexs[i];//输出景点信息coutendl;}intjud()//用于判断是否继续执行特定的下一步程序{inta;cout还想继续查询?(1&0);cina;returna;}intmain()数据结构实验报告班级：06软件工程姓名：周邓雄学号：06517037{inti,j;initgraph();//initgraph()函数来实现键盘输入图的结构floyd(&graph,&path);cout为了验证下面运算结果的方便，循环输出nextvex[i][j]数组;for(i=0;igraph.n;i++){for(j=0;jgraph.n;j++)//为了验证下面运算结果的方便，循环输出nextvex[i][j]数组printf(%d,path.nextvex[i][j]);//nextvex[i][j]存放vi到vj最短路径上vi的后继顶点的下标值putchar('\n');}coutendl;outgraph();while(jud())outgraph();//outgraph()函数用于实现显示起始点和终点间的最短路径和其长度vist(graph);//函数用于实现访问任一景点的信息coutendl;while(jud())vist(graph);coutendl;return0;}数据结构实验报告班级：06软件工程姓名：周邓雄学号：06517037验四：图（内容：某公园导游图）①.问题描述给出一张某公园的导游图，游客通过终端询问可知：（1）从某一景点到另一景点的最短路径。（2）游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览景点，最后回到出口（出口就在入口处旁边）。②.要求将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值给游客。③.实现提示（1）第一问实际是最短路径问题，如果有几条路径长度相同，可选择途径景点较少的路径提供给游客。（2）第二问可采用深度优先搜索，如果有多种路径可选择，则选择带权路径最小的路线提供给游客。④.选做内容可以把各种路径都显示给游客，由游客自己选择游览路线。数据结构实验报告班级：06软件工程姓名：周邓雄学号：06517037