《数据结构》单元设计报告-用C#语言解决最短路径问题.doc

长沙民政职业技术学院 《数据结构》单元设计报告 学 院 软件学院 专 业 软件开发与项目管理 班 级 XXXX 学 号 XXX 学生姓名 XXXX 指导教师 XXXX 课程成绩 完成日期 2011年12月2日 单元设计成绩评定 学 院 软件学院 专 业 软件开发与项目管理 班 级 XXXXX 学 号 XXXX 学生姓名 XXXX 指导教师 XXX 完成日期 2011年12月2日 指导教师对学生在单元设计中的评价 评分项目 优 良 中 及格 不及格 课程设计中的创造性成果 学生掌握课程内容的程度 单元设计完成情况 单元设计动手能力 文字表达 学习态度 规范要求 单元设计论文的质量 指导教师对单元设计的评定意见 综合成绩 指导教师签字 2010年7月10日 单元设计任务书 软件学院 软件开发与项目管理专业 课程名称 数据结构单元设计 时间 2011学年第下学期13周 学生姓名 指导老师 XXX 题 目 用C#语言解决最短路径问题 主要内容： 　最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径 要求： （1）通过实际的分析、设计、、试，掌握。 （2）按要求编写课程设计报告书，能正确设计。1）单元设计设计附件（）一个弗洛伊德一个最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括： 　　确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。 　　确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。 　 　确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。 全局最短路径问题 - 求图中所有的最短路径。 功能名称 产生最短路线及最短距离 功能描述 输入起始位置v0，得到该点到所有点的最短路线，及距离 输入数据 数字v0 v0{v0`vn} 事件流 1.运行程序，提示输入一个数字n； 2.提交数字后，按输出数据的要求显示输出结果。 输出数据 1.以多行形式输出路线及距离。  思路提示 求解的很多，这里采用： 按路径长度递增次序产生最短路径算法： 　　把V分成两组： 　　（1）S：已求出最短路径的顶点的集合 　　（2）V-S=T：尚未确定最短路径的顶点集合 　　将T中顶点按最短路径递增的次序加入到S中， 　　保证：（1）从源点V0到S中各顶点的最短路径长度都不大于 　　从V0到T中任何顶点的最短路径长度 　　（2）每个顶点对应一个距离值 　　S中顶点：从V0到此顶点的最短路径长度 　　T中顶点：从V0到此顶点的只包括S中顶点作中间 　　顶点的最短路径长度 　　依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的 　　直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和 3 概要设计 3.1 数据结构与数据存储表示 这方面使用二维数组n[MAX][MAX]来静态存储不超过MAX行MAX列的距离方阵。 3.2 程序结构 主要使用与实现如下类： (1)界面类MagicSquareCon，用于调用业务类，实现最短路线，及距离的输出。 (2业务类Dijkstra，用于实现需求分析的功能，主要包括以下方法或属性： int[] PathArc: 路径下标的数组ShortPathTable 存储到各点最短路径的权值和ShortPath(int init) 计算init 点到各顶点的最最短路径 3.3 函数逻辑功能调用图 图3.1 逻辑功能调用图 4 详细设计 int[] PathArc路径下标的数组V8的最短路径为v8-v7-v6-v3-v4-v2-v1-v0,即v0-v1-v2-v4-v3-v6-v7- -v8。 （2）int[] ShortPathTable 存储到各点最短路径的权值和ShortPath(int init) 计算init 点到各顶点最短路径的方法，构造函数调用。 3.4 程序执行流程图 5 运行环境与结果 5.1程序运行环境: VS2008 VS2005开发平台。 5.2 程序运行结果 （1）运