毕业论文：基于vc的图的遍历算法的动态演示系统的设计与实现.docx

毕业论文：基于vc的图的遍历算法的动态演示系统的设计与实现.docx

《毕业论文：基于vc的图的遍历算法的动态演示系统的设计与实现.docx》由会员分享，可在线阅读，更多相关《毕业论文：基于vc的图的遍历算法的动态演示系统的设计与实现.docx（40页珍藏版）》请在冰点文库上搜索。

摘要

《数据结构》作为信息类专业的一门核心专业课，对《编译原理》等后续课程的学习极其重要。

传统的《数据结构》算法是基于以Turbo C为代表的DOS开发坏境，可视化效果很差。

而这种坏境给学习者的理解和深入探讨带来很大的问题。

本设计从对数据结构图的算法的深入研究开始，在Visual C++的编程坏境下，致力于开发一套专门帮助学习者理解数据结构算法的动态演示系统。

该系统将可视性，交互性和可扩展性紧紧的结合在一起，能大大改善传统教学的弊端，使复杂的难以理解的数据结构算法通过教师的课堂演示和学习者的不断自我交互式操作试验变得通俗明朗，有效地提高教学的质量和效果。

关键字：

动态演示系统；VisualC++

II

Abstract

Thedatastructureasacoreofinformationspecialtycourses,learningtofollow-upsuchasthecompilingprinciplesofcourseextremelyimportant.

TraditionalalgorithmisbasedonthedatastructuretoDOSdevelopmentrepresentedTurboCborders,verypoorvisualeffects.Andthisbadbordertothelearner'sunderstandingandin-depthdiscussionscausegreatproblems.Thedesignstartsfromthein-depthstudyondatastructurealgorithm,programminginVisualC++underbadborder,iscommittedtodevelopingasetofspecializedhelplearnersunderstanddatastructurealgorithmofdynamicdemosystem.ThesystemofVisual,interactivecombinationofscalabilityandtightlytogether,cangreatlyimprovetheshortcomingsoftraditionalteaching,sothatcomplex,difficulttounderstandthedatastructurealgorithmsthroughteachers'classroompresentationsandcontinuousinteractiveoperationtestoflearnersbecomingpopularisclear,effectivelyimprovethequalityandeffectivenessofteaching.

Keywords:

dynamicdemosystem;VisualC++

III

第1章系统开发平台与环境

1.1选题背景

1.1.1课题来源

《数据结构》作为信息类专业的一门核心专业课，对《编译原理》等后续课程的学习极其重要。

但该课程涉及大量的概念、定义、模型和算法，尤其是图的算法显得很抽象和深奥。

用传统的“粉笔+黑板”形式很难将算法的执行过程动态地演示出来，影响了教学效果。

传统的《数据结构》算法是基于以TurboC为代表的DOS开发坏境，可视化效果很差。

而这种坏境给学习者的理解和深入探讨带来很大的问题。

后来，随着多媒体技术的发展，《数据结构》的教学开始运用教学幻灯片的形式来讲授，这些教学幻灯片大多数都是静态的图片或者是一些基本的算法。

这种教学模式弥补了传统的黑板板书的不足，较大地提高了教学质量。

不过这种教学模式在可视性和交互性方面都存在较大的不足。

目前，还有一种教学模式是采用

flash动画演示并配加一定的文字说明的方式，这种方式可以在很大程度上揭示算法原理，唯一的遗憾就是这种动画演示的内容不是很全面，而且在与学习者的交互性方面存在不足，不能让学习者自己输入相关的参数。

因此有必要对图的算法的动态演示进行研究，设计《数据结构》算法演示系统，，帮助学生更快地掌握算法的精髓与实质。

1.1.2本课题的研究意义

本设计从对数据结构图的算法的深入研究开始，在Visual C++的编程坏境下，致力于开发一套专门帮助学习者理解数据结构算法的动态演示系统。

该系统将可视性，交互性和可扩展性紧紧的结合在一起，能大大改善传统教学的弊端，使复杂的难以理解的数据结构算法通过教师的课堂演示和学习者的不断自我交互式操作试验变得通俗明朗，有效地提高教学的质量和效果。

1.1.3课题的关键技术

本系统的核心技术为深度优先搜索遍历算法与图的广度优先搜索遍历算法的动态演示技术研究及其实现。

37

1.2系统开发平台MicrosoftVisualStudio2008

微软发布了.NET开发平台，这是自1993年7月随着WindowsNT3.0出现的Win32 API后微软软件开发平台的第一次大升级。

比起Win16来，

Win32提供了更多功能强大的API，但没有对工具和技术进行引人注目的改变。

与之不同的是，.NET开发平台在开发者用以创造应用程序的工具和技术上做

了根本的改变。

.NET开发平台使得开发者创建运行在Internet Information Server

（IIS）（互联网信息服务器）Web服务器上的Web应用程序更为容易，它也使创建稳定、可靠而又安全的Windows桌面应用程序更为容易。

.NET开发平台包括以下内容：

.NET Framework（架构），包括：

Common LanguageRuntime（CLR）（通用语言运行环境），这是用于运行和加载应用程序的软件组件；新的类库，分级组织了开发者可以在他们的应用程序中用来显示图形用户界面、访问数据库和文件以及在Web上通信的代码集。

.NET开发者工具，包括：

VisualStudio.NETIntegratedDevelopmentEnvironment（IDE）（VisualStudio.NET集成开发环境），用来开发和测试应用程序；.NET编程语言（例如VisualBasic.NET和新的VisualC#），用来创建运行在CLR下并且使用类库的应用程序。

·ASP.NET，一个取代以前的ActiveServerPages（ASP）的特殊类库，用来创建动态的Web内容和Web服务器应用程序，这些都将采用诸如

HTML、XML和SimpleObjectAccessProtocol（SOAP）（简单对象访问协议）

等Internet协议和数据格式。

.NET开发平台是一组用于建立Web服务器应用程序和Windows桌面应用程序的软件组件，用该平台创建的应用程序在Common Language

Runtime（CLR）（通用语言运行环境）（底层）的控制下运行。

CLR是一个

软件引擎，用来加载应用程序，确认它们可以没有错误地执行，进行相应的安全许可验证，执行应用程序，然后在运行完成后将它们清除。

类库集提供了使应用程序可以读写XML数据、在Internet上通信、访问数据库等的代码。

所有的类库都建立在一个基础的类库之上，它提供管理使用最为频繁的数据类型

（例如数值或文本字符串）的功能，以及诸如文件输入/输出等底层功能[1]。

VisualStudio.NET提供了一个用于在该平台上创建应用程序的图形

IntegratedDevelopmentEnvironment（IDE）（集成开发环境）。

程序员可以使用一种或多种.NET编程语言，来编写他们的代码，例如微软自己的VisualBasic.NET（VB.NET），VisualC++,VisualC#和JScrjpt.NET等。

大量其它的.NET编程语言可以从第三方厂商获得。

VisualStudio是微软公司推出的开发环境。

是目前最流行的Windows

平台应用程序开发环境。

目前已经开发到9.0版本，也就是VisualStudio

2008。

VisualStudio可以用来创建Windows平台下的Windows应用程序和网络应用程序，也可以用来创建网络服务、智能设备应用程序和Office插件。

Visual Studio 97 是最早的 Visual Studio 版本。

包含有面向

Windows开发使用的VisualBasic5.0、VisualC++5.0，面向Java开发的VisualJ++和面向数据库开发的VisualFoxPro，还包含有创建DHTML（DynamicHTML）所需要的VisualInterDev。

其中，Visual

Basic和VisualFoxPro使用单独的开发环境，其他的开发语言使用统一的开发环境。

VisualStudio2008提供了高级开发工具、调试功能、数据库功能和创新功能，帮助在各种平台上快速创建当前最先进的应用程序。

VisualStudio2008在三个方面为开发人员提供了关键改进：

快速的应用程序开发、高效的团队协作、突破性的用户体验。

VisualStudio2008包括各种增强功能，例如可视化设计器（使用.NETFramework3.5加速开发）、对Web开发工具的大量改进，以及能够加速开发和处理所有类型数据的语言增强功能。

VisualStudio2008为开发人员提供了所有相关的工具和框架支持，帮助创建引人注目的、令人印象深刻并支持

AJAX的Web应用程序。

开发人员能够利用这些丰富的客户端和服务器端框架轻松构建以客户为中心的Web应用程序，这些应用程序可以集成任何后端数据提供程序、在任何当前浏览器内运行并完全访问ASP.NET应用程序服务和Microsoft平台。

快速的应用程序开发：

为了帮助开发人员迅速创建先进的软件，VisualStudio2008提供了改进的语言和数据功能，例如语言集成的查询（LINQ），

各个编程人员可以利用这些功能更轻松地构建解决方案以分析和处理信息。

VisualStudio2008还使开发人员能够从同一开发环境内创建面向多个.NET

Framework 版本的应用程序。

开发人员能够构建面向 .NET Framework

2.0、3.0或3.5的应用程序，意味他们可以在同一环境中支持各种各样的项目。

突破性的用户体验：

VisualStudio2008为开发人员提供了在最新平台上加速创建紧密联系的应用程序的新工具，这些平台包括 Web、Windows

Vista、Office2007、SQLServer2008和WindowsServer2008。

对于

Web，ASP.NETAJAX 及其他新技术使开发人员能够迅速创建更高效、交互式更强和更个性化的新一代Web体验。

高效的团队协作：

VisualStudio2008提供了帮助开发团队改进协作的扩展的和改进的服务项目，包括帮助将数据库专业人员和图形设计人员加入到开发流程的工具。

使用Microsoft.NETFramework3.5：

.NETFramework提供了用于解决常见编程任务的构建基块（预制的软件），从而能够快速构造具有出色的最终用户体验的紧密联系的应用程序。

在.NETFramework模型业务流程上有效构建的紧密联系的应用程序有利于在异类环境中实现系统集成。

VisualStudio和.NETFramework的结合使用减少了对公用管道代码的需要，从而缩短了开发时间并使开发人员能够集中精力解决业务问题。

.NETFramework3.5是在.NETFramework3.0的基础上构建的更高版本。

得到增强的功能领域包括基类库、Windows workflow

foundation、Windows Communication Foundation、Windows

PresentationFoundation和WindowsCardSpace。

因此本动态演示系统选择MicrosoftVisualStudio作为开发平台是一个不错的选择。

1.3MSDN

MSDN的全称是MicrosoftDeveloperNetwork。

这是微软公司面向软件开发者的一种信息服务。

MSDN实际上是一个以 VisualStudio和

Windows 平台为核心整合的开发虚拟社区，包括技术文档、在线电子教程、

网络虚拟实验室、微软产品下载（几乎全部的操作系统、服务器程序、应用程序和开发程序的正式版和测试版，还包括各种驱动程序开发包和软件开发包）、

Blog、BBS、MSDNWebCast、与CMP合作的MSDN杂志等等一系

列服务。

一般情况下，很多人误认为MSDN为联机帮助文件和技术文献的集合。

但事实上，这两者只占MSDN庞大计划的一小部分。

其中产品下载、在线电子教程、MSDN 杂志和技术紧急电话支援是要付费的，其余基本免费。

当然，MSDN杂志可以通过微软公司的网站免费观看或者下载。

MSDN涵盖了所有的可以被开发扩充的平台和应用程序，因此如微软公司的百科全书Encarta，或者是各种游戏，是不包括在 MSDN 之内的，因为这些产品直接面向最终用户，没有进行程序开发的必要。

用户接触到的最多关于 MSDN 的信息可能是来自于 MSDN

Library。

MSDNLibrary就是通常人们眼中的MSDN，涵盖了微软全套可开发产品线的技术开发文档和科技文献（部分包括源代码），也包括过刊的

MSDN杂志节选和部分经典书籍的节选章节。

MSDNLibrary有1.8GB

左右，可以通过在线或者MSDN订阅（需付费）以脱机方式浏览。

每个时期，随着不同版本VisualStudio发布的时候，都会有对应的MSDNLibrary发布，而从最新版的VisualStudio发布之后，对应旧版本VisualStudio的MSDNLibrary会慢慢停止发布，仅随该Visual

Studio发布的MSDNLibrary以及后续的MSDNLibrary更新才可以被整合到最新版本的VisualStudio中。

1.4MSDN访问

MSDN订购版带有一个可安装的界面，并且Professional和Universal订购版还带有一批Microsoft产品软件，比如Windows平台版本和BackOfice应用程序。

没有必要再向用户阐述如何使用Microsoft产品软件，但是还是要提供一些快速且有用的指导，以弄明白界面的含义，并在MSDN订购版所提供的似乎无穷无尽的参考资料中遨游。

对于使用过MSDN的用户来说，图3-2所示的界面是很熟悉的：

它是MSDN参考资料的导航前台界面。

图3-2MSDN界面

虽然界面很熟悉，并已经是相当直观，但是如果还没有掌握其特性和浏览工具，可能还是会在信息的汪洋大海中迷失方向的。

通过掌握关于高效浏览的一些说明和提示，即可迅速提高其使用效率。

1.4.1浏览MSDN

MSN最主要的特性之一（也许地是最主要的缺点）是资料太完整，包含的信息总量超过1.1GB，并且还在不断增长。

但是MSDN的创建者可能意识到了这一点，已经采取步骤缓解这一问题。

这些步骤之一就是允许开发人员有选择地在MSDN的目录中进行跳转。

MSDN的基本浏览很简单，与在Windows资

源管理器及其文件夹结构中的浏览非常相似。

MSDN没有使用文件夹，它将

“书本”按照专题进行组织。

点击书本左边的+号，可以将书本展开，显示出目录和嵌套的书本或者参考页面，如图3-3所示。

如果在MSDN浏览器中没有看到左边的面板，请到View菜单再选择NavigationTabs菜单项，面板就会出现。

图3-3MSDN浏览界面

MSDN左边面板中的四个选项卡是在MSDN目录中跳转的主要方式。

这四个选项卡，与其上方的Active Subset下拉菜单框协同工作，是用以在

MSDN目录中进行搜索的工具。

在熟练掌握它们之后，这些浏览辅助工具将极大地丰富MSDN的使用经验。

Active Subset下拉菜单框提供的是一种过滤器机制。

从下拉框中选择所感兴趣的MSDN信息子集，四个导航选项卡

（包括Contents选项卡）都将显示的信息限制为所选子集中包含的信息。

这就意味着在Searh选项卡中所做的任何搜索，以及在Index选项卡中的索引，都被其定义的结果值过滤，并且或者与用户所定义的子集相匹配，从而极大地限制了给定查询所得结果的数量，让用户可以得到真正需要的信息。

在Index

选项卡中，符合查询条件而不在所选子集内，将被显示为浅色（但仍然可以选择），在Search选项卡中，它们将根本不会被显示。

MSDN中有下列预定义的子集：

EntireCollectionPlatformSDK,ToolsandLanguages

MSDN,BooksandPeriodicalsPlatformSDK,UserInterfaceServicesMSDN,ContentonDisk2onlyPlatformSDK,WebServicesMSDN,ContentonDisk3onlyPlatformSDK,What'sNew?

MSDN,KnowledgeBasePlatformSDK,Win32API

MSDN,OfficeDevelopmentRepository2.0Documentation

MSDN , Technical Articles and Backgrounders Visual BasicDocumentation

PlatformSDK,BackOfficeVisualC++Documentation

Platform SDK, Base Services Visual C++,Platform SDK andEnterpriseDocs

Platform SDK,Component Services Visual C++,Platform SDK,andWinCEDocs

PlatformSDK,DataAccessServicesVisualFoxProDocumentationPlatform SDK,Graphics and Multimedia Services Visual InterDevDocumentation

PlatformSDK,ManagementServicesVisualJ++Documentation

PlatformSDK,MessagingandCollaborationServicesVisualSourceSafeDocumentation

PlatformSDK,NetworkingServicesPlatformVisualStudioProduct

读者可以看到，过滤选项本质上是MSDN使用的信息结构的一个镜像。

但是，如果用户希望看到这些子集的部分信息，又该怎么办呢？

例如，用户对PlatformSDK'sSecurity、NetworkingServices和ManagementServices子集的某个关键字搜索以及BaseServices子集的部分章节感兴趣，该如何去做呢？

其实相当简单—仅需定义自己的子集即可。

选择View菜单，然后选择DefineSubset菜单项，即可定义子集。

用户面对的是如图3-4所示的窗口。

图3-4DefineSubset窗口

定义子集是很简单的，仅需按照如下步骤进行：

1）选择希望放置到新子集的信息；可以选择整个子集，或者在可用子集中选取“书本”/“目录”。

2）点击Add按钮，将选取的信息放入新创建的子集。

3）在SaveNewSubsetAs文本框中键入名称，为新创建的子集命名。

注意所定义的子集（包括用户自己创建的）将以字母表顺序排列。

如果希望的话，也可以从MSDN安装中删除整个子集。

仅需在SelectSubsetToDisplay下拉框中选择希望删除的子集，然后点击旁边的Delete按钮即可。

一旦定义了一个子集，它将和预定义的子集一样在MSDN中可用。

并且在四个导航选项卡中也会过滤可用信息，和预定义子集表现相同。

1.4.2快速提示

现在读者知道如何浏览MSDN了，还有一些提示和诀窍，可以利用它们来尽可能高效地使用MSDN。

•使用Locate按钮定位也许是人的天性，需要知道现在身处何方。

但遗憾的是，如果在右边面板显示参考页面（也许是从搜索结果中跳转过来的），而对于左边面板的Contents选项卡，没有在信息树中同步地显示参考页面的位置，会很让人头疼。

即使用户知道参考页面所在的技术目录，但最好还是能够找出在目录结构中的位置。

问题的解决很容易：

仅需点击导航工具条中的

Locate按钮，所有的参考将会同步。

像浏览器那样使用Back按钮导航工具条中Back按钮的功能和浏览器

Back按钮的一样。

如果需要先前浏览过的某个参考页面信息，就可以使用

Back按钮返回该页，而不用再重新经历一次搜索过程。

定义用户子集并且使用它们如本章开始时所述，当前可用的信息量太多，有时让人的工作无法进行。

定义MSDN的子集，可以筛选出和工作相关的内容，使得工作起来效率更高。

在命名子集的开始使用下划线在ActiveSubset下拉框里的子集是按照字母表进行排列的，而下拉框每次只能够显示少量子集（使得选中可用子集比较困难）。

下划线在字母表中位于字母之前，因此如果在所有自定义子集的名称都

以下划线开始的话，它们就会在ActiveSubset下拉框中处在可用子集的前面。

另外，使用下划线，用户可以一眼就看出哪些子集是自定义的，而哪些自己是

MSDN附带的—这至少可以节约几秒钟，而这些几秒钟是可以累加的。

1.5系统开发语言MicrosoftVisualC++

MicrosoftVisualC++是Microsoft公司推出的开发Win32环境程序，面向对象的可视化集成编程系统。

它不但具有程序框架自动生成、灵活方便的类管理、代码编写和界面设计集成交互操作、可开发多种程序等优点，而且通过简单的设置就可使其生成的程序框架支持数据库接口、OLE2，WinSock