用图论实现校园导游咨询 [文档在线提供].doc

校园导游咨询一：需求分析【基本要求】1、设计某大学校区的校园平面图（不在程序中画图），包含你熟悉的至少10个景点。以图中顶点表示校内各景点，存放景点名称、简介等信息；以边表示路径，存放路径长度等相关信息。2、为来访客人提供图中任意景点相关信息的查询。3、为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。【测试数据】根据自己对学校熟悉情况自定。二：概要设计1 抽象数据类型图的定义如下：ADT Graph数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。数据关系：Graph = (V , R )。其中，R| v,wV且P(v,w) ， 表示从v到w的一条弧基本操作P：/ ADT Graph2本程序包含三个模块：（1） 主程序模块：void main() /*主函数*/初始化；while(1) 显示界面；接受命令；处理命令；键入E或e退出；/main实现人机界面和命令处理（2） 景点查询模块：void introduce() 输入景点编号；Switch() case 1; printf(查询信息); /景点介绍(3) 最短距离模块；int shortestdistance() 初始化；输入要查询的两个景点的编号if(输入数字10 or 10的数字编号！nn”); break; /* introduce */（3）要查找的两景点的最短距离：int shortestdistance()/*要查找的两景点的最短距离*/int i,j; printf(“请输入要查询的两个景点的编号(1-10的数字编号并用,间隔):”); scanf(“%d,%d”,&i,&j); if(in|in|j10的数字编号并用,间隔):n”);scanf(“%d,%d”,&i,&j); else floyed();display(i,j); return 1;/*shortestdistance*/（4）弗洛伊德算法：void floyed()/*用floyed算法求两个景点的最短路径*/int i,j,k; for(i=1;i=n;i+) for(j=1;j=n;j+) shortestij=costij;pathij=0; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j(shortestik+shortestkj) /*用path记录从i到j的最短路径上点j的前驱景点的序号*/shortestij=shortestik+shortestkj; pathij=k; pathji=k; /*floyed*/（2）函数的调用关系图main Introduce shortestdistance Floyed display四：调试分析1 由于导游程序在实际执行时，需要根据用户的临时输入求最短路径。以全局变量来存储最短距离以及所经过的景点，虽然时间复杂度为O( n)，但只须计算一次以后只要查表即可，有利于之进行一次查询即可得出所有路径，节省了查询时间，提高了查询效率。2采用稀疏矩阵的存储方法，其时间是均在查找最短路径时消耗，故时间复杂度即为floyed算法的时间复杂度O( n)。五：用户手册1 本程序的运行环境为DOS控制台，执行文件为：图.exe2进入程序后即显示用户界面，有3种操作可供实现：景点信息查询，景点最短路径查询，退出系统，用户可根据提示操作。3景点信息查询：出现提示信息后，输入查询景点号，程序可给出查询信息。4景点最短路径查询：出现提示信息后，输入要查询的两个景点的编号，程序既可给出查询信息。5退出：程序结束。六：测试结果1景点信息查询,操作命令符i:2景点最短路径查询，操作命令符s:3 退出, 操作命令符e,程序退出结束。七：附录源程序文件名清单： 图.C /主程序 图.exe /执行程序源码：#define INT_MAX 10000#define n 10/*定义全局变量*/int costnn;/* 边的值*/int shortestnn;/* 两点间的最短距离*/int pathnn;/* 经过的景点*/*自定义函数原型说明*/void introduce();int shortestdistance();void floyed(); void display(int i,int j);void main() /*主函数*/ int i,j; char k; for(i=0;i=n;i+) for(j=0;j10的数字编号！nn); break; /*introduce*/int shortestdistance()/*要查找的两景点的最短距离*/ int i,j; printf(请输入要查询的两个景点的编号(1-10的数字编号并用,间隔):); scanf(%d,%d,&i,&j); if(in|in|j10的数字编号并用,间隔):n);scanf(%d,%d,&i,&j); else floyed();display(i,j); return 1;/*shortestdistance*/void floyed()/*用floyed算法求两个景点的最短路径*/ int i,j,k; for(i=1;i=n;i+) for(j=1;j=n;j+) shortestij=costij;pathij=0; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j(shortestik+shortestkj) /*用path记录从i到j的最短路径上点j的前驱景点的序号*/shortestij=shortestik+shortestkj;pathij=k;pathji=k; /*floyed*/void display(int i,int j)/* 打印两个景点的路径及最短距离 */ int a,b; a=i; b=j; printf(您要查询的两景点间最短路径是:nn); if(shortestij!=INT_MAX) if(ij) printf(%d,b);while(pathij!=0)/* 把i到j的路径上所有经过的景点按逆序打印出来*/printf(-%d,pathij);if(ij)j=pathij; else i=pathji; printf(%d)最短距离是:%d米nn,a,b,shortestab);else printf(%d,a);while(pathij!=0)/* 把i到j的路径上所有经过的景