《用图论实现校园导游咨询 [文档在线提供].doc》由会员分享，可在线阅读，更多相关《用图论实现校园导游咨询 [文档在线提供].doc（13页珍藏版）》请在金锄头文库上搜索。
1、校园导游咨询一：需求分析【基本要求】1、设计某大学校区的校园平面图（不在程序中画图），包含你熟悉的至少10个景点。以图中顶点表示校内各景点，存放景点名称、简介等信息；以边表示路径，存放路径长度等相关信息。2、为来访客人提供图中任意景点相关信息的查询。3、为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。【测试数据】根据自己对学校熟悉情况自定。二：概要设计1 抽象数据类型图的定义如下：ADT Graph数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。数据关系：Graph = (V , R )。其中，R| v,wV且P(v,w) ， 表示从v到w的一条弧基
2、本操作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 s
3、hortestdistance()/*要查找的两景点的最短距离*/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
4、+) 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 由于导游程序在实际执行时，需要根据用户的临时输入求最短路径。以全局变量来存储最短距离以及
5、所经过的景点，虽然时间复杂度为O( n)，但只须计算一次以后只要查表即可，有利于之进行一次查询即可得出所有路径，节省了查询时间，提高了查询效率。2采用稀疏矩阵的存储方法，其时间是均在查找最短路径时消耗，故时间复杂度即为floyed算法的时间复杂度O( n)。五：用户手册1 本程序的运行环境为DOS控制台，执行文件为：图.exe2进入程序后即显示用户界面，有3种操作可供实现：景点信息查询，景点最短路径查询，退出系统，用户可根据提示操作。3景点信息查询：出现提示信息后，输入查询景点号，程序可给出查询信息。4景点最短路径查询：出现提示信息后，输入要查询的两个景点的编号，程序既可给出查询信息。5退出：
6、程序结束。六：测试结果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
7、 j);void main() /*主函数*/ int i,j; char k; for(i=0;i=n;i+) for(j=0;j=n;j+) costij=INT_MAX; cost12=cost21=2; cost23=cost32=1; cost24=cost42=2; cost34=cost43=4; cost14=cost41=5; cost25=cost52=3; cost510=cost105=8; cost56=cost65=2; cost67=cost76=1; cost78=cost87=3; cost79=cost97=3; cost89=cost98=4; cost1
8、1=cost22=cost33=cost44=cost55=0; cost66=cost77=cost88=cost99=cost1010=0; while(1) printf(-欢迎使用校园导游系统!-n);printf(1.景点信息查询请按 i (introduc)键n);printf(2.景点最短路径查询请按 s (shortestdistance)键n);printf(3.退出系统请按 e (exit)键n);printf(学校景点列表:n);printf(1:学校南门 );printf(2:一号教学楼 );printf(3:体育馆 );printf(4:大学生活动中心 );printf(5:带河n);printf(6:后山 );printf(7:自由广场 );printf(8:风雨操场 ); printf(9:图书馆 );printf(10:竹园n);printf(请选择服务:);scanf(n%c,&k); switch(k) case i:printf(进入景点信息查询:);introduce();break; case s:printf(进入最短路径查询:);shortestdistance();break; case e:exit(0); default:printf(输入信息错误！n请输入字母i或s或e.n);break;
