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

计算机应用技术系课程设计报告书数据结构与算法课程设计报告书题目： 导航最短路径查询 班级： 11101111 学号： 1110111105 姓名： 教师周期： 2012.12.17-2012.12.21 （以下由验收教师填写）成绩： 2012年12月21日导航最短路径查询一、课程设计的目的与要求（一）课程设计目的与任务通过学习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、编码集成以及调试分析，熟练掌握数据结构的选择、设计、实现、以及操作方法，为进一步的开发应用打好基础。（二）题目要求要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、设计正文1、 系统分析和开发背景该程序所做的工作是给司机们提供最佳路线，来提高能源和时间的合理利用。（1）把城市交通线路转化为图，从而对图进行相应的结构存储； （2）程序的输出信息主要为：起始城市到目的城市的最短路路径。 （3）程序的功能主要包括：城市之间路径的存储，最短路径的计算，以及最短路径和邻接矩阵的输出；2 、功能详细描述先假设有四个城市甲乙丙丁，甲乙相距2千米，且只有从乙到甲的单程线路。甲丙相距7千米，且只有从甲到丙的单程线路。甲丁相距4千米，且只有从甲到丁的单程线路。乙丙相距5千米，且只有从丙到乙的单程线路。乙丁相距3千米，且只有从丁到乙的单程线路。丙丁相距3千米，且只有从丁到丙的单程线路。戊甲相距6千米，且只有从戊到甲的单程线路。戊丁相距2千米，且只有从丁到戊的单程线路。乙己相距8千米，且只有从乙到己的单程线路。丙己相距6千米，且只有从己到丙单程线路。编程出能求出个一点到任一点的最短路经。3、数据结构设计（1）typedef structint no; /顶点编号InfoType info; /顶点其他信息，这里用于存放边的权值VertexType; /顶点类型typedef struct /图的定义 int edgesMAXVMAXV; /邻接矩阵int n,e; /顶点数，弧数VertexType vexsMAXV; /存放顶点信息MGraph; /图的邻接矩阵类型/以下定义邻接表类型typedef struct ANode /弧的结点结构类型int adjvex; /该弧的终点位置struct ANode *nextarc; /指向下一个弧的指针InfoType info; /该弧的相关信息，这里用于存放权值ArcNode; typedef int Vertex;typedef struct Vnode /邻接表头结点的类型Vertex data; /顶点信息ArcNode *firstarcMAXV; /指向第一条弧VNode;typedef VNode AdjListMAXV;/AdjList是邻接表类型typedef structAdjList adjlist; /邻接表int n,e; /图中顶点数n和边数eALGraph; /图的邻接表类型4、主要功能逻辑过程和实现算法用到的主要函数：（1）void DispMat(MGraph g) /输出邻接矩阵（2）void ppath(int pathMAXV,int v,int endv) /输出相应选择的起点和终点的最短路。（3）void DisPath(int AMAXV,int pathMAXV,int n,int v,int endv)/由path计算最短路径。（4）void Floyd(MGraph g,int v,int endv) /采用弗洛伊德算法求每对顶点之间的最短路径。（5）int main（） /主函数各程序模块之间的调用关系：函数3）可以调用函数2）。 函数4）可以调用函数3）。函数5）可以调用函数1）和函数4）。（1）void Floyd(MGraph g,int v,int endv) /采用弗洛伊德算法求没对顶点之间的最短路径。（2）int AMAXVMAXV,pathMAXVMAXV;int i,j,k,n=g.n;for(i=0;in;i+) /给数组A置初值for(j=0;jn;j+)Aij=g.edgesij;pathij=-1;for(k=0;kn;k+) /计算Akfor(i=0;in;i+)for(j=0;j(Aik+Akj)Aij=(Aik+Akj);pathij=k;流程图：开始i=0,i+i=3？是 否输入v请重新输入v=0,v+v=6？否输入起点代号是 输入错误V=6输入错误输入终点代号是 否输出最短路径5、界面设计1、 图1、功能界面6、系统测试1、 图2、功能选择2、 图3、输出最短路径3、图4、选择功能 4 图5、输出邻接矩阵三、小组成员分工说明独立完成四、课程设计总结或结论1、课程设计过程中出现的技术难点和解决方法：在进行课程设计过程中对弗洛伊德算法知识理解不够透彻，对邻接矩阵的代码认识不全面。2 、课程设计期间的主要收获：通过这次课程设计使我对数据结构有了更深的了解，也明白了数据结构在生活中的实际应用，对邻接矩阵输入输出，最短路径算法更加熟悉的掌握了，对数据结构的上机操作更加熟练，3、 对今后课程设计的建议课设对我们来说是