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

《数据结构经典算法演示系统论文》由会员分享，可在线阅读，更多相关《数据结构经典算法演示系统论文（45页珍藏版）》请在装配图网上搜索。

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目录摘要IABSTRACTII第1

5、章 绪论11.1 开发演示系统的背景11.2 数据结构经典算法演示系统的研究内容21.3 开发该系统的可行性21.4 演示系统在教学中的优点3第2章 系统概述及开发工具42.1 演示系统设计要求42.2演示系统的需求分析42.2.1 应用对象52.2.2 应用环境52.2.3 任务分析52.3 演示系统总体规划62.3.1 开发过程应遵循的要求62.3.2 系统组成72.3.3 功能要求72.4 选用MFC进行系统开发82.5 本章小结9第3章 演示系统设计103.1 系统组成103.2 各个功能模块的要求113.2.1 主界面功能要求113.2.2 表与栈113.2.3 栈的递归过程汉诺塔1

6、23.2.4 最短路径133.3 本章小结14第4章 演示系统实现154.1 系统框架的实现154.2 顺序表演示模块的实现174.2.1 设计思想174.2.2 算法演示流程图184.2.3 关键技术的实现184.3 链表演示模块的实现214.3.1 设计思想214.3.2 成品展示214.4 汉诺塔演示模块的实现224.4.1 设计思想224.4.2 用递归互换法解决汉诺塔问题的流程图244.4.3 关键代码展示254.4.4 成品展示284.5 最短路径演示模块的实现304.5.1 设计思想304.5.2 算法演示流程图324.5.3 关键代码展示334.5.4 成品展示354.6 系统

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

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

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

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

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

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

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

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

15、，策略性的作用，他在软件开发的过程中具有举足轻重的地位。大家一定要对需求分析具有足够的重视。在一个大型软件系统的开发中，它的作用要远远大于程序代码的编写。 应用对象在第一章已经讲过的数据结构教学中的困难中可以看出，教学活动需要注入新活力，使用演示系统辅助教学是很好的选择，也就是说它有应用前景，由老师利用该演示系统指导学生学习数据结构或者学生利用该演示系统自主复习数据结构。它的应用对象是学习数据结构的学生。数据结构的概念晦涩难懂，尤其是在当今学生学习主动性不是很好的环境下，学生就很难掌握该课程了。有的时候直观的演示可能比详尽的概念解释更易让学生学习到知识。数据结构几个经典算法的演示系统大致能满足

16、教师授课的需要，给学生以直观的教学印象，让学生清楚的知道数据怎么变化的，调动学生学习的积极性。不过该系统不是完善的，只有有限的几个算法演示。开发该系统只希望能起到抛砖引玉的作用，给学生带来一定的启发。 应用环境开发该演示系统的目的是为了在教学中引入新的教学手段，调动学生学习积极性，提供教师授课的方便。该系统的是在Windows XP操作系统下实现的，这样符合大多数教学所用的计算机所采用的系统，方便软件在不同计算机之间的转移。它可以是教师使用或者学生使用，软件界面的简单使得不同知识层次的人使用起来不会有麻烦。 任务分析使用该演示系统是为了促进学生对数据结构课程的理解，提高数据结构课程的教学质量。

17、在现代化的教学过程中，由于多媒体辅助教学能够化静为动，寓教于乐，培养和激发学生的学习兴趣；能使抽象问题形象化，便于学生对知识点的理解和运用；能节约传统的板书时间，开阔知识面，增加信息量，提高学习效率，所以这种教学手段被广泛采用。但是滥用多媒体辅助教学，不但不能达到预期的教学效果，反而会分散学生的注意力，削弱了教师在教学过程中应起的主导作用，甚至影响学生的学习积极性。因此要注意怎么使用软件。虽然教学课件已经事先做好，但不是说在课堂上教师只要在教师用机的位置上单纯地“演示”课件就可以了，这样可能会出现学生看了很多，听了很多，却不知道要学什么，而事与愿违。其实，多媒体辅助教学作为一种现代化的教学手段

18、，是用来提高课堂教学的效率、突破重点难点、解决一些传统教学不易解决的问题。教师应该凭自身丰富的教学经验和生动的讲解，通过师生间的情绪感染，来调动学生学习的积极性，并使学生能够自觉的参与到新的教学当中去。另外，事先做好的课件灵活性可能较差，有时会限制教师的临场发挥，这时就要求教师应积极有效地利用投影仪等现代媒体辅助教学，来解决这个矛盾。2.3 演示系统总体规划 开发过程应遵循的要求（1）符合一般环境需求。可视化软件的系统平台必须符合学生一般常接触的环境。现在常见到的不外乎是Java Applet和应用软件。对于Java Applet而言，是属于客户机/ 服务器架构。学生必须经由网络的连接，将需求

19、传送至服务器端，然后才能执行。如此，对于缺乏网络或网络不顺畅的教学环境而言，就容易受到限制。对于应用软件而言，要求系统简洁，小巧便于移动。（2）界面设计的便利性。在有限时间内，学生不应花费太多的时间去摸索复杂困难的学生界面。所以在接口设计上，必须以学生操作方便为原则。（3）提供学生输入数据。当学生初次使用可视化软件时，系统必须告知其所接受的数据形态和范围。如利用系统自行产生数据的功能，让学生便于执行算法。如此可以鼓励学生主动去探索各种情况下算法的执行效率。（4）学生控制。不同的学生，其吸收知识的速度不一定相同。因而，让学生自行掌握学习的速度是有必要的。在可视化软件中可提供调整动画执行过程的延迟

20、时间，或是利用单步执行按键，让学生自行控制学习速度。此外还原键也是让学生往回追溯不懂之处的重要按键之一。（5）算法的全貌浏览。当学生想快速观看算法的部分片段时，提供快速执行功能是有其必要性的。学生可直接执行算法的某一时点，或大略观看演算法的执行全貌。（6）提供伪码的对照。单纯展示算法执行过程，只能让学生在算法程序上有所了解。若要让学生在概念上更加清楚，则提供算法的伪码是一个好方法。（7）相关辅助信息。例如对于不熟悉算法的学生而言，可提供相关的背景数据与算法所要达成的目标。2.3.2 系统组成演示系统包含教五个教学单元：顺序表的插入和删除、链表的插入、栈的递归过程汉诺塔、最短路径。每个单元的内容

21、相互独立，并由主菜单调入。每个单元都有各自的功能，可由主菜单进入各个独立单元。系统的总体框架如下图2-2。顺序表链表栈最短路径插入删除插入汉诺塔迪杰斯特拉欢迎界面图2-2 演示系统总体框架2.3.3 功能要求（1）用动态图形对数据结构中如: 线形表的插入删除算法、汉诺塔及最短路径问题进行了形象直观、准确生动的演示。能够很好地帮助学生深入理解算法，有利于培养学生的抽象能力；（2）系统控制能力强, 具有暂停、重复和恢复等功能；（3）良好的操作界面, 同时支持键盘和鼠标, 操作简单。菜单提示, 可点对象醒目；（4）软件脚本根据由严蔚敏编著的国优教材数据结构一书编写的。内容编排合理, 教学功能强；（5

22、）交互性强。系统中使用的大部分参数可由使用者自行设置。学习内容及学习进度也可由使用者自行选择；（6）系统采用模块化结构, 可维护性强。2.4 选用MFC进行系统开发该演示系统使用了大量的视图界面作为演示系统的操作界面，而且演示系统为了用户的使用方便采取的是基于对话框的结构构架，利用微软基本类库MFC（Microsoft Foundation Class）能够很好的开发出符合这种需要的软件，因此选择使用MFC以及Visual C+开发系统来编写自己的基于Windows 的应用程序。MFC提供了很多的图形控件，可以比较方便的设计出算法演示系统的界面。MFC是微软为Windows 程序员提供的一个面

23、向对象的Windows 编程接口, 它大大简化了Windows 编程工作。该层次结构包容了Windows API 中的用户界面部分, 并使程序员能够很容易地以面向对象的方式建立Windows 应用程序。这种层次结构适用于所有版本的Windows , 并彼此兼容。基础类库的核心是以C + + 形式封装了大部分的Windows API。类库表示窗口, 对话框, 设备上下文, 公共GDI 对象如画笔、调色板、控制框和其他标准的Windows 部件。这些类提供了一个面向Windows 中结构的简单的C + + 成员函数的接口。MFC的本质就是一个包含了许多微软公司已经定义好的对象的类库，我们知道，虽然

24、我们要编写的程序在功能上是千差万别的，但从本质上来讲，都可以化归为用户界面的设计，对文件的操作，多媒体的使用，数据库的访问等等一些最主要的方面。这一点正是微软提供MFC类库最重要的原因，在这个类库中包含了一百多个程序开发过程中最常用到的对象。在进行程序设计的时候，如果类库中的某个对象能完成所需要的功能，这时我们只要简单地调用已有对象的方法就可以了。我们还可以利用面向对象技术中很重要的“继承”方法从类库中的已有对象派生出我们自己的对象，这时派生出来的对象除了具有类库中的对象的特性和功能之外，还可以由我们自己根据需要加上所需的特性和方法，产生一个更专门的，功能更为强大的对象。当然，你也可以在程序中

25、创建全新的对象，并根据需要不断完善对象的功能。正是由于MFC编程方法充分利用了面向对象技术的优点，它使得我们编程时极少需要关心对象方法的实现细节，同时类库中的各种对象的强大功能足以完成我们程序中的绝大部分所需功能，这使得应用程序中程序员所需要编写的代码大为减少，有力地保证了程序的良好的可调试性。最后要指出的是MFC类库在提供的对象的各种属性和方法都是经过谨慎的编写和严格的测试，可靠性很高，这就保证了使用MFC类库不会影响程序的可靠性和正确性。2.5 本章小结本章是对系统的概述以及开发工具的介绍。详细说明了系统的需求分析。系统是在Windows XP系统下使用MFC构架的，并说明了使用MFC构架

26、系统的优越性。第3章 演示系统设计一个好的计算机应用软件，都是经过程序员冷静的思考，详尽的分析而产生的。设计远比编程重要。设计的过程就是将事务处理抽象成计算机模型的过程。本章详细的介绍演示系统的系统组成与各个功能模块的要求。3.1 系统组成该演示系统是几个经典数据结构算法的演示系统。这几个经典算法分别是顺序表的插入、删除算法，链表的插入算法，栈的递归过程中的汉诺塔，使用迪杰斯特拉算法求最短路径。系统设计图如下图3-1所示。由图3-1可以看到，系统设计是采用模块化思想，这样每个算法之间都是独立的，便于系统维护，也便于以后再向里面添加新的算法。每个算法演示下面都有其详细的操作界面。以顺序表插入为例

27、子，它的具体设计思想如下图3-2所示。其他各个算法的演示大致和顺序表插入算法相同，有方便的操作，动态的图形演示和跟随程序运行的伪代码。欢迎界面线性表链表栈最短路径顺序表插入顺序表删除返回链表删除返回汉诺塔返回最短路径返回图3-1演示系统总体设计顺序表的插入操作模块演示模块算法说明图形演示伪代码暂停返回单步执行恢复插入元素输入数据图3-2顺序表插入算法演示模块3.2 各个功能模块的要求3.2.1 主界面功能要求主界面是一个选择界面，它们的功能是转到下一个界面。(1)顺序表:它的作用是转到顺序表插入删除算法选择界面。(2)链表:它的作用是转到链表插入算法选择界面。(3)栈:它的作用是转到汉诺塔算法

28、选择界面。(4)最短路径:它的作用是转到迪杰斯特拉算法选择界面。二级界面同样是一个选择界面，它们的功能是转到相应算法演示界面。它们的要求如附录。3.2.2 表与栈该演示系统演示算法中有关表的演示有两个：顺序表和链表。它们都是数据结构课程的基本知识，在实际中也有很广的用途。算法说明：对演示算法的说明，该系统的教学对象对算法概念不清楚时可以查看，或者让初学者知道该算法是怎么样的。因此算法说明应该能清楚的表明算法的思想。输入数据：输入数据就是向系统中写入数据，为演示做好准备。输入数据时弹出一个对话框，在指定地方输入数据，并且有说明什么样的数据是系统允许的。输入非法数据时系统将不能接受或者弹出错误提示

29、。插入元素：该功能允许用户输入要插入的元素，并把要插入的位置表示出来。同样的，系统对插入的元素有要求，当输入非法时将不能把数据写入系统。（顺序表中插入位置不能为负数。）恢复：在演示完成后如果用户想要再进行一次演示或者演示途中想重新看的时候，可以用这个功能来把数据恢复到演示之前的状态，即输入元素和插入元素之后的状态。执行：在输入数据和插入元素步骤之后，可以使用该功能来进行算法的演示。它将在算法演示完成后停下来，并且有提示算法演示完成了。单步：为了教学的方便，设置了这个单步功能。它可以使程序一个语句一个语句的执行，类似看电影中的慢镜头，可以让学习者更清楚的看到程序执行的过程。它需要操作者手动点击，

30、点击一次执行一次该功能。暂停：该功能是能够让使用者在程序执行过程中把程序停下来。对学习者尤其有用，当遇到不太了解的地方时，可以把程序停下来仔细揣摩。当想要继续演示下去时，可以点击执行来继续操作。返回：该功能是把算法演示界面返回到上一个选择界面。图形演示：在输入数据后演示模块就把数据生成一个顺序表，插入的数据在顺序表上方显示。在元素移动时以闪烁的箭头表示移动方向。而后元素移动到相应位置。 这个功能是在一个系统分配固定的范围执行的，因此对要演示的数据有要求，即输入的数据长度不能超出它的范围。伪代码：伪代码是便于学习者理解算法的，它在学习中被广泛应用。本演示系统使用的伪代码和数据结构（严蔚敏）版一书

31、很贴切，体现了为教学而制作软件的目的。在程序执行时，该伪代码以红色显示正在执行的语句，提示醒目方便学习。3.2.3 栈的递归过程汉诺塔汉诺塔演示模块设计为四个不分，因为对它的演示比对线性表的演示要复杂。它采用递归互换法来解决汉诺塔问题。功能设计如下图3-3。汉诺塔操作模块演示模块图形演示伪代码栈地址展示步骤展示返回单步暂停执行恢复输入数据算法说明图3-3 汉诺塔演示模块同顺序表算法中相同功能就不重复叙述了，下面着重介绍不同的地方。输入数据：汉诺塔的输入数据是要求输入演示盘子的个数。这个数据的输入依然有限制，限制输入自然数在12以内。图形演示：汉诺塔的图形演示包括基座和盘子的显示。基座一般呈现的

32、是倒T型图形。盘子以黑色矩形图形表示，矩形按从小到大表示盘子的顺序。步骤展示：汉诺塔演示中，当盘子数目稍多时，盘子的移动步骤是相当复杂的。这个时候仅仅观看图形的移动很可能记不清盘子到底是怎么移动的。该功能就是记录盘子的移动步骤，使用户及其对象能对照步骤加深对汉诺塔的理解。栈地址展示：该功能是展示汉诺塔演示时，代表盘子的数据在栈中的地址。从表面到深入了解数据的变化。3.2.4 最短路径它与表的演示有所不同。本演示系统是使用迪杰斯特拉算法求最短路径，这个算法注重的是算法的思想。它求解从原点出发的各有向路径的从小到大的排列，但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对

33、于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身就不是难题了。它比表的功能多了几个：新建节点：这个同表的输入数据，但由于这是图的演示，输入数据变成了建节点。该功能允许用户在演示模块上建立节点。在创建过程中节点可以按用户心意随意移动。添加线：图的节点之间需要线来连接，这种线是有向线段。连接好节点之后可以鼠标双击连线，在弹出的对话框填写权值，这个权值也是有要求的。当节点移动时，连线的连接两节点的作用并没有消失。创建结束：当节点和连线好了之后，确人不需要修改之后可以点击此键准备演示，该功能执行后，节点和权值将不能再进行修改。设置起点：该算法实际

34、上是求出起点到各个节点的最短路径，在本小节开头已经说过，两点之间的最短路径只是这个算法的副产物。设置起点能够指定一个节点作为该部分演示的原点。设置了起点后就可以开始演示了。演示模块：这个演示界面中，矩形框架里面是图的数据。路径是起点到各个节点之间的最短路径，如果没有，则显示没有路径。3.3 本章小结 本章是对演示系统的总体规划和各个功能模块的要求说明。介绍了系统的组成部分，并分模块的详细介绍了各个模块的功能要求。第4章 演示系统实现基于Windows XP操作系统的数据结构几个经典算法的演示系统是用MFC制作的，它是单文档多视图结构。本系统作为教学软件，设计时充分考虑了软件的适用性和风格，它简

35、单易用，交互性强。本演示系统，从以下几个方面一步步达到第三章提出的设计要求：(1)主体欢迎界面(2)选择算法界面(3)顺序表演示界面(4)链表演示界面(5)汉诺塔演示界面(6)最短路径演示界面4.1 系统框架的实现该系统是基于单文档多视图结构构架的，通过发送消息来实现各个界面之间的转换。可以用添加资源功能制作一个基本的视图，然后在上面加上各种控件，再对各个控件做细化处理。如下图4-1。同样的，先把所有的界面都这样的画出来，但是这样的界面都是孤立的，它们之间没有任何关系。每个单独的界面里面也没有填写程序。这只是做一个框架出来。然后就要对界面进行处理。在大多数的界面设计中，并不是所有元素都具有相同

36、的重要性，精心设计将保证较重要的元素对用户来说处在一目了然的位置。重要的和需要经常访问的元素应当处于显著的位置，次要的元素应处于次要的位置。我们习惯的阅读顺序一般是从左到右，从上到下。可以说，用户第一看到的是屏幕的左上部分，因此，主要的元素应放在这里，而类似“确定”、“下一步”之类的按键则应处于屏幕的右下方，因为用户通常是在完成了整个窗口的工作后才访问它们3。最后形成的主界面如下图4-2所示：它有一个说明和四个主按键，通过它们就可以使用到这个演示系统的全部功能。而且它的界面简单清新，也可以为以后向里面添加新的算法做好准备。图4-1添加资源图4-2是主选择界面，图4-3是第二级选择界面。它们之间

37、的转化是通过一个消息函数来实现的。其代码如下：void CViewHello:OnBnClickedButton2()/ TODO: 在此添加控件通知处理程序代码this-GetParent()-SendMessage(WM_DLF_SHOW_VIEW,IDD_FORMVIEW_DIJKSTRA);消息发送后，系统就重画视图，如图4-3视觉上的效果就是从图4-2界面转到了图4-3界面。演示系统的退出可以通过点对话框右上的来实现。 图4-2完成后的主界面图4-3最短路径选择算法界面4.2 顺序表演示模块的实现4.2.1 设计思想顺序表算法演示模块有两个部分：顺序表的插入和顺序表的删除。顺序表的算

38、法说明：线形表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也相邻，因此，除非插入位置I的值等于表长加1（即插入表尾之后），否则都必须移动元素才能反映这个逻辑关系的变化。一般情况下，在第I（0=In?I=I+1I=1, B(I)=13=1 打印B(J) J=1, ,2n-1终止图4-10 用递归互换法实现n个盘子的移动 关键代码展示演示模块的关键技术在顺序表中已经详细说明了。本演示系统在四大模块的设计上所用的关键技术都和类似，因此这里就不重复叙述这些关键技术的实现而是展示一些在汉诺塔演示模块中实现这些关键技术的部分代码。.1 绘制图形在系统分配好的动画演示区模块中，由程序把该演示区长度

39、等分为6个部分，在奇数等分地方即1，3，5等分地方画2个矩形图形。它们在视觉效果上一个为竖直的矩形一个为横向的矩形，呈倒T状。并且把它们填充成紫色矩形块，用它们表示汉诺塔的基座x，y，z。表示盘子的图形是黑色的矩形块，它们是以紫色横向矩形块的上边为最大的盘子与基座的接触面，以竖直的紫色矩形块为柱子(以它呈对称状)而绘制的。CRect 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.F

40、illRect(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, &newBrush);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(

41、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.CreateSolidBrush(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-

42、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, &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.FillRec

43、t(rect, &newBrush2);.2 展示伪代码前面说过，伪代码展示区是基于List Control控件构架的。设计该模块就是为了把伪代码展示给学习者观看，并且使伪代码变红显示和动画演示保持同步。for (int i=0; iCODE_LINES; i+)int line = mListSF.GetItemCount();mListSF.InsertItem(line, mExplaini);.3 恢复功能在算法演示过程中暂停，单步和演示完成状态下，用户可以把演示中变化了的数据恢复到刚输入到演示系统的状态。这个功能的实现原理是：在把数据输入到系统中时，程序自动把输入的数据备份。当使用恢

44、复功能时，系统把备份的数据调出而实现对数据的恢复。mArry.Total = dlg.num;/保存汉诺塔的盘子数mArry.n = mArry.Total;/设置盘符(柱子)mArry.x = 1;mArry.y = 2;mArry.z = 3;mArry.ATotal = mArry.Total;/刚开始所有盘放在A柱/设置多个盘子的大小for (int i=0; imArry.ATotal; i+)mArry.AmArry.ATotal-1-i = i+1;/备份数据mArry1 = mArry;mDoLine = -1;void CViewHanoi:OnBnClickedButton

45、Resume()/ TODO: 在此添加控件通知处理程序代码/恢复数据mArry = mArry1;/把当前行变为黑色mListSF.SetItemColor(mDoLine/*行*/,(DWORD)RGB(0,0,0)/*颜色*/);mDoLine = -1;SetStatus(Inition); 成品展示汉诺塔演示界面分功能按键区和四个演示图块区。同其他设计的界面保持一致，整个演示界面的最上面放置功能按键。在按键的左下是醒目的图形演示区。以三个紫色倒T图形表示三个基座。以黑色矩形表示汉诺塔演示的盘子。矩形按顺序从小到大表示盘子。如图4-11和图4-12。图4-11 原始汉诺塔演示界面前面已

46、经说过，汉诺塔的盘子数目过多时移动它的所需的时间将达到一个不可能接受的程度。因此本模块为了演示方便对盘子数目做了限制，限定为12个盘子。以四个盘子移动为例展示该模块的实现。如下图所示，在第一个基座上，有四个从上到下依次变大的黑色矩形表示的盘子。图4-12 放置四个盘子的汉诺塔演示开始执行演示后，图形演示区显示盘子的移动，右边展示汉诺塔的伪代码，这样便于理解汉诺塔的盘子移动问题。界面左下显示盘子移动的具体步骤，右下显示汉诺塔问题用栈的递归的办法来解决的入栈地址。如图4-13。图4-13 四个盘子的汉诺塔演示过程 演示完成后，在步骤显示区有具体的盘子移动步骤，使用者可以对照该步骤回顾汉诺塔问题解决

47、的过程，达到教学目的。如图4-14。图4-14 四个盘子汉诺塔演示完成后的界面4.5 最短路径演示模块的实现求两点间的最短路径是一个很经典的问题。本演示系统是用DIJKSTRA算法来求最短路径的。最短路径不仅仅指一般意义上的距离最短, 诸如时间、费用都可被引申为最短路径。相应地, 最短路径问题就成为最快路径问题、最低费用问题等。4.5.1 设计思想该演示模块是要实现对有向带权图的最短路径的演示。这个模块对图形输入设计要求很高。该演示模块同汉诺塔演示模块一样，分为四个演示区。但是算法演示的不同导致了演示模块布局的不同。整个演示区先分为两大块，图形演示块和伪代码演示块。它们一左一右占据演示区给人醒目的感觉。图形演示区又横向分成上下两大块。下面的演示区是用来展示原点到其它各个节点的最短路径。上面的演示区继续分成两块，左边是对图形的输入。右边是对应图形数据的矩阵。其中图形输入区的难度最高。它要求输入数据生成一幅有向图，图形节点能在绘图区任意移动，有向线(路径)连接两个节点，不管节点怎么移动它们的关系保持不变。有向线上面要能够标注权值。下面就分四个部分详细介绍对各个图形演示区的设计思想。.1 绘制图形区绘制图形是通过鼠标的各种操作和适当的键盘操作来实现的，因此该模块要能够识别鼠标的各种操作信息，并执行用户希望的操作。设计