《[计算机软件及应用]简单校园导游实验报告的设计与实现.doc》由会员分享，可在线阅读，更多相关《[计算机软件及应用]简单校园导游实验报告的设计与实现.doc（33页珍藏版）》请在三一文库上搜索。
1、简单校园导游实验报告的设计与实现本实验的目的是通过对“校园导游”程序的设计与实现来熟练掌握图形结构在实际问题中的应用。一、问题描述当人们到一个陌生的地方去旅游时，可能会找一个导游为自己在游玩的过程中提供帮助。导游可以提供很多服务，如介绍参观景点的历史背景等相关消息，推经到下一个景点的最佳路径，解答旅游者所提出的关于旅游经典的相关问询等。对于刚刚来到校园的新生，对校园环境不熟悉的情况也是如此，一般都是高年级的学生充当“校园导游”的角色。如果能够提供一个程序让新生或来访的客人自主地通过与机器的“对话”来获得相关的信息的话，将会节省大量的的人力和时间，并且所提供的信息应做到尽可能的准确、详尽。一个成
2、功的校园导游程序可以代替现实生活中这些“校园导游”，更方便大家查询校园的信息。二、数据结构设计由于各场所通过校园中的道路相连，各个场所和连接它们的道路构成整个校园的地理环境，所以使用图这种数据结构对它们进行描述。以图中的顶点表示校园内各个场所，应包含场所名称、代号、描述等信息；以边表示连接各个场所的道路，包含道路的长度信息。图的定义：typedef structint vexn;int costnn;/* 边的值*/ MGraph;MGraph G;三、功能设计1、构建邻接矩阵，将边地信息存入矩阵中，存入边长，若两点间无邻接边，则存一个极大值MAX。函数原型如下：MGraph CreatMGr
3、aph(MGraph & G )/构建邻接矩阵，将边信息存入矩阵中 int i,j;for(i=0;in;i+)G.vexi=i;for(j=0;jn;j+) G.costij=MAX;G.cost01=G.cost10=400;G.cost02=G.cost20=500;G.cost03=G.cost30=700;G.cost04=G.cost40=100;G.cost05=G.cost50=200;G.cost09=G.cost90=800;G.cost15=G.cost51=250;G.cost24=G.cost42=200;G.cost37=G.cost73=150;G.cost39=
4、G.cost93=150;G.cost45=G.cost54=150;G.cost46=G.cost64=150;G.cost56=G.cost65=200;G.cost78=G.cost87=50;G.cost79=G.cost97=100;G.cost89=G.cost98=200;return G;2、景点介绍，函数原型如下：void introduce()/*景点介绍*/ int a; couta; getchar(); switch(a) case 0: cout0:学校大门nn 学校的正门，“河北大学”字样在蓝天的衬托下显得气势恢宏。nn;break; case 1: cout1:
5、多功能馆nn许多文艺节目在这里举行nn;break; case 2: cout2:八教nn 同学们上课与自习的地方，尤其到了期末复习时一般座无虚席nn;break; case 3: cout3：北院食堂nn 共有三层，种类较多，味道一般nn;break; case 4: cout4:图书馆nn 知识的海洋，各种书册种类丰富nn;break; case 5: cout5:主楼nn 河大的标志性建筑之一，很有气势nn;break; case 6: cout6:毓秀园nn 绿树成荫，大学的爱情生活从这里开始nn;break; case 7: cout7:熙园nn 男生宿舍nn;break; case
6、 8: cout8:超市nn 没饭吃的时候，学生的最爱nnn;break; case 9: cout9: 沁园nn 女生宿舍，每天晚上各种情侣在宿舍门口各种亲昵nn;break; default: cout10的数字编号！nn; break; /*introduce*/3、用Floyd算法求最短路径，并存入shortestnn;/* 两点间的最短距离*/中，函数原型如下：void Floyd (MGraph G)/*用Floyd 算法求两个景点的最短路径*/ int i,j,k; for(i=0;in;i+) for(j=0;jn;j+) shortestij=G.costij;if(shor
7、testijMAX) pathij=i;elseif(i!=j) pathij=-2;else pathij=-1; for(k=0;kn;k+) for(i=0;in;i+) for(j=0;j(shortestik+shortestkj) /*用path记录从i到j的最短路径上点j的前驱景点的序号*/ shortestij=shortestik+shortestkj; pathij=k;pathji=k;for(i=0;in;i+)pathii=-1;4、求最短路径，函数原型为：int shortestdistance(MGraph G)/*要查找的两景点的最短距离*/ int i,j;
8、cout9的数字编号):; cini; cinj; if(in|in|j0) cout输入信息错误！nn; cout9的数字编号):n; cini; cinj; else Floyd(G); display(i,j); return 1;/*shortestdistance*/void display(int i,int j)/* 打印两个景点的路径及最短距离*/ int a,b;if(ij)int c;c=i;i=j;j=c; a=i; b=j;coutendl; cout您要查询的两景点间最短路径是:nn; if(shortestijMAX&i!=j) coutb;while(ij)cou
9、tpathij;j=pathij;coutendl;cout最短路径长度为：shortestab;replace(); else cout输入错误！不存在此路！nn; /*display*/5、推荐路径算法就是将Floyd算法的第一个参数定为0，然后加循环既可，函数原型：void advice() Floyd(G); for(int j=1;jn;j+) display(0,j);四、界面设计本程序为方便用户所设计，由于用户大多对校园的情况并不熟悉，所以在图中给出的任何提示信息一定要准确，尽量避免歧义。五、编码实现#include stdafx.h#includeusing namespace
10、 std;/*定义符号常量*/#define MAX 1000000#define n 10/*定义全局变量*/int shortestnn;/* 两点间的最短距离*/int pathnn;/* 经过的景点*/typedef structint vexn;int costnn;/* 边的值*/ MGraph;MGraph G;/*自定义函数原型说明*/void introduce();void replace();int shortestdistance(MGraph G);void Floyd(MGraph G); void display(int i,int j);void advice(
11、);MGraph CreatMGraph(MGraph & G )/构建邻接矩阵，将边信息存入矩阵中 int i,j;for(i=0;in;i+)G.vexi=i;for(j=0;jn;j+) G.costij=MAX;G.cost01=G.cost10=400;G.cost02=G.cost20=500;G.cost03=G.cost30=700;G.cost04=G.cost40=100;G.cost05=G.cost50=200;G.cost09=G.cost90=800;G.cost15=G.cost51=250;G.cost24=G.cost42=200;G.cost37=G.cos
12、t73=150;G.cost39=G.cost93=150;G.cost45=G.cost54=150;G.cost46=G.cost64=150;G.cost56=G.cost65=200;G.cost78=G.cost87=50;G.cost79=G.cost97=100;G.cost89=G.cost98=200;return G;void main() /*主函数*/ CreatMGraph( G );while(1)coutnn -欢迎使用河北大学校园导游系统- n;coutnt1.景点信息查询请按i 键nn;coutt2.景点最短路径查询请按s 键nn;coutt3.推荐路径请按a
13、 键nn;coutt4.退出系统请按e 键nn;coutnt学校景点代码及名称（代码：景点名称）列表:nn;coutt0:学校大门 ;cout1:多功能馆 ;cout2:八教 ;cout3:北院食堂 ;cout4:图书馆nn;coutt5:主楼 ;cout6:毓秀园 ;cout7:熙园 ;cout8:超市 ;cout9：沁园nn;coutk;switch(k)case i:coutt进入景点信息查询:n;introduce();break;casea:cout推荐路径为：endl;advice();break;case s:coutt进入最短路径查询:;shortestdistance(G);
14、break; case e: exit(0); default:cout输入信息错误！n请输入字母i或s或e.n;break; /*main*/void introduce()/*景点介绍*/ int a; couta; getchar(); switch(a) case 0: cout0:学校大门nn 学校的正门，“河北大学”字样在蓝天的衬托下显得气势恢宏。nn;break; case 1: cout1:多功能馆nn许多文艺节目在这里举行nn;break; case 2: cout2:八教nn 同学们上课与自习的地方，尤其到了期末复习时一般座无虚席nn;break; case 3: cout
15、3：北院食堂nn 共有三层，种类较多，味道一般nn;break; case 4: cout4:图书馆nn 知识的海洋，各种书册种类丰富nn;break; case 5: cout5:主楼nn 河大的标志性建筑之一，很有气势nn;break; case 6: cout6:毓秀园nn 绿树成荫，大学的爱情生活从这里开始nn;break; case 7: cout7:熙园nn 男生宿舍nn;break; case 8: cout8:超市nn 没饭吃的时候，学生的最爱nnn;break; case 9: cout9: 沁园nn 女生宿舍，每天晚上各种情侣在宿舍门口各种亲昵nn;break; defau
16、lt: cout10的数字编号！nn; break; /*introduce*/void Floyd (MGraph G)/*用Floyd 算法求两个景点的最短路径*/ int i,j,k; for(i=0;in;i+) for(j=0;jn;j+) shortestij=G.costij;if(shortestijMAX) pathij=i;elseif(i!=j) pathij=-2;else pathij=-1; for(k=0;kn;k+) for(i=0;in;i+) for(j=0;j(shortestik+shortestkj) /*用path记录从i到j的最短路径上点j的前驱景
17、点的序号*/ shortestij=shortestik+shortestkj; pathij=k;pathji=k;for(i=0;in;i+)pathii=-1;int shortestdistance(MGraph G)/*要查找的两景点的最短距离*/ int i,j; cout9的数字编号):; cini; cinj; if(in|in|j0) cout输入信息错误！nn; cout9的数字编号):n; cini; cinj; else Floyd(G); display(i,j); return 1;/*shortestdistance*/void display(int i,int
18、 j)/* 打印两个景点的路径及最短距离*/ int a,b;if(ij)int c;c=i;i=j;j=c; a=i; b=j;coutendl; cout您要查询的两景点间最短路径是:nn; if(shortestijMAX&i!=j) coutb;while(ij)coutpathij;j=pathij;coutendl;cout最短路径长度为：shortestab;replace(); else cout输入错误！不存在此路！nn; /*display*/void advice() Floyd(G); for(int j=1;jn;j+) display(0,j);void repla
19、ce()cout学校名称用如下数字代替，请自行核对：endl;coutt0:学校大门 ;cout1:多功能馆 ;cout2:八教 ;cout3:北院食堂 ;cout4:图书馆nn;coutt5:主楼 ;cout6:毓秀园 ;cout7:熙园 ;cout8:超市 ;cout9：沁园nn;六、运行于测试1、景点信息查询2、推荐路径查询3、查询两点间的最短距离正输反输均可：4、若在输入过程中出现错误，会让从新输入5、景点查询输入错误，也会从新输入6、最短路径错误，提示从新输入七、实验总结通过对校园导游图的设计，我更加深刻的理解了邻接矩阵的存储与最短路径的求解方法。在设计途中，因为自己的粗心，使邻接矩阵没有在主函数中运行，使矩阵中存储信息错误，浪费了很多时间。但是从这件事中，我也明白了一个道理，编程需要耐心更需要细心，万万马虎不得！