校园导航系统-数据结构

《数据结构预与算法分析》课程设计报告题目：校园导航系统班级：网络工程姓名：xxx学号：xxxxxxx指导教师：xxx日期：2016/7/112目录1.任务说明（要求、知识点、实现的功能）...................................................................................11.1题目:........................................................................................................................................11.2要求:........................................................................................................................................11.3知识点：.................................................................................................................................12．概要设计（结构体类型及函数声明，功能模块图，流程图）................................................12.1结构体类型及函数声明.........................................................................................................12.2功能模块图.............................................................................................................................22.3流程图.....................................................................................................................................23.1节点数据结构类型：.............................................................................................................43.2创建导航图函数：.................................................................................................................43.3最短路径导航函数：.............................................................................................................43.4导航菜单函数声明.................................................................................................................54调试分析（出现哪些问题，如何解决）.......................................................................................55．测试结果........................................................................................................................................56．总结................................................................................................................................................77.附录...................................................................................................................................................87.1源代码.....................................................................................................................................87.2参考文献...............................................................................................................................1811.任务说明（要求、知识点、实现的功能）1.1题目:校园导航系统1.2要求:用无向网表示你所在学校的校园景点品面图，图中顶点表示主要景点，存放景点的编号，名称，简绍等信息，图中的边表示景点间的道路，存放路径长度等信息。系统功能:（1）景点信息简绍（2）任意两景点间最短距离（3）任意一点到所有点最短距离1.3知识点：图的创建，图的搜素，领接矩阵，迪杰斯特拉算法，结构体，函数的声明与调用等知识点。2．概要设计（结构体类型及函数声明，功能模块图，流程图）2.1结构体类型及函数声明在近一个星期的努力下，我编写的校园导航系统软件终于能够成功完成。采用工程思想，将系统共分一下几个模块:导航图建立模块、求最短路径模块、主菜单；下面是具体各功能简单的实际应用：导航图建立模块：采用上述结构体类型对导航图中每个节点进行赋值。包括：各定点的名称（地点名），各个节点到其他所有节点的真实路径长度（赋权值）。求最短路径模块：本模块的基本思想是采用迪杰斯特拉算法求最短路径。次模块是本校园导航系统的核心模块，求两点间的最短路径与求一点到其他所有点最短路径两个子功能均是在最短路径算法模块的基础上进行调用，进而实现导航功2能。主菜单：主菜单中主要是显示导航图中的所有导航节点，能够快速方便的对各个地点进行导航。以上程序的几个模块，构成了校园导航系统的基本组成部分，程序运行良好，达到了课程设计的基本要求。由于所学知识有限，功能各个方面还有欠妥之处，希望得到指出与改正。函数声明：intCreateUDN(MGraph&G)创建导航图函数voidShortPath(MGraph&G,intv0,intp[MAX_V][MAX_V],intd[])最短路径导航函数voidmenu()导航菜单声明2.2功能模块图总功能模块图2.3流程图校园导航系统获取最短路径查询最短路径存储导航图任意俩景点之间某景点到所有景点查询最短路径获取最短路径3迪杰斯特拉算法流程图开始k=1v=0vG.vexnumfinal[v]=0d[v]=G.arcs[v0-1][v]w=0wG.vexnump[v][w]=0w++d[v]INFINITYp[v][v0-1]=1p[v][v]=1Y1YNNYNd[v0-1]=0final[v0-1]=1have[0]=v0-1i=11iG.vexnummin=INFINITYw=0wG.vexnum!final[w]&&d[w]minv=wmin=d[w]final[v]=1have[k]=vk++w=0wG.vexnum!final[w]&&(min+G.arcs[v][w]d[w])d[w]=min+G.arcs[v][w]jG.vexnumj=0p[w][j]=p[v][j]p[w][w]=1YYYYYYNNNNEndNN43．详细设计（数据类型实现、编码）3.1节点数据结构类型：#defineMAX_V40//最大顶点个数typedefstruct{char*vexs[MAX_V];//顶点向量intarcs[MAX_V][MAX_V];//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}MGraph;3.2创建导航图函数：intCreateUDN(MGraph&G)函数描述：主要将每个节点进行命名、每个顶点到其他所有定点的路径值用邻接矩阵进行存储。例：G.vexs[0]=校门;G.vexs[2]=校办公室;作用：使0号定点命名为“校门”；G.arcs[0][2]=G.arcs[2][0]=900;作用：使0号节点到2号节点的路径赋值为900，因为是无向图，所以2号节点到0号节点的路径长度也应赋值为900；3.3最短路径导航函数：voidShortPath(MGraph&G,intv0,intp[MAX_V][MAX_V],intd[])函数描述：用Dijkstra算法求无向网G的V0定点到其余定点V的最短路径P[v]及其带权长度D[v]。若P[v][w]为True，则w是从V0到V当前求得最短路径上的顶点。5Final[v]为True当且仅当V∈S，即已经求得从V0到V的最短路径。3.4导航菜单函数声明voidmenu()函数描述：输出各个节点的编号，放便导航。4调试分析（出现哪些问题，如何解决）问题：在程序的一开始是准备，将系统共分为:数据结构定义模块、导航图建立模块、求最短路径模块、主菜单这四个模块的来构成了校园导航系统的基本组成部分，但调试的过程数据结构定义这一模块总是出现调试错误，程序的调试一度进入难题。改进方法：由于数据结构定义模块总出错，便不再把数据结构定义设为单独的模块，而是在每一个其他模块中都进行一次编写，这样就避免了数据结构定义模块的调用错误，虽然这样使得程序变得冗余，但好在能调试成功，能使校园导航系统按照预先的设想正常运行。5．测试结果系统登陆界面：6导航功能1——景点信息介绍导航功能2——两点最短距离导航测试结果如下7导航功能3——某点到其他所有点的距离6．总结经过一个学期对数据结构课程的学习，我能够掌握数据结构所教会我的对待问题的方法，以及遇到问题时如何抽象出一个合理的数据结构类型。数据结构教会我的不但是每一个算法，更多的是如何解决问题的方法。例如，在本次课程设计中我做的是校园导航系统，对于校园导航问题的关键是最短路径的问题，在教材中有算法——迪杰斯特拉求最短路径问题，在花了几天时间后，终于能够将算法的整个流程弄清楚，在对各个定点的存储上采用邻接矩阵的方法，在寻找各个点到其他所有点的关系的时候更为方便直观。在课程设计中遇到的一系列问题都能够在老师和同学的指导下及时解决。最后，感谢一年来为我们付出努力的老师们，感谢给过我指导意见的同学们，在这一年对数据结构的学习中，真的收获颇多，为我以后继续学习计算机的基础课程打下了坚实的基础。87.附录7.1源代码Creat.cpp#includestdio.h#defineMAX_V36#defineINFINITY32767typedefstruct{char*vexs[MAX_V];intarcs[MAX_V][MAX_V];intvexnum,arcnum;}MGraph;intCreateUDN(MGraph&G){inti=