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

1、摘要数据结构作为信息类专业的一门核心专业课，对编译原理等后续课程的学习极其重要。传统的数据结构算法是基于以 TurboC 为代表的 DOS 开发坏境，可视化效果很差。而这种坏境给学习者的理解和深入探讨带来很大的问题。本设计从对数据结构图的算法的深入研究开始，在 VisualC+的编程坏境下，致力于开发一套专门帮助学习者理解数据结构算法的动态演示系统。该系统将可视性，交互性和可扩展性紧紧的结合在一起，能大大改善传统教学的弊端，使复杂的难以理解的数据结构算法通过教师的课堂演示和学习者的不断自我交互式操作试验变得通俗明朗，有效地提高教学的质量和效果。关键字：动态演示系统；Visual C+IIAbs

2、tractThe data structure as a core of information specialty courses, learning to follow-up such as the compiling principles of course extremely important.Traditional algorithm is based on the data structure to DOS development represented TurboC borders, very poor visual effects. And this bad border t

3、o the learners understanding and in-depth discussions cause great problems. The design starts from the in-depth study on data structure algorithm, programming in Visual C+ under bad border, is committed to developing a set of specialized help learners understand data structure algorithm of dynamic d

4、emo system. The system of Visual, interactive combination of scalability and tightly together, can greatly improve the shortcomings of traditional teaching, so that complex, difficult to understand the data structure algorithms through teachers classroom presentations and continuous interactive oper

5、ation test of learners becoming popular is clear, effectively improve the quality and effectiveness of teaching.Keywords: dynamic demo system; Visual C+III第 1 章 系统开发平台与环境1.1 选题背景1.1.1 课题来源数据结构作为信息类专业的一门核心专业课，对编译原理等后续课程的学习极其重要。但该课程涉及大量的概念、定义、模型和算法，尤其是图的算法显得很抽象和深奥。用传统的“粉笔+黑板”形式很难将算法的执行过程动态地演示出来，影响了教学效

6、果。传统的数据结构算法是基于以 TurboC 为代表的 DOS 开发坏境，可视化效果很差。而这种坏境给学习者的理解和深入探讨带来很大的问题。后来，随 着多媒体技术的发展，数据结构的教学开始运用教学幻灯片的形式来讲授， 这些教学幻灯片大多数都是静态的图片或者是一些基本的算法。这种教学模式 弥补了传统的黑板板书的不足，较大地提高了教学质量。不过这种教学模式在 可视性和交互性方面都存在较大的不足。目前，还有一种教学模式是采用flash 动画演示并配加一定的文字说明的方式，这种方式可以在很大程度上揭示算法原理，唯一的遗憾就是这种动画演示的内容不是很全面，而且在与学习者的交互性方面存在不足，不能让学习者

7、自己输入相关的参数。因此有必要对图的算法的动态演示进行研究，设计数据结构算法演示系统，帮助学生更快地掌握算法的精髓与实质。1.1.2 本课题的研究意义本设计从对数据结构图的算法的深入研究开始，在 VisualC+的编程坏境下，致力于开发一套专门帮助学习者理解数据结构算法的动态演示系统。该系统将可视性，交互性和可扩展性紧紧的结合在一起，能大大改善传统教学的弊端，使复杂的难以理解的数据结构算法通过教师的课堂演示和学习者的不断自我交互式操作试验变得通俗明朗，有效地提高教学的质量和效果。1.1.3 课题的关键技术本系统的核心技术为深度优先搜索遍历算法与图的广度优先搜索遍历算法的动态演示技术研究及其实现

8、。371.2 系统开发平台 Microsoft Visual Studio 2008微软发布了.NET 开发平台，这是自 1993 年 7 月随着 Windows NT3.0 出现的 Win32API 后微软软件开发平台的第一次大升级。比起 Win16 来，Win32 提供了更多功能强大的 API，但没有对工具和技术进行引人注目的改变。与之不同的是，.NET 开发平台在开发者用以创造应用程序的工具和技术上做了根本的改变。.NET 开发平台使得开发者创建运行在 InternetInformationServer(IIS）（互联网信息服务器）Web 服务器上的 Web 应用程序更为容易，它也使创建

9、稳定、可靠而又安全的 Windows 桌面应用程序更为容易。.NET 开发平台包括以下内容：.NETFramework（架构），包括：CommonLanguage Runtime（CLR）（通用语言运行环境），这是用于运行和加载应用程序的软件组件；新的类库，分级组织了开发者可以在他们的应用程序中用来显示图形用户界面、访问数据库和文件以及在 Web 上通信的代码集。.NET 开发者工具，包括：Visual Studio .NET Integrated Development Environment （IDE）（Visual Studio .NET 集成开发环境），用来开发和测试应用程序；.NET

10、 编程语言（例如 Visual Basic .NET 和新的 Visual C#），用来创建运行在 CLR 下并且使用类库的应用程序。 ASP .NET，一个取代以前的 Active Server Pages （ASP）的特殊类库，用来创建动态的 Web 内容和 Web 服务器应用程序，这些都将采用诸如HTML、XML 和 Simple Object Access Protocol（SOAP）（简单对象访问协议）等 Internet 协议和数据格式。.NET 开发平台是一组用于建立 Web 服务器应用程序和 Windows 桌面应用程序的软件组件，用该平台创建的应用程序在 CommonLang

11、uageRuntime（CLR）（通用语言运行环境）（底层）的控制下运行。CLR 是一个软件引擎，用来加载应用程序，确认它们可以没有错误地执行，进行相应的安全许可验证，执行应用程序，然后在运行完成后将它们清除。类库集提供了使应用程序可以读写 XML 数据、在 Internet 上通信、访问数据库等的代码。所有的类库都建立在一个基础的类库之上，它提供管理使用最为频繁的数据类型（例如数值或文本字符串）的功能，以及诸如文件输入/输出等底层功能1。Visual Studio .NET 提供了一个用于在该平台上创建应用程序的图形Integrated Development Environment（IDE

12、）（集成开发环境）。程序员可以使用一种或多种.NET 编程语言，来编写他们的代码，例如微软自己的 Visual Basic .NET（VB.NET），Visual C+, Visual C#和 JScrjpt .NET 等。大量其它的.NET 编程语言可以从第三方厂商获得。Visual Studio 是微软公司推出的开发环境。是目前最流行的 Windows平台应用程序开发环境。目前已经开发到 9.0 版本，也就是 Visual Studio2008。Visual Studio 可以用来创建 Windows 平台下的 Windows 应用程序和网络应用程序，也可以用来创建网络服务、智能设备应用程

13、序和 Office 插件。VisualStudio97是最早的VisualStudio版本。包含有面向Windows 开发使用的 Visual Basic 5.0、Visual C+ 5.0，面向 Java 开发的 Visual J+ 和面向数据库开发的 Visual FoxPro，还包含有创建DHTML (Dynamic HTML) 所需要的 Visual InterDev。其中，VisualBasic 和 Visual FoxPro 使用单独的开发环境，其他的开发语言使用统一的开发环境。Visual Studio 2008 提供了高级开发工具、调试功能、数据库功能和创新功能，帮助在各种平台

14、上快速创建当前最先进的应用程序。Visual Studio 2008 在三个方面为开发人员提供了关键改进：快速的应用程序开发、高效的团队协作、突破性的用户体验。Visual Studio 2008 包括各种增强功能，例如可视化设计器（使用 .NET Framework 3.5 加速开发）、对 Web 开发工具的大量改进，以及能够加速开发和处理所有类型数据的语言增强功能。Visual Studio 2008 为开发人员提供了所有相关的工具和框架支持，帮助创建引人注目的、令人印象深刻并支持AJAX 的 Web 应用程序。开发人员能够利用这些丰富的客户端和服务器端框架轻松构建以客户为中心的 Web

15、应用程序，这些应用程序可以集成任何后端数据提供程序、在任何当前浏览器内运行并完全访问 ASP.NET 应用程序服务和 Microsoft 平台。快速的应用程序开发：为了帮助开发人员迅速创建先进的软件，Visual Studio 2008 提供了改进的语言和数据功能，例如语言集成的查询 (LINQ)，各个编程人员可以利用这些功能更轻松地构建解决方案以分析和处理信息。Visual Studio 2008 还使开发人员能够从同一开发环境内创建面向多个 .NETFramework版本的应用程序。开发人员能够构建面向.NETFramework2.0、3.0 或 3.5 的应用程序，意味他们可以在同一环境

16、中支持各种各样的项目。突破性的用户体验：Visual Studio 2008 为开发人员提供了在最新平台上加速创建紧密联系的应用程序的新工具，这些平台包括Web、WindowsVista、Office 2007、SQL Server 2008 和 Windows Server 2008。对于Web，ASP.NET AJAX及其他新技术使开发人员能够迅速创建更高效、交互式更强和更个性化的新一代 Web 体验。高效的团队协作：Visual Studio 2008 提供了帮助开发团队改进协作的扩展的和改进的服务项目，包括帮助将数据库专业人员和图形设计人员加入到开发流程的工具。使用 Microsoft

17、 .NET Framework 3.5：.NET Framework 提供了用于解决常见编程任务的构建基块（预制的软件），从而能够快速构造具有出色的最终用户体验的紧密联系的应用程序。在 .NET Framework 模型业务流程上有效构建的紧密联系的应用程序有利于在异类环境中实现系统集成。Visual Studio 和 .NET Framework 的结合使用减少了对公用管道代码的需要，从而缩短了开发时间并使开发人员能够集中精力解决业务问题。.NET Framework 3.5 是在 .NET Framework 3.0 的基础上构建的更高版本。得到增强的功能领域包括基类库、Windowswo

18、rkflowfoundation、WindowsCommunicationFoundation、WindowsPresentation Foundation 和 Windows CardSpace 。因此本动态演示系统选择 Microsoft Visual Studio 作为开发平台是一个不错的选择。1.3 MSDNMSDN 的全称是 Microsoft Developer Network。这是微软公司面向软件开发者的一种信息服务。MSDN 实际上是一个以Visual Studio 和Windows平台为核心整合的开发虚拟社区，包括技术文档、在线电子教程、网络虚拟实验室、微软产品下载（几乎全部

19、的操作系统、服务器程序、应用程序和开发程序的正式版和测试版，还包括各种驱动程序开发包和软件开发包）、Blog、BBS、MSDN WebCast、与 CMP 合作的 MSDN 杂志等等一系列服务。一般情况下，很多人误认为 MSDN 为联机帮助文件和技术文献的集合。但事实上，这两者只占 MSDN 庞大计划的一小部分。 其中产品下载、在线电子教程、MSDN杂志和技术紧急电话支援是要付费的，其余基本免费。当然， MSDN 杂志可以通过微软公司的网站免费观看或者下载。MSDN 涵盖了所有的可以被开发扩充的平台和应用程序，因此如微软公司的百科全书Encarta，或者是各种游戏，是不包括在MSDN之内的，因

20、为这些产品直接面向最终用户，没有进行程序开发的必要。用户接触到的最多关于MSDN的信息可能是来自于MSDNLibrary。MSDN Library 就是通常人们眼中的 MSDN，涵盖了微软全套可开发产品线的技术开发文档和科技文献（部分包括源代码），也包括过刊的MSDN 杂志节选和部分经典书籍的节选章节。MSDN Library 有 1.8 GB左右，可以通过在线或者 MSDN 订阅（需付费）以脱机方式浏览。每个时期，随着不同版本 Visual Studio 发布的时候，都会有对应的MSDN Library 发布，而从最新版的 Visual Studio 发布之后，对应旧版本Visual Stu

21、dio 的 MSDN Library 会慢慢停止发布， 仅随该 VisualStudio 发布的 MSDN Library 以及后续的 MSDN Library 更新才可以被整合到最新版本的 Visual Studio 中。1.4 MSDN 访问MSDN订购版带有一个可安装的界面，并且Professional和Universal订购版还带有一批Microsoft产品软件，比如Windows平台版本和BackOfice应用程序。没有必要再向用户阐述如何使用Microsoft产品软件，但是还是要提供一些快速且有用的指导，以弄明白界面的含义，并在MSDN订购版所提供的似乎无穷无尽的参考资料中遨游。对

22、于使用过M S D N的用户来说，图3 - 2所示的界面是很熟悉的：它是MSDN参考资料的导航前台界面。图3-2 MSDN界面虽然界面很熟悉，并已经是相当直观，但是如果还没有掌握其特性和浏览工具，可能还是会在信息的汪洋大海中迷失方向的。通过掌握关于高效浏览的一些说明和提示，即可迅速提高其使用效率。1.4.1 浏览 MSDNMSN 最主要的特性之一（也许地是最主要的缺点）是资料太完整，包含的信息总量超过 1.1GB，并且还在不断增长。但是 MSDN 的创建者可能意识到了这一点，已经采取步骤缓解这一问题。这些步骤之一就是允许开发人员有选择地在 MSDN 的目录中进行跳转。MSDN 的基本浏览很简单

23、，与在 Windows 资源管理器及其文件夹结构中的浏览非常相似。MSDN 没有使用文件夹，它将“书本”按照专题进行组织。点击书本左边的+号，可以将书本展开，显示出目录和嵌套的书本或者参考页面，如图 3 - 3 所示。如果在 MSD N 浏览器中没有看到左边的面板，请到 View 菜单再选择 Navigation Tabs 菜单项，面板就会出现。图 3-3 MSDN 浏览界面MSDN 左边面板中的四个选项卡是在 MSDN 目录中跳转的主要方式。这四个选项卡，与其上方的 ActiveSubset 下拉菜单框协同工作，是用以在MSDN 目录中进行搜索的工具。在熟练掌握它们之后，这些浏览辅助工具将极

24、大地丰富 MSDN 的使用经验。ActiveSubset 下拉菜单框提供的是一种过滤器机制。从下拉框中选择所感兴趣的 MSDN 信息子集，四个导航选项卡（包括 Contents 选项卡）都将显示的信息限制为所选子集中包含的信息。这就意味着在 Searh 选项卡中所做的任何搜索，以及在 Index 选项卡中的索引， 都被其定义的结果值过滤，并且或者与用户所定义的子集相匹配，从而极大地限制了给定查询所得结果的数量，让用户可以得到真正需要的信息。在 Index选项卡中，符合查询条件而不在所选子集内，将被显示为浅色（但仍然可以选择），在 Search 选项卡中，它们将根本不会被显示。MSDN 中有下列

25、预定义的子集：Entire Collection Platform SDK,Tools and LanguagesMSDN,Books and Periodicals Platform SDK,User Interface Services MSDN,Content on Disk 2 only Platform SDK,Web Services MSDN,Content on Disk 3 only Platform SDK,Whats New?MSDN,Knowledge Base Platform SDK,Win32 APIMSDN , O ffice Development Repos

26、itory 2.0 DocumentationMSDN,TechnicalArticlesandBackgroundersVisualBasic DocumentationPlatform SDK,BackOffice Visual C+ DocumentationPlatformSDK,BaseServicesVisualC+,PlatformSDKand EnterpriseDocsPlatformSDK,ComponentServicesVisualC+,PlatformSDK,and WinCEDocsPlatform SDK,Data Access Services Visual F

27、oxPro Documentation PlatformSDK,GraphicsandMultimediaServicesVisualInterDev DocumentationPlatform SDK,Management Services Visual J+ DocumentationPlatform SDK,Messaging and Collaboration Services Visual SourceSafe DocumentationPlatform SDK,Networking Services Platform Visual Studio Product读者可以看到，过滤选项

28、本质上是M S D N使用的信息结构的一个镜像。但是， 如果用户希望看到这些子集的部分信息，又该怎么办呢？例如，用户对Platform SDKs Security、NetworkingServices和Management Services 子集的某个关键字搜索以及Base Services子集的部分章节感兴趣，该如何去做呢？其实相当简单仅需定义自己的子集即可。选择View菜单，然后选择Define Subset菜单项，即可定义子集。用户面对的是如图3 - 4所示的窗口。图 3-4 Define Subset 窗口定义子集是很简单的，仅需按照如下步骤进行：1) 选择希望放置到新子集的信息；可以

29、选择整个子集，或者在可用子集中选取“书本” /“目录”。2) 点击 Add 按钮，将选取的信息放入新创建的子集。3) 在 Save New Subset As 文本框中键入名称，为新创建的子集命名。注意所定义的子集（包括用户自己创建的）将以字母表顺序排列。如果希望的话，也可以从 MSDN 安装中删除整个子集。仅需在 Select Subset To Display 下拉框中选择希望删除的子集，然后点击旁边的 Delete 按钮即可。一旦定义了一个子集，它将和预定义的子集一样在 MSDN 中可用。并且在四个导航选项卡中也会过滤可用信息，和预定义子集表现相同。1.4.2 快速提示现在读者知道如何浏

30、览 MSDN 了，还有一些提示和诀窍，可以利用它们来尽可能高效地使用 MSDN。 使用 Locate 按钮定位也许是人的天性，需要知道现在身处何方。但遗憾的是，如果在右边面板显示参考页面（也许是从搜索结果中跳转过来的），而对于左边面板的 Contents 选项卡，没有在信息树中同步地显示参考页面的位置，会很让人头疼。即使用户知道参考页面所在的技术目录，但最好还是能够找出在目录结构中的位置。问题的解决很容易：仅需点击导航工具条中的Locate 按钮，所有的参考将会同步。像浏览器那样使用 Back 按钮导航工具条中 Back 按钮的功能和浏览器Back 按钮的一样。如果需要先前浏览过的某个参考页面

31、信息，就可以使用Bac k 按钮返回该页，而不用再重新经历一次搜索过程。定义用户子集并且使用它们如本章开始时所述，当前可用的信息量太多， 有时让人的工作无法进行。定义 MSDN 的子集，可以筛选出和工作相关的内容，使得工作起来效率更高。在命名子集的开始使用下划线在 ActiveSubset 下拉框里的子集是按照字母表进行排列的，而下拉框每次只能够显示少量子集（使得选中可用子集比较困难）。下划线在字母表中位于字母之前，因此如果在所有自定义子集的名称都以下划线开始的话，它们就会在 Active Subset 下拉框中处在可用子集的前面。另外，使用下划线，用户可以一眼就看出哪些子集是自定义的，而哪些自己是MSDN 附带的这至少可以节约几秒钟，而这些几秒钟是可以累加的。1.5 系统开发语言 Microsoft Visual C+Microsoft Visual C+是 Microsoft 公司推出的开发 Win32 环境程序， 面向对象的可视化集成编程系统。它不但具有程序框架自动生成、灵活方便的 类管理、代码编写和界面设计集成交互操作、可开发多种程序等优点，而且通 过简单的设置就可使其生成的程序框架支持数据库接口、OLE2，WinSock