1、1 1本科毕业论文（20 届）数据结构算法演示系统的设计与实现所在学院专业班级 软件工程学生姓名指导教师完成日期2 2摘要数据结构不仅是大学计算机专业的核心课程之一,也是非计算机专业的主要选修课程之一。该课程理论性强又较为抽象,尤其是对算法描述的执行过程的理解是难点和重点。利用可视化图形效果来动态演示算法的执行过程,对学员深入理解教材内容、掌握基本的数据结构及相应算法的实现过程有很好的帮助作用,同时该系统可用于各种不同层次的教学，便于课上教师的讲解和课下学生的复习、自修。本文简要介绍了数据结构算法演示系统的项目开发背景和意义，着重阐述了该系统开发实现过程，从系统的需求分析、方案设计、模块设计、
2、数据结构设计、详细设计和实现等各个环节都进行了详尽的分析和描述。该系统采用汇编、C/C+等技术开发，具有操作便捷、形象生动等特点，对于深化对数据结构算法的理解，提高计算机程序设计水平具有很好的促进作用，而且具有一定的实用价值。关键词：数据结构，算法演示，C+，图形3 3Abstract“Data structure“ is not only one of the core courses in university computer professional, is also one of the main elective course for non computer majors. Th
3、e course theory and abstract, especially the execution process of the algorithm described the understanding is the emphasis and difficulty in. The implementation process using visual effects to the algorithm dynamic demonstration, the realization process master the basic data structure and the corre
4、sponding algorithm are very helpful for students in-depth understanding of teaching content, at the same time, the system can be used for a variety of different levels of teaching, for students to teach classes teacher explanation and class review, self-study.This paper briefly introduces the projec
5、t development background and significance of data structure algorithm demonstration system, emphatically elaborated the system development process, from the system needs analysis, program design, module design, data structure design, detailed design and implementation of all aspects of a detailed an
6、alysis and description. The system uses the assembly, C/C+ technology, has convenient operation, vivid image characteristics, to deepen the understanding of data structure algorithm, has the very good role in promoting to improve the design level of computer program, and has certain practical value.
7、Keywords：Data structure, algorithm demo, C+,graphics1 1目录1 绪论 .11.1 背景和意义 .11.2系统目标 .11.3 可行性分析 .11.3.1. 经济可行性分析 .11.3.2. 技术可行性分析 .21.3.3. 社会可行性分析 .22技术介绍及开发环境 .22.1汇编技术简介 .22.2图形学技术简介 .32.3 C/C+语言简介 .32.4开发环境 .42.4.1 Broland C+编译器 .42.4.2 Editplus .42.4.3 make工具 .42.4.4 操作系统 .43 系统分析 .43.1 需求分析 .43
8、.2 系统功能 .53.2.1系统功能描述 .53.2.2系统功能图 .54 系统设计 .64.1图形库设计 .64.1.1图形库需求分析 .64.1.2图形库设计 .64.2类图设计 .74.3 UI界面设计 .85 系统实现 .95.1链表算法演示 .95.1.1 创建 .95.1.2遍历 .135.1.3插入 .145.1.4删除 .155.2二叉树算法演示 .175.2.1 创建 .175.2.2遍历 .19总结 .21致谢 .22参考文献 .231 11 绪论1.1 背景和意义数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数
9、据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。数据结构课程的主要目的是介绍一些常用的数据结构，阐明数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种数据结构，讨论对它们实行的各种运算的实现算法。很多算法实际上是对某种数据结构施行的一种变换，研究算法也就是研究在实施变换过程中数据结构
10、的动态性质。数据结构，作为计算机学科的基础性专业课程，其在计算机科学中的及其重要，课程学习的好坏，直接关系到学员后期计算机水平的高低。而这门课程一直因为过于抽象，难以理解，而让人望而止步。如果能够把这门抽象的课程变得具体而生动，必将提高学习人员兴趣，增加其积极性和主动性，也有利于人员的对此课程的学习。基于这些目的，我开发了这个数据结构算法演示系统，数据结构是我所做的系统的主要理论基础，我完成了线性表、堆栈、队列、树、图几个主要结构，在学习数据结构这门课程的时候，我了解了这些结构的算法，当时也做过一些相关的程序，在此基础之上，我运用 BrolandC+开发工具，把这些算法演示出来。数据结构算法演
11、示系统可以演示线性表、堆栈、队列、树、图等几个基础结构的算法，辅助一些算法说明，让使用者更好地掌握算法，在帮助中把演示的具体过程和操作做详细的介绍。该系统具有操作简单、形象生动，能很好地改善人员对数据结构课程的学习理解，从很大程度上提高人员的学习质量和效率。1.2系统目标课题实现一个基于 dos 系统（windows 的模拟 dos）的数据结构算法演示系统。系统主要要求模拟演示单链表、栈、队列、二叉树、图、查找、排序等数据结构中典型算法的执行过程。根据此要求每一个算法设计为一个模块，每一模块中都通过动画详细演示了算法的执行过程。1.3 可行性分析1.3.1. 经济可行性分析主要是对项目的经济效
12、益进行评价，一方面是支出的费用，其中包括设备购置费，软件开发费，管理和维护费，人员工资和培训费等。另一方面是取得的收益中可以用钱2 2来衡量的那部分（收益的另一部分难以用钱来表示） 。基于企业的现有计算机及配套设备，部署系统，可以在教学中减少很大的工作量，所以从人力、物力、财力方面来说都是可行的。1.3.2. 技术可行性分析技术上的可行性分析主要分析现有技术条件能否顺利完成开发工作，软硬件配置能否满足开发者需要等，这一特点非常适合计算机的特点，发挥计算机的数据处理速度快，准确率高的优势，现代计算机硬件和软件技术的飞速发展，为系统的建设提供了技术条件。由于对算法演示这一类的教学系统进行开发已有一
13、定的时期，有很多成功的实例，技术基础也已经非常雄厚，因而技术上的准备应该不成问题。1.3.3. 社会可行性分析社会可行性有时也称为操作可行性，主要论证新系统在机构开发和运行的可能性以及运行后可能一起的对教学的影响，即组织内外是否具备接受和使用新系统的条件。在当前信息技术飞速发展的大环境下，计算机技术和软件技术的更新使人们完全有可能也有能力采用这样先进的技术。在某种意义上，信息与科技在现代化建设中显现出越来越重要的地位。好的演示系统对教学效果有很大的促进意义。2技术介绍及开发环境2.1汇编技术简介为了克服机器语言的缺点，人们采用便于记忆、并能描述指令功能的符号来表示指令的操作码。这些符号被称为指
14、令助记符。助记符一般是说明指令功能的英语词汇或者词汇的缩写。同时也用符号表示操作数，如 CPU的寄存器、存储单元地址等。由于汇编语言使用指令助记符和符号地址，所以它要比机器语言容易掌握得多。与高级语言相比较，汇编语言有如下特点： 汇编语言与机器关系密切汇编语言与机器所带飞 CPU有着十分密切的关系。对于各种不同类型的 CPU，要使用各种不同的汇编语言，此系统使用的是 8086汇编。汇编语言可以直接操作硬件进行工作。 汇编程序效率高用汇编语言编写的源程序在汇编后所得的目标程序效率高。这种目标程序的高效率反应在时间和空间两个方面：其一是运行速度快；其二是目标程序短。在采用相同算法的前提下，任何高级
15、语言程序在这两方面的效率都不如汇编程序，许多情况下更是远远不及。汇编程序能获得“时空”高效率的主要原因是：构成汇编语言主体的汇编格式指令是机器指令的符号表示，每一条汇编格式指令都是所对应的某条机器指令的“化身”;另一个重要原因是汇编程序能直接并充分利用机器硬件系统的许多特性。 编写繁琐、调试困难3 3程序员在利用汇编语言编程程序时，必须考虑包括寄存器、存储单元和寻址方式在内的几乎所有细节问题。例如：指令执行对标志的影响，堆栈设置的位置等。调试汇编程序往往要比调试高级语言程序困难。汇编格式指令的功能有限和程序员要注意太多的细节问题是造成这种困难的两个客观原因；汇编语言提供给了程序员最大的“舞台”
16、而程序员往往为了追求“时空”上的高效而不顾程序的结构，这是在成调试困难的主观原因。2.2图形学技术简介算机图形学（Computer Graphics，简称 CG） ，狭义上是一种研究基于物理定律、经验方法以及认知原理，使用各种数学算法处理二维或三维图形数据，生成可在计算机等显示设备上显示的可视化数据的科学。它是计算机科学的一个分支领域与应用方向。广义上来看，计算机图形学不仅包含了从三维图形建模、绘制，到生成动画的过程，同时也包含了对二维向量图形以及图像视频融合处理的研究。计算机图形学的研究内容非常广泛，如图形硬件、图形标准、图形交互技术、光栅图形生成算法、曲线曲面造型、实体造型、真实感图形计算
17、与显示算法、非真实感绘制，以及科学计算可视化、计算机动画、自然景物仿真、虚拟现实等。简单地说，计算机图形学的主要研究内容就是研究如何在计算机中表示图形、以及利用计算机进行图形的计算、处理和显示的相关原理与算法。图形通常由点、线、面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。从处理技术上来看，图形主要分为两类，一类是基于线条信息表示的，如工程图、等高线地图、曲面的线框图等，另一类是明暗图，也就是通常所说的真实感图形。计算机图形学一个主要的目的就是要利用计算机产生令人赏心悦目的真实感图形。为此，必须建立图形所描述的场景的几何表示，再用某种光照模型，计算在假想的光源、纹理、材质属性下的光
18、照明效果。所以计算机图形学与另一门学科计算机辅助几何设计有着密切的关系。事实上，图形学也把可以表示几何场景的曲线曲面造型技术和实体造型技术作为其主要的研究内容。同时，真实感图形计算的结果是以数字元元图像的方式提供的，计算机图形学也就和图像处理有着密切的关系。2.3 C/C+语言简介C语言是当今最流行的程序设计语言之一，它的功能丰富、表达力强、使用灵活方便、应用面广、目标程序高、可植入性好，既有高级语言的特点，又有低级语言的许多特点，适合作为系统描述语言，既可以用来编写系统软件，也可以用来编写应用软件。C语言诞生后，许多原来用汇编语言编写的软件，现在都可以用C语言编写了（如UNIX操作系统） ，
19、而学习和适用C语言要比学习和适用汇编语言容易得多。C语言是一种结构化语言。它层次清晰，便于按模块化方式组织程序，易于调试和维护。C 语言的表现能力和处理能力极强。它不仅具有丰富的运算符和数据类型，便于实现各类复杂的数据结构。它还可以直接访问内存的物理位元址，进行位(bit)一级的操作。由于C语言实现了对硬件的编程操作，因此C语言集高级语言和低级语言的功能于一体。既可用于系统软件的开发，也适合于应用软件的开发4 4在C的基础上，一九八三年又由贝尔实验室的Bjarne Strou-strup推出了C+。C+进一步扩充和完善了C语言，成为一种面向对象的程序设计语言。C+目前流行的编译器最新版本是Bo
20、rlandC+4.5,SymantecC+6.1,和MicrosoftVisualC+2012。C+提出了一些更为深入的概念，它所支持的这些面向对象的概念容易将问题空间直接地映像到程序空间，为程序员提供了一种与传统结构程序设计不同的思维方式和编程方法。因而也增加了整个语言的复杂性，掌握起来有一定难度。但是，C 是C+的基础，C+语言和C语言在很多方面是兼容的。因此，掌握了C语言，再进一步学习C+就能以一种熟悉的语法来学习面向对象的语言，从而达到事半功倍的目的。2.4开发环境此次的开发并未使用一套完整的IDE开发环境，通过一些工具的拼合组成了此系统的开发环境2.4.1 Broland C+编译器
21、Broland C+，一个当年在 dos 平台叱咤风云的编译器，具有高速的编译，连接和执行速度，但其自带的集成开发环境不是太好用2.4.2 EditplusEditPlus（文字编辑器）是一套功能强大，可取代记事本的文字编辑器，拥有无限制的撤销与重做、英文拼字检查、自动换行、列数标记、搜寻取代、同时编辑多文件、全屏幕浏览功能2.4.3 make工具当源文件很多时，我不想在修改了一个档后，还要重新编译所有的源文件，这是make 这个小工具可以帮到我。这个檔决定了源文件之间的依赖关系。而且决定了源文件什么时候该编译什么时候不应该编译。2.4.4 操作系统演示系统运行于 dos5.0 及其以上的兼容
22、系统中3 系统分析3.1 需求分析做为一个数据结构演示系统，首先我确定要演示的内容，在本系统中，我对线性表、堆栈和队列、树、图几个主要数据结构做了讲解；接着，对这几种算法的说明也是必不可少的，这样配合演示，可以达到更好地效果；最后，作为我设计的演示过程，使用者5 5对操作不是太了解，我有必要做个详细的操作过程，让使用者更好地使用系统。3.2 系统功能系统由数据结构、操作、帮助、程序四个部分组成。现分述如下：数据结构由线性表、堆栈和队列、树、图、查找、排序 7 个部分组成，分别对应数据结构的各个部分。线性表又分为链表概念、链表模型、链表操作、双向链表四个部分，堆栈和队列分为基本堆栈、基本队列、循
23、环队列三个部分，树分为数据二叉树、结构二叉树、类二叉树，图分为图表示、图搜索、最短路径。操作由线性表说明、堆栈说明、队列说明、树说明、图说明组成，对各数据结构的算法说明。帮助由关于和帮助组成，是本系统的一些说明和对演示过程的操作详细说明。程序部分由主接口和退出组成，完成系统的起始和终止。3.2.1系统功能描述此系统需要完成功能主要有： 链表演算法演示，包括创建、插入、删除、查找，遍历。 栈算法演示，包括创建，出栈，入栈。队列算法演示，包括创建、入队、出队。二叉树算法演示，包括创建，遍历，线索化，查找，删除，插入。图算法演示，包括创建、增加、删除、遍历。查找和排序，包括基本的排序和查找算法。3.
24、2.2系统功能图主页进入单链表 栈队列二叉树 图关于 帮助 退出查找 、 排序创建遍历删除插入创建入栈出栈取栈顶创建入队出队取队首创建遍历线索插入创建遍历插入删除冒泡简单二分删除图 3-1 系统功能图6 64 系统设计4.1图形库设计4.1.1图形库需求分析图形库支持基本绘图、多种格式图形显示、鼠标操作、时钟、音频播放、多种字体的汉字及英文显示等等特性；可以工作于高分辨率下（比如 800X600、1024X768 甚至1280X1024） ；而且，它支持最高 24 位的各种色深！并拥有不错的处理速度。它主要拥有以下特性： 支持 320X200，640X400，640X480，800X600，1
25、024X768，1280X1024 等各种标准分辨率，以及各种诸如 320X240，320X400，512X512 等 ModeX分辨率； 全面支持 8位 256色，15 位 32768色，16 位即 65536色三种色深模式， 较为齐全的基本的绘图函数，让你轻松绘制象点、线、方、圆等各种简单的图形； 支持多种格式图形的显示，在这一版里，支持 BMP、ICO 和 CUR的显示。 支持鼠标操作，并集成一套功能强大高级鼠标控制函数，譬如能够检测双击，还支持使用 ICOCUR文件作为鼠标游标； 拥有一套高级键盘处理函数，用户可以通过安装键盘中断来使用它们； 集成时钟控制模块； 可以显示多种字体的英文
26、和中文，并支持一些常用的文字特效； 支持矩形输出裁剪，让动画等各种显示特效均成为可能； 支持类似 Borlandgraphics.h中库函数的作图模式，譬如 XOR异或模式； 相容 Borlandgraphics.h中的大部分函数以方便将原来使用 graphics.h的程序移植过来； 强大的错误处理系统，能根据用户的设置决定输出错误信息的方式，譬如直接在屏幕上显示还是输出到错误日志，或者仅仅只用喇叭报一下警； 强大快速的调色板操作函数，可以实现淡出淡入特效，还能够使用 8位色彩分量长的调色板，还可以实现 64级调色板之间的过渡； 提供了多图形缓冲页架构，并支持高效率的硬件换页机制和滚屏机制； 支持诸如翻折，灰度，半透明，模糊，反色，颜色加强等多种图形显示特效； 全面支持 Borland全系列 CC+编译器。4.1.2图形库设计图形库这一部分代码可以用汇编好 C 语言进行编写，主要模块如下： 图形模式通过调用 vbe 提供的 dos 中断，我可以修改屏幕的分辨率为300*200、640*480、1024*768 等模式。例如调用 int10h 的 0X117 子功能可以设置屏幕为1024*76824bit 色模式下。 基本绘图函数基本绘图，都是可以通过点来的不同排列来实现。故画点函数的实现需要重点优化，
