校园导游咨询(最短路径).doc

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