数据结构+课程设计+校园最短路径问题

一、课程设计题目： 校园最短路径问题二、课程设计目的：1. 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所具备的科学工作方法和作风。三、课程设计要求：1. 设计的题目要求达到一定的工作量（300 行以上代码） ，并具有一定的深度和难度。2. 编写出课程设计报告书，内容不少于 10 页（代码不算） 。四、需求分析 ：1、问题描述图的最短路径问题是指从指定的某一点 v 开始，求得从该地点到图中其它各地点的最短路径，并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。校园最短路径问题中的数据元素有：a) 顶点数b) 边数c) 边的长度2、功能需求要求完成以下功能：a) 输出顶点信息：将校园内各位置输出。b) 输出边的信息：将校园内每两个位置（若两个位置之间有直接路径）的距离输出。c) 修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离。d) 求最短路径：输出给定两点之间的最短路径的长度及途径的地点或输出任意一点与其它各点的最短路径。e) 删除：删除任意一条边。f) 插入：插入任意一条边。3、实现要点a) 对图的创建采用邻接矩阵的存储结构，而且对图的操作设计成了模板类。为了便于处理，对于图中的每一个顶点和每一条边都设置了初值。b) 为了便于访问，用户可以先输出所有的地点和距离。c) 用户可以随意修改两点之间好的距离。d) 用户可以增加及删除边。e) 当用户操作错误时，系统会出现出错提示。五、概要设计:1. 抽象数据类型图的定义如下：ADT Graph数据对象 V：V 是具有相同特性数据元素的集合，称为顶点集。数据关系 R：R=VRVR=（v，w）| v , wV, (v , w)表示 v 和 w 之间存在路径 基本操作 P：CreatGraph( int num; VEXTYPE; typedef struct VEXTYPE vexsMAXLEN; /顶点的信息 ADJTYPE arcsMAXLENMAXLEN; /邻接矩阵 int vexnum,arcnum ; /顶点数和边数 MGraph;MGraph b; MGraph InitGraph() /*建立无向网的邻接矩阵结构*/ int i, j; MGraph G; G.vexnum =8; /存放顶点数G.arcnum =13; /存放边点数 for(i=0;ivexnum;v+) vexnum;i+) for(int j=0;jvexnum;j+) if(G-arcsijv0; cinv1; coutlength;G-arcsv0v1=G-arcsv1v0=length;void Dijkstra(MGraph * G) /迪杰斯特拉算法求最短路径int v,w,i,min,t=0,x,v0,v1; int final20, D20, p2020; coutv0; if(v0G-vexnum) coutv0; coutv1; if(v1G-vexnum) coutv1; for(v=0;vvexnum;v+) / 初始化 final20,p2020,finalv=1 即已经求得 v0 到 v 的最短路径，/pvw=1 则是 w 从 v0 到 v 当前求得最短路径上的顶点，Dv带权长度finalv=0; Dv=G-arcsv0v; for(w=0;wvexnum;w+) pvw=0; if(Dvvexnum;i+) min=MAX; for(w=0;wvexnum;w+) if(!finalw) if(Dwvexnum;w+) if(!finalw for(x=0;xvexnum;x+) pwx=pvx; pww=1; vexnum;j+)if(pv1j=1)v0;for(int i=v0;ivexnum;i+)G-vexsi=G-vexsi+1;G-vexnum-;for(row=0;rowvexnum;row+)for(col=v0;colvexnum;col+)G-arcsrowcol=G-arcsrowcol+1;for(col=0;colvexnum;col+)for(row=v0;rowvexnum;row+)G-arcscolrow=G-arcscolrow+1;void DeleteArc(MGraph *G) /删除某条边int v0,v1;coutv0v1;G-arcsv0v1=MAX;G-arcsv1v0=MAX;void InsertArc(MGraph *G) /插入某条边int v0,v1,l=0;coutv0v1;coutl;G-arcsv0v1=l;G-arcsv1v0=l;void main() /主函数 int a; b=InitGraph(); Menu(); cina; while(a!=7) switch(a) case 0:PutOutVex(Menu();break; case 1:PutOutArc(Menu();break; case 2:Change(Menu();break; case 3:Dijkstra(Menu();break;case 4:DeleteVex(Menu();break; case 5:DeleteArc(Menu();break; case 6:InsertArc(Menu();break;case 7:exit(1);break; default:break; cina; 八、调试分析 1) 本程序在求最短路径的问题上采用迪杰斯特拉算法解决，虽然该算法与弗洛伊德算法相比时间复杂度低，但每求一条最短路径都必须重新搜索一遍，在频繁查询时会导致查询效率低，而弗洛伊德算法只要计算一次，即可求得每一对顶点之间的最短路径，虽然时间复杂度为高，但以后每次查询只要查表即可，会极大地提高查询的效率，而且，弗洛伊德算法还支持带负权的图的最短路径的计算。由此可见，选用算法时必须综合各方面因素考虑。2) 由于功能函数较多，在编写程序时将函数逐个添加完成的，就