(精品论文)优秀毕业设计论文 数据结构算法演示系统

毕业设计（论文）专用纸 数据数据结结构算法演示系构算法演示系统统 学学 校：校：昆明理工大学津桥学院昆明理工大学津桥学院 系系 部：部：计算机科学及电子信息工程系计算机科学及电子信息工程系 专专 业：业：计算机科学与技术计算机科学与技术 年年 级：级： 学生姓名：学生姓名： 学学 号：号： 指导教师：指导教师： 毕业设计（论文）专用纸 Data Structure Demonstration System UniversityUniversity：OxbridgeOxbridge CollegeCollege，KunmingKunming UniversityUniversity ofof ScienceScience andand TechnologyTechnology DepartmentDepartment：ComputerComputer ScienceScience andand ElectronicElectronic InformationInformation EngineeringEngineering Specialty:Specialty:ComputerComputer ScienceScience andand TechnologyTechnology Class:Class:20052005 StudentssStudentss Name:Name:YanlinYanlin ZhengZheng StudentsStudents Number:Number:200511602150200511602150 FacultyFaculty Adviser:Adviser:FeiFei DaiDai 毕业设计（论文）专用纸 目录 目录.I 摘要IV ABSTRACTV 前言1 第 1 章 绪论2 1.1 课题研究背景2 1.2 国内计算机辅助教学的现状2 1.3 计算机辅助教学的发展趋势4 1.4 系统建设的目的4 本章小结.5 第 2 章 需求分析6 2.1 功能性需求分析6 2.1.1 系统需求.6 2.1.2 识别参与者和用例.7 2.1.3 用例的事件流描述.9 2.2 非功能性需求分析18 2.2.1 设计思想.18 毕业设计（论文）专用纸 第 页II 2.2.2 可行性分析.19 本章小结.20 第 3 章 系统详细设计21 3.1 系统总体结构图21 3.2 静态结构模型21 3.2.1 定义系统对象类.21 3.2.2 定义用户界面类.25 3.2.3 建立类图.31 3.3 动态行为模型31 本章小结.39 第 4 章 系统实现40 4.1 多线程简介40 4.1.1 线程、多线程概念.40 4.1.2 实现多线程的方法.40 4.2 动态算法演示模板42 4.3 算法演示的多线程设计43 4.3.1 源代码同步演示的实现.44 4.3.2 动画的同步实现.45 4.3.3 算法中变量值的同步实现.45 本章小结.45 结论46 毕业设计（论文）专用纸 第 页III 总结与体会47 谢辞48 参考文献49 附录一50 附录二55 毕业设计（论文）专用纸 第 页IV 数据结构算法演示系统 摘要 本系统以清华大学出版社出版的 C 语言版数据结构为蓝本，合理地选择数据 结构中部分算法并在系统中进行有机地组合,形成优化的动态演示系统。 它可适应读 者对算法的演示数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法 执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行过程中栈的变化状 况。本系统采用 C#多线程技术来实现数据结构算法的算法动态演示设计，提供及源代 码跟踪、变量跟踪、模拟动态效果“三合一“的算法演示同步平台。 关键词关键词：算法,动态演示,C#,多线程,同步 毕业设计（论文）专用纸 第 页V Data Structure Demonstration System ABSTRACT This system takes Qinghua University publishing house publication C language version “Data Structure“ as a main source, reasonably chooses part of algorithms in the Data Structure and carries on in the system organically combinations, forms the optimized dynamic demonstration system. It may adapt the readers different demands to the algorithm data-in and control modes the process execution, and demonstrates in the algorithm implementation on the computer screen the data logical organization either the memory structure change condition or the stack change condition in the recursion algorithm implementation. With C# multithread, the Data Structure CAI can provide a “tree in one” platform, on which algorithm animation, source code and variable value can be executed and shown synchronously. Keywords: Data structures, Dynamic demonstration, C#, Multhread, Synchronous 毕业设计（论文）专用 纸 第 页1 前言 数据结构是计算机专业的核心课程，对各类算法的理解则是课程教学的重点和难 点，算法动态演示作为辅助教学过程的手段则可以有效帮助学生更快的理解、掌握算 法。数据结构对后续课程的学习极其重要。但该课程涉及大量的概念、定义、模型和 算法，显得很抽象和深奥。在教学过程中，如果能加以计算机辅助教学，可以提高教 学效果，所以编写这样的程序不仅有助于学习数据结构，同时也大大增强了学生的学 习兴趣，提高学生的编程能力。这是因为，一方面利用算法演示系统的生动性和直观 性，使教学内容条理化和形象化，降低了对知识理解的难度；另一方面，由于演示系 统的趣味性和交互性，有利于激发学生浓厚的学习兴趣，使其愿学、乐学。 可视化是演示系统应该具备的要求。本系统采用 C#多线程技术来实现数据结构算 法的算法动态演示设计，提供及源代码跟踪、变量跟踪、模拟动态效果“三合一“的 算法演示同步平台。 毕业设计（论文）专用 纸 第 页2 第 1 章 绪论 数据结构是计算机专业的核心课程，重点培养学生在对数据分析组织与程序设 计算法思想上的综合能力。算法是数据结构的主要内容，也是数据结构教学的重点和 难点。但在数据结构的教学过程中，使用传统的静态课件或“粉笔 + 黑板”教学形式 很难将算法的执行过程动态地演示出来，影响了教学效果。 数据结构算法动态演示设 计是使用专业编程技术实现算法的动态展示，使学生更直观的从算法的设计思想、 程序运行描述、程序运行结果同步跟踪展示等全方位的了解算法，使学生能主动积极 地学习和掌握应用这些算法。 1.1 课题研究背景 随着现代科学技术的迅猛发展，计算机技术已渗透到各个领域，成为各行业必不 可少的工具，特别是 Internet 技术的推广和信息高速公路的建立，使 IT 产业在市场竞 争中越发显示出其独特的优势，步入数字化时代，有巨大的数据信息等待着加工处理 和传输，这将现实的许多东西都进入虚拟的世界当中，这都需要计算机技术的支持。 同样的，学院的教学手段也在逐步信息化，这使得计算机辅助教学 CAI 的出现成为一 种必然的趋势。 90 年代以来, 随着多媒体和 Internet 网络的出现，计算机教育已步入一个全新 的阶段，计算机辅助教学 CAI 作为一种先进的教学手段正逐步渗透于各类院校的各个 学科。数据结构不仅是大学计算机专业的核心课程之一，也是非计算机专业的主 要选修课程之一。该课程涉及大量的概念、数据结构和算法，理论性强又较为抽象， 尤其是对算法描述的执行过程的理解是难点和重点。在课堂教学上，大量的算法不可 能也无法一一详述。运用计算机辅助教学系统数据结构算法动态演示系统可 以使教学内容化静为动，调动学生的学习兴趣；变难为易，提高学生学习兴趣；使学 生寓学于乐，培养学生的学习兴趣，与此同时，利用计算机辅助教学还可以满足学生 的学习兴趣。它已成为激发学生兴趣的新方法、新手段。 毕业设计（论文）专用 纸 第 页3 1.2 国内计算机辅助教学的现状 随着时代的进步，电子技术的飞速发展，全球网络化进程的加快，社会各行各业 中都应用到了计算机这种现代技术工具，目前我国的教育领域也已经开始运用计算机 辅助教学（Computer-Assisted Instruction,以下简称 CAI）这一现代化教学手段进行教 育教学。 作为一种媒体，计算机与其他教学媒体（如黑板、教科书、投影仪、电视机、录 像机等）没有什么不同，能够帮助教师提高教学效果、扩大教学范围、延伸教师的教 育功能。 课堂教学，在今天和今后相当长的历史时期中，仍然是学校教学活动的主要 场所，因此计算机辅助教学（CAI）作为一种现代化的教学技术，将集中体现在课堂 教学中。计算机辅助教学是利用计算机作为主要的教学媒体来进行教学活动，即利用 计算机来辅助教师执行教学。计算机不仅能呈现单纯的文字、数字等字符教学信息， 而且还能。输出动画、视频、图像和声音，能非常容易做到教学信息的图、文、声并 茂，这种多维立体的教育信息传播，增强了信息的真实感和表现力。另外，计算机作 为教学媒体，学生可利用一定的输入、输出设备，通过人机“对话”的方式进行学习， 这种人机交互作用是计算机媒体所特有的。 计算机辅助教学的作用。多年以来，我们的教学工作一般都是教师用黑板板书， 用口头说教；学生用笔记录，用耳朵听讲，所以，教师和学生都形成了一定的思维定 势。随着时代的发展和科学技术的进步，人类的教育水平及教育手段也在不断的提高。 电化教育已渗透到各个学科当中，近 30 年来，计算机辅助教学（CAI）兴起，利用计 算机来帮助教师执行教学功能，老师运用计算机辅助教学的手段，采用计算机多媒体 教学方法，成为激发学生兴趣的新方法。如教师在教学中，可以运用计算机来呈现教 学计划、教学内容、记录学生的学习情况和控制学习进程等；教师可以在教学中根据 本学科的特点，制作各种课件、软件，使整个课堂从原来抽象、死板的氛围转到生动、 活跃起来，把教师的主导性和学生的主体性充分发挥出来16。 传统的教学方法正在逐步向现代化计算机辅助教学方向发展。但目前，计算机辅 助教学还属于起步阶段，很多工作还需要进一步开展。目前我国经济欠发达地区还没 毕业设计（论文）专用 纸 第 页4 有开展计算机辅助教学，还有一些教育工作者对计算机普及教育以及运用计算机改革 传统教学的兴趣不浓，积极性不高，为此，应从提高认识入手，着力从教育系统内部 的观念更新向全社会教育观念更新推进。 1.3 计算机辅助教学的发展趋势 目前我国已认识到计算机辅助教学在教育教学中的重要作用，无论是从经济上还 是在教师培训上都在采用积极的态度：对 CAI 软件的开发作理论上、技术上和应用方 面的深入研究，是促进 CAI 不断发展的基础工作，此方面已给予充分重视。同时也正 在不断地解决 CAI 软件使用中的问题，其中教师的培训是一个关键。不仅要使教师掌 握 CAI 软件的具体的使用方法，更重要的是观念的转变，以教学改革促进 CAI 的应用， 反之又通过 CAI 的应用促进教学改革。CAI 是在教育教学改革中产生和发展起来的， 它本身带有鲜明的革新品格。用传统的方法、其它的媒体，甚至人类教师本身无法或 难以实现的目标，通过计算机资源的合理应用，将使问题得到圆满地解决。因此，明 确 CAI 软件的研究和应用的根本目的在于改革教学、提高学生的培养质量，而不在于 为了形式上的使用，把研究、应用和教师培训有机地结合起来，以研究促进应用，反 过来又以应用促进研究，使其形成互动机制，是保证 CAI 发展的正确途径。计算机辅 助教学的发展趋势是：一是网络化。网络化进程的加快，信息资源无比丰富，我们可 以利用网络资源来制作自己的软件和课件；视频技术在教学中的应用，我们可以把自 己优秀的课例通过视频编辑后在网上发布，也可以从网络上观看其他地方的优秀课例 及对自己有用的资料，最终实现通过网络的交流。二是智能化。CAI 正向着智能化方 向发展，虚拟的社会学习系统，计算机作为导师、同学，同时作为教师与学习伙伴、 学员，利用这一点我们可以只利用一条网线、一台计算机、就可以实现在网络上的学 习和交流，并且可以采用“面对面”的、“超越时空”的形式进行学习和沟通15。 1.4 系统建设的目的 科学技术越向前发展，人们越容易操作和驾驭。计算机技术的迅速发展必将推动 CAI 向着更先进、更高水平的方向发展，在教育领域最终实现人机之间的交互， 毕业设计（论文）专用 纸 第 页5 对我国的教育事业最终起到大大的推动作用。计算机辅助教学系统数据结构算 法动态演示系统建设的目的有以下几点： 1)该系统可以使学员深入理解教材内容、掌握基本的数据结构及相应算法的实现过 程有很好的帮助作用。 2)该系统不仅能呈现单纯的文字、数字等字符教学信息，而且还能输出动画、视频、 图像和声音，能非常容易做到教学信息的图、文、声并茂，这种多维立体的教育 信息传播，增强了信息的真实感和表现力。 3)该系统可以使教学内容化静为动，调动学生的学习兴趣；变难为易，提高学生学 习兴趣；使学生寓学于乐,培养学生的学习兴趣，与此同时，可以满足学生的学习 兴趣。 根据以上 3 点可知该系统的建设是非常必要的。 本章小结 本章重点介绍了“基于 C#多线程技术的数据结构算法动态演示系统”该课题的研 究背景、国内计算机辅助教学系统的现状和发展趋势以及建设该系统的目的。 毕业设计（论文）专用 纸 第 页6 第 2 章 需求分析 所谓需求分析是指研究问题域，产生一个满足用户需求的系统模型。这个系统模 型应能正确地描述问题域和系统责任，并使后续开发阶段的有关人员能根据这个模型 继续进行工作。 2.1 功能性需求分析 本系统是一个动态演示数据结构算法执行过程的辅助教学软件，它可适应读者对 算法的输入数据和过程执行的控制方式的不同需求，在计算机的屏幕上显示算法执行 过程中数据的逻辑结构或存储结构的变化状况或递归算法执行过程中栈的变化状况。 整个系统使用菜单驱动方式, 每个菜单包括若干菜单项。每个菜单项对应一个动作或 一个子菜单。系统一直处于选择菜单项或执行动作状态，直到选择了退出动作为止5。 2.1.1 系统需求 经过对数据结构算法动态演示系统的基本需求分析后，该系统至少具备以下功能： 1) 可以动态演示顺序表； 2) 可以动态演示链表； 3) 可以动态演示二叉树遍历； 4) 可以动态演示二叉树线索化； 5) 可以动态演示赫夫曼树； 6) 可以动态演示拓扑排序； 7) 可以动态演示内部排序； 8) 可以显示 C 语言编写的核心代码； 9) 可以显示变量； 10) 可以跟踪变量； 毕业设计（论文）专用 纸 第 页7 11) 可以显示算法设计思想； 12) 可以暂停正在执行的系统； 13) 可以将暂停了的系统继续执行； 14) 可以返回上一级菜单； 15) 可以跟踪代码； 16) 可以恢复到演示的开始； 17) 可以重新设置数据； 18) 可以显示变动态画面。 上面每一行描述了一个功能，这种表达有利于测试需求的定义，因为每一行描述 的功能都是单独可测的。由于分析设计是一个迭代的软件开发过程，所以需求也会在 分析设计过程中不断的补充、细化。上述的需求只是初步的基本需求，还有待不断地 细化、完善。 2.1.2 识别参与者和用例 通过分析数据结构算法动态演示系统的功能需求，由于它是一个单机版的系统， 因此可识别出 1 个参与者，那就是操作该系统的人操作者（OP） 。 用例是什么？其原始英文是 use case，直译过来就成了用例。这也是一个比较贴 切的叫法了，从字面的直接理解就是使用的例子。另一种比较流行的定义是用例就是 与使用者(actor)交互的，并且给使用者提供可观测的有意义的结果的一系列活动的集 合。最具普遍意义的理解错误是认为用例就是功能的划分和描述，认为一个用例就是 一个功能点。在这种理解下，用例变成了仅仅是较早前需求中功能框图的翻版，很多 人用用例来划分子系统，功能模块和功能点。如果这样，用例根本没有存在的必要。 如果用例不是功能的话，它是什么呢？从定义上说，能给使用者提供一个执行结 果的活动，不就是功能吗？我的回答是：错！功能是计算机术语，它是用来描述计算 机的，而非定义需求的术语。功能实际描述的是输入计算输出。这让你想到了 什么？DFD 图？这可是典型的面向过程分析模式。实际上，把用例解释为某个参与者 (actor)要做的一件事可能更为合适。 毕业设计（论文）专用 纸 第 页8 上面已经识别出了参与者，通过对需求的进一步分析，可以确定系统中有如下用 例存在： 2)show sqList（演示顺序表） 本用例提供了演示顺序表的插入和删除的功能 3)show linkList（演示链表） 本用例提供了演示链表的创建、插入和删除的功能。 4)show OrderTree（演示二叉树遍历） 本用例提供了演示二叉树先序、中序和后序遍历的功能。 5)show ThreTree（演示二叉树线索化） 本用例提供了演示二叉树先序、中序和后序线索化的功能。 由于用例（3）和（4）有公共行为，因此可以抽象出一个父用例“create Tree” 。 6)create Tree（创建二叉树） 本用例描述了创建二叉树的通用行为，是用例（3）和（4）的父用例。 7)show HuffmanCode（演示赫夫曼树） 本用例提供了演示赫夫曼树创建的功能。 8)show TopoSort（演示拓扑排序） 本用例提供了演示拓扑排序的功能。 9)show Sort（演示内部排序） 本用例提供了演示内部排序中的希尔排序和快速排序的功能。 系统的用例图如图 2.2 所示，参与者“OP”与“show sqList”、 “ show linkList”、 “ show OrderTree“、 ”show ThreTree“、 “create Tree”、 ”show HuffmanCode“、 ”show TopoSort“、 ” show Sort“交互。 毕业设计（论文）专用 纸 第 页9 show OrderTree show linkList show ThreTree show HuffmanCode show TopoSort show Sort show sqList OP create Tree 图 2.2 系统用例图 2.1.3 用例的事件流描述 用例的事件流是对完成用例行为所需的事件的描述4。事件流描述了系统作什么， 而不是描述系统应该怎么做。下面对前面识别出的用例逐个进行描述。 1) show sqList（演示顺序表） 用例编号 001 用例名称演示顺序表 用例描述动态演示顺序表的添加和删除 参与者角色操作者 前置条件系统处于运行状态 后置条件动态演示顺序表的添加和删除 基本路径1. 操作者进入演示系统界面，用例开始； 2. 操作者向系统发出“演示顺序表”请求； 3. 系统要求操作者选择顺序表演示的是添加还是删除 A1： 操作者做出选择； 4. 操作者输入信息，并发出“确定”请求； 5. 系统自动根据输入信息建立相应的界面； 毕业设计（论文）专用 纸 第 页10 6. 操作者向系统发出“说明”请求； 7. 系统显示相关说明，系统转到 13 8. 操作者向系统发出“返回”请求； 9. 系统转到 2； 10. 操作者向系统发出“执行”请求； 11. 系统动态地演示操作者选择的请求 12. 在系统演示未结束时，操作者是否向系统发出请求； A2：发出请求； 13. 用例结束； 14. 操作者向系统发出“重新输入信息”请求后，转到 4； 扩展路径A1： 操作者做出选择； 1. 操作者选择顺序表添加的演示，显示相应的界面，转到 4； 2. 操作者选择顺序表删除的演示，显示相应的界面，转到 4； A2：发出请求； 1. 操作者向系统发出“暂停”请求，系统将停止演示； B1：演示是否结束； 异常路径B1：演示是否结束； 1. 操作者向系统发出“继续”请求，系统将接着暂停的位 置继续执行转到 13； 2. 操作者向系统发出“恢复”请求，系统转到 5。 补充说明无 2)show linkList（演示链表） 用例编号 002 用例名称演示链表 毕业设计（论文）专用 纸 第 页11 用例描述动态演示链表的创建、添加和删除 参与者角色操作者 前置条件系统处于运行状态 后置条件动态演示链表的创建、添加和删除 基本路径1. 操作者进入演示系统界面，用例开始； 2. 操作者向系统发出“演示链表”请求； 3. 系统要求操作者选择演示链表的创建、添加还是删除 A1： 操作者做出选择； 4. 操作者输入信息，并发出“确定”请求； 5. 系统自动根据输入信息建立相应的界面； 6. 操作者向系统发出“说明”请求, 系统转到 13； 7. 系统显示相关说明； 8. 操作者向系统发出“返回”请求； 9. 系统转到 2； 10. 操作者向系统发出“执行”请求； 11. 系统动态地演示操作者选择的请求 12. 在系统演示未结束时，操作者是否向系统发出请求； A2：发出请求； 13. 用例结束； 14. 操作者向系统发出“重新输入信息”请求后，转到 4； 扩展路径A1： 操作者做出选择； 1. 操作者选择链表创建的演示，显示相应的界面，转到 4； 2. 操作者选择链表添加的演示，显示相应的界面，转到 4； 3. 操作者选择链表删除的演示，显示相应的界面，转到 毕业设计（论文）专用 纸 第 页12 4； A2：发出请求； 2. 操作者向系统发出“暂停”请求，系统将停止演示； B1：演示是否结束； 异常路径B1：演示是否结束； 1. 操作者向系统发出“继续”请求，系统将接着暂停的位 置继续执行转到 13； 2. 操作者向系统发出“恢复”请求，系统转到 5。 补充说明无 3)show OrderTree（演示二叉树遍历） 用例编号 003 用例名称演示二叉树遍历 用例描述动态演示二叉树的先序、中序和后序遍历 参与者角色操作者 前置条件系统运行于二叉树状态 后置条件动态演示二叉树的先序、中序和后序遍历，并显示遍历的结 果 基本路径1. 操作者进入二叉树演示界面，用例开始； 2. 操作者向系统发出“演示二叉树遍历”请求； 3. 系统要求操作者选择演示二叉树的先序、中序还是后序 遍历； A1： 操作者做出选择； 4. 操作者输入信息； A2： 操作者对输入信息做出选择； 5. 系统自动根据输入信息建立相应的界面； 6. 操作者向系统发出“说明”请求, 系统转到 13； 毕业设计（论文）专用 纸 第 页13 7. 系统显示相关说明； 8. 操作者向系统发出“返回”请求； 9. 系统转到 2； 10.操作者向系统发出“执行”请求； 11.系统动态地演示操作者选择的请求； 12.在系统演示未结束时，操作者是否向系统发出请求； A3：发出请求； 13.用例结束； 14.操作者向系统发出“重新输入信息”请求后，转到 4； 扩展路径A1： 操作者做出选择； 1. 操作者选择先序遍历的演示，显示相应的界面，转到 4； 2. 操作者选择中序遍历的演示，显示相应的界面，转到 4； 3. 操作者选择后序遍历的演示，显示相应的界面，转到 4 A2：操作者对输入信息做出选择； 1. 操作者选择“自动建树”按钮，操作者向系统发出“确 定”请求，系统转到 5； 2. 操作者选择“满树”按钮，操作者向系统发出“确定” 请求，系统转到 5； A3：发出请求； 1. 操作者向系统发出“暂停”请求，系统将停止演示； B1：演示是否结束； 异常路径B1：演示是否结束； 1. 操作者向系统发出“继续”请求，系统将接着暂停的位 置继续执行转到 13； 毕业设计（论文）专用 纸 第 页14 2. 操作者向系统发出“恢复”请求，系统转到 5。 补充说明无 4) show ThreTree（演示二叉树线索化） 用例编号 004 用例名称演示二叉树线索化 用例描述动态演示二叉树的先序、中序和后序线索化 参与者角色操作者 前置条件系统运行于二叉树状态 后置条件动态演示二叉树的先序、中序和后序线索化 基本路径1. 操作者进入二叉树演示界面，用例开始； 2. 操作者向系统发出“演示二叉树线索化”请求； 3. 系统要求操作者选择演示二叉树的先序、中序还是后序 线索化； A1： 操作者做出选择； 4. 操作者输入信息； A2： 操作者对输入信息做出选择； 5. 系统自动根据输入信息建立相应的界面； 6. 操作者向系统发出“说明”请求, 系统转到 13； 7. 系统显示相关说明； 8. 操作者向系统发出“返回”请求； 9. 系统转到 2； 10.操作者向系统发出“执行”请求； 11.系统动态地演示操作者选择的请求； 12.在系统演示未结束时，操作者是否向系统发出请求； A3：发出请求； 毕业设计（论文）专用 纸 第 页15 13.用例结束； 14.操作者向系统发出“重新输入信息”请求后，转到 4； 扩展路径A1： 操作者做出选择； 1. 操作者选择先序线索化的演示，显示相应的界面，转到 4； 2. 操作者选择中序线索化的演示，显示相应的界面，转到 4； 3. 操作者选择后序线索化的演示，显示相应的界面，转到 4； A2：操作者对输入信息做出选择； 1. 操作者选择“自动建立”按钮，操作者向系统发出“确 定”请求，系统转到 5； 2. 操作者选择“满树”按钮，操作者向系统发出“确定” 请求，系统转到 5； 3. 操作者选择“保存数据”按钮，操作者向系统发出“确 定”请求，保存该文件； 4. 操作者选择“导入数据”按钮，操作者向系统发出“确 定”请求，导入一文件； A3：发出请求； 1. 操作者向系统发出“暂停”请求，系统将停止演示； B1：演示是否结束； 异常路径B1：演示是否结束； 1. 操作者向系统发出“继续”请求，系统将接着暂停的位 置继续执行转到 13； 2. 操作者向系统发出“恢复”请求，系统转到 5。 补充说明无 毕业设计（论文）专用 纸 第 页16 5)show HuffmanCode（演示赫夫曼树） 用例编号 005 用例名称演示赫夫曼树 用例描述动态演示赫夫曼树的创建 参与者角色操作者 前置条件系统运行于二叉树状态 后置条件动态演示赫夫曼树的创建 基本路径1. 操作者进入二叉树演示界面，用例开始； 2. 操作者向系统发出“演示赫夫曼树”请求； 3. 系统要求操作者输入信息； 4. 操作者输入信息完成后，并发出“确定”请求； 5. 系统自动根据输入信息建立相应的界面； 6. 操作者向系统发出“说明”请求； 7. 系统显示相关说明，系统转到 13 8. 操作者向系统发出“返回”请求； 9. 系统转到 2； 10. 操作者向系统发出“执行”请求； 11. 系统动态地演示操作者选择的请求； 12. 在系统演示未结束时，操作者是否向系统发出请求； A2：发出请求； 13. 用例结束； 14. 操作者向系统发出“重新输入信息”请求后，转到 3； 扩展路径A2：发出请求； 1. 操作者向系统发出“暂停”请求，系统将停止演示； B1：演示是否结束； 异常路径B1：演示是否结束； 毕业设计（论文）专用 纸 第 页17 1. 操作者向系统发出“继续”请求，系统将接着暂停的位 置继续执行转到 13； 2. 操作者向系统发出“恢复”请求，系统转到 5。 补充说明无 6)show TopoSort（演示拓扑排序） 用例编号 006 用例名称演示图 用例描述动态演示拓扑排序 参与者角色操作者 前置条件系统处于运行状态 后置条件动态演示拓扑排序 基本路径1. 操作者进入系统演示界面，用例开始； 2. 操作者向系统发出“演示拓扑排序”请求； 3. 系统要求操作者输入信息； A1：操作者对输入信息做出选择； 4. 操作者输入信息完成后，并发出“确定”请求； 5. 系统自动根据输入信息建立相应的界面； 6. 操作者向系统发出“说明”请求； 7. 系统显示相关说明，系统转到 13 8. 操作者向系统发出“返回”请求； 9. 系统转到 2； 10. 操作者向系统发出“执行”请求； 11. 系统动态地演示操作者选择的请求 12. 在系统演示未结束时，操作者是否向系统发出请求； A2：发出请求； 13. 用例结束； 毕业设计（论文）专用 纸 第 页18 14. 操作者向系统发出“重新输入信息”请求后，转到 3； 扩展路径A1：操作者对输入信息做出选择； 1. 操作者选择“随机建立”按钮； B1：发出请求； 2. 操作者选择“导入”按钮，操作者向系统发出“确定” 请求，导入一文件； A2：发出请求； 1. 操作者向系统发出“暂停”请求，系统将停止演示； B2：演示是否结束； 异常路径B1：发出请求； 1. 操作者向系统发出“确定”请求，系统转到 5； 2. 操作者选择“保存”按钮，操作者向系统发出“确定” 请求，保存该文件； B2：演示是否结束； 1. 操作者向系统发出“继续”请求，系统将接着暂停的位 置继续执行转到 13； 2. 操作者向系统发出“恢复”请求，系统转到 5。 补充说明无 7)show Sort（演示内部排序） 用例编号 007 用例名称演示内部排序 用例描述动态演示内部排序中的希尔排序和快速排序 参与者角色操作者 前置条件系统处于运行状态 毕业设计（论文）专用 纸 第 页19 后置条件动态演示内部排序中的希尔排序和快速排序 基本路径1. 操作者进入演示系统界面，用例开始； 2. 操作者向系统发出“演示内部排序”请求； 3. 系统要求操作者选择顺序表演示的是希尔排序还是快速 排序； A1： 操作者做出选择； 4. 操作者输入信息，并发出“确定”请求； 5. 系统自动根据输入信息建立相应的界面； 6. 操作者向系统发出“说明”请求； 7. 系统显示相关说明，系统转到 13 8. 操作者向系统发出“返回”请求； 9. 系统转到 2； 10. 操作者向系统发出“执行”请求； 11. 系统动态地演示操作者选择的请求； 12. 在系统演示未结束时，操作者是否向系统发出请求； A2：发出请求； 13. 用例结束； 14. 操作者向系统发出“重新输入信息”请求后，转到 4； 扩展路径A1： 操作者做出选择； 3. 操作者选择希尔排序的演示，显示相应的界面，转到 4； 4. 操作者选择快速排序的演示，显示相应的界面，转到 4； A2：发出请求； 3. 操作者向系统发出“暂停”请求，系统将停止演示； B1：演示是否结束； 毕业设计（论文）专用 纸 第 页20 异常路径B1：演示是否结束； 8) 操作者向系统发出“继续”请求，系统将接着暂停 的位置继续执行转到 13； 9) 操作者向系统发出“恢复”请求，系统转到 5。 补充说明无 2.2 非功能性需求分析 2.2.1 设计思想 课件是教学内容和教学处理两大类信息的有机结合，其目的是按某种学习理论和 教学策略将教学中的重点和难点，教学上不容易讲清楚的内容借助计算机演示。CAI 系统在注重教学先进性、科学性的同时更强调实用性。开发满足以下原则： 1)内容覆盖面宽：系统应覆盖该课程的主要内容，并结合课程选用教材，用 C 语言来描述数据结构的算法。 2)功能实用化：为了能真正起到辅助教学的效果，系统使用多种演示手段如用 单步跟踪、连续执行和跨越函数(或过程) 调用等方式来演示算法的具体执行 过程，且演示方式可随时更换；演示的速度可随时调节。 3)人机交互界面友好性：系统界面设计遵循实用、方便的原则，各种操作简洁 明了。同时具备鼠标接口和键盘接口，可接受来自于鼠标或键盘的输入；为 了加深对算法的理解，允许用户通过输入不同的初始数据来观察算法的具体 执行情况。 4)中文字幕提示：系统演示插入了适当的说明及注释信息，以帮助系统使用者 对演示过程的理解；为满足不同层次用户的需求，各种提示信息用中文给出。 5)系统运行环境及可靠性：在保证系统功能的前提下，适当地降低了系统对运 行环境的要求，以便系统可以在较低的配置系统软件环境中正常运行。对于 各种有意或无意的错误操作及错误的输入数据，系统能正确处理，保证系统 不会意外终止。 毕业设计（论文）专用 纸 第 页21 2.2.2 可行性分析 1)技术可行性研究 在 IT 行业中从业的工作人员一般都要求懂计算机，具有一定软硬件基础，会使用 各种管理软件，熟悉 IT 产品。因为该系统是针对数据结构算法的进行动态的演示，使 学生更能理解算法和培养学生的兴趣。又因为学数据结构这门课的老师和学生一般都 是计算机专业的学生，所以在新系统投入使用时，用户都能很快地使用该系统。 2)操作可行性研究 本系统采用 Windows 图形界面，是大家熟悉的操作系统，对于用户只需要具有一 般的计算机知识的人员都可以轻松上手。而且整个系统采用最友好的交互界面，简洁 明了，不需要对数据库的了解。由此，该系统的操作是可行的，有必要推广该系统！ 综合以上二方面，该系统具有很高的开发可行性，无论是从技术上还是操作上。 本章小结 本章重点介绍了基于 C#多线程技术的数据结构算法动态演示系统功能性需求分 析和非功能性需求分析。前者主要是对系统需求、系统总体结构图、用例的事件流描 述和用例图进行分析，后者主要描述了系统的设计思想和可行性分析。 毕业设计（论文）专用 纸 第 页22 第 3 章 系统详细设计 3.1 系统总体结构图 根据系统的需求，将系统划分为图 2.1 的结构图： 数据结构算法动态演示系统 顺 序 表 链 表 栈 二 叉 树 图 顺 序 表 插 入 顺 序 表 删 除 链 表 创 建 内 部 排 序 链 表 插 入 链 表 删 除 迷 宫 问 题 二 叉 树 遍 历 二 叉 树 线 索 化 赫 夫 曼 树 拓 扑 排 序 希 尔 排 序 快 速 排 序 先 序 遍 历 中 序 遍 历 后 序 遍 历 先 序 线 索 化 中 序 线 索 化 后 序 线 索 化 图 3.1 系统结构图 3.2 静态结构模型 进一步分析系统需求，识别出类以及类之间的关系，确定它们的静态结构和动态 行为，是面向对象分析的基本任务。系统的静态结构模型主要用类图或对象图来描述 8。 3.2.1 定义系统对象类 毕业设计（论文）专用 纸 第 页23 定义过系统需求，就可以根据系统需求来识别系统中所存在的对象7。系统对象 的识别可以通过寻找系统域描述和需求描述中的名词来进行，从前述的系统需求的描 述中可以找到的名词有顺序表（sqList） 、链表（linkList） 、二叉树遍历（OrderTree） 、 二叉树线索化（ThreTree） 、赫夫曼树（HuffmanCode） 、拓扑排序（TopoSort） 、内部 排序（Sort） ，这些都是对象图中的候选对象，判断是否应该为这些候选对象创建类的 方法是：是否有与该对象相关的身份和行为？如果答案是肯定的，那么候选对象应该 是一个存在与模型中的对象，就应该为之创建类。 1) 顺序表（sqList） 顺序表是没有身份的，但它具有相关的行为，系统要创建顺序表，可以演示顺序 表的插入和删除。所以顺序表是系统中的一个类，类名为 sqList。 2) 链表（linkList） 链表是没有身份的，但它具有相关的行为，系统要，可以演示链表的创建、插入 和删除。所以链表是系统中的一个类，类名为 linkList。 3) 二叉树遍历（OrderTree） 二叉树遍历是没有身份的，但它具有相关的行为，系统要创建二叉树，可以演示 二叉树的先序、中序和后序遍历。所以二叉树遍历是系统中的一个类，类名为 OrderTree。 4) 二叉树线索化（ThreTree） 二叉树线索化是没有身份的，但它具有相关的行为，系统要创建二叉树，可以演 示二叉树的先序、中序和后序线索化。所以二叉树线索化是系统中的一个类，类名为 ThreTree。 5) 赫夫曼树（HuffmanCode） 赫夫曼树是没有身份的，但它具有相关的行为，可以演示赫夫曼树的创建。所以 赫夫曼树是系统中的一个类，类名为 HuffmanCode。 6) 拓扑排序（TopoSort） 拓扑排序是没有身份的，但它具有相关的行为，系统要创建有向图，可以演示拓 毕业设计（论文）专用 纸 第 页24 扑排序。所以拓扑排序是系统中的一个类，类名为 TopoSort。 7) 内部排序（Sort） 内部排序是没有身份的，但它具有相关的行为，可以演示希尔排序和快速排序。 所以内部排序是系统中的一个类，类名为 Sort。 从上述分析，可以看出系统至少有 7 个重要的类：顺序表（sqList） 、链表 （linkList） 、二叉树遍历（OrderTree） 、二叉树线索化（ThreTree） 、赫夫曼树 （HuffmanCode） 、拓扑排序（TopoSort） 、内部排序（Sort） 。接着要确定这些类的属 性和方法。 1) 类 sqList transfer(string: str, sqList: String str; for(i=0;i=10;i+) str =“Step number“+ i.ToString()+“executed“; Thread.Sleep(500); /当前线程休眠(暂停)500ms 主程序中建立和启动线程： public class mainForm public delegate void DelegateStep(int s); public void startAlgorithmThread() m_algotithmThread=new Thread(new ThreadStart (this.ThreadFunction); /创建线程实例 毕业设计（论文）专用 纸 第 页46 m_algotithmThread.Start();/启动线程，即调用ThreadFunction线程函数 private void ThreadFunction() /线程函数 AlgorithmThread algorithmThread; algorithmThread=new AlgorithmThread(); algorithmThread.run();/调用AlgorithmThread的run函数，执行线程体 这样就在主线程 mainForm 中建立并启动了用户自定义线程 m_algotithmThread。 6) 线程同步 若一个对象同时被多个其他线程访问，则这多个线程之间在微观上存在先后执行 顺序的关联关系，这就是线程同步。在 C#里面用于实现线程同步的常用类有如下几类： Mutex 类，Monitor 类，lock 方法。 Manual(Auto)ResetEvent 类。 ReaderWriterLock 类。 c# Windows 应用程序中，在窗体上显示线程中处理的信息，需要在一个线程中引 用另一个线程中的窗体控件。常用办法是使用委托(delegate)完成这个工作，即在不是 创建控件的线程中直接创建一个委托实例，调用控件对象的 Invoke 方法，并传入需要 的参数，完成对其他线程中的控件的操作。 4.2 动态算法演示模板 数据结构算法演示系统采用 Windows 应用程序项目来创建，在算法演示系统的主 页上有启动各个算法的按钮，通过这些按钮启动每个算法演示界面。算法演示的图形 用户界面采用图 4.1 所示的模板。该模板有几个主要区域，每个区域对应一个组件。 毕业设计（论文）专用 纸 第 页47 1) 主窗口：包括标题栏和工具栏，用来实现系统控制。 2) 动画演示区：以图形和动画的方式模拟和显示算法执行的过程和结果。 3) 源代码区：用来显示类 C 语言编写的算法描述，为了更清楚地描绘算法的执 行过程，当程序运行到当前行时，用一条高亮度光带罩住此语句，表示该语 句被执行。 4) 变量当前值显示区：由控件 ListView 实现，负责当前演示算法的重要参数及 变化值的显示。 图 4.1 动态算法演示模板 4.3 算法演示的多线程设计 对一个具体的算法演示子模块，须满足执行、暂停、速度可调、任意时刻复位并 能重新执行等复杂切换控制功能，设计 AlgorithmThread 线程负责执行链表创建算法， 而在主线程(主窗口)中需要同步显示被执行到的源代码行和该行代码中涉及到变量的 当前值的获取和显示，这涉及到多线程间的同步和交互的问题。 毕业设计（论文）专用 纸 第 页48 用 ManualResetEvent 类来解决线程的同步和交互控制。具体使用 Invoke()、 ManualResetEvent、WaitOne()、Suspend()、Sleep()、Resume()等同步、交互技巧可以 实现专业的多线程程序，线程之间既解决了同步问题，又使线程之间的交互十分迅速。 下面以创建链表算法的动态演示(见图 4.1)为实例说明它的实现方法。其他算法 的实现与此相似。 有 2 个线程：主线程算法演示窗体所在的主线程 mainForm 和用户自定义线 程 AlgorithmThread。主线程 mainForm 主要负责显示算法演示窗体、启动执行自定义 线程 AlgorithmThread，调用 ListBox 控件显示源代码的方法，调用 ListView 控件显示 算法中变量和参数的当前值。线程 AlgorithmThread 负责执行链表创建算法和调用 DrawImage 类中绘制动画图形的方法 1824。 4.3.1 源代码同步演示的实现 为了看到算法的执行过程，算法的执行与算法的源代码显示应该同步进行。并在 源代码区显示读入的源代码，同时还要将当前正在执行的那条语句置成相反色。下面 以连续执行的演示方法的实现为例进行介绍6 9： 为实现连续执行的演示效果，使用上述 ManualResetEve