校园导游系统毕业论文.doc

校园导游系统毕业论文目录目录3第一章 绪论11.1本课题的研究背景、内容11.2开发工具的简介21.3开发语言3第二章 需求分析63.1 引言63.2 功能需求7第三章 可行性分析82.1可行性分析的任务82.2技术可行性82.3经济可行性92.4开发环境可行性92.5操作可行性9第四章 总体设计104.1概念结构的特点104.2抽象出类104.3 概念结构的特点是：114.4 E-R图11第五章 详细设计145.1主界面设计145.2景点介绍设计145.3数据维护设计155.4线路查询设计18第六章 系统测试206.1测试方法206.2测试步骤21第七章系统维护及性能分析237.1系统维护237.2性能分析23第八章 总结25参考文献26致 谢27附 录28辽宁科技大学本科生毕业设计(论文) 第 57 页 第一章 绪论1.1本课题的研究背景、内容目前，电子地图在商业应用领域不断发展。在终端嵌入式领域，有汽车导航、个人导航、GPS导航等应用;在平台应用领域，有行业应用-智能交通系统、车队管理、资产跟踪等;还有市场前景颇为乐观的位置服务领域(如手机位置服务及互联网位置服务等)。卫星导航目前主要在车载导航系统、手机、掌上电脑等设备中有所应用。这个由汽车商、地图供应商、手机商、电信运营商组成的产业已有近百家企业参与。“电子地图行业仍然属于测绘范畴，在我国，一家企业必须具有测绘资质才能从事测绘活动。但这并不意味着市场没有开放。”孙国军说。随着电子地图应用面的拓宽，其与老百姓的生活也结合得越来越紧密，市场的变化迫使国家测绘主管部门和相关部门积极地思考如何推进测绘产品的市场化问题。实际上，国家相关部门一直在有步骤地推进电子地图的产业化进程，包括先后出台了保密法、地图出版的相关管理条例和电子地图制作资质标准。另外，在技术手段上，国家也采取了一些办法。比如，国家发展和改革委员会在2002年曾主导了一个专业化产业化项目卫星导航产业化应用专项，其中涉及到导航的硬件、软件、应用平台和导航电子地图，并设立了一些项目来直接推进电子地图的产业化。北京四维图新公司当时便承担此项目中关于电子地图开发部分的工作。国家发改委希望通过该计划在国内形成100亿元规模的卫星导航应用市场，推出一批有特色的中国导航产品，培育起一批在相关领域里的一流企业。此外，国家测绘局也从测绘和地图产品管理的角度出发，在资质、标准、地图保密等方面形成了一整套方案，产业政策层面的框架已经基本形成。目前，这些产业政策和标准仍在不断完善之中。1.2开发工具的简介Eclipse 是一个开放源代码的、基于 Java 的可扩展开发平台。就其本身而言，它只是一个框架和一组服务，用于通过插件组件构建开发环境。幸运的是，Eclipse 附带了一个标准的插件集，包括 Java 开发工具（Java Development Tools，JDT）。 Eclipse 还包括插件开发环境（Plug-in Development Environment，PDE），这个组件主要针对希望扩展 Eclipse 的软件开发人员，因为它允许他们构建与 Eclipse 环境无缝集成的工具。多数人认为Eclipse是Java IDE，不过，当下载Eclipse之后，除了有Java IDE(就是JDT)，还有PDE。然而Eclipse是万用工具平台。JDT实际上是Eclipse的添加品，也就是外挂程序。Eclipse本身实际上是指Eclipse平台(Eclipse Platform)，除了下载时能取得Java工具集以外，还提供各种工具的支持，所以平台本身只是相当小的组软件。 如果想开发Java程序，用的是Eclipse随附的JDT外挂程序。如果想开发其它语言的程序，就需要拿到其它外挂程序，诸如CDT(C Development Toolkit)就可以开发C/C+程序。 Eclipse跨计算机语言，也跨人类的语言。相同的外挂机制可用来增加对不同语言的支持，这里使用一种特殊的外挂，叫做外挂程序片断(plug-in fragment)。IBM以捐出一个语言套件，支持中文(繁体与简体)、法文、德文、意大利文、日文、韩文、葡萄牙文(巴西)与西班牙文。 照理说Eclipse以Java写成，应该可以在任何的平台执行。但严格来说Eclipse不是跨平台的，因为它使用作业平台的原生图形来建置。因此要等SWT(Standard Widget Toolkit)移植到该平台，Eclipse才能在那个平台执行。但就现实而言到不是什么大问题，因为SWT已经被移植到数个常见平台上了，包括Windows、Linux/Motif、Linux/GTK2、Solaris、QNX、AIX、HP-UX与Mac OS X。 JAVA GUI插件jigloo jigloo严格意义上来说也是收费的，不过他提供了non_commercial的版本，而这个版本的功能和commercial是完全一样的。作为个人开发来说，是不受限制的。jigloo很小，最新的版本才3MB多，安装也比较简单。 jigloo同时支持SWT和Swing。 jigloo也是完全基于Java代码的，不过它的code parse的能力远比VE要强，也要快。至少我很多在VE下出现问题，不能显示的Visual Class可以很好地在jigloo下编辑，至今还没有遇到jigloo不能编辑，parse出错的时候。而jigloo还可以集成了一写比较好的Java GUI风格代码的支持，功能上比VE要强大一些。 当然，3MB多的插件，再强也强不过SWT-Designer完整版的，但是比其基础版的要好很多。而SWT-Designer也并不是完全基于JAVA开发的，比如Windows版本的，还携带了dll文件。而jigloo是完全基于JAVA开发的，下载下来只有一个class的zip文件，也支持Eclipse的在线安装。 jigloo的安装很简单，和其它Eclipse插件一样，不需要任何安装程序，直接解压出来就行了。 创建新的窗口，直接输入File-New-Others-GUI Forms就可以了。 而如果要打开一个已经存在的Visual Class，可以直接右键点击，选择Open With-Form Editor打开就可以了。打开后，首先要进行code parse，不过这个速度很快，也不需要像VE那样还启动一个JVM。1.3开发语言JAVA语言的特点：1、Java语言是简单的。Java语言的语法与C语言和C+语言很接近，使得大多数程序员很容易学习和使用Java。另一方面，Java丢弃了C+ 中很少使用的、很难理解的、令人迷惑的那些特性，如操作符重载、多继承、自动的强制类型转换。特别地，Java语言不使用指针，并提供了自动的废料收集，使得程序员不必为内存管理而担忧。2、Java语言是一个面向对象的。Java语言提供类、接口和继承等原语，为了简单起见，只支持类之间的单继承，但支持接口之间的多继承，并支持类与接口之间的实现机制（关键字为implements）。Java语言全面支持动态绑定，而C+ 语言只对虚函数使用动态绑定。总之，Java语言是一个纯的面向对象程序设计语言。3、Java语言是分布式的。Java语言支持Internet应用的开发，在基本的Java应用编程接口中有一个网络应用编程接口（），它提供了用于网络应用编程的类库，包括URL、URLConnection、Socket、 ServerSocket等。Java的RMI(远程方法激活)机制也是开发分布式应用的重要手段。4、Java语言是健壮的。Java的强类型机制、异常处理、废料的自动收集等是Java程序健壮性的重要保证。对指针的丢弃是Java的明智选择。Java的安全检查机制使得Java更具健壮性。5、Java语言是安全的。Java通常被用在网络环境中，为此，Java提供了一个安全机制以防恶意代码的攻击。除了Java语言具有的许多安全特性以外，Java对通过网络下载的类具有一个安全防范机制（类ClassLoader），如分配不同的名字空间以防替代本地的同名类、字节代码检查，并提供安全管理机制（类SecurityManager）让Java应用设置安全哨兵。 6、Java语言是体系结构中立的。Java程序（后缀为java的文件）在Java平台上被编译为体系结构中立的字节码格式（后缀为class的文件）, 然后可以在实现这个Java平台的任何系统中运行。这种途径适合于异构的网络环境和软件的分发。 7、Java语言是可移植的。这种可移植性来源于体系结构中立性，另外，Java还严格规定了各个基本数据类型的长度。Java系统本身也具有很强的可移植性，Java编译器是用Java实现的，Java的运行环境是用ANSI C实现的。8、Java语言是解释型的。如前所述，Java程序在Java平台上被编译为字节码格式， 然后可以在实现这个Java平台的任何系统中运行。在运行时，Java平台中的Java解释器对这些字节码进行解释执行，执行过程中需要的类在联接阶段被载入到运行环境中。9、Java是高性能的。与那些解释型的高级脚本语言相比，Java的确是高性能的。事实上，Java的运行速度随着JIT(Just-In-Time)编译器技术的发展越来越接近于C+。 10、Java语言是多线程的。在Java语言中，线程是一种特殊的对象，它必须由Thread类或其子（孙）类来创建。通常有两种方法来创建线程：其一，使用型构为Thread(Runnable) 的构造子将一个实现了Runnable接口的对象包装成一个线程，其二，从Thread类派生出子类并重写run方法，使用该子类创建的对象即为线程。值得注意的是Thread类已经实现了Runnable接口，因此，任何一个线程均有它的run方法，而run方法中包含了线程所要运行的代码。线程的活动由一组方法来控制。 Java语言支持多个线程的同时执行，并提供多线程之间的同步机制（关键字为synchronized）。11、Java语言是动态的。Java语言的设计目标之一是适应于动态变化的环境。Java程序需要的类能够动态地被载入到运行环境，也可以通过网络来载入所需要的类。这也有利于软件的升级。另外，Java中的类有一个运行时刻的表示，能进行运行时刻的类型检查。Java语言的优良特性使得Java应用具有无比的健壮性和可靠性，这也减少了应用系统的维护费用。Java对对象技术的全面支持和Java平台内嵌的API能缩短应用系统的开发时间并降低成本。Java的编译一次，到处可运行的特性使得它能够提供一个随处可用的开放结构和在多平台之间传递信息的低成本方式。特别是Java企业应用编程接口（Java Enterprise APIs）为企业计算及电子商务应用系统提供了有关技术和丰富的类库。第二章 需求分析为了开发出真正满足用户需求的软件产品，首先必须知道用户的需求。而需求分析是软件定义时期的最后一个阶段，它的基本任务是系统必须完成那些工作，也就是对目标系统提出完整、准确、清晰、具体的要求。它需要系统分析员、程序员、用户这三方面人员采用有效的通信技术，集中精力通力合作，以确定系统的功能要求、系统的性能要求、运行要求以及将来可能提出的新的问题。因此需求分析是软件开发的关键、必不可少的过程。可行性研究阶段所产生的数据流图是需求分析的出发点，从图中可以得知系统必须完成的基本功能，在需求分析阶段将对各个模块的功能进一步的细化。需求分析是系统软件开发的基础，它关系到软件产品的质量和满足用户需求。因此要个审查验证软件的需求。3.1 引言需求分析简单地说就是分析用户的要求。需求分析是涉及数据库的起点，需求分析的结果是否准确的反映了用户的实际要求，将直接影响到后面各个阶段的设计，并影响到设计结果是否合理和实用。需求分析是软件定义时期的最后一个阶段，它的任务是准确了解用户的需求，确定系统必须完成哪些工作，也就是对目标提出完整准确地问题。软件开发人员知道怎样用软件实现人们的要求，但对特定用户的具体要求并不完全清楚。因此在需求分析阶段必须和用户密切配合，充分交流信息，以得出经过用户确认的系统逻辑模型。并与软件开发技术人员进行交流，以保证在目前先有的人员条件和技术条件下，用户需求是可实现的，系统逻辑模型是合理可行的。 虽然在可行性研究阶段已经粗略了解了用户的需求，甚至还提出一些可行性方案，但是，可行性研究的基本目的是用较小的成本在较短的时间内是否存在可行的方案，由此，许多细节以被忽略了。3.2 功能需求1.从辽宁科技大学中选取39个景点与另外46个中转路标，抽象成一个无向带权图。以图中顶点表示景点，边上的权值表示两地的距离。 2.本程序的目的是为用户提供路径咨询和景点查询。根据用户指定的始点和终点输出相应路径或者根据用户指定的景点输出景点的信息。 3.本系统同时提供了后台数据管理维护的接口，管理员可以通过数据维护功能模块对景点以及路径等信息进行实时维护。第三章 可行性分析2.1可行性分析的任务可行性研究的目的就是用最小的代价在尽可能短的时间内确定问题是否能够解决，必须记住，可行性研究的目的不是解决问题，而是确定问题是否值得去解决。如何达到这样的目的呢？必须分析几种重要的可能解法的利弊，从而判断原定的系统目标和规模是否能实现，系统完成后所能带来的效益是否达到值得投资开发这个系统的程度。因此，可行性研究的实质是要进行一次大大的压缩简化了的系统分析和设计的过程，也是在较高层次上一觉抽象的方式进行的系统分析和设计的过程。首先需要进一步分析和澄清问题定义。在问题定义阶段初步确定的规模和目标，如果是正确的就进一步加以确定，如果有错误就应该及时改正，如果对目标系统有任何约束或限制，也必须把它们清除的一一列举出来。在澄清了问题定义之后，分析员应该导出系统的逻辑模型。然后从系统逻辑模型出发，探索若干种可供选择的主要方法。对每种解法都应该仔细研究它的可行性，一般有以下几方面的可行性：（1） 技术可行性（2） 经济可行性（3） 开发环境可行性（4） 操作可行性2.2技术可行性技术方面，系统的整个设计使用结构化设计。利用JAVA多线程以及线程通信的特点。以及图形用户界面的第三方插件GUI jigloo ，利用MYSQL数据库存储，完全可以实现校园导游系统的主要功能。2.3经济可行性一般情况下软件的寿命是5年，而开发的时间是17周，现在实际投入大约5000元，包括购买计算机、软件、调试的费用；现在年利率约为3.6%，根据公式： F=P（1+i）的n次幂公式中：i表示年利率；n表示软件使用时间；P表示实际投入资金；F表示n年后收入的资金那么，5年后收入为5967.18，明显能为学校带来实际收益，工程投资的回收率约20%。目标系统开发所需要求比较低，加上开发所需的软硬件基本无需再次投入资金，所以在软硬件的支出上十分有限。目标系统复杂度不是很高，开发周期不会过长，人员经济支出有限。开发此系统带来的回报远超过支出，因此，开发目标系统是完全可行的。2.4开发环境可行性服务器操作系统：Windows XP Professional (NT | SERVER)内存：512M以上硬盘：40G以上CPU：P4 2.0G以上2.5操作可行性简洁的外观设计，和人性化的布局将使用户更容易登陆系统进行各种操作，全中文的界面和形象化的路线分析可以使使用者清楚的了解自己将有行进的路线。第四章 总体设计4.1概念结构的特点(1) 能真实、充分地反映现实世界，包括事物和事物之间的联系，能满足用户对数据的处理要求。是对现实世界的一种真实模型。(2) 易于理解，从而可以用它和不熟悉计算机的用户交换意见，用户的积极参与是数据库的设计成功的关键。(3) 易于更改，当应用环境和应用要求改变时，容易对概念模型修改和扩充。(4) 易于向关系、网状、层次等各种数据模型转换。概念结构是各种数据模型的共同基础。通常的概念结构设计有四类：l 自顶向下。即首先定义全局概念结构的框架，然后逐步细化。l 自底向上。即首先定义各局部应用的概念结构，然后将他们集成起来得到全局概念结构。l 逐步扩张。首先定义最重要的核心概念结构，然后向外扩充，一滚雪球的方式逐步生成其他概念结构，直至总体概念结构。l 混合策略。即将自顶向下和自底向上向结合，自顶向下策略设计一个全局概念结构的框架，以他为骨架集成由自底向上策略中设计的各局部概念结构。我将采用的策略是自底向上方法。即自顶向下地进行需求分析。根据上面得到的数据项和数据结构以后，就可以设计出能够满足用户需求的各种实体，以及他们的关系，为后面的逻辑结构设计打下基础。这些实体包含各种具体信息，通过相互之间的作用形成数据的流动。4.2抽象出类根据需要我将这个项目抽象出八个类，分别是主界面类、景点介绍界面类、路线查询界面类、点类、边类、自定义下拉框类、信息线程类。主界面是一个Frame类，它实现了事件监听和键盘监听器的接口，这个类用来形成窗体以及窗体菜单，并且控制线程的开启和结束。以及对鼠标和键盘事件的监听，本程序的主函数就是写在这个类里。景点介绍和路线查询类也都是Frame类，用来形成相关的窗体界面，并且对用户的操作做出相应。边和点类是hibernate的pojo类，用来封装对数据库的操作信息。是一个实体Bean。信息线程类实现了Runnable接口，也就是说当开始计算路径时创建一个线程，来显示正在计算的信息。4.3概念结构的特点是：(5) 能真实、充分地反映现实世界，包括事物和事物之间的联系，能满足用户对数据的处理要求。是对现实世界的一种真实模型。(6) 易于理解，从而可以用它和不熟悉计算机的用户交换意见，用户的积极参与是数据库的设计成功的关键。(7) 易于更改，当应用环境和应用要求改变时，容易对概念模型修改和扩充。(8) 易于向关系、网状、层次等各种数据模型转换。概念结构是各种数据模型的共同基础。通常的概念结构设计有四类：l 自顶向下。即首先定义全局概念结构的框架，然后逐步细化。l 自底向上。即首先定义各局部应用的概念结构，然后将他们集成起来得到全局概念结构。l 逐步扩张。首先定义最重要的核心概念结构，然后向外扩充，一滚雪球的方式逐步生成其他概念结构，直至总体概念结构。l 混合策略。即将自顶向下和自底向上向结合，自顶向下策略设计一个全局概念结构的框架，以他为骨架集成由自底向上策略中设计的各局部概念结构。我将采用的策略是自底向上方法。即自顶向下地进行需求分析。根据上面得到的数据项和数据结构以后，就可以设计出能够满足用户需求的各种实体，以及他们的关系，为后面的逻辑结构设计打下基础。这些实体包含各种具体信息，通过相互之间的作用形成数据的流动。4.4 E-R图ER模型中包含“实体”、“联系”和“属性”等三个基本部分，下面分别介绍这三个基本部分：l 实体实体是客观世界中存在的且可相互区分的事物。实体可以是人也可以是物；可以是具体事物也可以是抽象概念。例如，本系统中火车和地区都是实体。在ER图中用矩形框代表实体l 联系客观世界中的事物彼此间往往是有联系的。例如本系统中火车与地区间存在“路经”这种联系。联系分为三种：（1） 一对一联系（1：1）（2） 一对多联系（1：N）（3） 多对多联系（M：N）在ER图中，用连接相关联实体的菱形表示联系。l 属性属性是实体或联系所具有的性质。通常一个实体由若干个属性来刻画。在ER图中，用椭圆或圆角矩形表示实体（或联系）的属性，并用无向边把实体（或联系）与其属性连接起来。x坐标景点主键景点名称y坐标 景点介绍景点类型图4.1 景点信息E-R图终点路线两点距离起点图4.2 路线信息E-R图第五章 详细设计5.1主界面设计一、功能描述下图界面为系统主界面，是用户运行程序后看到的第一个界面，也是系统功能导航的支点。其中最左侧是一个只读模式的textfield控件，控件的内容是利用Java文件流从程序当前目录下的img子文件夹中的一个文本文件中读取出来的，如果文本文件不存在则控件中会显示相关的提示信息。最右侧的五个按钮分别代表本系统的五大功能模块。通过点击不通的模块程序会先隐藏主界面，然后打开子功能界面。如果点击退出系统，则程序首先会释放所有的界面资源，然后清除内存，退出程序。二、具体实现详细设计调用FrmMain类下的主方法运行程序，main方法调用initData方法初始化程序需要的各种数据，包括景点数据，路径信息等，然后再调用initGUI方法初始化主界面的各个控件并设置窗体可见性为true以显示窗体界面。在数据初始化过程中对可能出现的运行时错误进行了各种处理以保证程序在遇到数据问题而出现异常时不会崩溃，而是以程序设置好的步骤继续运行。图5.1 主界面图5.2景点介绍设计点击景点介绍按钮，进入景点介绍界面。这里在这个按钮对象加入了一个监听器，当点击按钮的时候触发事件，将景点介绍的frame的Visible属性设为true，并且把主页面的属性设为false。进入后，右侧有一个下拉框，要说明的是这个下拉框是动态获得数据库中所有景点的信息，当选中其中某个景点的时候，下面就会出现该景点的介绍，左面显示该景点的图片。由于当程序运行时，就已经把所有景点的信息全都加载到了内存里，因此此处在选中景点信息的时候，不需要每次都去访问数据库，避免因为误操作而频繁的去访问数据库，大大的提高了效率。图5.2 景点简介图5.3数据维护设计数据维护功能有对景点基本信息的维护，和对景点与路线关联的维护。对景点基本信息的维护包括添加新景点和修改景点的基本信息，用户可以按要求填入景点的基本信息，并且可在右侧预览要上传的图片。图5.3 景点维护图1图5.4 景点维护图2在维护路径数据中，通过下拉框选择节点，可在下面的地图中预览线路情况。图5.5 路径维护图这里通过选择目标节点动态获得它的相邻节点集合和其他节点集合，其他节点不包括目标节点以及其相邻节点，这里获得相邻结点的方法是先取得所有边，然后获得与目标节点相关的边，根据这些边取得与之相关的结点，然后把目标节点移除掉，剩下的就是相邻结点了。代码实现是这样的：public List findUpon(Node objNode) / Auto-generated method stubList bs = this.findUponBorder(objNode);List upon = null;if (bs != null) upon = new ArrayList();for (Border b : bs) Node nf = b.getNodeByBnf();Node nb = b.getNodeByBnb();boolean nfExists = false;boolean nbExists = false;for (Node n : upon) if (n.getNid().intValue() = nf.getNid().intValue() nfExists = true;if (n.getNid().intValue() = nb.getNid().intValue() nbExists = true;if (nfExists & nbExists) break;if (!nfExists& objNode.getNid().intValue() != nf.getNid().intValue() upon.add(nf);if (!nbExists& objNode.getNid().intValue() != nb.getNid().intValue() upon.add(nb);return upon;5.4线路查询设计 用图的结点代表景点，用图的边代表景点之间的路径。首先设计一个图类。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值用顺序表存储，所以需要设计一个顺序表类。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个状态，利用面向对象的思想实现。计算路径长度和路线时可用Dijkstra算法实现，Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述是用tempA, tempB表方式，这里均采用tempA,tempB表的方式。其采用的是贪心法的算法策略大概过程：创建两个表，tempA, tempB。tempA表保存所有已生成而未考察的节点，tempB表中记录已访问过的节点。1 访问路网中距离起始点最近且没有被检查过的点，把这个点放入tempA组中等待检查。2 从tempA表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到tempB表中。3 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到tempA表中。4 重复第2和第3步,直到tempA表为空，或找到目标点。Dijkstra算法是由荷兰计算机科学家艾兹格迪科斯彻发现的。算法解决的是有向图中最短路径问题。 举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。 Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。 每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 我们以E所有边的集合，而边的权重则由权重函数w: E 0, 定义。 因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。 已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。 算法描述 这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时，源点s的路径长度值被赋为0（ds=0）， 同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外dv= ）。当算法结束时，dv中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路径。这条路径的长度是du+w(u,v)。如果这个值比目前已知的dv的值要小，我们可以用新值来替代当前dv中的值。拓展边的操作一直执行到所有的dv都代表从s到v最短路径的花费。这个算法经过组织因而当du达到它最终的值的时候没条边(u,v)都只被拓展一次。 算法维护两个顶点集S和Q。集合S保留了我们已知的所有dv的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的du值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。 伪码 在下面的算法中,u:=Extract_Min(Q)在在顶点集Q中搜索有最小的du值的顶点u。这个顶点被从集合Q中删除并返回给用户。 1 function Dijkstra(G, w, s) 2 for each vertex v in VG / 初始化 3 dv := infinity 4 previousv := undefined 5 ds := 0 6 S := empty set 7 Q := set of all vertices 8 while Q is not an empty set / Dijstra算法主体 9 u := Extract_Min(Q) 10 S := S union u 11 for each edge (u,v) outgoing from u 12 if dv du + w(u,v) / 拓展边(u,v) 13 dv := du + w(u,v) 14 previousv := u 如果我们只对在s和t之间寻找一条最短路径的话，我们可以在第9行添加条件如果满足u=t的话终止程序。 现在我们可以通过迭代来回溯出s到t的最短路径 1 S := empty sequence 2 u := t 3 while defined u 4 insert u to the beginning of S 5 u := previousu 现在序列S就是从s到t的最短路径的顶点集. 时间复杂度 我们可以用大O符号将Dijkstra算法的运行时间表示为边数m和顶点数n的函数。 Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q)只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。 对于边数少于n2稀疏图来说，我们可以用邻接表来更有效的实现Dijkstra算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点(Extract-Min)。当用到二叉堆的时候，算法所需的时间为O(m+n)log n)，斐波纳契堆能稍微提高一些性能，让算法运行时间达到O(m + n log n)。 相关问题和算法 在Dijkstra算法的基础上作一些改动，可以扩展其功能。例如，有时希望在求得最短路径的基础上再列出一些次短的路径。为此，可先在原图上计算出最短路径，然后从图中删去该路径中的某一条边，在余下的子图中重新计算最短路径。对于原最短路径中的每一条边，均可求得一条删去该边后子图的最短路径，这些路径经排序后即为原图的一系列次短路径。 OSPF（open shortest path first, 开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。 与Dijkstra算法不同，Bellman-Ford算法可用于具有负花费边的图，只要图中不存在总花费为负值且从源点 s 可达的环路（如果有这样的环路，则最短路径不存在，因为沿环路循环多次即可无限制的降低总花费）。 与最短路径问题有关的一个问题是旅行商问题(traveling salesman problem)，它要求找出通过所有顶点恰好一次且最终回到源点的最短路径。该问题是NP难的；换言之，与最短路径问题不同，旅行商问题不太可能具有多项式时间算法。 如果有已知信息可用来估计某一点到目标点的距离，则可改用A*算法，以减小最短路径的搜索范围。图5.6 线路查询图第六章 系统测试测试与调试是软件开发过程中占据重要的地位，在传统的瀑布模型中，软件测试学仅处于运行维护阶段之前，是软件产品交付用户使用之前保证软件质量的重要手段。近来，软件工程界趋向于一种新的观点，即认为软件生命周期每一阶段中都应包含测试，从而检验本阶段的成果是否接近预期的目标，尽可能早的发现错误并加以修正，如果不在早期阶段进行测试，错误的延时扩散常常会导致最后成品测试的巨大困难。 事实上，对于软件来讲，不论采用什么技术和什么方法，软件中仍然会有错。采用新的语言、先进的开发方式、完善的开发过程，可以减少错误的引入，但是不可能完全杜绝软件中的错误，这些引入的错误需要测试来找出，软件中的错误密度也需要测试来进行估计。测试是所有工程学科的基本组成单元，是软件开发的重要部分。自有程序设计的那天起测试就一直伴随着。统计表明，在典型的软件开发项目中，软件测试工作量往往占软件开发总工作量的40以上。而在软件开发的总成本中，用在测试上的开销要占30到50。如果把维护阶段也考虑在内，讨论整个软件生存期时，测试的成本比例也许会有所降低，但实际上维护工作相当于二次开发，乃至多次开发，其中必定还包含有许多测试工作。6.1测试方法软件测试在软件生命周期中横跨两个阶段:白盒测试法和黑盒测试法。软件测试的正确定义是:为了发现程序中的错误而执行程序的过程。如果知道了产品应该具有的功能，可以通过测试来检测是否每个功能都能实现，这种测试方法叫作黑盒测试法；如果知道产品的内部工作过程，可以通过测试来检验是否按照规格说明书的规定正常运行，这个方法叫白盒测试法。对于软件而言，黑盒测试法是把程序看成一个黑盒子，完全不考虑程序的内部结构和处理过程。也就是说黑盒测试是在程序的接口进行测试，它只检查程序的功能是否按照规格说明说的说明正常运行，程序是否能恰当的接受输入数据，产生正确的输出信息，并且保持外部信息的完整性。黑盒测试又称为功能测试。与黑盒测试法相反，白盒测试法是把程序看成是装在一个透明的白盒子里。也就是完全了解程序的结构和处理过程，这种方法按照程序内部的逻辑测试程序，检验程序中的每条通路是否能按预定的要求正确工作，白盒测试又称为结构测试。 通过这两种测试方法，纠正系统中存在的错误，提高软件的可靠性。因此，必须仔细设计测试方案，力争用尽可能少的测试发现尽可能多的错误。6.2测试步骤软件测试是软件开发过程中最艰巨最繁重的任务，大型软件的测试应该分阶段地进行，通常至少分为单元测试、集成测试和验收测试三个基本阶段。首先，测试人员要仔细阅读有关资料，包括规格说明、设计文档、使用说明书及在设计过程中形成的测试大纲、测试内容及测试的通过准则，全面熟悉系统，编写测试计划，设计测试用例，作好测试前的准备工作。 为了保证测试的质量，将测试过程分成几个阶段，即：代码审查、单元测试、集成测试和验收测试。 (1)代码会审： 代码会审是由一组人通过阅读、讨论和争议对程序进行静态分析的过程。对某个局部性小问题修改方法的讨论，可能发现与之有牵连的甚至能涉及到模块的功说明、模块间接口和系统总结构的大问题，导致对需求定义的重定义、重设计验证，大大改善了软件的质量。 (2)单元测试： 单元测试集中在检查软件设计的最小单位模块上，通过测试发现实现该模块的实际功能与定义该模块的功能说明不符合的情况，以及编码的错误。由于模块规模小、功能单一、逻辑简单，测试人员有可能通过模块说明书和源程序，清楚地了解该模块的I/O条件和模块的逻辑结构，采用结构测试（白盒法）的用例，尽可能达到彻底测试，然后辅之以功能测试（黑盒法）的用例，使之对任何合理和不合理的输入都能鉴别和响应。高可靠性的模块是组成可靠系统的坚实基础。 (3)集成测试： 集成测试是将模块按照设计要求组装起来同时进行测试，主要目标是发现与接口有关的问题。如数据穿过接口时可能丢失；一个模块与另一个模块可能有由于疏忽的问题而造成有害影响；把子功能组合起来可能不产生预期的主功能；个别看起来是可以接受的误差可能积累到不能接受的程度；全程数据结构可能有错误等。 (4)验收测试： 验收测试的目的是向未来的用户表明系统能够像预定要求那样工作。经集成测试后，已经按照设计把所有的模块组装成一个完整的软件系统，接口错误也已经基本排除了，接着就应该进一步验证软件的有效性，这就是验收测试的任务，来满足用户的需求。 经过上述的测试过程对软件进行测试后，软件基本满足开发的要求，然后通过进一步完善使系统更加有效使用。第七章系统维护及性能分析7.1系统维护软件维护是软件生命周期最后一个阶段，其基本任务是保证软件在一个相当长的时期能够正常的运行。 软件维护就是在软件已经交付使用之后，为了改正错误或满足新的要求而修改软件的过程。软件维护通常包括四类活动：改正性维护；适应性维护；完善性维护；预防性维护，本程序主要采用的是改正性维护与完善性维护。在程序的设计过程中，我不断地采用可改正性维护（纠正在使用过程中暴露出来的错误而进行的改正性维护），使程序逐步的减少错误的发生。在程序设计完成后，我继续进行完善性维护（改进原有的软件），不断增加系统的功能，完善系统的功能，使系统能够更好的运行。本系统的维护措施有数据备份和数据恢复，管理员可以经常对数据库信息进行备份，以防止数据库被破坏。同时还包括对用户权限的管理，通过对不同用户设置不同的权限，防止用户对无权操作的数据进行修改。软件维护是软件使用中的重要部分。软件的维护会一直持续到软件报废为止，也就是软件再也没有维护的价值了，必须报废再开发新的软件来替代它。只有到此时，软件的生命周期结束了，也就不用再进行维护了，软件的维护也就到此终止了。所以说，我们不能忽略软件维护这个问题。7.2性能分析通过三个多月的设计，校园导游系统的各功能已基本实现，完全达到了系统的需求。 系统设计结构合理，系统的运行速度快，可以对用户的操作立即做出反应。系统采用统一的设计风格，能够使用户易于接受，系统操作方便。本系统设计了数据备份与恢复功能，增加了系统的可靠性。另外，能够对用户的错误输入进行屏蔽，以减少用户操作错误。同时，防止非法用户的使用，增强了系统的安全性。第八章 总结毕业设计已经接近尾声了，经过这段时间的努力，这个校园导游系统的功能已基本实现。在本次设计中，我依据软件生命周期方法学，将系统逐渐完善，使系统由最初的模糊状态到今天的条理清晰。在设计期间，我也深深地体会到了软件开发的辛苦，但在完成系统设计时，也让我尝到了成功的喜悦。在刚开始设计时，真的觉得无从下手，虽然以前学习过大量的理论知识，然而理论和实践毕竟不同，但是，经过我的努力，我也逐渐掌握了开发软件的技巧，同时也学到了一些编程的方法。使我四年所学的理论知识与实践很好的融为了一体，做到了理论实践相结合。但是，在设计系统的过程中，也遇到了一些问题，例如，在划分系统功能模块的时候，由于对问题的理解不当，从而延误了这一阶段的设计进程，不过，在指导教师的帮助下一级经过我自己的努力，也将问题顺利地解决，并在后期的设计将时间迅速地赶上了。通过这次设计，让我的动手能力确实得到了提高，也让我所学到的理论知识在实践中得到了应用，不仅提高了实践动手的能力，同时也巩固了理论知识。更为重要的是，我掌握了一些编程技巧以及编程语言的运用，为我以后的设计打下了一个坚实的基础。可以说，在这次设计中我受益匪浅。本系统通过指导教师的悉心指导和同学的帮助以及自己的努力，经过试用证明，系统基本能实现核心课成绩管理方面的需要。实现了对学生基本信息及学生成绩进行管理等功能，给学校的管理带来很多方便。在界面上力求做到完美，在操作方面尽量做到满足用户使用习惯。但由于自己水平有限，加上时间有限，系统还存在很多不足，一定要在以后的实践当中有所提高。参考文献1 （美）埃克尔（Eckel,B.）. Java编程思想.第3版.机械工业出版社，2005年05月，72-96.2 孙鑫. Java Web开发详解. 机械工业出版社， 2006年04月，58-56.3 孙卫琴. JAVA面向对象编程. 电子工业出版社, 2006年07月，145-146.4 阎宏, Java与模式, 电子工业出版社, 2002年10月，12-85.5 盖国强, Oracle数据库性能优化, 人民邮电出版社, 2005年06月，55-566 盖国强, 深入浅出Oracle DBA 入门、进阶与诊断案例,人民邮电出版社,2006年07月，23-56.7 （美）哈德曼（Hardman，R），Oracle Database10g PL/SQL程序设计, 清华大学出版社 ,2005年11月，8-12.8向传杰，JAVA编程案例教程，电子工业出版社，2004-05，45-56.9李兆军，赵家俊，数据库应用基础，电子工业出版社，2000-7，99-10210戴红，张睿哲，数据库技术基础，机械工业出版社，2006-07，86-8911张俊玲，王秀英，数据库技术，人民邮电出版社，2006-07，76-7912吴洪潭，数据库原理，国防工业出版社，2003-01.12-9613美麦克劳夫林，Java与XML数据绑定，中国电力出版社，2003-2，2-3.14美 坎农，JAVA程序设计基础，中国水利水电出版社，2004-