数据结构最短路径课设报告

《数据结构最短路径课设报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机应用技术系课程设计报告书数据结构与算法课程设计报告书题目：导航最短路径查询班级：11101111学号：1110111105姓名：教师周期：2012.12.17-2012.12.21（以下由验收教师填写）成绩：2012年12月21日计算机应用技术系课程设计报告书《导航最短路径查询》一、课程设计的目的与要求（一）课程设计目的与任务通过学习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、编码集成以及调试分析，熟练掌握数据结构的选择、设计、实现、以及操作方法，为进一步的开发应用打好基础。（二）题目要求要求在数据结构的逻辑特性和物理表示、数据结构的选

2、择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、设计正文1、系统分析和开发背景该程序所做的工作是给司机们提供最佳路线，来提高能源和时间的合理利用。（1）把城市交通线路转化为图，从而对图进行相应的结构存储；（2）程序的输出信息主要为：起始城市到目的城市的最短路路径。（3）程序的功能主要包括：城市之间路径的存储，最短路径的计算，以及最短路径和邻接矩阵的输出；2、功能详细描述先假设有四个城市甲乙丙丁，甲乙相距2千米，且只有从乙到甲的单程线路。甲丙相距7千米，且只有从甲到丙的单

3、程线路。甲丁相距4千米，且只有从甲到丁的单程线路。乙丙相距5千米，且只有从丙到乙的单程线路。乙丁相距3千米，且只有从丁到乙的单程线路。丙丁相距3千米，且只有从丁到丙的单程线路。戊甲相距6千米，且只有从戊到甲的单程线路。戊丁相距2千米，且只有从丁到戊的单程线路。乙己相距8千米，且只有从乙到己的单程线路。丙己相距6千米，且只有从己到丙单程线路。编程出能求出个一点到任一点的最短路经。3、数据结构设计（1）typedefstruct{intno;//顶点编号InfoTypeinfo;//顶点其他信息，这里用于存放边的权值}VertexType;//顶点类型typedefstr

4、uct//图的定义{intedges[MAXV][MAXV];//邻接矩阵intn,e;//顶点数，弧数VertexTypevexs[MAXV];//存放顶点信息}MGraph;//图的邻接矩阵类型//以下定义邻接表类型typedefstructANode//弧的结点结构类型计算机应用技术系课程设计报告书{intadjvex;//该弧的终点位置structANode*nextarc;//指向下一个弧的指针InfoTypeinfo;//该弧的相关信息，这里用于存放权值}ArcNode;typedefintVertex;typedefstructVnode//邻接表头结点

5、的类型{Vertexdata;//顶点信息ArcNode*firstarc[MAXV];//指向第一条弧}VNode;typedefVNodeAdjList[MAXV];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;//图中顶点数n和边数e}ALGraph;//图的邻接表类型4、主要功能逻辑过程和实现算法用到的主要函数：（1）voidDispMat(MGraphg)//输出邻接矩阵（2）voidppath(intpath[][MAXV],intv,intendv)//输出相应选择的起点和终点的最短路。（

6、3）voidDisPath(intA[][MAXV],intpath[][MAXV],intn,intv,intendv)//由path计算最短路径。（4）voidFloyd(MGraphg,intv,intendv)//采用弗洛伊德算法求每对顶点之间的最短路径。（5）intmain（）//主函数各程序模块之间的调用关系：函数3）可以调用函数2）。函数4）可以调用函数3）。函数5）可以调用函数1）和函数4）。（1）voidFloyd(MGraphg,intv,intendv)//采用弗洛伊德算法求没对顶点之间的最短路径。（2）{intA[MAXV][MAXV],pat

7、h[MAXV][MAXV];inti,j,k,n=g.n;for(i=0;i(A[i][k]+A[k][j])){A[i][j]=(A[i][k]+A[k][j]);path[i][j]=k;流程图：开始i=0,i++i<=3？是否输入v请重新输入v