文档介绍：长沙民政职业技术学院
《数据结构》单元设计报告
学院软件学院专业软件开发与项目管理
班级 XXXX 学号 XXX
学生姓名 XXXX 指导教师 XXXX
课程成绩完成日期 2011年12月2日
单元设计成绩评定
学院软件学院专业软件开发与项目管理
班级 XXXXX 学号 XXXX
学生姓名 XXXX 指导教师 XXX
完成日期 2011年12月2日
指导教师对学生在单元设计中的评价
评分项目
优
良
中
及格
不及格
课程设计中的创造性成果
学生掌握课程内容的程度
单元设计完成情况
单元设计动手能力
文字表达
学习态度
规范要求
单元设计论文的质量
指导教师对单元设计的评定意见
综合成绩指导教师签字 2010年7月10日
单元设计任务书
软件学院软件开发与项目管理专业
课程名称
数据结构单元设计
时间
2011学年第下学期13周
学生姓名
指导老师
XXX
题目
用C#语言解决最短路径问题
主要内容:
最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。
要求:
(1)通过实际项目的分析、设计、编码、测试等工作,掌握用C#语言来开发和维护软件。
(2)按要求编写课程设计报告书,能正确编写分析、设计、编码、测试等技术文档和用户使用手册。
应当提交的文件:
(1)单元设计文档。
(2)单元设计附件(主要是源程序)。
用C#语言解决最短路径的问题
学生姓名: 指导老师:XXXX
摘要本单元设计主要解决设计一个程序,用户输入起始位置,就能得到该点到其他点的最短路线,及最短距离。程序运行平台为Windows 98/2000/XP/7,.net 。在程序设计中,采用了C#面向对象编程语言,将功能实现封装在业务类中,对问题中的要求做出了准确的实现。程序通过调试运行,实现了设计目标。
关键词 C#;业务类、业务方法、控制台界面迪杰斯特拉(Dijkstra)、弗洛伊德(Floyd)
1 引言
本单元设计主要解决设计一个程序,用户输入起始位置,就能得到该点到其他点的最短路线,及最短距离。(各点之间的距离要求事先录入)
单元设计目的
通过这次单元设计进一步了解了最短路径的算法。
单元设计内容
本次单元设计内容主要是利用迪杰斯特拉求解最短路径。
最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。算法具体的形式包括:
确定起点的最短路径问题- 即已知起始结点,求最短路径的问题。
确定终点的最短路径问题- 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。
确定起点终点的最短路径问题- 即已知起点和终点,求两结点之间的最短路径。
全局最短路径问题- 求图中所有的最短路径。
2 需求分析
功能名称
产生最短路线及最短距离
功能描述
输入起始位置v0,得到该点到所有点的最短路线,及距离
输入数据
数字v0 v0{v0`vn}
事件流
,提示输入一个数字n;
,按输出数据的要求显示输出结果。
输出数据
。
思路提示
求解最短路径的算法很多,这里采用迪杰斯特拉:
按路径长度递增次序产生最短路径算法:
把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 概要设计
数据结构与数据存储表示
这方面使用二维数组n[MAX][MAX]来静态存储不超过MAX行MAX列的距离方阵。
程序结构
主要使用与实现如下类:
(1)界面类MagicSquareCon,用于调用业务类,实现最短路线,及距离的输出。
(2业务类Dijkstra,用于实现需求分析的功能,主要包括以下方法或属性:
int[] PathArc: 路径下标的数组
int[] ShortPathTable 存储到各点最短路径的权值和
ShortPath(int init) 计算init 点到各顶