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

实验四：图（内容：某公园导游图）一、问题描述：公园导游系统：给出一张某公园的导游图，游客通过终端询问可知从某一景到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。二、设计描述： 1.输入导游图的算法（存储方法）.本程序特地设计函数void initgraph()用于实现键盘输入图的结构；2.可访问导游图中任一景点的算法.为此设计了函数void vist(GraphMatrix graph)用于实现访问任一景点的信息；3.最短路径从一景点到另一景点的算法。利用floyd算法-实现每一对景点间的最短路径。并利用void outgraph()函数实现显示起始点和终点间的最短路径和其长度；三、程序清单：#includeusing namespace std;#include#define MAXVEX 100#define MAX 999 typedef char VexType;typedef float AdjType;typedef struct /定义图结构 int n; /* 图的顶点个数 */ VexType vexsMAXVEX; /* 顶点信息 */ AdjType arcsMAXVEXMAXVEX; /* 边信息 */ GraphMatrix;GraphMatrix graph; /定义一个图graphtypedef struct /定义最短路径ShortPath结构 AdjType aMAXVEXMAXVEX; /* 关系矩阵A，存放每对顶点间最短路径长度 */ int nextvexMAXVEXMAXVEX; /* nextvexij存放vi到vj最短路径上vi的后继顶点的下标值 */ ShortPath;ShortPath path; /定义路径pathvoid floyd(GraphMatrix * 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; else ppath-nextvexij = -1; ppath-aij = pgraph-arcsij; for (k = 0; k n; k+) for (i = 0; i n; i+) for (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;cout请输入想查找起始点和终点:; /输入要查找起始点和终点（本程序限于编号（int型）coutc;cinb;i=path.acb; /通过path.acb把路径长度赋给icout该路径总长为:;coutiendl; /输出路径长度cout所得路径顺序为;coutc; /此处输出路径的第一个编号 c=path.nextvexcb; for(;c!=b;c=path.nextvexcb) /循环顺序输出路径始点和终点之间的景点编号cout,c;cout,b; /再输出路径的最后一个编号 coutendl;void initgraph() /该函数用于实现键盘输入图的结构int i,m,j;printf(请输入公园景点的个数：); /图结点的个数赋给graph.nscanf(%d,&m);graph.n=m;for(i=0;igraph.vexsi;printf(请输入公园的邻接矩阵的信息n);/循环输入图的邻接矩阵信息（也就是输入一个二维数组）for(i=0;igraph.n;i+)for(j=0;jgraph.arcsij;void vist(GraphMatrix graph) /函数用于实现访问任一景点的信息 int i; coutendl; couti; coutendl; cout景点信息查询结果为：; coutgraph.vexsi; /输出景点信息 coutendl;int jud() /用于判断是否继续执行特定的下一步程序int a;couta;return a;int main() int i,j; initgraph(); /initgraph()函数来实现键盘输入图的结构 floyd(&graph, &path); cout为了验证下面运算结果的方便，循环输出nextvexij数组; for (i = 0; i graph.n; i+) for (j = 0; j graph.n; j+) /为了验证下面运算结果的方便，循环输出nextvexij数组 printf(%d , path.nextvexij); /nextvexij存放vi到vj最短路径上vi的后继顶点的下标值 putchar(n); coutendl; outgraph(); while(jud() outgraph(); /outgraph()函数用于实现显示起始点和终点间的最短路径和其长度 vist(graph); /函数用于实现访问任一景点的信息 coutendl; while(jud() vist(graph); coutendl; return 0;验四：图（内容：某公园导游图）.问题描述给出一张某公园的导游图，游客通过终端询问可知：（1）从某一景点到另一景点的最短路径。（2）游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览景点，最后回到出口（出口就在入口处旁边）。. 要求将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值给游客。.实现提示（1）第一问实际是最短路径问题，如果有几条路径长度相同，可选择途径景点较少的路径提供给游客。（2）第二问可采用深度优先搜索，如果有多种路径可选择，则选择带权路径最小的路线提供给游客。.选做内容可以把各种路径都显示给游客，由游客自己选择游览路线。