校园导游图系统数据结构实验报告.doc

一. 设计目的通过布置具有一定难度的实际程序设计项目，使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法；使学生掌握分析问题，求解问题的方法并提高学生设计编程实现的能力。二. 设计内容用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。游客通过终端可询问： （1）从某一景点到另一景点的最短路径。（2）游客从公园进入，选取一条最佳路线。（3）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。基本要求 （1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离为此图选择适当的数据结构。 （2）把各种路径都显示给游客，由游客自己选择浏览路线。 （3）画出景点分布图于屏幕上。实现提示 （1）构造一个无向图G并用邻接矩阵来存储。 （2）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组pi来记录，最短路径长度就用一维数组di存放；i的范围：020。 （3）一维数组have是用来记录最短路径出现顶点的顺序。 （4）根据起点和终点输出最短路径和路径长度。三概要设计1功能模块图；结束退出系统两景点最短距离浏览校园全景查看景点信息某一景点到其余景点开始定义变量Void Menu()进入菜单Switch()选择功能2.各个模块详细的功能描述。1.浏览校园全景：采用深度遍历遍历图进行所有景点浏览，将遍历景点信息输出2.查看所有游览路线：用户输入一个景点，采用迪杰斯特拉算法将从该景点起所有路径查出并输出在屏幕上3.选择出发点和目的地：用户输入一个出发点和一个目的地编号，采用弗洛伊德算法求出发点到目的地的最短路径4.查看景点信息：直接用编号进行单个景点查询。四详细设计重点设计及编码在求最短路径时采用迪杰斯特拉算法/ 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点void ShortestPath_DIJ(MGraph * G) /迪杰斯特拉算法，求从顶点v0到其余顶点的最短路经及其带权长度dv /若pvw为1，则w是从v0到v的最短路经上的顶点 /finalv类型用于设置访问标志int v,w,i,min, final20, D20, p2020,t=0,x,flag=1,v0; /vo为起始景点的编号while(flag)printf(请输入一个起始景点编号:);scanf(%d,&v0);if(v0G-vexnum)printf(景点编号不存在!请重新输入景点编号:);scanf(%d,&v0);if(v0=0&v0vexnum)flag=0;for(v=0;vvexnum;v+)finalv=0;/初始化各顶点访问标志Dv=G-arcsv0v.adj; /v0 到各顶点 v 的权值赋值给dvfor(w=0;wvexnum;w+) /初始化p数组，各顶点间的路径全部设置为空路径0pvw=0;if(DvINFINITY)pvv0=1;pvv=1; /v0 到v 有边相连，修改pvv0的值为1 /各顶点自己到自己要连通Dv0=0; /自己到自己的权值设为0finalv0=1; /v0的访问标志设为1，v 属于 s 集for(i=1;ivexnum;i+) /对其余g.vexnum-1个顶点w，依次求 v 到 w 的最短路径min=INFINITY;for(w=0;wvexnum;w+)/在未被访问的顶点中，查找与 v0 最近的顶点vif(!finalw)if(Dwmin)/v0 到 w (有边)的权值minv=w;min=Dw;finalv=1; /v 的访问标志设置为1，v 属于s集for(w=0;wvexnum;w+)/修改v0 到其余各顶点w 的最短路径权值dwif(!finalw&(min+G-arcsvw.adjarcsvw.adj; /修改v0 到w 的权值dwfor(x=0;xvexnum;x+) /所有v0 到v 的最短路径上的顶点x，都是v0 到w 的最短路径上的顶点pwx=pvx;pww=1;for(v=0;vvexnum;v+) /输出v0 到其它顶点v 的最短路径if(v0!=v)printf(%s,G-); /输出景点v0 的景点名for(w=0;wvexnum;w+) /对图中每个顶点w，试探w 是否是v0 到v 的最短路径上的顶点if(pvw&w!=v0) /若w 是且w 不等于v0，则输出该景点printf(-%s,G-);t+;if(tG-vexnum-1&v0!=v)printf( 总路线长%dmnn,Dv);五测试数据及运行结果1正常测试数据和运行结果1.浏览校园全部景点信息：2.查看景点信息：3.输出两个景点间的最短路径:2异常测试数据及运行结果1.当输出错误编号时程序没有反映，继续输入直到输入正确：2.当查询两景点编号相同时的最短路径时，结果如下：六调试情况，设计技巧及体会每当写完一个函数的时候，一编译会出现很多错误，当时的信息一下就没了，但怎么样还得继续做下去，就这样坚持着改错误，慢慢的发现其实很多是由于自己粗心造成的，别的错误改多了就习惯了。1改进方案程序设计的不是很复杂，有的Bug没有修复，譬如，当输入景点编号为-1时，程序没有任何提示，也退不出系统；还有在功能方面，应该增加一项：路径的修改，这样就更便于管理改系统了，也就更方便用户使用。2体会经过几周的课程设计，我学到了很多东西：巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。够按要求编写课程设计报告书，能正确阐述设计和实验结果，正确绘制系统和程序框图。通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。同时，通过这次课程设计我发现，我的数据结构基础不够扎实，有很多地方还需要继续努力。 课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的