文档介绍：长沙理工大学
《数据结构》课程设计报告
杭宸
学院计算机与通信工程专业计算机科学与技术
班级计科11-1 学号 36
学生姓名杭宸指导教师黄敏
课程成绩完成日期 2013年7月4日
课程设计成绩评定
学院计算机与通信工程专业计算机科学与技术
班级计算机1101 学号 201150080136
学生姓名杭宸指导教师黄敏
完成日期 2013年7月4日
指导教师对学生在课程设计中的评价
评分项目
优
良
中
及格
不及格
课程设计中的创造性成果
学生掌握课程内容的程度
课程设计完成情况
课程设计动手能力
文字表达
学习态度
规范要求
课程设计论文的质量
指导教师对课程设计的评定意见
综合成绩指导教师签字 2009年9月15日
用java的方式实现可视化的Dijkstra最短路径算法(无向图)
学生:杭宸指导老师:黄敏
摘要在这个学期,我学习了数据结构这门课程,正是这门课程让我正真地开始懂得了一些基础的编程思想,而通过这次的实习我更是成功实现了数据结构可视化,具体化的想法。在整个学期中,我主要使用面向对象的JAVA语言进行编程,深刻地感受到面向对象的优势,因此在本次试验中,我采用了JAVA语言。另外在本次试验的3天中,我走过了不少弯路,不在此一一列举,具体遇到的问题详见正文部分。最后也是真心感谢各位老师的倾力栽培和对我任性(没用使用大众的C语言)的包容。不过有些功能尚未实现,请老师能够指导。
1 引言
本次实验,主要的目的有两个,一是实现图的可视化操作,二是进行最短路径算法的实践学习。这个算法能够普遍运用于地图查询,工程安排,交通路线规划等许多方面,可见熟练掌握这种算法是非常重要的。
正因为此次我使用的语言在我们年级中比较罕见,所以会尽可能详细得将代码进行注释,以便读者理解。
正如大家所知,编程语言有三种重要的思想——面向机器、面向过程和面向对象。而面向地分析问题,能够把具有相似属性以及相似处理方法的事物归为一类进行操作,而且能够有继承、重载、覆盖等各类手段,这使得针对某一类对象问题的处理不再单一,这种思想和人类的自然思想很像,更加容易使人们理解。而JAVA的各种强大的jar包蕴含着丰富的类库,比起C语言更加容易实现诸如可视化、多媒体文件处理等功能,而单纯在数据结构与算法分析层面,JAVA就可以通过在类的内部建立自己的一个对象代替了指针,有效地避免了函数返回容易出错的问题,而且JAVA存在垃圾回收机制,被遗弃的对象不需要用函数释放空间。在众多理由下,我选择了这个语言进行本次课程设计。
我将会依次介绍算法和可视化两大部分。这么做是为了强调算法的重要性,因为算法是程序的灵魂,没有好的算法,就难以实现节省空间时间的目的,甚至会使得程序的结果出错。而且算法比起可视化的操作也好懂些,可视化的操作需要一定的开发经验才能够明白。
预备知识:
JAVA的类大致如下:
public class XXX{
变量
public XXX(){ 构造函数可以有参也可以无参,也可以重载
}
public void(或者变量)(){
}带变量的要返回,没带变量的用return;是直接挑出函数
}
主函数:
public static void main(String args[]){String 是字符串
}
在带有主函数的类中,如果主函数要调用本类的变量或者是其他函数,请在定义时加上static,不过构造函数是不能够加static的,要注意啊。另外JAVA没有友元函数,而且变量的赋值操作只能写在类的所有方法之前或者方法中,在方法外面不能够定义变量后另外写赋值(初始化)语句,要把定义和赋值写在一起。
2 算法的概述
本来,大家都会认为Dijkstra算法是用于有向图的,实际上呢,这也可以用于无向图,因为我们可以把线段AB看做既是A指向B也是B指向A的有向图。
简单地说,这种算法是将出发点的最短距离看做了0(因为自身和自身的距离就是0,无需通过走动就能到达自身),然后将出发点的所有邻接点放入一个存储结构,把这些邻接点的最短距离置为边的值加上自身的最短路径,某些点被拿出来以后,又会把它的所有邻接点送入这个存储结构(已经放过的就不放了)再去刷新其他点的最短距离,直到所有的点都被处理过了,这样从出发点,到所有点的最短距离就求出来了。
你是不是发现了一个巧妙的事情呢?没错,在每次处理点的时候,总要把它所有没放入存储结构的点放入这个存储结构中,这不是很明显的广度优先搜索?对了,这里的存储结构就是队列了。
那么,让我们来通过我的可视化程序来详细的用例子阐释这个算法吧,如下图所示:
看,这是我们的图(以为长度是自己输入可能很不准确):
如果我想知道A到