资源描述：
《校园导游咨询(最短路径).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构课程设计实验报告学号：姓名：提交日期：成绩：东北大学秦皇岛分校网络技术实验报告设计题目：校园导游咨询一、实验目的（1）熟练掌握图的创建及遍历基本操作算法。（2）熟练掌握最短路径算法。（3）利用图的遍历和最短路径求解技术，设计一个校园导游程序，为来访的客人提供各种信息查询服务。二、需求分析实验内容【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】(1)设计你所在学校的校园平面图,所含景点不少于10个。以图中顶点表示校内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等相关信息。(2)为来访客人提
2、供图中任意景点相关信息的查询。(3)为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。【测试数据】由读者根据实际情况指定。【实现提示】一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。【实现功能】这个系统给用户提供查询景点，浏览路径，寻找最佳的方案到达目的地，还提供了最佳路径。三、概要设计1.系统分析：用的图的算法进行构造，用邻接表建立图，图的每一个顶点代表相应的景点。然后再用深度优先遍历进行搜索，查找所需的路径。再用迪杰特斯拉算法求出一个景点到其他景点之间的最佳路径。然后再用弗
3、洛伊德算法求出要查询的出发点到目的地的最短路径。东北大学秦皇岛分校电子信息系第15页网络技术实验报告2．功能模块图；结束查看各景点游览路线开始定义变量VoidMenu()进入菜单Switch()选择功能退出系统浏览校园全景显示此图的邻接矩阵查看景点信息选择出发点和目的地3.各个模块详细的功能描述（1）主菜单（Menu）：存放着所有的选择供用户查询。用户可通过输入编号来查询自己想要获得的信息。（2）浏览校园全景（Browser）：采用深度遍历遍历图进行所有景点浏览，将遍历景点信息输出。东北大学秦皇岛分校电子信息系第15页网络技术实验报告（3）查看各景
4、点游览路线（ShortestPath_DIJ）：用户输入一个景点，采用迪杰斯特拉算法将从该景点起所有路径查出并输出在屏幕上。（4）选择出发点和目的地(Floyd)：用户输入一个出发点和一个目的地编号，采用弗洛伊德算法求出发点到目的地的最短路径。（5）查看景点信息(Search)：直接输入编号进行单个景点查询。（6）显示图的邻接矩阵(print)（7）退出系统(exit)四．详细设计（1）图的结构typedefstructArCell//对弧的定义{intadj;//路径长度}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_
5、VERTEX_NUM];typedefstruct//图中顶点表示主要景点，存放景点的编号、名称、简介等信息，{charname[30];intnum;charintroduction[100];//简介}infotype;//数据域typedefstruct{infotypevexs[MAX_VERTEX_NUM];//顶点的数据域AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}MGraph;（2）各个函数的声明如下：voidcmd(void);MGraphInitGraph(void);//初
6、始化图voidMenu(void);//整体菜单voidBrowser(MGraph*G);//遍历校园全景voidShortestPath_DIJ(MGraph*G);//景点所有路线voidFloyd(MGraph*G);//两景点之间最短距离voidSearch(MGraph*G);//查看景点信息voidprint(MGraph*G);//输出该图邻接矩阵（3）主函数voidmain(void)//定义主函数{system("color1f");system("modecon:cols=100lines=40");cmd();//调用cmd
7、（）}（4）主要函数<1>迪杰斯特拉算法算法思想：依路径长度递增的次序求得各条路径//迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点voidShortestPath_DIJ(MGraph*G){intv,w,i,min,t=0,x,flag=1,v0;//flag=1保证输入编号有效东北大学秦皇岛分校电子信息系第15页网络技术实验报告intfinal[20],D[20],p[20][20];//用迪杰斯特拉算法求网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v]//若P[v][w]为1，则w是从v0到v当前求得最短路径上
8、的顶点//final[v]为1当且仅当v属于s(s是已求得最短路径的终点的集合)，即已经求得从v0到v的最短路径while
