数据结构经典算法演示系统论文

1、摘要本文所涉及的应用程序作为多媒体课堂教学的辅助工具，为数据结构课程的算法演示课件，旨在增加课堂教学手段的多样性和教学的生动性。本软件是为了丰富课堂教学手段，提高数据结构教学质量而开发的。它包括数据结构一书中的几个经典算法。是在Microsoft Visual C+ 2003环境下开发的。它为数据结构课程中几个经典算法提供一种形象的动画表达方式。本文从总体出发，逐步细化，介绍了该软件的设计、开发的基本情况。并带有相应的截图和一些典型源代码，以方便说明和理解。关键词：多媒体课件，数据结构课程，VCABSTRACTThe application program referred in this p

2、aper is an assistant implement for multimedia class. Its an arithmetic_demonstrate_application for Data Structure. The purpose of this application program is to offer more teaching instrumentality and make the process of teaching much more vivid. This application program is being designed to offer m

3、ore teaching instrumentality, and the exaltation data structure teaching quality. It has several famous arithmetic of Data Structure. And the tool of exploitation is Microsoft Visual C+ 2003.This application can offer a kind of way that can bring forth that arithmetic vividly. Its begun with collect

4、ivity, and then introduces the basic cases of design and exploitation for this software bit by bit imperceptibly. There are some pictures of the application and some typical code to explain the application in this paper, too.Keywords: multimedia courseware, data structure course, VC目录 TOC o 1-3 h z

5、u HYPERLINK l _Toc169519283 摘要 PAGEREF _Toc169519283 h I HYPERLINK l _Toc169519284 ABSTRACT PAGEREF _Toc169519284 h II HYPERLINK l _Toc169519285 第1章 绪论 PAGEREF _Toc169519285 h 1 HYPERLINK l _Toc169519286 1.1 开发演示系统的背景 PAGEREF _Toc169519286 h 1 HYPERLINK l _Toc169519287 1.2 数据结构经典算法演示系统的研究内容 PAGEREF

6、_Toc169519287 h 2 HYPERLINK l _Toc169519288 1.3 开发该系统的可行性 PAGEREF _Toc169519288 h 2 HYPERLINK l _Toc169519289 1.4 演示系统在教学中的优点 PAGEREF _Toc169519289 h 3 HYPERLINK l _Toc169519290 第2章 系统概述及开发工具 PAGEREF _Toc169519290 h 4 HYPERLINK l _Toc169519291 2.1 演示系统设计要求 PAGEREF _Toc169519291 h 4 HYPERLINK l _Toc1

7、69519292 2.2演示系统的需求分析 PAGEREF _Toc169519292 h 4 HYPERLINK l _Toc169519293 2.2.1 应用对象 PAGEREF _Toc169519293 h 5 HYPERLINK l _Toc169519294 2.2.2 应用环境 PAGEREF _Toc169519294 h 5 HYPERLINK l _Toc169519295 2.2.3 任务分析 PAGEREF _Toc169519295 h 5 HYPERLINK l _Toc169519296 2.3 演示系统总体规划 PAGEREF _Toc169519296 h

8、6 HYPERLINK l _Toc169519297 2.3.1 开发过程应遵循的要求 PAGEREF _Toc169519297 h 6 HYPERLINK l _Toc169519298 2.3.2 系统组成 PAGEREF _Toc169519298 h 7 HYPERLINK l _Toc169519299 2.3.3 功能要求 PAGEREF _Toc169519299 h 7 HYPERLINK l _Toc169519300 2.4 选用MFC进行系统开发 PAGEREF _Toc169519300 h 8 HYPERLINK l _Toc169519301 2.5 本章小结

9、PAGEREF _Toc169519301 h 9 HYPERLINK l _Toc169519302 第3章 演示系统设计 PAGEREF _Toc169519302 h 10 HYPERLINK l _Toc169519303 3.1 系统组成 PAGEREF _Toc169519303 h 10 HYPERLINK l _Toc169519304 3.2 各个功能模块的要求 PAGEREF _Toc169519304 h 11 HYPERLINK l _Toc169519305 3.2.1 主界面功能要求 PAGEREF _Toc169519305 h 11 HYPERLINK l _T

10、oc169519306 3.2.2 表与栈 PAGEREF _Toc169519306 h 11 HYPERLINK l _Toc169519307 3.2.3 栈的递归过程汉诺塔 PAGEREF _Toc169519307 h 12 HYPERLINK l _Toc169519308 3.2.4 最短路径 PAGEREF _Toc169519308 h 13 HYPERLINK l _Toc169519309 3.3 本章小结 PAGEREF _Toc169519309 h 14 HYPERLINK l _Toc169519310 第4章 演示系统实现 PAGEREF _Toc1695193

11、10 h 15 HYPERLINK l _Toc169519311 4.1 系统框架的实现 PAGEREF _Toc169519311 h 15 HYPERLINK l _Toc169519312 4.2 顺序表演示模块的实现 PAGEREF _Toc169519312 h 17 HYPERLINK l _Toc169519313 4.2.1 设计思想 PAGEREF _Toc169519313 h 17 HYPERLINK l _Toc169519314 4.2.2 算法演示流程图 PAGEREF _Toc169519314 h 18 HYPERLINK l _Toc169519315 4.

12、2.3 关键技术的实现 PAGEREF _Toc169519315 h 18 HYPERLINK l _Toc169519316 4.3 链表演示模块的实现 PAGEREF _Toc169519316 h 21 HYPERLINK l _Toc169519317 4.3.1 设计思想 PAGEREF _Toc169519317 h 21 HYPERLINK l _Toc169519318 4.3.2 成品展示 PAGEREF _Toc169519318 h 21 HYPERLINK l _Toc169519319 4.4 汉诺塔演示模块的实现 PAGEREF _Toc169519319 h 2

13、2 HYPERLINK l _Toc169519320 4.4.1 设计思想 PAGEREF _Toc169519320 h 22 HYPERLINK l _Toc169519321 4.4.2 用递归互换法解决汉诺塔问题的流程图 PAGEREF _Toc169519321 h 24 HYPERLINK l _Toc169519322 4.4.3 关键代码展示 PAGEREF _Toc169519322 h 25 HYPERLINK l _Toc169519323 4.4.4 成品展示 PAGEREF _Toc169519323 h 28 HYPERLINK l _Toc169519324 4

14、.5 最短路径演示模块的实现 PAGEREF _Toc169519324 h 30 HYPERLINK l _Toc169519325 4.5.1 设计思想 PAGEREF _Toc169519325 h 30 HYPERLINK l _Toc169519326 4.5.2 算法演示流程图 PAGEREF _Toc169519326 h 32 HYPERLINK l _Toc169519327 4.5.3 关键代码展示 PAGEREF _Toc169519327 h 33 HYPERLINK l _Toc169519328 4.5.4 成品展示 PAGEREF _Toc169519328 h

15、35 HYPERLINK l _Toc169519329 4.6 系统模块间的联系 PAGEREF _Toc169519329 h 37 HYPERLINK l _Toc169519330 4.7 本章小结 PAGEREF _Toc169519330 h 37 HYPERLINK l _Toc169519331 第5章 结论 PAGEREF _Toc169519331 h 38 HYPERLINK l _Toc169519332 致谢 PAGEREF _Toc169519332 h 39 HYPERLINK l _Toc169519333 参考文献 PAGEREF _Toc169519333

16、h 40 HYPERLINK l _Toc169519334 附录 PAGEREF _Toc169519334 h 41第1章 绪论数据结构是计算机科学与技术专业的核心基础课程之一。但是它概念抽象，算法枯涩难懂，难以提起学生的学习兴趣。如何有效的让学生掌握该课程是一个值得研究的问题。计算机辅助教学（CAI）作为一种先进的教学手段正逐步渗透到各类学校的各个学科，多媒体技术给CAI注入了新的活力。由于多媒体技术能够综合处理文本、图像、动画、音频、视频等多种媒体, 并通过视觉、听觉对人体产生多重感官刺激, 从而使学生在较短的时间内获得较多的信息量。本文重点介绍如何用MFC开发的几个数据结构经典算法的

17、演示系统（下文简称为演示系统），并讨论实现中的一些关键技术。 开发演示系统的背景数据结构是计算机相关专业的一门重要的专业基础课。它主要研究计算机加工对象的逻辑结构、数据在计算机中的表示形式以及实现各种基本操作的算法，该课程在计算机科学与技术的专业教学中的地位可用四个词概括：核心、基础、纽带、桥梁。“核心”即指这门课在计算机专业中占有非常重要的地位，是一门核心基础课。数据是计算机处理的对象，使用计算机就是对数据进行加工处理的过程，因而数据的组织与结构被确立为计算机科学中最为基本的内容。数据结构课程以问题求解方法、程序设计方法及一些典型的数据结构算法为研究对象，要求学生学会分析数据对象特征，掌握数

18、据组织方法和计算机的表示方法，为数据选择适当的逻辑结构、存储结构以及相应的处理算法，培养学生良好的程序设计风格，因而数据结构课程是计算机专业的一门核心课程。“基础”指该课程为后续多门计算机专业课提供了必要的基础。如操作系统、数据库原理、编译原理、算法分析与设计、软件工程、计算机网络、人工智能等都需要数据结构作为课程的基础；同时这门课又是横贯数学与计算机、计算机硬件与软件并将数学与计算机、计算机软件与硬件有机的融合在一起的一门学科，是将计算机理论与上机实践融合在一起的一门学科，是它们之间的“纽带”。没有它作为基础，后继大部分课程将不能展开，也就是说。这门课程是通往其它课程的一座“桥梁”。因此大力

19、加强数据结构课程的建设，提高数据结构课程的教学质量，有利于教学改革和教育创新，有利于创新人才的培养。努力提高数据结构课程的教学质量，对于新一轮的以创新教育和素质教育为主要内容的教学改革将起到积极的推进和示范作用。1.2 数据结构经典算法演示系统的研究内容为了适应课堂教学的要求，数据结构经典算法演示系统应该具有：（1）软件界面的设计要求：较强的交互能力、动态的算法演示、形象的图形设计、充分应用声音和色彩体现算法的细节、屏幕设计简洁明快、屏幕元素布局合理、突出教学内容的重点等等；（2）软件中不仅包含主要的教学内容，而且还应提供一些特殊例题的算法演示，用以扩大学生的编程思维能力，从而实现用形象的图形

20、界面为学生搭起通向掌握抽象思维方法的桥梁；（3）软件中通过图形演绎出来的所有算法思想必须准确；（4）操作简单，易于理解，符合Windows的操作规则，便于使用；（5）软件在设计开发过程中具有自身的规范，而对于教学软件来说，设计开发者应该在遵循一般规范的基础上，深入研究学与教的原理，在有关科学理论指导下设计开发教学软件。1.3 开发该系统的可行性传统教学模式注重基础知识理论的掌握。用大量的时问讲定义、语法、概念语句，对学生的要求是注重接受、理解、记忆，讲课方式是老师讲、学生听。学生掌握的知识比较抽象、机械、静止、片面和孤立，缺乏创造性，严重影响了学生就业和个人发展。因此使当前的大学生具备扎实基础

21、知识的同时又具备解决实际问题、批判性思维和创造性思维，发展合作能力与自主学习能力，是目前急待解决的问题，也是人们进行教学改革的思路。 在教学过程中的具体做法是：开始上课时演示一个精心设计的、 吸引学生注意并包含当天上课新内容的运行结果。这个过程实际上也就是向学生提出了一个新的问题。给学生一定的时间去思考，然后在讲授。或者是留下问题让同学们在课下去想办法解决然后在上机时实现。这样一步一步地分析问题解决问题拓展问题有助于促进学生创造性思维的形成。1.4 演示系统在教学中的优点（1）可视化教学软件不像教材那样枯燥乏味，教师可以利用它来吸引学生的注意力；（2）可视化教学软件可将文字、数据、图片、影片动

22、态地整合在一起；（3）可视化教学软件可以让学生体会在大量不同的数据结构下，算法执行效率的差异；（4）学生在课后可利用可视化教学软件探索算法的执行过程，提高学生个别化学习能力；（5）加强刺激，加深印象。第2章 系统概述及开发工具数据结构几个经典算法的演示系统作为一个教学软件，要求界面清新简单，可操作性强，与使用者的操作系统兼容性强。本软件是在Windows XP操作系统下用MFC开发的，可在装有VC+（2003版）的使用Windows XP操作系统的电脑上使用。 演示系统设计要求算法演示软件服务于教学目的，其设计目标是通过演示以最大限度地帮助学习者理解算法，并掌握其实质。演示内容包括：程序的运行

23、过程、数据结构的变化及一些动态结果。其是一个可视化软件。开发数据结构几个经典算法的演示系统的过程包括五个基本的步骤：需求分析、设计、制作、成品使用、评价和修改。其工作流程如图2-1所示。评价和修改设 计教学目标教学内容教学策略结构设计脚本编写制作工具选择素材准备开发实施成品使用需求分析应用对象应用环境任务分析图2-1数据结构几个经典算法演示系统的开发过程演示系统的需求分析需求分析就是分析软件用户的需求是什么。如果投入大量的人力、物力、财力和时间开发出的软件却没人要，那所有的投入都是徒劳。如果费了很大的精力，开发一个软件，最后却不满足用户的要求，从而要重新开发过，这种返工是让人痛心疾首的。需求分

24、析之所以重要，就因为他具有决策性，方向性，策略性的作用，他在软件开发的过程中具有举足轻重的地位。大家一定要对需求分析具有足够的重视。在一个大型 HYPERLINK :/ itisedu /phrase/200602281706245.html t _new 软件系统的开发中，它的作用要远远大于 HYPERLINK :/ itisedu /phrase/200602281641255.html t _new 程序代码的编写。 应用对象在第一章已经讲过的数据结构教学中的困难中可以看出，教学活动需要注入新活力，使用演示系统辅助教学是很好的选择，也就是说它有应用前景，由老师利用该演示系统指导学生学习数

25、据结构或者学生利用该演示系统自主复习数据结构。它的应用对象是学习数据结构的学生。数据结构的概念晦涩难懂，尤其是在当今学生学习主动性不是很好的环境下，学生就很难掌握该课程了。有的时候直观的演示可能比详尽的概念解释更易让学生学习到知识。数据结构几个经典算法的演示系统大致能满足教师授课的需要，给学生以直观的教学印象，让学生清楚的知道数据怎么变化的，调动学生学习的积极性。不过该系统不是完善的，只有有限的几个算法演示。开发该系统只希望能起到抛砖引玉的作用，给学生带来一定的启发。 应用环境开发该演示系统的目的是为了在教学中引入新的教学手段，调动学生学习积极性，提供教师授课的方便。该系统的是在Windows

26、 XP操作系统下实现的，这样符合大多数教学所用的计算机所采用的系统，方便软件在不同计算机之间的转移。它可以是教师使用或者学生使用，软件界面的简单使得不同知识层次的人使用起来不会有麻烦。 任务分析使用该演示系统是为了促进学生对数据结构课程的理解，提高数据结构课程的教学质量。在现代化的教学过程中，由于多媒体辅助教学能够化静为动，寓教于乐，培养和激发学生的学习兴趣；能使抽象问题形象化，便于学生对知识点的理解和运用；能节约传统的板书时间，开阔知识面，增加信息量，提高学习效率，所以这种教学手段被广泛采用。但是滥用多媒体辅助教学，不但不能达到预期的教学效果，反而会分散学生的注意力，削弱了教师在教学过程中应

27、起的主导作用，甚至影响学生的学习积极性。因此要注意怎么使用软件。虽然教学课件已经事先做好，但不是说在课堂上教师只要在教师用机的位置上单纯地“演示”课件就可以了，这样可能会出现学生看了很多，听了很多，却不知道要学什么，而事与愿违。其实，多媒体辅助教学作为一种现代化的教学手段，是用来提高课堂教学的效率、突破重点难点、解决一些传统教学不易解决的问题。教师应该凭自身丰富的教学经验和生动的讲解，通过师生间的情绪感染，来调动学生学习的积极性，并使学生能够自觉的参与到新的教学当中去。另外，事先做好的课件灵活性可能较差，有时会限制教师的临场发挥，这时就要求教师应积极有效地利用投影仪等现代媒体辅助教学，来解决这

28、个矛盾。2.3 演示系统总体规划 开发过程应遵循的要求（1）符合一般环境需求。可视化软件的系统平台必须符合学生一般常接触的环境。现在常见到的不外乎是Java Applet和应用软件。对于Java Applet而言，是属于客户机/ 服务器架构。学生必须经由网络的连接，将需求传送至服务器端，然后才能执行。如此，对于缺乏网络或网络不顺畅的教学环境而言，就容易受到限制。对于应用软件而言，要求系统简洁，小巧便于移动。（2）界面设计的便利性。在有限时间内，学生不应花费太多的时间去摸索复杂困难的学生界面。所以在接口设计上，必须以学生操作方便为原则。（3）提供学生输入数据。当学生初次使用可视化软件时，系统必须

29、告知其所接受的数据形态和范围。如利用系统自行产生数据的功能，让学生便于执行算法。如此可以鼓励学生主动去探索各种情况下算法的执行效率。（4）学生控制。不同的学生，其吸收知识的速度不一定相同。因而，让学生自行掌握学习的速度是有必要的。在可视化软件中可提供调整动画执行过程的延迟时间，或是利用单步执行按键，让学生自行控制学习速度。此外还原键也是让学生往回追溯不懂之处的重要按键之一。（5）算法的全貌浏览。当学生想快速观看算法的部分片段时，提供快速执行功能是有其必要性的。学生可直接执行算法的某一时点，或大略观看演算法的执行全貌。（6）提供伪码的对照。单纯展示算法执行过程，只能让学生在算法程序上有所了解。若

30、要让学生在概念上更加清楚，则提供算法的伪码是一个好方法。（7）相关辅助信息。例如对于不熟悉算法的学生而言，可提供相关的背景数据与算法所要达成的目标。2.3.2 系统组成演示系统包含教五个教学单元：顺序表的插入和删除、链表的插入、栈的递归过程汉诺塔、最短路径。每个单元的内容相互独立，并由主菜单调入。每个单元都有各自的功能，可由主菜单进入各个独立单元。系统的总体框架如下图2-2。顺序表链表栈最短路径插入删除插入汉诺塔迪杰斯特拉欢迎界面图2-2 演示系统总体框架2.3.3 功能要求（1）用动态图形对数据结构中如: 线形表的插入删除算法、汉诺塔及最短路径问题进行了形象直观、准确生动的演示。能够很好地帮

31、助学生深入理解算法，有利于培养学生的抽象能力；（2）系统控制能力强, 具有暂停、重复和恢复等功能；（3）良好的操作界面, 同时支持键盘和鼠标, 操作简单。菜单提示, 可点对象醒目；（4）软件脚本根据由严蔚敏编著的国优教材数据结构一书编写的。内容编排合理, 教学功能强；（5）交互性强。系统中使用的大部分参数可由使用者自行设置。学习内容及学习进度也可由使用者自行选择；（6）系统采用模块化结构, 可维护性强。2.4 选用MFC进行系统开发该演示系统使用了大量的视图界面作为演示系统的操作界面，而且演示系统为了用户的使用方便采取的是基于对话框的结构构架，利用微软基本类库MFC（Microsoft Fou

32、ndation Class）能够很好的开发出符合这种需要的软件，因此选择使用MFC以及Visual C+开发系统来编写自己的基于Windows 的应用程序。MFC提供了很多的图形控件，可以比较方便的设计出算法演示系统的界面。MFC是微软为Windows 程序员提供的一个面向对象的Windows 编程接口, 它大大简化了Windows 编程工作。该层次结构包容了Windows API 中的用户界面部分, 并使程序员能够很容易地以面向对象的方式建立Windows 应用程序。这种层次结构适用于所有版本的Windows , 并彼此兼容。基础类库的核心是以C + + 形式封装了大部分的Windows A

33、PI。类库表示窗口, 对话框, 设备上下文, 公共GDI 对象如画笔、调色板、控制框和其他标准的Windows 部件。这些类提供了一个面向Windows 中结构的简单的C + + 成员函数的接口。MFC的本质就是一个包含了许多微软公司已经定义好的对象的类库，我们知道，虽然我们要编写的程序在功能上是千差万别的，但从本质上来讲，都可以化归为用户界面的设计，对文件的操作，多媒体的使用，数据库的访问等等一些最主要的方面。这一点正是微软提供MFC类库最重要的原因，在这个类库中包含了一百多个程序开发过程中最常用到的对象。在进行程序设计的时候，如果类库中的某个对象能完成所需要的功能，这时我们只要简单地调用已

34、有对象的方法就可以了。我们还可以利用面向对象技术中很重要的“继承”方法从类库中的已有对象派生出我们自己的对象，这时派生出来的对象除了具有类库中的对象的特性和功能之外，还可以由我们自己根据需要加上所需的特性和方法，产生一个更专门的，功能更为强大的对象。当然，你也可以在程序中创建全新的对象，并根据需要不断完善对象的功能。正是由于MFC编程方法充分利用了面向对象技术的优点，它使得我们编程时极少需要关心对象方法的实现细节，同时类库中的各种对象的强大功能足以完成我们程序中的绝大部分所需功能，这使得应用程序中程序员所需要编写的代码大为减少，有力地保证了程序的良好的可调试性。最后要指出的是MFC类库在提供的

35、对象的各种属性和方法都是经过谨慎的编写和严格的测试，可靠性很高，这就保证了使用MFC类库不会影响程序的可靠性和正确性。2.5 本章小结本章是对系统的概述以及开发工具的介绍。详细说明了系统的需求分析。系统是在Windows XP系统下使用MFC构架的，并说明了使用MFC构架系统的优越性。第3章 演示系统设计一个好的计算机应用软件，都是经过程序员冷静的思考，详尽的分析而产生的。设计远比编程重要。设计的过程就是将事务处理抽象成计算机模型的过程。本章详细的介绍演示系统的系统组成与各个功能模块的要求。3.1 系统组成该演示系统是几个经典数据结构算法的演示系统。这几个经典算法分别是顺序表的插入、删除算法，

36、链表的插入算法，栈的递归过程中的汉诺塔，使用迪杰斯特拉算法求最短路径。系统设计图如下图3-1所示。由图3-1可以看到，系统设计是采用模块化思想，这样每个算法之间都是独立的，便于系统维护，也便于以后再向里面添加新的算法。每个算法演示下面都有其详细的操作界面。以顺序表插入为例子，它的具体设计思想如下图3-2所示。其他各个算法的演示大致和顺序表插入算法相同，有方便的操作，动态的图形演示和跟随程序运行的伪代码。欢迎界面线性表链表栈最短路径顺序表插入顺序表删除返回链表删除返回汉诺塔返回最短路径返回图3-1演示系统总体设计顺序表的插入操作模块演示模块算法说明图形演示伪代码暂停返回单步执行恢复插入元素输入数

37、据图3-2顺序表插入算法演示模块3.2 各个功能模块的要求3.2.1 主界面功能要求主界面是一个选择界面，它们的功能是转到下一个界面。(1)顺序表:它的作用是转到顺序表插入删除算法选择界面。(2)链表:它的作用是转到链表插入算法选择界面。(3)栈:它的作用是转到汉诺塔算法选择界面。(4)最短路径:它的作用是转到迪杰斯特拉算法选择界面。二级界面同样是一个选择界面，它们的功能是转到相应算法演示界面。它们的要求如附录。3.2.2 表与栈该演示系统演示算法中有关表的演示有两个：顺序表和链表。它们都是数据结构课程的基本知识，在实际中也有很广的用途。算法说明：对演示算法的说明，该系统的教学对象对算法概念不

38、清楚时可以查看，或者让初学者知道该算法是怎么样的。因此算法说明应该能清楚的表明算法的思想。输入数据：输入数据就是向系统中写入数据，为演示做好准备。输入数据时弹出一个对话框，在指定地方输入数据，并且有说明什么样的数据是系统允许的。输入非法数据时系统将不能接受或者弹出错误提示。插入元素：该功能允许用户输入要插入的元素，并把要插入的位置表示出来。同样的，系统对插入的元素有要求，当输入非法时将不能把数据写入系统。（顺序表中插入位置不能为负数。）恢复：在演示完成后如果用户想要再进行一次演示或者演示途中想重新看的时候，可以用这个功能来把数据恢复到演示之前的状态，即输入元素和插入元素之后的状态。执行：在输入

39、数据和插入元素步骤之后，可以使用该功能来进行算法的演示。它将在算法演示完成后停下来，并且有提示算法演示完成了。单步：为了教学的方便，设置了这个单步功能。它可以使程序一个语句一个语句的执行，类似看电影中的慢镜头，可以让学习者更清楚的看到程序执行的过程。它需要操作者手动点击，点击一次执行一次该功能。暂停：该功能是能够让使用者在程序执行过程中把程序停下来。对学习者尤其有用，当遇到不太了解的地方时，可以把程序停下来仔细揣摩。当想要继续演示下去时，可以点击执行来继续操作。返回：该功能是把算法演示界面返回到上一个选择界面。图形演示：在输入数据后演示模块就把数据生成一个顺序表，插入的数据在顺序表上方显示。在

40、元素移动时以闪烁的箭头表示移动方向。而后元素移动到相应位置。 这个功能是在一个系统分配固定的范围执行的，因此对要演示的数据有要求，即输入的数据长度不能超出它的范围。伪代码：伪代码是便于学习者理解算法的，它在学习中被广泛应用。本演示系统使用的伪代码和数据结构（严蔚敏）版一书很贴切，体现了为教学而制作软件的目的。在程序执行时，该伪代码以红色显示正在执行的语句，提示醒目方便学习。3.2.3 栈的递归过程汉诺塔汉诺塔演示模块设计为四个不分，因为对它的演示比对线性表的演示要复杂。它采用递归互换法来解决汉诺塔问题。功能设计如下图3-3。汉诺塔操作模块演示模块图形演示伪代码栈地址展示步骤展示返回单步暂停执行

41、恢复输入数据算法说明图3-3 汉诺塔演示模块同顺序表算法中相同功能就不重复叙述了，下面着重介绍不同的地方。输入数据：汉诺塔的输入数据是要求输入演示盘子的个数。这个数据的输入依然有限制，限制输入自然数在12以内。图形演示：汉诺塔的图形演示包括基座和盘子的显示。基座一般呈现的是倒T型图形。盘子以黑色矩形图形表示，矩形按从小到大表示盘子的顺序。步骤展示：汉诺塔演示中，当盘子数目稍多时，盘子的移动步骤是相当复杂的。这个时候仅仅观看图形的移动很可能记不清盘子到底是怎么移动的。该功能就是记录盘子的移动步骤，使用户及其对象能对照步骤加深对汉诺塔的理解。栈地址展示：该功能是展示汉诺塔演示时，代表盘子的数据在栈

42、中的地址。从表面到深入了解数据的变化。3.2.4 最短路径它与表的演示有所不同。本演示系统是使用迪杰斯特拉算法求最短路径，这个算法注重的是算法的思想。它求解从原点出发的各有向路径的从小到大的排列，但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身就不是难题了。它比表的功能多了几个：新建节点：这个同表的输入数据，但由于这是图的演示，输入数据变成了建节点。该功能允许用户在演示模块上建立节点。在创建过程中节点可以按用户心意随意移动。添加线：图的节点之间需要线来连接，这种线

43、是有向线段。连接好节点之后可以鼠标双击连线，在弹出的对话框填写权值，这个权值也是有要求的。当节点移动时，连线的连接两节点的作用并没有消失。创建结束：当节点和连线好了之后，确人不需要修改之后可以点击此键准备演示，该功能执行后，节点和权值将不能再进行修改。设置起点：该算法实际上是求出起点到各个节点的最短路径，在本小节开头已经说过，两点之间的最短路径只是这个算法的副产物。设置起点能够指定一个节点作为该部分演示的原点。设置了起点后就可以开始演示了。演示模块：这个演示界面中，矩形框架里面是图的数据。路径是起点到各个节点之间的最短路径，如果没有，则显示没有路径。3.3 本章小结 本章是对演示系统的总体规划

44、和各个功能模块的要求说明。介绍了系统的组成部分，并分模块的详细介绍了各个模块的功能要求。第4章 演示系统实现基于Windows XP操作系统的数据结构几个经典算法的演示系统是用MFC制作的，它是单文档多视图结构。本系统作为教学软件，设计时充分考虑了软件的适用性和风格，它简单易用，交互性强。本演示系统，从以下几个方面一步步达到第三章提出的设计要求：(1)主体欢迎界面(2)选择算法界面(3)顺序表演示界面(4)链表演示界面(5)汉诺塔演示界面(6)最短路径演示界面4.1 系统框架的实现该系统是基于单文档多视图结构构架的，通过发送消息来实现各个界面之间的转换。可以用添加资源功能制作一个基本的视图，然

45、后在上面加上各种控件，再对各个控件做细化处理。如下图4-1。同样的，先把所有的界面都这样的画出来，但是这样的界面都是孤立的，它们之间没有任何关系。每个单独的界面里面也没有填写程序。这只是做一个框架出来。然后就要对界面进行处理。在大多数的界面设计中，并不是所有元素都具有相同的重要性，精心设计将保证较重要的元素对用户来说处在一目了然的位置。重要的和需要经常访问的元素应当处于显著的位置，次要的元素应处于次要的位置。我们习惯的阅读顺序一般是从左到右，从上到下。可以说，用户第一看到的是屏幕的左上部分，因此，主要的元素应放在这里，而类似“确定”、“下一步”之类的按键则应处于屏幕的右下方，因为用户通常是在完

46、成了整个窗口的工作后才访问它们3。最后形成的主界面如下图4-2所示：它有一个说明和四个主按键，通过它们就可以使用到这个演示系统的全部功能。而且它的界面简单清新，也可以为以后向里面添加新的算法做好准备。图4-1添加资源图4-2是主选择界面，图4-3是第二级选择界面。它们之间的转化是通过一个消息函数来实现的。其代码如下：void CViewHello:OnBnClickedButton2()/ TODO: 在此添加控件通知处理程序代码this-GetParent()-SendMessage(WM_DLF_SHOW_VIEW,IDD_FORMVIEW_DIJKSTRA);消息发送后，系统就重画视图，

47、如图4-3视觉上的效果就是从图4-2界面转到了图4-3界面。演示系统的退出可以通过点对话框右上的来实现。 图4-2完成后的主界面图4-3最短路径选择算法界面4.2 顺序表演示模块的实现4.2.1 设计思想顺序表算法演示模块有两个部分：顺序表的插入和顺序表的删除。顺序表的算法说明：线形表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也相邻，因此，除非插入位置I的值等于表长加1（即插入表尾之后），否则都必须移动元素才能反映这个逻辑关系的变化。一般情况下，在第I（0=In?I=I+1I=1, B(I)=13=1 打印B(J) J=1, ,2n-1终止图4-10 用递归互换法实现n个盘子的移动

48、 关键代码展示演示模块的关键技术在顺序表中已经详细说明了。本演示系统在四大模块的设计上所用的关键技术都和类似，因此这里就不重复叙述这些关键技术的实现而是展示一些在汉诺塔演示模块中实现这些关键技术的部分代码。.1 绘制图形在系统分配好的动画演示区模块中，由程序把该演示区长度等分为6个部分，在奇数等分地方即1，3，5等分地方画2个矩形图形。它们在视觉效果上一个为竖直的矩形一个为横向的矩形，呈倒T状。并且把它们填充成紫色矩形块，用它们表示汉诺塔的基座x，y，z。表示盘子的图形是黑色的矩形块，它们是以紫色横向矩形块的上边为最大的盘子与基座的接触面，以竖直的紫色矩形块为柱子(以它呈对称状)而绘制的。CR

49、ect rect;CString strTemp;GetClientRect(&rect);int x = rect.right;int y = rect.bottom;/绘制矩形rect.SetRect(x/6-10, 50, x/6+10, y-50);MemDC.FillRect(rect, &newBrush);rect.SetRect(x/6-50, y-50, x/6+50, y-70);MemDC.FillRect(rect, &newBrush);rect.SetRect(x/2-10, 50, x/2+10, y-50);MemDC.FillRect(rect, &newBr

50、ush);rect.SetRect(x/2-50, y-50, x/2+50, y-70);MemDC.FillRect(rect, &newBrush);rect.SetRect(x*5/6-10, 50, x*5/6+10, y-50);MemDC.FillRect(rect, &newBrush);rect.SetRect(x*5/6-50, y-50, x*5/6+50, y-70);MemDC.FillRect(rect, &newBrush);int heigh = y - 70;int step = 4;CBrush newBrush2;newBrush2.CreateSolid

51、Brush(RGB(0,50,105);if (mpArry != NULL)for (int i=0; iATotal; i+)rect.SetRect(x/6+step*mpArry-Ai, heigh-i*10, x/6-step*mpArry-Ai, heigh-i*10-9);MemDC.FillRect(rect, &newBrush2);for (int i=0; iBTotal; i+)rect.SetRect(x/2+step*mpArry-Bi, heigh-i*10,x/2-step*mpArry-Bi,heigh-i*10-9);MemDC.FillRect(rect,

52、 &newBrush2);for (int i=0; iCTotal; i+) rect.SetRect(x*5/6+step*mpArry-Ci, heigh-i*10, x*5/6-step*mpArry-Ci, heigh-i*10-9);MemDC.FillRect(rect, &newBrush2);.2 展示伪代码前面说过，伪代码展示区是基于List Control控件构架的。设计该模块就是为了把伪代码展示给学习者观看，并且使伪代码变红显示和动画演示保持同步。for (int i=0; iCODE_LINES; i+)int line = mListSF.GetItemCount(

53、);mListSF.InsertItem(line, mExplaini);.3 恢复功能在算法演示过程中暂停，单步和演示完成状态下，用户可以把演示中变化了的数据恢复到刚输入到演示系统的状态。这个功能的实现原理是：在把数据输入到系统中时，程序自动把输入的数据备份。当使用恢复功能时，系统把备份的数据调出而实现对数据的恢复。mArry.Total = dlg.num;/保存汉诺塔的盘子数mArry.n = mArry.Total;/设置盘符(柱子)mArry.x = 1;mArry.y = 2;mArry.z = 3;mArry.ATotal = mArry.Total;/刚开始所有盘放在A柱/设

54、置多个盘子的大小for (int i=0; irectNodeMap.left)& (point.xrectNodeMap.top)& (point.yrectNodeMap.left)& (point.xrectNodeMap.top)& (point.yrectNodeMap.bottom)mNodeNum = -1;/调用函数判断鼠标所在位置是否在节点上int k = mArry.ChickNode(point.x-rectNodeMap.left, point.y-rectNodeMap.top);if (kmArry.GetNodeFactCount()/在节点上，把节点编号保存在这

55、里mNodeNum = k;if (AddLineFlage = 1)/添加线状态mLineNum = mArry.AddLine(mNodeNum); /判断鼠标位置是否在节点上if (mLineNum = -1)/不在节点上，弹出消息MessageBox(无法连线，请先点中节点！);AddLineFlage = 0;SetStatus(Inition);4.5.4 成品展示画图区是为输入数据做准备的。这个部分主要是能识别鼠标的信息。画图的很多地方都要通过鼠标来实现。当点击新建节点时，激活了画图区的识别功能。鼠标在画图区点击左键时，程序在这个点画出一个圆点，并在上面标志为A，以此来表示节点的

56、顺序。已经画了一个节点之后，鼠标点在这个上面不放时，程序相应部分得以激活，这时可以在画图区拖动该节点移动到想要移动到的位置。连线的实现符合大多软件的习惯。在连接两个节点时，点击一个节点不放移动鼠标，到达到另外一个节点时松开，连线就成立了。并且以有箭头指向连线方向。如果点击一个节点开始并不放鼠标左键移动到一个没有节点的位置时放开鼠标，连线将不能被创建。这样就保证了每条连线的可靠性。在靠近箭头的位置上，每条连线都有一个小圆圈。这个圆圈是设置权值的标志位置，在鼠标双击该圆圈时，将会弹出一个对话框，在这个对话框输入该条路径的权值。在这些信息输入同时，画图区右边的矩阵显示出各节点之间路径的权值。其中负值

57、1表示没有路径。这些如下图4-16。图4-16 带权有向图G6的演示界面迪杰斯特拉算法求的是一个节点到其他各个节点间的最短路径。因此，演示前，要设置一个起点。设置起点是由一个对话框实现的。在弹出的对话框输入起点起点的标志符号。例如设置A节点为起点。在对话框中输入大写字母A。在设置完起点后，对演示的准备就完成了。可以点击执行来演示该算法。演示中会把该起点到其他各个节点的最短路径在演示界面的左下方位置展示出来。有向图G6的演示结果如下图4-17。图4-17向图G6的演示结果4.6 系统模块间的联系该演示系统是应用模块化思想构建的。每个模块和总体框架都有其相似点。对一个系统的设计，一致性应该保持。这

58、个前面已经说过这样设计软件的优点了。在该系统中，每个二级界面返回主欢迎界面所用的消息函数是一样的。这是系统设计上的一致性。各个演示模块所用背景图片一致。这样给用户心理上带来熟悉感。每个模块演示完成时都会弹出显示“演示完成”的对话框。4.7 本章小结 本章详细的说明了数据结构几个经典算法演示系统的各个功能模块的实现思想与方法。以各种完成后的作品的截图来说明系统达到的目标。并且介绍了在设计软件中的一些优秀思想。第5章 结论在本次毕业设计的过程中，通过指导老师的耐心指导和自身的学习及努力，对数据结构知识和教学软件有了进一步的提高。在整个设计过程中深深地体会到要把所学的知识理论变成可实际应用的系统时所

59、面临的种种困难，认识到提高运用知识、解决实际问题的能力是十分重要的。在该软件的设计与实现过程中，有几个方面是关键。首先是系统界面的清新简单和各个模块设计的一致性。其次是为教学效果而完成的一些功能的实现，比如对单步执行程序的设计。再次，作为一个教学软件，该系统所演示的几个经典算法是不够的，为了以后能够添加其他的算法演示，采用模块化设计思想。在设计和实现的过程中，遇到不少问题。在老师帮助指导和本人努力下，本课题所涉及的难题都已经基本解决，满足本次毕业设计的要求。本演示系统作为一个多媒体动态教学演示课件，在毕业设计过程中完成的部分还有欠缺。但由于找工作和时间的紧缺，一些设想并没有去实现。如在算法演示

60、过程中播放适当的音乐显然也能提高学生的学习兴趣，以及为更适合不同的使用者而应该设计的演示速度模块。这些设想有待以后再实现。关于本次毕业设计，由于设计经验的不足和所掌握知识的限制，该演示系统虽然已经能实现对一些算法很好的演示，但在某些方面还有更加优秀的演示方法、某些功能设计构想还没有完整的表达出来。通过本次设计的学习和实践，对理论知识的认识有了进一步的加强，实践能力和独立思考的能力都得到了提高，这是在书本上所学不到的。这次毕业设计过程中所积累的经验将为本人在今后工作岗位上发挥自己的才能奠定坚实的基础。致谢本课题在选题及研究过程中得到老师的悉心指导。他们多次询问研究进程，并为我指点迷津，帮助我开拓