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

1、数据结构实验报告班级： 06 软件工程姓名：周邓雄学号： 06517037实验 四：图(内容：某公园导游图) 一、问题描述： 公园导游系统：给出一张某公园的导游图，游客通过终端询问可知：从某 一景到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客 可以不重复地游览各景点，最后回到出口(出口就在入口旁边)。 二、设计描述： 1输入导游图的算法(存储方法)本程序特地设计函数void initgraph()用于 实现键盘输入图的结构； 2. 可访问导游图中任一景点的算法 .为此设计了函数 void vist(GraphMatrix graph)用于实现访问任一景点的信息； 3. 最短路

2、径从一景点到另一景点的算法。利用 floyd 算法-实现每一对景点间 的最短路径。 并利用void outgraph()函数实现显示起始点和终点间的最短路径和其长度； 三、程序清单： #include using namespace std; #include #define MAXVEX100 #define MAX 999 typedef char VexType; 数据结构实验报告班级： 06软件工程姓名：周邓雄学号： 06517037typedef float AdjType; typedef struct/ 定义图结构 int n;/* 图的顶点个数 */ VexType vexsM

3、AXVEX;/顶点信息 */ AdjType arcsMAXVEXMAXVEX;/边信息 */ GraphMatrix; GraphMatrix graph;/ 定义一个图 graph typedef struct/ 定义最短路径 ShortPath 结构 AdjType aMAXVEXMAXVEX;/关系矩阵A,存放每对顶点间最短路径长度 */int nextvexMAXVEXMAXVEX; /* nextvexij 存放 vi 到 vj 最短路径上 vi 的后继顶点的下标值 */ ShortPath; ShortPath path;/ 定义路径 path void floyd(GraphM

4、atrix * pgraph, ShortPath * ppath)/floyd 算法-用于实现每 一对景点间的最短路径 int i, j, k; for (i = 0; i n; i+) for (j = 0; j n; j+) if (pgraph-arcsij != MAX) ppath-nextvexij = j; 数据结构实验报告班级： 06 软件工程姓名：周邓雄学号： 06517037else ppath-nextvexij = -1; ppath-aij = pgraph-arcsij; for (k = 0; k n; k+) for (i = 0; i n; i+) for

5、(j = 0; j n; j+) if ( ppath-aik = MAX | ppath-akj = MAX ) continue; if ( ppath-aij ppath-aik+ ppath-akj ) ppath-aij = ppath-aik + ppath-akj; ppath-nextvexij = ppath-nextvexik; void outgraph()/out() 函数用于实现显示起始点和终点间的最短路径和其长 度 int c,b,i; coutendl; coutvv请输入想查找起始点和终点：;/输入要查找起始点和终点(本程序 限于编号( int 型) coutc

6、; cinb; i=path.acb;通过path.acb把路径长度赋给i数据结构实验报告班级: 06软件工程姓名：周邓雄学号：06517037coutv，该路径总长为:; coutiendl;/ 输出路径长度 coutvv所得路径顺序为; coutc;/ 此处输出路径的第一个编号 c=path.nextvexcb; for(;c!=b;c=path.nextvexcb)/ 循环顺序输出路径始点和终点之间的景点编 号 cout,c; cout,b;/ 再输出路径的最后一个编号 coutendl; void initgraph()/ 该函数用于实现键盘输入图的结构 int i,m,j; prin

7、tf( 请输入公园景点的个数： );/ 图结点的个数赋给 graph.n scanf(%d, graph.n=m; for(i=0;igraph.vexsi; printf( 请输入公园的邻接矩阵的信息 n);/ 循环输入图的邻接矩阵信息(也 就是输入一个二维数组) for(i=0;igraph.n;i+) 数据结构实验报告班级： 06 软件工程姓名：周邓雄学号： 06517037for(j=0;jgraph.arcsij; void vist(GraphMatrix graph)/ 函数用于实现访问任一景点的信息 int i; couti; coutendl; coutvv景点信息查询结果为

8、：; couta; return a; int main() 数据结构实验报告班级： 06软件工程姓名：周邓雄学号： 06517037 int i,j; initgraph();/initgraph() 函数来实现键盘输入图的结构 floyd( coutvv为了验证下面运算结果的方便，循环输出nextvexij数组; for (i = 0; i graph.n; i+) for (j = 0; j graph, n; j+)为了验证下面运算结果的方便，循环输出 nextvexij 数组 printf(%d , path.nextvexij);/nextvexij 存放 vi 到 vj 最短路

9、径上 vi 的后继顶点的下标值 putchar(n); coutendl; outgraph(); while(jud() outgraph();/outgraph() 函数用于实现显示起始点和终点间的最短路径和其长 度vist(graph);/函数用于实现访问任一景点的信息coutendl; while(jud() vist(graph); coutendl; return 0; 数据结构实验报告班级： 06 软件工程姓名：周邓雄学号： 06517037验四： 图(内容：某公园导游图) , 问题描述 给出一张某公园的导游图，游客通过终端询问可知： （1）从某一景点到另一景点的最短路径。 （2）游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览景 点，最后回到出口（出口就在入口处旁边）。 .要求 将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点 之间的道路，边上的权值给游客。 .实现提示 （1）第一问实际是最短路径问题，如果有几条