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

数据结构课程设计实验报告学号：姓名：提交日期：成绩：东北大学秦皇岛分校网络技术实验报告东北大学秦皇岛分校电子信息系第1页设计题目：校园导游咨询一、实验目的（1）熟练掌握图的创建及遍历基本操作算法。（2）熟练掌握最短路径算法。（3）利用图的遍历和最短路径求解技术，设计一个校园导游程序，为来访的客人提供各种信息查询服务。二、需求分析实验内容【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】(1)设计你所在学校的校园平面图,所含景点不少于10个。以图中顶点表示校内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等相关信息。(2)为来访客人提供图中任意景点相关信息的查询。(3)为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。【测试数据】由读者根据实际情况指定。【实现提示】一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。【实现功能】这个系统给用户提供查询景点，浏览路径，寻找最佳的方案到达目的地，还提供了最佳路径。三、概要设计1.系统分析：用的图的算法进行构造，用邻接表建立图，图的每一个顶点代表相应的景点。然后再用深度优先遍历进行搜索，查找所需的路径。再用迪杰特斯拉算法求出一个景点到其他景点之间的最佳路径。然后再用弗洛伊德算法求出要查询的出发点到目的地的最短路径。网络技术实验报告东北大学秦皇岛分校电子信息系第2页2．功能模块图；3.各个模块详细的功能描述（1）主菜单（Menu）：存放着所有的选择供用户查询。用户可通过输入编号来查询自己想要获得的信息。（2）浏览校园全景（Browser）：采用深度遍历遍历图进行所有景点浏览，将遍历景点信息输出。开始定义变量浏览校园全景查看各景点游览路线选择出发点和目的地显示此图的邻接矩阵退出系统VoidMenu()进入菜单Switch()选择功能查看景点信息结束网络技术实验报告东北大学秦皇岛分校电子信息系第3页（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;charintroduction[100];//简介}infotype;//数据域typedefstruct{infotypevexs[MAX_VERTEX_NUM];//顶点的数据域AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}MGraph;（2）各个函数的声明如下：voidcmd(void);MGraphInitGraph(void);//初始化图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（）}（4）主要函数1迪杰斯特拉算法算法思想：依路径长度递增的次序求得各条路径//迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点voidShortestPath_DIJ(MGraph*G){intv,w,i,min,t=0,x,flag=1,v0;//flag=1保证输入编号有效网络技术实验报告东北大学秦皇岛分校电子信息系第4页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(v00||v0G-vexnum){printf(景点编号不存在!请重新输入景点编号:);scanf(%d,&v0);}if(v0=0&&v0G-vexnum)flag=0;}for(v=0;vG-vexnum;v++){final[v]=0;//v不属于s，即v顶点还没有走过D[v]=G-arcs[v0][v].adj;//v0到v的弧权值for(w=0;wG-vexnum;w++)p[v][w]=0;//设置空路径if(D[v]INFINITY){p[v][v0]=1;p[v][v]=1;//v0是从v0到v的顶点，v是从v0到v的顶点}}D[v0]=0;final[v0]=1;//初始化，v0到v0的带权路径长度为0，最短路径,v0顶点属于s集//开始主循环，每次求得v0到某个v顶点的最短路径，并加v到s集for(i=1;iG-vexnum;i++)//其余G.vexnum-1个顶点{min=INFINITY;//当前所知离v0顶点的最近距离for(w=0;wG-vexnum;w++)if(!final[w])//w顶点在v-s中if(D[w]min){v=w;min=D[w];}//w顶点离v0顶点更近final[v]=1;//离v0顶点最近的v加入s集for(w=0;wG-vexnum;w++)//更新当前的最短路径及距离if(!final[w]&&(min+G-arcs[v][w].adjD[w]))//修改D[w]和P[w]，w属于v-s{D[w]=min+G-arcs[v][w].adj;for(x=0;xG-vexnum;x++)p[w][x]=p[v][x];p[w][w]=1;}}//用来更新到每一个顶点的最短路径for(v=0;vG-vexnum;v++){if(v0!=v)printf(%s,G-vexs[v0].name);//输出字符串for(w=0;wG-vexnum;w++){if(p[v][w]&&w!=v0)printf(--%s,G-vexs[w].name);t++;}if(tG-vexnum-1&&v0!=v)printf(总路线长%dm\n\n,D[v]);}}//ShortestPath_DIJend网络技术实验报告东北大学秦皇岛分校电子信息系第5页2Floyd算法算法思想：从vi到vj的所有存在的路径中，选出一条长度最短的路径，即每一对顶点之间的最短路径。voidFloyd(MGraph*G)//用Floyd算法求图中各对顶点v和w之间的最短路径P[v][w]及其//带权长度D[v][w]。若P[v][w][u]为1，则u是从v到w当前求得最短//路径上的顶点。{intv,u,i,w,k,j,flag=1,p[10][10][10],D[10][10];for(v=0;vG-vexnum;v++)//各对结点之间初始已知路径及距离for(w=0;wG-vexnum;w++){D[v][w]=G-arcs[v][w].adj;for(u=0;uG-vexnum;u++)p[v][w][u]=0;if(D[v][w]INFINITY){p[v][w][v]=1;p[v][w][w]=1;}}for(u=0;uG-vexnum;u++)for(v=0;vG-vexnum;v++)for(w=0;wG-vexnum;w++)if(D[v][u]+D[u][w]D[v][w])//从v经u到w的一条路径更短{D[v][w]=D[v][u]+D[u][w];//修改权值for(i=0;iG-vexnum;i++)p[v][w][i]=p[v][u][i]||p[u][w][i];}while(flag){printf(请输入出发点和目的地的编号:);scanf(%d%d,&k,&j);if(k0||kG-vexnum||j0||jG-vexnum){printf(景点编号不存在!请重新输入出发点和目的地的编号:);scanf(%d%d,&k,&j);}if(k=0&&kG-vexnum&&j=0&&jG-vexnum)flag=0;}printf(%s,G-vexs[k].name);for(u=0;uG-vexnum;u++)if(p[k][j][u]&&k!=u&&j!=u)printf(--%s,G-vexs[u].name);printf(--%s,G-vexs[j].name);printf(总路线长%dm\n,D[k][j]);}//Floydend网络技术实验报告东北大学秦皇岛分校电子信息系第6页五、测试结果程序界面：主界面：1.浏览校园全景网络技术实验报告东北大学秦皇岛分校电子信息系第7页2.查看各景点所有游览路线输入景点编号1：输入顶点编号3：网络技术实验报告东北大学秦皇岛分校电子信息系第8页3.选择出发点和目的地输入出发点和目的地的编号分别是：2和8输入出发点和目的地的编号分别是：1和9网络技术实验报告东北大学秦皇岛分校电子信息系第9页4.查看景点信息查看景点信息：1查看景点信息4：网络技术实验报告东北大学秦皇岛分校电子信息系第10页5.显示此图的邻接矩阵6.退出系统六、调试与分析刚开始调试时出现很多错误，有些忘了写头文件，然后迅速从网上查到该词的头文件加在程序里。也有的函数忘记了提前声明导致了程序不能运行，以及其他各种问题。不过最后都能够通过各种途径调试出来，有查书的，也有向同学请教的。当程序能够正常运行出来时，界面显示也出现了很多问题。有的是因为少了换行符，导致界面排列不好。不过，最终都慢慢地改了过来。七、心得与体会经过两周的课程设计收获很多，在做课程设计之前，我觉得这是一项浩大的工程，总觉得自己会做不到。现在当我真的完成这个课程设计时，心里有一种成就感。这次课程设计，我学到了很多东西：学会了在编写几百行程序时如何查找错误，如何改错误；了解数据结构在编写比较复杂的程序的重要作用；对数据结构中定义无向图和创建无向图的理解更加深刻；最重要的是让我基本上明白了迪杰斯特拉算法和弗洛伊德算法。巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试，网络技术实验报告东北大学秦皇岛分校电子信息系第11页掌握应用软件的分析方法和工程设计方法。够按要求编写课程设计报告书，能正确阐述设计和实验结果，正确绘制系统和程序框图。通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。同时，通过这次课程设计我发现，我的数据结构基础不够扎实，有很多地方还需要继续努力。课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我