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

I 摘要摘要 本文所涉及的应用程序作为多媒体课堂教学的辅助工具 为数据结构课程的 算法演示课件 旨在增加课堂教学手段的多样性和教学的生动性 本软件是为了丰富课堂教学手段 提高数据结构教学质量而开发的 它包括 数据结构一书中的几个经典算法 是在 Microsoft Visual C 2003 环境下开发的 它为数据结构课程中几个经典算法提供一种形象的动画表达方式 本文从总体出 发 逐步细化 介绍了该软件的设计 开发的基本情况 并带有相应的截图和一 些典型源代码 以方便说明和理解 关键词 多媒体课件 数据结构课程 VC II ABSTRACT The application program referred in this paper is an assistant implement for multimedia class It s 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 more 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 It s begun with collectivity 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 III 目录目录 摘要 I ABSTRACT II 第 1 章 绪论 1 1 1 开发演示系统的背景 1 1 2 数据结构经典算法演示系统的研究内容 2 1 3 开发该系统的可行性 2 1 4 演示系统在教学中的优点 3 第 2 章 系统概述及开发工具 4 2 1 演示系统设计要求 4 2 2 演示系统的需求分析 4 2 2 1 应用对象 5 2 2 2 应用环境 5 2 2 3 任务分析 5 2 3 演示系统总体规划 6 2 3 1 开发过程应遵循的要求 6 2 3 2 系统组成 7 2 3 3 功能要求 7 2 4 选用 MFC 进行系统开发 8 2 5 本章小结 9 第 3 章 演示系统设计 10 3 1 系统组成 10 3 2 各个功能模块的要求 11 3 2 1 主界面功能要求 11 3 2 2 表与栈 11 3 2 3 栈的递归过程汉诺塔 12 3 2 4 最短路径 13 3 3 本章小结 14 第 4 章 演示系统实现 15 IV 4 1 系统框架的实现 15 4 2 顺序表演示模块的实现 17 4 2 1 设计思想 17 4 2 2 算法演示流程图 18 4 2 3 关键技术的实现 18 4 3 链表演示模块的实现 21 4 3 1 设计思想 21 4 3 2 成品展示 21 4 4 汉诺塔演示模块的实现 22 4 4 1 设计思想 22 4 4 2 用递归互换法解决汉诺塔问题的流程图 24 4 4 3 关键代码展示 25 4 4 4 成品展示 28 4 5 最短路径演示模块的实现 30 4 5 1 设计思想 30 4 5 2 算法演示流程图 32 4 5 3 关键代码展示 33 4 5 4 成品展示 35 4 6 系统模块间的联系 37 4 7 本章小结 37 第 5 章 结论 38 致谢 39 参考文献 40 附录 41 1 第第 1 章章 绪论绪论 数据结构是计算机科学与技术专业的核心基础课程之一 但是它概念抽象 算法枯涩难懂 难以提起学生的学习兴趣 如何有效的让学生掌握该课程是一个 值得研究的问题 计算机辅助教学 CAI 作为一种先进的教学手段正逐步渗透 到各类学校的各个学科 多媒体技术给 CAI 注入了新的活力 由于多媒体技术能 够综合处理文本 图像 动画 音频 视频等多种媒体 并通过视觉 听觉对人 体产生多重感官刺激 从而使学生在较短的时间内获得较多的信息量 本文重点 介绍如何用 MFC 开发的几个数据结构经典算法的演示系统 下文简称为演示系统 并讨论实现中的一些关键技术 1 1 开发演示系统的背景开发演示系统的背景 数据结构是计算机相关专业的一门重要的专业基础课 它主要研究计算机加 工对象的逻辑结构 数据在计算机中的表示形式以及实现各种基本操作的算法 该课程在计算机科学与技术的专业教学中的地位可用四个词概括 核心 基础 纽带 桥梁 核心 即指这门课在计算机专业中占有非常重要的地位 是一门核心基础 课 数据是计算机处理的对象 使用计算机就是对数据进行加工处理的过程 因 而数据的组织与结构被确立为计算机科学中最为基本的内容 数据结构课程以问 题求解方法 程序设计方法及一些典型的数据结构算法为研究对象 要求学生学 会分析数据对象特征 掌握数据组织方法和计算机的表示方法 为数据选择适当 的逻辑结构 存储结构以及相应的处理算法 培养学生良好的程序设计风格 因 而数据结构课程是计算机专业的一门核心课程 基础 指该课程为后续多门计算机专业课提供了必要的基础 如操作系统 数据库原理 编译原理 算法分析与设计 软件工程 计算机网络 人工智能等 都需要数据结构作为课程的基础 同时这门课又是横贯数学与计算机 计算机硬 件与软件并将数学与计算机 计算机软件与硬件有机的融合在一起的一门学科 是将计算机理论与上机实践融合在一起的一门学科 是它们之间的 纽带 没 有它作为基础 后继大部分课程将不能展开 也就是说 这门课程是通往其它课 程的一座 桥梁 2 因此大力加强数据结构课程的建设 提高数据结构课程的教学质量 有利于 教学改革和教育创新 有利于创新人才的培养 努力提高数据结构课程的教学质 量 对于新一轮的以创新教育和素质教育为主要内容的教学改革将起到积极的推 进和示范作用 1 2 数据结构经典算法演示系统的数据结构经典算法演示系统的研究内容研究内容 为了适应课堂教学的要求 数据结构经典算法演示系统应该具有 1 软件界面的设计要求 较强的交互能力 动态的算法演示 形象的图 形设计 充分应用声音和色彩体现算法的细节 屏幕设计简洁明快 屏幕元素布 局合理 突出教学内容的重点等等 2 软件中不仅包含主要的教学内容 而且还应提供一些特殊例题的算法 演示 用以扩大学生的编程思维能力 从而实现用形象的图形界面为学生搭起通 向掌握抽象思维方法的桥梁 3 软件中通过图形演绎出来的所有算法思想必须准确 4 操作简单 易于理解 符合 Windows 的操作规则 便于使用 5 软件在设计开发过程中具有自身的规范 而对于教学软件来说 设计 开发者应该在遵循一般规范的基础上 深入研究学与教的原理 在有关科学理论 指导下设计开发教学软件 1 3 开发该系统的可行性开发该系统的可行性 传统教学模式注重基础知识理论的掌握 用大量的时问讲定义 语法 概念 语句 对学生的要求是注重接受 理解 记忆 讲课方式是老师讲 学生听 学 生掌握的知识比较抽象 机械 静止 片面和孤立 缺乏创造性 严重影响了学 生就业和个人发展 因此使当前的大学生具备扎实基础知识的同时又具备解决实 际问题 批判性思维和创造性思维 发展合作能力与自主学习能力 是目前急待 解决的问题 也是人们进行教学改革的思路 在教学过程中的具体做法是 开 始上课时演示一个精心设计的 吸引学生注意并包含当天上课新内容的运行结 果 这个过程实际上也就是向学生提出了一个新的问题 给学生一定的时间去思 考 然后在讲授 或者是留下问题让同学们在课下去想办法解决然后在上机时实 现 这样一步一步地分析问题解决问题拓展问题有助于促进学生创造性思维的形 3 成 1 4 演示系统在教学中的优点演示系统在教学中的优点 1 可视化教学软件不像教材那样枯燥乏味 教师可以利用它来吸引学生 的注意力 2 可视化教学软件可将文字 数据 图片 影片动态地整合在一起 3 可视化教学软件可以让学生体会在大量不同的数据结构下 算法执行 效率的差异 4 学生在课后可利用可视化教学软件探索算法的执行过程 提高学生个 别化学习能力 5 加强刺激 加深印象 4 第第 2 章章 系统概述及开发工具系统概述及开发工具 数据结构几个经典算法的演示系统作为一个教学软件 要求界面清新简单 可操作性强 与使用者的操作系统兼容性强 本软件是在 Windows XP 操作系统 下用 MFC 开发的 可在装有 VC 2003 版 的使用 Windows XP 操作系统的 电脑上使用 2 1 演示系统设计要求演示系统设计要求 算法演示软件服务于教学目的 其设计目标是通过演示以最大限度地帮助学 习者理解算法 并掌握其实质 演示内容包括 程序的运行过程 数据结构的变 化及一些动态结果 其是一个可视化软件 开发数据结构几个经典算法的演示系统的过程包括五个基本的步骤 需求分 析 设计 制作 成品使用 评价和修改 其工作流程如图 2 1 所示 设设 计计 教学目标 教学内容 教学策略 结构设计 脚本编写 制制 作作 工具选择 素材准备 开发实施 成成 品品 使使 用用 需求分析需求分析 应用对象 应用环境 任务分析 图图 2 1 数据结构几个经典算法演示系统的开发过程数据结构几个经典算法演示系统的开发过程 2 2 演示系统的需求分析演示系统的需求分析 需求分析就是分析软件用户的需求是什么 如果投入大量的人力 物力 财 力和时间开发出的软件却没人要 那所有的投入都是徒劳 如果费了很大的精力 开发一个软件 最后却不满足用户的要求 从而要重新开发过 这种返工是让人 痛心疾首的 需求分析之所以重要 就因为他具有决策性 方向性 策略性的作 用 他在软件开发的过程中具有举足轻重的地位 大家一定要对需求分析具有足 够的重视 在一个大型软件系统的开发中 它的作用要远远大于程序代码的编写 评评 价价 和和 修修 改改 5 2 2 1 应用对象应用对象 在第一章已经讲过的数据结构教学中的困难中可以看出 教学活动需要注入 新活力 使用演示系统辅助教学是很好的选择 也就是说它有应用前景 由老师 利用该演示系统指导学生学习数据结构或者学生利用该演示系统自主复习数据结 构 它的应用对象是学习数据结构的学生 数据结构的概念晦涩难懂 尤其是在当今学生学习主动性不是很好的环境下 学生就很难掌握该课程了 有的时候直观的演示可能比详尽的概念解释更易让学 生学习到知识 数据结构几个经典算法的演示系统大致能满足教师授课的需要 给学生以直观的教学印象 让学生清楚的知道数据怎么变化的 调动学生学习的 积极性 不过该系统不是完善的 只有有限的几个算法演示 开发该系统只希望 能起到抛砖引玉的作用 给学生带来一定的启发 2 2 2 应用环境应用环境 开发该演示系统的目的是为了在教学中引入新的教学手段 调动学生学习积 极性 提供教师授课的方便 该系统的是在 Windows XP 操作系统下实现的 这 样符合大多数教学所用的计算机所采用的系统 方便软件在不同计算机之间的转 移 它可以是教师使用或者学生使用 软件界面的简单使得不同知识层次的人使 用起来不会有麻烦 2 2 3 任务分析任务分析 使用该演示系统是为了促进学生对数据结构课程的理解 提高数据结构课程 的教学质量 在现代化的教学过程中 由于多媒体辅助教学能够化静为动 寓教 于乐 培养和激发学生的学习兴趣 能使抽象问题形象化 便于学生对知识点的 理解和运用 能节约传统的板书时间 开阔知识面 增加信息量 提高学习效率 所以这种教学手段被广泛采用 但是滥用多媒体辅助教学 不但不能达到预期的 教学效果 反而会分散学生的注意力 削弱了教师在教学过程中应起的主导作用 甚至影响学生的学习积极性 因此要注意怎么使用软件 虽然教学课件已经事先做好 但不是说在课堂上教师只要在教师用机的位置 上单纯地 演示 课件就可以了 这样可能会出现学生看了很多 听了很多 却 不知道要学什么 而事与愿违 其实 多媒体辅助教学作为一种现代化的教学手 6 段 是用来提高课堂教学的效率 突破重点难点 解决一些传统教学不易解决的 问题 教师应该凭自身丰富的教学经验和生动的讲解 通过师生间的情绪感染 来调动学生学习的积极性 并使学生能够自觉的参与到新的教学当中去 另外 事先做好的课件灵活性可能较差 有时会限制教师的临场发挥 这时就要求教师 应积极有效地利用投影仪等现代媒体辅助教学 来解决这个矛盾 2 3 演示系统总体规划演示系统总体规划 2 3 1 开发过程应遵循的要求开发过程应遵循的要求 1 符合一般环境需求 可视化软件的系统平台必须符合学生一般常接触 的环境 现在常见到的不外乎是 Java Applet 和应用软件 对于 Java Applet 而言 是属于客户机 服务器架构 学生必须经由网络的连接 将需求传送至服务器端 然后才能执行 如此 对于缺乏网络或网络不顺畅的教学环境而言 就容易受到 限制 对于应用软件而言 要求系统简洁 小巧便于移动 2 界面设计的便利性 在有限时间内 学生不应花费太多的时间去摸索复 杂困难的学生界面 所以在接口设计上 必须以学生操作方便为原则 3 提供学生输入数据 当学生初次使用可视化软件时 系统必须告知其所 接受的数据形态和范围 如利用系统自行产生数据的功能 让学生便于执行算法 如此可以鼓励学生主动去探索各种情况下算法的执行效率 4 学生控制 不同的学生 其吸收知识的速度不一定相同 因而 让学生 自行掌握学习的速度是有必要的 在可视化软件中可提供调整动画执行过程的延 迟时间 或是利用单步执行按键 让学生自行控制学习速度 此外还原键也是让 学生往回追溯不懂之处的重要按键之一 5 算法的全貌浏览 当学生想快速观看算法的部分片段时 提供快速执行 功能是有其必要性的 学生可直接执行算法的某一时点 或大略观看演算法的执 行全貌 6 提供伪码的对照 单纯展示算法执行过程 只能让学生在算法程序上有 所了解 若要让学生在概念上更加清楚 则提供算法的伪码是一个好方法 7 相关辅助信息 例如对于不熟悉算法的学生而言 可提供相关的背景数 据与算法所要达成的目标 7 2 3 2 系统组成系统组成 演示系统包含教五个教学单元 顺序表的插入和删除 链表的插入 栈的递 归过程 汉诺塔 最短路径 每个单元的内容相互独立 并由主菜单调入 每 个单元都有各自的功能 可由主菜单进入各个独立单元 系统的总体框架如下图 2 2 顺序表 链表 栈 最短路径 插入 删除 插入 汉诺塔 迪杰斯特拉 欢 迎 界 面 图图 2 2 演示系统总体框架演示系统总体框架 2 3 3 功能功能要求要求 1 用动态图形对数据结构中如 线形表的插入删除算法 汉诺塔及最短 路径问题进行了形象直观 准确生动的演示 能够很好地帮助学生深入理解算法 有利于培养学生的抽象能力 2 系统控制能力强 具有暂停 重复和恢复等功能 3 良好的操作界面 同时支持键盘和鼠标 操作简单 菜单提示 可点 对象醒目 4 软件脚本根据由严蔚敏编著的国优教材数据结构一书编写的 内容编 排合理 教学功能强 5 交互性强 系统中使用的大部分参数可由使用者自行设置 学习内容 及学习进度也可由使用者自行选择 6 系统采用模块化结构 可维护性强 8 2 4 选用选用 MFC 进行系统开发进行系统开发 该演示系统使用了大量的视图界面作为演示系统的操作界面 而且演示系统 为了用户的使用方便采取的是基于对话框的结构构架 利用微软基本类库 MFC Microsoft Foundation Class 能够很好的开发出符合这种需要的软件 因此 选择使用 MFC 以及 Visual C 开发系统来编写自己的基于 Windows 的应用程序 MFC 提供了很多的图形控件 可以比较方便的设计出算法演示系统的界面 MFC 是微软为 Windows 程序员提供的一个面向对象的 Windows 编程接口 它大大简化了 Windows 编程工作 该层次结构包容了 Windows API 中的用户界 面部分 并使程序员能够很容易地以面向对象的方式建立 Windows 应用程序 这 种层次结构适用于所有版本的 Windows 并彼此兼容 基础类库的核心是以 C 形式封装了大部分的 Windows API 类库表示窗口 对话框 设备上下文 公共 GDI 对象如画笔 调色板 控制框和其他标准的 Windows 部件 这些类提供了 一个面向 Windows 中结构的简单的 C 成员函数的接口 MFC 的本质就是一个包含了许多微软公司已经定义好的对象的类库 我们知 道 虽然我们要编写的程序在功能上是千差万别的 但从本质上来讲 都可以化 归为用户界面的设计 对文件的操作 多媒体的使用 数据库的访问等等一些最 主要的方面 这一点正是微软提供 MFC 类库最重要的原因 在这个类库中包含 了一百多个程序开发过程中最常用到的对象 在进行程序设计的时候 如果类库 中的某个对象能完成所需要的功能 这时我们只要简单地调用已有对象的方法就 可以了 我们还可以利用面向对象技术中很重要的 继承 方法从类库中的已有 对象派生出我们自己的对象 这时派生出来的对象除了具有类库中的对象的特性 和功能之外 还可以由我们自己根据需要加上所需的特性和方法 产生一个更专 门的 功能更为强大的对象 当然 你也可以在程序中创建全新的对象 并根据 需要不断完善对象的功能 正是由于 MFC 编程方法充分利用了面向对象技术的优点 它使得我们编程 时极少需要关心对象方法的实现细节 同时类库中的各种对象的强大功能足以完 成我们程序中的绝大部分所需功能 这使得应用程序中程序员所需要编写的代码 大为减少 有力地保证了程序的良好的可调试性 最后要指出的是 MFC 类库在提供的对象的各种属性和方法都是经过谨慎的 编写和严格的测试 可靠性很高 这就保证了使用 MFC 类库不会影响程序的可 9 靠性和正确性 2 5 本章小结本章小结 本章是对系统的概述以及开发工具的介绍 详细说明了系统的需求分析 系 统是在 Windows XP 系统下使用 MFC 构架的 并说明了使用 MFC 构架系统的优 越性 10 第第 3 章章 演示系统设计演示系统设计 一个好的计算机应用软件 都是经过程序员冷静的思考 详尽的分析而产生 的 设计远比编程重要 设计的过程就是将事务处理抽象成计算机模型的过程 本章详细的介绍演示系统的系统组成与各个功能模块的要求 3 1 系统组成系统组成 该演示系统是几个经典数据结构算法的演示系统 这几个经典算法分别是顺 序表的插入 删除算法 链表的插入算法 栈的递归过程中的汉诺塔 使用迪杰 斯特拉算法求最短路径 系统设计图如下图 3 1 所示 由图 3 1 可以看到 系统设计是采用模块化思想 这样每个算法之间都是独 立的 便于系统维护 也便于以后再向里面添加新的算法 每个算法演示下面都有其详细的操作界面 以顺序表插入为例子 它的具体 设计思想如下图 3 2 所示 其他各个算法的演示大致和顺序表插入算法相同 有方便的操作 动态的图 形演示和跟随程序运行的伪代码 图图 3 1 演示系统总体设计演示系统总体设计 欢迎界面 线 性 表 链 表 栈最 短 路 径 顺 序 表 插 入 顺 序 表 删 除 返 回 链 表 删 除 返 回 汉 诺 塔 返 回 最 短 路 径 返 回 11 图图 3 2 顺序表插入算法演示模块顺序表插入算法演示模块 3 2 各个功能模块的要求各个功能模块的要求 3 2 1 主界面功能要求主界面功能要求 主界面是一个选择界面 它们的功能是转到下一个界面 1 顺序表 它的作用是转到顺序表插入删除算法选择界面 2 链表 它的作用是转到链表插入算法选择界面 3 栈 它的作用是转到汉诺塔算法选择界面 4 最短路径 它的作用是转到迪杰斯特拉算法选择界面 二级界面同样是一个选择界面 它们的功能是转到相应算法演示界面 它们的要求如附录 3 2 2 表与栈表与栈 该演示系统演示算法中有关表的演示有两个 顺序表和链表 它们都是数据 结构课程的基本知识 在实际中也有很广的用途 算法说明 对演示算法的说明 该系统的教学对象对算法概念不清楚时可以 查看 或者让初学者知道该算法是怎么样的 因此算法说明应该能清楚的表明算 法的思想 输入数据 输入数据就是向系统中写入数据 为演示做好准备 输入数据时 弹出一个对话框 在指定地方输入数据 并且有说明什么样的数据是系统允许的 输入非法数据时系统将不能接受或者弹出错误提示 顺序表的插入 操作模块演示模块 算 法 说 明 图 形 演 示 伪 代 码 暂 停 返 回 单 步 执 行 恢 复 插 入 元 素 输 入 数 据 12 插入元素 该功能允许用户输入要插入的元素 并把要插入的位置表示出来 同样的 系统对插入的元素有要求 当输入非法时将不能把数据写入系统 顺 序表中插入位置不能为负数 恢复 在演示完成后如果用户想要再进行一次演示或者演示途中想重新看的 时候 可以用这个功能来把数据恢复到演示之前的状态 即输入元素和插入元素 之后的状态 执行 在输入数据和插入元素步骤之后 可以使用该功能来进行算法的演示 它将在算法演示完成后停下来 并且有提示算法演示完成了 单步 为了教学的方便 设置了这个单步功能 它可以使程序一个语句一个 语句的执行 类似看电影中的慢镜头 可以让学习者更清楚的看到程序执行的过 程 它需要操作者手动点击 点击一次执行一次该功能 暂停 该功能是能够让使用者在程序执行过程中把程序停下来 对学习者尤 其有用 当遇到不太了解的地方时 可以把程序停下来仔细揣摩 当想要继续演 示下去时 可以点击执行来继续操作 返回 该功能是把算法演示界面返回到上一个选择界面 图形演示 在输入数据后演示模块就把数据生成一个顺序表 插入的数据在 顺序表上方显示 在元素移动时以闪烁的箭头表示移动方向 而后元素移动到相 应位置 这个功能是在一个系统分配固定的范围执行的 因此对要演示的数据 有要求 即输入的数据长度不能超出它的范围 伪代码 伪代码是便于学习者理解算法的 它在学习中被广泛应用 本演示 系统使用的伪代码和数据结构 严蔚敏 版一书很贴切 体现了为教学而制作软 件的目的 在程序执行时 该伪代码以红色显示正在执行的语句 提示醒目方便 学习 3 2 3 栈的递归过程汉诺塔栈的递归过程汉诺塔 汉诺塔演示模块设计为四个不分 因为对它的演示比对线性表的演示要复杂 它采用递归互换法来解决汉诺塔问题 功能设计如下图 3 3 13 图图 3 3 汉诺塔演示模块汉诺塔演示模块 同顺序表算法中相同功能就不重复叙述了 下面着重介绍不同的地方 输入数据 汉诺塔的输入数据是要求输入演示盘子的个数 这个数据的输入 依然有限制 限制输入自然数在 12 以内 图形演示 汉诺塔的图形演示包括基座和盘子的显示 基座一般呈现的是倒 T 型图形 盘子以黑色矩形图形表示 矩形按从小到大表示盘子的顺序 步骤展示 汉诺塔演示中 当盘子数目稍多时 盘子的移动步骤是相当复杂 的 这个时候仅仅观看图形的移动很可能记不清盘子到底是怎么移动的 该功能 就是记录盘子的移动步骤 使用户及其对象能对照步骤加深对汉诺塔的理解 栈地址展示 该功能是展示汉诺塔演示时 代表盘子的数据在栈中的地址 从表面到深入了解数据的变化 3 2 4 最短路径最短路径 它与表的演示有所不同 本演示系统是使用迪杰斯特拉算法求最短路径 这 个算法注重的是算法的思想 它求解从原点出发的各有向路径的从小到大的排列 但是算法最终确实得到了从原点到图中其余各点的最短路径 可以说这是个副产 品 对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜 清楚了算法的这种巧妙构思后 理解算法本身就不是难题了 它比表的功能多了 几个 新建节点 这个同表的输入数据 但由于这是图的演示 输入数据变成了建 节点 该功能允许用户在演示模块上建立节点 在创建过程中节点可以按用户心 意随意移动 汉诺塔 操作模块演示模块 图 形 演 示 伪 代 码 栈 地 址 展 示 步 骤 展 示 返 回 单 步 暂 停 执 行 恢 复 输 入 数 据 算 法 说 明 14 添加线 图的节点之间需要线来连接 这种线是有向线段 连接好节点之后 可以鼠标双击连线 在弹出的对话框填写权值 这个权值也是有要求的 当节点 移动时 连线的连接两节点的作用并没有消失 创建结束 当节点和连线好了之后 确人不需要修改之后可以点击此键准备 演示 该功能执行后 节点和权值将不能再进行修改 设置起点 该算法实际上是求出起点到各个节点的最短路径 在本小节开头 已经说过 两点之间的最短路径只是这个算法的副产物 设置起点能够指定一个 节点作为该部分演示的原点 设置了起点后就可以开始演示了 演示模块 这个演示界面中 矩形框架里面是图的数据 路径是起点到各个 节点之间的最短路径 如果没有 则显示没有路径 3 3 本章小结本章小结 本章是对演示系统的总体规划和各个功能模块的要求说明 介绍了系统的组 成部分 并分模块的详细介绍了各个模块的功能要求 15 第第 4 章章 演示系统实现演示系统实现 基于 Windows XP 操作系统的数据结构几个经典算法的演示系统是用 MFC 制 作的 它是单文档多视图结构 本系统作为教学软件 设计时充分考虑了软件的 适用性和风格 它简单易用 交互性强 本演示系统 从以下几个方面一步步达到第三章提出的设计要求 1 主体欢迎界面 2 选择算法界面 3 顺序表演示界面 4 链表演示界面 5 汉诺塔演示界面 6 最短路径演示界面 4 1 系统框架的实现系统框架的实现 该系统是基于单文档多视图结构构架的 通过发送消息来实现各个界面之间 的转换 可以用添加资源功能制作一个基本的视图 然后在上面加上各种控件 再对各个控件做细化处理 如下图 4 1 同样的 先把所有的界面都这样的画出来 但是这样的界面都是孤立的 它 们之间没有任何关系 每个单独的界面里面也没有填写程序 这只是做一个框架 出来 然后就要对界面进行处理 在大多数的界面设计中 并不是所有元素都具有 相同的重要性 精心设计将保证较重要的元素对用户来说处在一目了然的位置 重要的和需要经常访问的元素应当处于显著的位置 次要的元素应处于次要的位 置 我们习惯的阅读顺序一般是从左到右 从上到下 可以说 用户第一看到的 是屏幕的左上部分 因此 主要的元素应放在这里 而类似 确定 下一步 之类的按键则应处于屏幕的右下方 因为用户通常是在完成了整个窗口的工作后 才访问它们 3 16 最后形成的主界面如下图 4 2 所示 它有一个说明和四个主按键 通过它们就可以使用到这个演示系统的全部功 能 而且它的界面简单清新 也可以为以后向里面添加新的算法做好准备 图图 4 1 添加资源添加资源 图 4 2 是主选择界面 图 4 3 是第二级选择界面 它们之间的转化是通过一 个消息函数来实现的 其代码如下 void CViewHello OnBnClickedButton2 TODO 在此添加控件通知处理程序代码 this GetParent SendMessage WM DLF SHOW VIEW IDD FORMVIEW DIJKSTRA 消息发送后 系统就重画视图 如图 4 3 视觉上的效果就是从图 4 2 界面转 到了图 4 3 界面 演示系统的退出可以通过点对话框右上的 来实现 17 图图 4 2 完成后的主界面完成后的主界面 图图 4 3 最短路径选择算法界面最短路径选择算法界面 4 2 顺序表演示模块的实现顺序表演示模块的实现 4 2 1 设计思想设计思想 顺序表算法演示模块有两个部分 顺序表的插入和顺序表的删除 顺序表的算法说明 线形表的顺序存储结构中 由于逻辑上相邻的数据元素 在物理位置上也相邻 因此 除非插入位置 I 的值等于表长加 1 即插入表尾之 后 否则都必须移动元素才能反映这个逻辑关系的变化 一般情况下 在第 I 0 In I I 1 I 1 B I 13 1 打印 B J J 1 2n 1 终止 图图 4 10 用递归互换法实现用递归互换法实现 n n 个盘子的移动个盘子的移动 4 4 3 关键代码展示关键代码展示 演示模块的关键技术在顺序表中已经详细说明了 本演示系统在四大模块的 设计上所用的关键技术都和类似 因此这里就不重复叙述这些关键技术的实现而 是展示一些在汉诺塔演示模块中实现这些关键技术的部分代码 4 4 3 1 绘制图形绘制图形 在系统分配好的动画演示区模块中 由程序把该演示区长度等分为 6 个部分 在奇数等分地方即 1 3 5 等分地方画 2 个矩形图形 它们在视觉效果上一个为 竖直的矩形一个为横向的矩形 呈倒 T 状 并且把它们填充成紫色矩形块 用它 们表示汉诺塔的基座 x y z 表示盘子的图形是黑色的矩形块 它们是以紫色 横向矩形块的上边为最大的盘子与基座的接触面 以竖直的紫色矩形块为柱子 以 它呈对称状 而绘制的 CRect rect CString strTemp GetClientRect int x rect right int y rect bottom 绘制矩形 rect SetRect x 6 10 50 x 6 10 y 50 26 MemDC FillRect rect rect SetRect x 6 50 y 50 x 6 50 y 70 MemDC FillRect rect rect SetRect x 2 10 50 x 2 10 y 50 MemDC FillRect rect rect SetRect x 2 50 y 50 x 2 50 y 70 MemDC FillRect rect rect SetRect x 5 6 10 50 x 5 6 10 y 50 MemDC FillRect rect rect SetRect x 5 6 50 y 50 x 5 6 50 y 70 MemDC FillRect rect 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 A i heigh i 10 x 6 step mpArry A i heigh i 10 9 MemDC FillRect rect for int i 0 iBTotal i rect SetRect x 2 step mpArry B i heigh i 10 x 2 step mpArry B i heigh i 10 9 27 MemDC FillRect rect for int i 0 iCTotal i rect SetRect x 5 6 step mpArry C i heigh i 10 x 5 6 step mpArry C i heigh i 10 9 MemDC FillRect rect 4 4 3 2 展示伪代码展示伪代码 前面说过 伪代码展示区是基于 List Control 控件构架的 设计该模块就是为 了把伪代码展示给学习者观看 并且使伪代码变红显示和动画演示保持同步 for int i 0 i CODE LINES i int line mListSF GetItemCount mListSF InsertItem line mExplain i 4 4 3 3 恢复功能恢复功能 在算法演示过程中暂停 单步和演示完成状态下 用户可以把演示中变化了 的数据恢复到刚输入到演示系统的状态 这个功能的实现原理是 在把数据输入 到系统中时 程序自动把输入的数据备份 当使用恢复功能时 系统把备份的数 据调出而实现对数据的恢复 mArry Total dlg num 保存汉诺塔的盘子数 mArry n mArry Total 设置盘符 柱子 mArry x 1 mArry y 2 28 mArry z 3 mArry ATotal mArry Total 刚开始所有盘放在A柱 设置多个盘子的大小 for int i 0 irectNodeMap left 调用函数判断鼠标所在位置是否在节点上 int k mArry ChickNode point x rectNodeMap left point y rectNodeMap top if k mArry GetNodeFactCount 35 在节点上 把节点编号保存在这里 mNodeNum k if AddLineFlage 1 添加线状态 mLineNum mArry AddLine mNodeNum 判断鼠标位置是否在节点上 if mLineNum 1 不在节点上 弹出消息 MessageBox 无法连线 请先点中节点 AddLineFlage 0 SetStatus Inition 4 5 4 成品展示成品展示 画图区是为输入数据做准备的 这个部分主要是能识别鼠标的信息 画图的 很多地方都要通过鼠标来实现 当点击新建节点时 激活了画图区的识别功能 鼠标在画图区点击左键时 程序在这个点画出一个圆点 并在上面标志为 A 以 此来表示节点的顺序 已经画了一个节点之后 鼠标点在这个上面不放时 程序 相应部分得以激活 这时可以在画图区拖动该节点移动到想要移动到的位置 连线的实现符合大多软件的习惯 在连接两个节点时 点击一个节点不放移 动鼠标 到达到另外一个节点时松开 连线就成立了 并且以有箭头指向连线方 向 如果点击一个节点开始并不放鼠标左键移动到一个没有节点的位置时放开鼠 标 连线将不能被创建 这样就保证了每条连线的可靠性 在靠近箭头的位置上 每条连线都有一个小圆圈 这个圆圈是设置权值的标 志位置 在鼠标双击该圆圈时 将会弹出一个对话框 在这个对话框输入该条路 径的权值 36 在这些信息输入同时 画图区右边的矩阵显示出各节点之间路径的权值 其 中负值 1 表示没有路径 这些如下图 4 16 图图 4 16 带权有向图带权有向图 G6 的演示界面的演示界面 迪杰斯特拉算法求的是一个节点到其他各个节点间的最短路径 因此 演示 前 要设置一个起点 设置起点是由一个对话框实现的 在弹出的对话框输入起 点起点的标志符号 例如设置 A 节点为起点 在对话框中输入大写字母 A 在设置完起点后 对演示的准备就完成了 可以点击执行来演示该算法 演 示中会把该起点到其他各个节点的最短路径在演示界面的左下方位置展示出来 有向图 G6 的演示结果如下图 4 17 图图 4 17 向图向图 G6 的演示结果的演示结果 37 4 6 系统模块间的联系系统模块间的联系 该演示系统是应用模块化思想构建的 每个模块和总体框架都有其相似点 对一个系统的设计 一致性应该保持 这个前面已经说过这样设计软件的优 点了 在该系统中 每个二级界面返回主欢迎界面所用的消息函数是一样的 这 是系统设计上的一致性 各个演示模块所用背景图片一致 这样给用户心理上带来熟悉感 每个模块演示完成时都会弹出显示 演示完成 的对话框 4 7 本章小结本章小结 本章详细的说明了数据结构几个经典算法演示系统的各个功能模块的实现思 想与方法 以各种完成后的作品的截图来说明系统达到的目标 并且介绍了在设 计软件中的一些优秀思想 38 第第 5 章章 结论结论 在本次毕业设计的过程中 通过指导老师的耐心指导和自身的学习及努力 对数据结构知识和教学软件有了进一步的提高 在整个设计过程中深深地体会到 要把所学的知识理论变成可实际应用的系统时所面临的种种困难 认识到提高运 用知识 解决实际问题的能力是十分重要的 在该软件的设计与实现过程中 有几个方面是关键 首先是系统界面的清新 简单和各个模块设计的一致性 其次是为教学效果而完成的一些功能的实现 比 如对单步执行程序的设计 再次 作为一个教学软件 该系统所演示的几个经典 算法是不够的 为了以后能够添加其他的算法演示 采用模块化设计思想 在设 计和实现的过程中 遇到不少问题 在老师帮助指导和本人努力下 本课题所涉 及的难题都已经基本解决 满足本次毕业设计的要求 本演示系统作为一个多媒体动态教学演示课件 在毕业设计过程中完成的部 分还有欠缺 但由于找工作和时间的紧缺 一些设想并没有去实现 如在算法演 示过程中播放适当的音乐显然也能提高学生的学习兴趣 以及为更适合不同的使 用者而应该设计的演示速度模块 这些设想有待以后再实现 关于本次毕业设计 由于设计经验的不足和所掌握知识的限制 该演示系统 虽然已经能实现对一些算法很好的演示 但在某些方面还有更加优秀的演示方法 某些功能设计构想还没有完整的表达出来 通过本次设计的学习和实践 对理论 知识的认识有了进一步的加强 实践能力和独立思考的能力都得到了提高 这是 在书本上所学不到的 这次毕业设计过程中所积累的经验将为本人在今后工作岗 位上发挥自己的才能奠定坚实的基础 39 致谢致谢 本课题在选题及研究过程中得到老师的悉心指导 他们多次询问研究进程 并为我指点迷津 帮助我开拓研究思路 给予我精心点拨 热忱鼓励 他们一丝 不苟的作风 严谨求实的态度 踏踏实实的精神 不仅授我以文 而且教我做人 使我受益无穷 而亲切和蔼的教育态度 几次到寝室给予指点的真挚关怀和丰富 的教育经验更使人终身难忘 不仅指导我的设计课题 而且总结出很多解决问题 的好的方法 使我不仅学到了计算机知识而且学到了对待难题的社会经验 对老 师的感激之情是无法用言语表达的 谢谢两位老师 同时也要感谢学校 学校对毕业设计的要求严格 使我学会了做事的严谨态 度 以及以往没学