《数据结构》中典型算法的动态演示毕业设计论文

PAGEPAGE44目录TOC\o"1-3"\u中文摘要 III英文摘要 IV前言 11绪论 21.1问题背景 21.2开发环境 21.3开发工具简介 21.3.1C语言图形程序设计 21.3.2图形模式下的汉字显示 51.3.3Turboc(V2.0)编译错误信息 61.4其它相关工具软件 71.4.1Dos屏幕下程序截图工具介绍及Dos抓图技巧 71.4.1拓扑图制作工具亿图V1.6.3 72需求分析 82.1问题定义 82.1.1问题分析 82.1.2用户目标 82.2系统的功能需求 82.2.1正确表达算法 82.2.2功能实用化 82.2.3具体演示功能 82.3系统的其他需求 92.3.1界面友好性 92.3.2系统的运行环境及可靠性要求 93概要设计 103.1方案确定 103.2系统结构 103.2.1系统结构总框图 103.2.2模块功能说明 113.2.3算法演示子模块中要注意的问题 114详细设计 124.1数据设计 124.2系统主程序界面设计 124.3演示模块流程图 124.3.1冒泡演示流程图 124.3.2汉诺塔演示流程图 144.3.3二叉树演示流程图 154.3.4单链表演示流程图 165系统功能实现 175.1欢迎界面模块编码 175.2主程序模块编码 195.3冒泡排序模块编码 225.4汉诺塔模块编码 245.5二叉树遍历模块编码 295.6链表模块编码 335.7退出模块编码 366系统测试 396.1系统测试常用的测试方法 396.2测试范围与主要内容 396.3黑盒测试用例 396.4测试报告 406.5改进建议与措施 40结束语 41参考文献 42致谢 43《数据结构》中典型算法的动态演示计算机科学与技术专业刘俊坤指导老师：符开耀摘要：数据结构作为计算机专业的一门综合性专业基础课，对后续课程的学习极其重要。但该课程涉及大量的概念、定义、模型和算法，显得很抽象和深奥。在教学过程中，如果能加以计算机辅助教学，可以提高教学效果，所以编写这样的程序不仅有助于学习数据结构，同时也大大增强了学生的学习兴趣，提高学生的编程能力。这是因为，一方面利用算法演示系统的生动性和直观性，使教学内容条理化和形象化，降低了对知识理解的难度；另一方面，由于演示系统的趣味性和交互性，有利于激发学生浓厚的学习兴趣，使其愿学、乐学。本系统以清华大学出版社出版的C语言版《数据结构》为蓝本，合理地选择数据结构中四个经典算法并在系统中进行有机地组合,形成优化的动态演示系统。它可适应读者对算法的演示数据和过程执行的控制方式的不同需求,在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行过程中栈的变化状况。可视化是演示系统应该具备的要求。本系统采用C语言图形编程技术来实现软件的可视化。因为C语言的图形编程对大多数人来说比较陌生，甚至让人误解C不能进行图形编程。通过本系统的设计，让大家知道C语言也可以进行图形编程，从而进行可视化设计与开发。关键词：算法；动态演示；图形编程；可视化Thedynamicdemonstrationoftypicalalgorithminthe"DataStructures"ComputerScienceandTechnologyLiuJunkunTutor:FuKaiyaoAbstract：Asone

computer-specializedcomprehensivebasiccourse,theconstructionofdataisextremelyimportanttothefollowingcurriculumstudy.Becausethiscurriculuminvolves

massiveconcepts,

definitions,

modelsand

operationalgorithms,thus

itseemsveryabstractandabstruse.Intheteachingprocess,however,ifit

beperformedthroughcomputer-aidedinstruction,itmay

improvetheteachingeffect,thereforecompilingsuchprocedurescannotonlybehelpfultothestudyofconstructionofdata,butalsogreatlystrengthenthestudent'sstudyinterest,sharpenthestudent'sprogrammingability.Thisisbecause,ontheonehand,algorithmdemonstrationsystem'svividnessanddirect-viewing,makethecontentinorderland

visual,reducetheknowledgeitselfdifficultydegree;Ontheotherhand,interestandtheinteractionasaresultofthedemonstrationsystem,

areadvantageoustostimulatethestudents’strongstudyinterest,causethemtobewillingto

study.ThissystemtakesQinghuaUniversitypublishinghousepublicationClanguageversion"Constructionofdata"asamainsource,reasonablychoosesfourclassicalalgorithmsintheconstructionofdataandcarriesoninthesystemorganicallycombinations,formstheoptimizeddynamicdemonstrationsystem.Itmayadaptthereaders’differentdemandstothealgorithmdata-inandcontrolmodestheprocessexecution,anddemonstratesinthealgorithmimplementationonthecomputerscreenthedatalogicalorganizationeitherthememorystructurechangeconditionorthestackchangeconditionintherecursionalgorithmimplementation.Visualizationdemonstrationsystemshouldbeavailable.ThesystemusedCprogramminglanguagegraphicssoftwaretechnologytoachievethevisualization.Cprogramminglanguageforgraphicsis

unfamiliar

tous,

orweevenmisleadC

notfor

graphicsprogramming.Throughthedesignofthissystem,weknowCprogramminglanguagecanbegraphic,andcancarryoutvisibledesign.Keywords:Datastructures;Dynamicdemonstration;Graphprogramming;Visible前言学习编写计算机程序设计仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法，这些都是数据结构研究的内容，也是我们进行计算机程序设计的重要基础。由于数据结构的原理和算法比较抽象，因此要理解和掌握其中的原理就比较困难。本文通过对几个经典算法的研究，并进行动态演示，使得能更好地了解算法的来龙去脉，更好地理解算法，抓住算法的本质，因而更好地学习数据结构这门课程。本文的目的是将抽象算法转为形象的演示。本文从软件工程的角度出发，严格按照软件开发的基本步骤，开发了一个数据结构中几个典型算法的可视化演示系统，并给出了C语言实现各功能模块的思想及相关核心代码，充分体现了C语言知识的综合运用，特别是平时大家接触较少的图形编程。由于编程水平有限以及时间仓促，故本系统难免有各种各样的不足，希望各位老师和朋友提出意见，在此衷心感谢！1绪论1.1问题背景数据结构是一门比较难学的课程，在教学过程中，如果能加以计算机辅助教学，可以提高教学效果，所以编写这样的程序不仅有助于学习数据结构，同时也大大增强了学生的学习兴趣，提高学生的编程能力。由于数据结构的原理和算法比较抽象，因此要理解和掌握其中的原理就比较困难。本系统通过对几个经典的算法进行动态演示，让人能更好地了解算法的来龙去脉，更好地理解算法，抓住算法的本质，从而更好地学习数据结构这门课程。1.2开发环境开发环境：TurboC(V2.0)运行环境：Windows98/2000/XP/DOS系列平台1.3开发工具简介1.3.1C语言图形程序设计计算机图形程序设计是程序设计中比较困难而且又吸引人的部分。为了方便用户设计图形程序，不同版本的C语言编译程序提供了许多图形的库函数。用户在设计图形程序时，只需要调用相应的库函数即可。在ANSIC中没有对图形库函数的要求，各版本的C语言编译环境图形库函数都不相同，下面以Turboc2.0的图形库来介绍图形程序设计[2]。Turboc2.0为用户提供了一个功能很强的图形函数库，又称为Borland图形接口（BGI）。编写图形程序时用到的一些图形库函数均包括在graphics.lib中。用到这些函数时，必须把图形头文件graphics.h包含进来[6]。计算机显示器的显示模式按功能可以分为字符模式和图形模式两大类。因此要进行图形编程，首先要对图形模式进行初始化。不同的显示器适配器有不同的图形分辨率。即使是同一显示器适配器，在不同模式下也有不同分辨率。因此，在屏幕作图之前，必须根据显示器适配器的种类将显示器设置成为某种图形模式。在未设置图形模式之前，微机系统默认屏幕为文本模式(80列，25行字符模式)，此时所有图形函数均不能工作。设置屏幕为图形模式，可用下列图形初始化函数：voidfarinitgraph(intfar*gdriver，intfar*gmode，char*path);其中gdriver和gmode分别表示图形驱动器和模式，path是指图形驱动程序所在的目录路径。图形驱动程序由TurboC出版商提供，文件扩展名为．BGI。根据不同的图形适配器有不同的图形驱动程序。例如对于EGA、VGA图形适配器的图形驱动程序为EGAVGA.BGI。有时编程者并不知道所用的图形显示器适配器种类，而且我们为了将编写的程序可以用于不同图形驱动器，增强程序的通用性，我们通常不指定图形显示器适配器种类，而使用TurboC提供了一个自动检测显示器硬件的函数，其调用格式为：voidfardetectgraph(int*gdriver,*gmode);例1：自动进行硬件测试后进行图形初始化[2]#include"graphics.h"main(){intgdriver,gmode;detectgraph(&gdriver,&gmode);/*自动测试硬件*/printf("driveris%d,modeis%d\n",gdriver,gmode);/*输出结果*/getch();initgraph(&gdriver,&gmode,"");/*根据测试结果初始化图形*/circle(320,240,50);getch();closegraph();}上例程序中先对图形显示器自动检测，然后再用图形初始化函数进行初始化设置。其中，closegraph()为退出图形状态的函数，其调用格式为：voidfarclosegraph(void)；调用该函数后可退出图形状态而进入文本方式，并释放用于保存图形驱动程序和字体的系统内存。同时TurboC提供了一种更简单的初始化图形的方法，即用gdriver=DETECT语句后再跟initgraph()函数就行了。比如，上例可改为如例2的情形[2]。例2：对例1的修改#include"graphics.h"main(){intgdriver=DETECT,gmode;initgraph(&gdriver,&gmode,"");circle(320,240,50);getch();closegraph();}对图形模式进行了初始化后，接下来要进行的工作是对于图形模式的屏幕颜色设置以及如何清屏。对于图形模式的屏幕颜色设置，分为背景色的设置和前景色的设置。在Turboc中分别使用以下两个函数：背景色设置函数：voidfarsetbkcolor(intcolor);该函数将使背景按照参数color指定的颜色来进行显示。前景色设置函数：voidfarsetcolor(intcolor);该函数将使前景按照参数color指定的颜色来进行显示。清除图形屏幕内容使用清屏函数，其调用格式如下voidfarcleardevice(void);该函数清除整个屏幕的内容，可以在绘图前调用这个函数进行清屏或者在画新图形时调用该函数清除以前画的图形。有关颜色设置、清屏函数的使用请看例3的示例[2]。例3：清屏函数的使用#include"stdio.h"#include"graphics.h"main(){intgdriver,gmode,i,j;gdriver=DETECT;initgraph(&gdriver,&gmode,"");/*图形初始化*/setbkcolor(0);/*设置图形背景*/cleardevice();setcolor(1);/*设置不同作图色*/circle(319,239,20);/*画圆*/setbkcolor(1);/*设置不同背景色*/cleardevice();}getch();closegraph();}另外，TURBOC也提供了几个获得现行颜色设置情况的函数。intfargetbkcolor(void);返回现行背景颜色值。intfargetcolor(void);返回现行作图颜色值。intfargetmaxcolor(void);返回最高可用的颜色值。接下来介绍一些基本的图形函数：画点函数：voidfarputpixel(intx,inty,intcolor);画线函数：Turboc提供了一系列画线函数，下面介绍其中最常用的一种：voidfarline(intx0,inty0,intx1,inty1);画(x0,y0)到(x1,y1)的直线。图形填充函数：voidfarsetfillstyle(intpattern,intcolor);color的值是当前屏幕图形模式时颜色的有效值。图形模式下的文本输出函数：voidfarouttextxy(intx,inty,charfar*textstring);该函数输出字符串指针textstring所指的文本在规定的(x,y)位置。其中x和y为象元坐标。1.3.2图形模式下的汉字显示在编写一些应用软件时，为了使软件更为通俗浅显、易学易用，具备汉字的用户界面是必不可少的条件。在文本模式下，只要有汉字操作系统的支持，显示汉字是不成问题的。只要用printf或cprintf就可以了。在图形模式下显示汉字就稍稍麻烦些。我们可以定义一个函数来用于汉字的显示。这个函数不需要汉字系统的支持，但用到其中的字库文件[2]。下面我看一个例子是如何实现汉字显示的。例4：图形模式下16点阵汉字的显示voidHZ16(intx0,inty0,intw,intcolor,char*s)/*横坐标,纵坐标,字间隔,汉字颜色,汉字字符串*/{FILE*fp;registercharbuffer[32];registercharstr[2];unsignedlongfpos;/*fpos为最终偏移动量*/registerinti,j,k;fp=fopen("hzk16","r");/*打开16*16汉字库*/while(*s)/*一直到字符串结束为止*/{if(*s<0)/*汉字输出*/{str[0]=(*s)-0xa0;str[1]=*(s+1)-0xa0;fpos=((str[0]-1)*94+(str[1]-1))*32L;/*计算汉字在hzk16的偏移量*/fseek(fp,fpos,SEEK_SET);/*指针移动到当前位置*/fread(buffer,32,1,fp);/*读取一个汉字到数组中*/for(i=0;i<16;i++)/*16行*/for(j=0;j<2;j++)/*两个字节*/for(k=0;k<8;k++)/*8位*/if(((buffer[i*2+j]>>(7-k))&0x1)!=NULL)/*是一就画点*/putpixel(x0+8*j+k,y0+i,color);s+=2;/*一个汉字占两个字节，现在将指针移动两个字节*/x0+=w;/*显示坐标也按照间隔移动*/}else/*显示非汉字字符*/{settextstyle(0,0,1);setcolor(color);str[0]=*s;str[1]=0;outtextxy(x0,y0+7,str);/*显示单个字符*/x0+=w-7;/*显示单个字符后的x坐标变化*/s++;/*指针移动到下一个字节*/}}fclose(fp);/*关闭16*16汉字库*/}1.3.3Turboc(V2.0)编译错误信息为了帮助读者调试程序和分析程序，下面简单介绍程序出错的种类[1]。Turboc(V2.0)的源程序错误分为三种类型：致命错误、一般错误和警告。其中，致命错误通常是内部编译出错；一般错误指程序的语法错误、磁盘或内存存取错误或命令行错误等；警告则只是指出一些得怀疑的情况，它并不防止编译的进行。下面按字母顺序A～Z分别列出致命错误及一般错误信息，英汉对照及处理方法：(1)致命错误英汉对照及处理方法：A-B致命错误Badcallofin-linefunction(内部函数非法调用)分析与处理：在使用一个宏定义的内部函数时，没能正确调用。一个内部函数以两个下划线(__)开始和结束。Irreducableexpressiontree(不可约表达式树)分析与处理：这种错误指的是文件行中的表达式太复杂，使得代码生成程序无法为它生成代码。这种表达式必须避免使用。Registerallocationfailure(存储器分配失败)分析与处理：这种错误指的是文件行中的表达式太复杂，代码生成程序无发把它生成代码。此时应简化这种繁杂的表达式或干脆避免使用它。(2)一般错误信息英汉照及处理方法详见参考文献[1]1.4其它相关工具软件1.4.1Dos屏幕下程序截图工具介绍及Dos抓图技巧现在的抓图软件基本上都只能在Windows下运行，可有时候我们还需要在纯DOS下（注意：不是Windows中的DOS模式）进行屏幕抓取工作。可以通过安装虚拟机来解决这个问题，但是很麻烦，怎么办呢？下面介绍一个工具Graffix，帮你完成纯DOS下的截图任务。用Graffix完成抓图操作一般情况下都要分成两个主要步骤：先将屏幕捕捉AT格式然后用附带的转换工具将ATF格式转换为GIF或者PCX图像格式。（1）ATF文件的获得①进入纯DOS后，在命令行后输入“DGFX”并回车，将出现用法提示（图1），可以看到抓取热键是“Ctrl+ALT＋空格键”。从内存卸载此程序的命令是“DGFX/U”。②运行需要抓图的程序，出现待抓画面后，按下热键，屏幕弹出提示（图2），输入文件名后按F1键可以将画面抓取为ATF格式，如果直接按Enter键，则得到的是TXT文本格式。（2）将ATF转换为GIF/PCX图像格式ATF格式的图片不能被Windows下应用程序所识别，因此我们需要将前面抓取到的ATF格式转换为GIF或者PCX格式。①在DOS提示符后输入“A2B”，回车，输入ATF文件名，之后在屏幕上会显示该ATF文件的内容。②再次按下热键“CTRL+ALT+空格”，会出现“SAVEINWHICHFORMATGIFORPCX（G/P）”的提示（询问你是将文件保存为GIF还是PCX格式），此时若按下字母G，则通过下面的步骤会将ATF转换为GIF格式；如按字母“P”则可得到PCX格式。③输入最终要得到的文件的主文件名并回车。现在进入软件目录看看，是不是得到所需要的GIF或PCX图像文件了？若要抓取的程序画面本身是图形模式，则将直接得到GIF或PCX图像格式的文件，从而可以省略转换步骤。1.4.1拓扑图制作工具亿图V1.6.3亿图是一款类似Visio的流程图、网络图绘制软件，新颖小巧，功能强大，可以很方便的绘制各种专业的业务流程图，程序流程图，数据流程图，网络拓扑图等。它在设计时采用全拖曳式操作，最大限度的简化用户的工作量，方便易用；提供各种图形模板库，方便专业人士的使用；提供强大的图文混排和所见即所得的图形打印。2需求分析2.1问题定义2.1.1问题分析本系统要完成的工作是通过对数据结构中经典算法的模拟，经用户输入数据和对数据处理后最终以图形的方式实时显示在屏幕上，从而使得抽象的算法形象化、生动化。用户通过使用这个动态的演示软件就能很好的理解算法的含义。2.1.2用户目标本系统可适应读者对算法的输入数据和过程执行的控制方式的不同需求,在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行过程中栈的变化状况。整个系统使用键盘操作和菜单驱动方式。每个菜单项对应一个动作或一个子菜单。系统一直处于选择菜单项或执行动作状态,直到选择了退出动作为止。用户的目标也就是该演示系统所希望达到的目的。2.2系统的功能需求系统的功能需求也即是本系统要实现的具体内容。算法演示系统要求能够动态演示《数据结构》中的算法的执行过程。用户可以自由选择演示的算法，且在执行某一个特定算法操作演示前提示用户输入操作元素及操作方法。由于时间有限而要演示的算法很多，故这里我以几个经典算法为例子，实现它们的动态演示并掌握这种方法，起到抛砖引玉的作用，希望大家能够不断完善这个系统。本系统要演示的内容包括四个经典算法：冒泡排序、汉诺塔的递归算法、单链表建立和二叉树的建立与遍历，由主界面菜单显示。2.2.1正确表达算法这是最基本的一项要求，算法演示的目的本来就是让大家更好地学习理解算法，演示只是一种手段，目的是降低知识难度，传递知识，因此首先得保证知识的正确性。2.2.2功能实用化为了真正起到深入理解算法的效果，系统使用多种演示手段如单步跟踪和连续执行等多种调用方式来演示算法的执行过程。为了针对用户的各种需要，演示的速度可以由用户自己调节。2.2.3具体演示功能冒泡排序算法=1\*GB3①选择系统自动产生随机数据和手动输入数据两种方式；=2\*GB3②选择自动排序和手动单步排序两种方式；=3\*GB3③屏幕上显示算法执行过程并输出所有排序序列。汉诺塔递归算法=1\*GB3①任意输入演示的个数；=2\*GB3②选择电脑自动演示和手动单步执行两种方式；=3\*GB3③若选择电脑自动演示请输入速度；=4\*GB3④屏幕上显示算法执行过程。单链表=1\*GB3①自由输入接点数据；=2\*GB3②屏幕上显示算法执行过程并输出单链表。二叉树算法=1\*GB3①选择系统自动产生随机二叉树和手动输入数据产生两种方式；=2\*GB3②选择电脑自动演示和手动单步执行两种方式；=3\*GB3③屏幕上显示算法执行过程并输出三种遍历序列。2.3系统的其他需求2.3.1界面友好性系统界面设计遵循实用、方便的原则，各种操作简单明了。系统具备键盘接口，接受键盘输入。为了加深对算法的理解，可允许用户通过输入不同的初始数据来观察算法的具体的执行情况。系统演示插入了适当的说明和注释信息，以帮助使用者对演示过程的理解，为满足各种不同层次用户的要求，各种提示信息用中文方式。2.3.2系统的运行环境及可靠性要求在保证了系统功能的前提下，适当降低了对系统运行环境的要求，以便系统可以在配置较低的软件环境中运行。对各种有意或无意的误操作，系统能正确处理，不会自动中止。3概要设计3.1方案确定本系统要求实现几种不同算法的演示功能，故可遵循结构化程序设计思想来进行本系统的设计自顶向下，逐步求精，将设计任务划分成许多子任务，即分解成多子功能模块进行设计。本系统采用结构化编程，编写主模块来调用不同的演示模块。主模块的菜单是选择演示模块的入口。对每一个演示模块，系统定义了公用的接口，每编写一个新模块，只需要连接到主界面模块即可。调用某个模块时，只需要执行语句system（）；括号里面加入模块函数名。当需要加入新模块时，将程序加入到系统文件中，编译即可[3]。3.2系统结构3.2.1系统结构总框图软件系统的结构如图3-1所示。有了系统总体结构图，我们就可以逐个模块的详细设计，直至所有的模块完全实现。为了增强系统的维护性和可扩充性，总框图中的各个模块基本是相互独立的，用户只需通过键盘即可方便地进入各个模块，实现不同模块的跳转。图3-1数据结构算法动态演示系统结构总框图3.2.2模块功能说明对本系统的功能进行分析后可做如下的模块化设计：主程序模块实现的功能：完成选项菜单的显示，及对各模块的调用。欢迎界面模块实现的功能：完成对系统的初始化及界面显示。冒泡排序模块实现的功能：完成冒泡算法的演示。汉诺塔模块实现的功能：完成汉诺塔算法的演示。二叉树遍历模块实现的功能：完成二叉树遍历算法的演示。链表模块实现的功能：完成单链表建立算法的演示。系统介绍的模块：对系统简单的介绍。退出界面模块：退出图形模式，关闭系统。3.2.3算法演示子模块中要注意的问题对一个具体的算法演示子模块，须满足单步执行，连续执行，速度可调，任意时刻复位等复杂功能，设计一个接收键盘输入的字符函数[7]实现。在使用中，只需要简单把接收键盘输入的字符函数语句插入演示流程的不同地方，就能达到上述要求。调速的话还要用到延迟函数，还有系统自动产生演示数据的话需要使用随机数发生函数，所有的算法演示均调用此类函数完成，使编程统一，方便。4详细设计4.1数据设计本系统的设计以数组和结构体为基类型，其他数据类型相辅来完成。在数据选择和输入方面，系统提供两种方式：一是系统自动随机产生，二是用户手动输入数据并支持自动执行和单步操作。4.2系统主程序界面设计欢迎界面：雪花飞舞，标题汉字显示并闪烁，颜色循环改变，显示系统开发人员信息。系统介绍：系统简单介绍。菜单界面：提供选择要演示的内容。退出界面：星空灿烂，标题汉字显示并闪烁，颜色循环改变，并在一次循环之后退出系统。4.3演示模块流程图4.3.1冒泡演示流程图由于冒泡排序这个算法我们已经非常熟悉，因此在这里具体排序算法不是我们关心的问题，我们要关心的是怎么样将它的排序过程动态地演示出来。该演示算法的基本思想是：用户进入程序后，可选择系统随机产生待排序的数据或者是自己手动输入数据（当然不能超过个数限制，否则超出部分会无效）；然后用户还可以选择系统自动排序或者是手动单步执行排序，这两种方式的区别在于选择了前者排序将自动进行直到结束，而选择后者的话每进行完一趟排序程序暂停，等待用户按任意键继续执行下一趟排序，直到全部排序结束退出。由图4-1可知，此冒泡排序算法演示分以下几个步骤：用户进入程序后，选择产生演示数据的方式；用户选择演示方式；演示完毕退出。由此，该算法要设置三个标志变量，分别用来判断数据产生方式、排序演示方式和排序是否完成。冒泡排序的基本原理是对存放原始数据的数组，按从前往后的方向进行多次扫描，每次扫描称为一趟。当发现相邻两个数据的次序与排序要求的大小次序不符合时，即将这两个数据进行互换。这样，较小的数据就会逐个向前移动，好像气泡向上浮起一样。此演示流程中将每一趟排序后的数据都显示在屏幕上，通过每一趟的数据对比，让人容易理解排序过程中数据怎么一步一步交换的，数据是怎么样变成有序的。当然具体的数据动态交换过程我们会在系统功能实现这一章中详细介绍，这里只谈整个演示的流程。该演示算法流程图如图4-1。图4-1冒泡算法演示流程4.3.2汉诺塔演示流程图这里我们主要关心的是汉诺塔的移盘过程。该演示程序的思想是：用户在进入程序后，先输入想要演示的盘子个数，然后再选择是否自动演示，若选择自动演示的话，输入演示速度；若是手动执行的话，移盘一次程序暂停一下，然后按任意键继续执行直到完成。该演示算法流程图如图4-2。图4-2汉诺塔演示流程4.3.3二叉树演示流程图该演示程序的思想是：用户在运行程序后，可选择系统随机生成二叉树或者手动产生，若是手动的话用户自己输入结点数值；然后用户可以选择系统自动和手动两种遍历方式。这两种方式的区别在于选择了前者遍历将自动进行直到结束并在屏幕上显示遍历序列，而选择后者的话每遍历一个结点暂停，等待用户按任意键继续执行，直到全部结点遍历完毕。该演示算法流程图如图4-3。图4-3二叉树演示流程4.3.4单链表演示流程图该演示的思想是：程序一运行便进入图形模式，随之对链表进行一系列的初始化，然后用户输入接点字符，程序接收后在屏幕上生成一个单链表结点，如果输入ESC字符的话，停止生成结点，链表建立完成，或者结点数超过限制也将停止建立结点。该算法流程图如图4-4。图4-4单链表演示流程5系统功能实现5.1欢迎界面模块编码本系统的欢迎界面是一个雪花飞舞的场景，系统标题和作者信息在场景中不断闪烁变色。关键技术：画雪景、让字循环变色模块实现步骤：１、定义雪花的结构及其一些基本参数２、保存雪花３、画雪花４、让字闪烁并循环变色核心代码实现如下：定义雪花的结构及其一些基本参数structSnow/*雪花的一些参数*/{intx;inty;intspeed;/*雪花的速度*/}snow[100];实现对雪花的保存首先定义两个指针变量来作为保存空间：void*save1,*save2;/*保存空间*/然后我们通过定义一个函数来申请空间，具体实现对雪花的保存。voidCopy(void)/*保存区域*/{setcolor(0);setfillstyle(SOLID_FILL,15);fillellipse(200,200,4,4);size=imagesize(196,196,204,204);/*定义保存图象区域大小*/save1=malloc(size);/*申请空间*/save2=malloc(size);getimage(196,196,204,204,save1);/*保存雪花*/getimage(96,96,104,104,save2);/*保存背景黑色*/}开始正式画雪花首先来做一些初始工作，定义几个变量：intsnownum=0;/*雪的个数*/intsize;/*保存区域的大小*/然后自定义一个具体的画雪函数来实现画雪景：voidDrawSnow(void){intj=0;inti;intsx[62];randomize();for(i=0;i<62;i++)/*定义雪花的x坐标*/sx[i]=(i+2)*10;cleardevice();while(!kbhit()){if(snownum!=100)/*生成新的雪花*/{ snow[snownum].speed=12+random(5);/*速度随机定，但不小于9*/ i=random(62); snow[snownum].x=sx[i];/*随机取x坐标*/ snow[snownum].y=10-random(100);}for(i=0;i<snownum;i++)/*去雪*/ putimage(snow[i].x,snow[i].y,save2,COPY_PUT);if(snownum!=100) snownum++;setfillstyle(SOLID_FILL,15);/*画雪*/for(i=0;i<snownum;i++){ snow[i].y+=snow[i].speed; putimage(snow[i].x,snow[i].y,save1,COPY_PUT); if(snow[i].y>500) snow[i].y=10-random(200);}}实现字体闪烁并循环变色这个问题相对来说比较简单，我们能够用if语句来实现对字体颜色的变化：首先我们定义一个变量j，初始化为零，假设我们要使字体在三种颜色之间循环变化的话，我们可以这样做，让j%3这个式子作为if语句的基本判断条件，我可以设定：j%3=0，字体显示蓝色；j%3=1，字体显示红色；j%3=2，字体显示黄色。每显示一种颜色后j自加1，这样字体将在这三种颜色间循环，形成欢迎界面中闪烁动人的一幕。欢迎界面效果如图5-1。图5-1欢迎界面5.2主程序模块编码系统主界面完成选项菜单的显示，及对各模块的调用。关键技术：画选择菜单、模块调用模块实现步骤：１、画选择菜单；２、实现对各模块的调用。核心代码实现如下：画选择菜单首先要做的对菜单的显示[14]，菜单一般是下拉式的，而我这里做的是直接选择项菜单，按上下键进行选择，当选中某一项的话，选择项以高亮度显示，小球移动到选择项处。下面我们来画选择的小球体[14]：我们先定义一个画球体的函数voidDrawBall(intx,inty,intcolor)/*x和y为坐标，color为球的颜色*/{setcolor(0);setfillstyle(SOLID_FILL,color);fillellipse(x,y+10,10,10);}接下来画选项菜单，选择项菜单用一个自定义函数Choose()实现，主要代码如下：…setcolor(11);rectangle(40,40,600,440);/*画边框线/setcolor(13);settextstyle(0,0,3);/*标题大一些*/HZ16(100,70,30,4,"请您选择要演示的算法");settextstyle(0,0,2);/*其它选项小一些*/HZ16(200,150,30,4,"起泡排序");/*起泡排序*/HZ16(200,190,30,1,"汉诺塔");/*汉诺塔*/HZ16(200,230,30,2,"单链表的建立");/*单链表的建立*/HZ16(200,270,30,14,"二叉树遍历");/*二叉树遍历*/HZ16(200,310,30,10,"系统介绍");/*系统介绍*/HZ16(200,350,30,5,"结束程序");/*结束程序*/…

有了选择菜单，我们还需要选择菜单的循环条件，它通过下面的语句来判断是否循环：…if(key==ESC)/*退出系统*/ break; if(key==UP)/*上键盘操作*/[12] { DrawBall(keyx,keyy,BLACK);/*先用黑色在原来位置去除球*/ if(keyy!=150) keyy-=40;/*球的纵坐标*/ else keyy=350; DrawBall(keyx,keyy,11);/*新位置输出球*/ } if(key==DOWN)/*下键盘操作*/ { DrawBall(keyx,keyy,BLACK);/*先用黑色在原来位置去除球*/ if(keyy!=350) keyy+=40; else keyy=150; DrawBall(keyx,keyy,11);/*新位置输出球*/ }…实现对各模块的调用接下来的事情是对各模块的调用，先将各模块代码编译成可执行文件，然后用函数system（）调用这些可执行文件就行了。其主要代码如下：…if(key==ENTER)/*确定键*/ { switch(keyy)/*判断内容*/ { case150:system("bubble");yes=0;break;/*调用起泡排序*/ case190:system("hanoi");yes=0;break;/*调用汉诺塔*/ case230:system("list");yes=0;break;/*调用链表*/ case270:system("tree");yes=0;break;/*调用二叉树*/ case310:system("help");yes=0;break;/*调用系统介绍*/ case350:yes=0;oyes=0;/*退出选项*/ }/*endswitch*/

…菜单界面效果如图5-2：图5-2主界面5.3冒泡排序模块编码本模块要实现冒泡排序的演示过程，因此在算法执行过程中，每发生一次交换，都将在屏幕上显示出来。关键技术：显示输出数组、画交换箭头、清除交换区域模块实现步骤：1、实现数组的输出显示2、画交换箭头3、清除交换区域核心代码实现如下：这里我们主要要解决的问题是在图形模式下输出整个待排序的数组元素，还有就是在交换过程中高亮度显示要交换的两个数，并画出交换箭头，其它要注意的是具体排序过程中判断发生交换的标志，以及结束标志和手动和电脑自动标志。实现数组的输出显示专门定义一个函数来解决数组显示的问题，主要代码如下：voidPr(inta[],intn)/*输出数组*/{inti;charnum[5];settextstyle(0,0,2);/*设置输出样式*/setcolor(GREEN);/*设置输出颜色*/for(i=100;i<500;i+=50)/*i控制显示位置和计算数组下标*/{sprintf(num,"%d",a[(i-100)/50]);/*将数值转化为字符串*/outtextxy(i,n,num);/*输出字符串*/}}画交换箭头这里用画线函数画五根线组成一双向箭头线来表示两个数发生交换，代码如下：voidDrawChange(inti,intj)/*画交换箭头*/{setcolor(6);line(j*50+120,i+8,j*50+140,i+8);/*按给出的坐标位置画直线*/line(j*50+120,i+8,j*50+120+5,i+4);line(j*50+120,i+8,j*50+120+5,i+12);line(j*50+140,i+8,j*50+140-5,i+4);line(j*50+140,i+8,j*50+140-5,i+12);}清除交换区域数据交换过程中要注意的问题：因为如果两个数发生交换的话，首先将这两个数加亮显示。这两个数将交换位置，因此得将交换好后的数据重新显示在数组中来，这样就得覆盖掉以前的数据，这里我们用画黑矩形的方式把这行给删除，具体代码如下：…inti,j,t,flag;charnum1[5],num2[5];for(i=0;i<n-1;i++)/*冒泡排序*/{flag=0;/*设置数据交换标志*/for(j=0;j<n-1-i;j++){ Pr(a,i*40+80);/*输出数*/ setcolor(BLUE);/*输出要比较的两个数*/ sprintf(num1,"%d",a[j]);/*将两个数字转成字符串输出*/ outtextxy(100+j*50,i*40+80,num1); sprintf(num2,"%d",a[j+1]); outtextxy(100+(j+1)*50,i*40+80,num2); sleep(1);/*暂停运行一秒*/ setfillstyle(SOLID_FILL,BLACK); bar(0,i*40+60,640,i*40+100);*//*只显示当前两个要交换的数据*/ if(a[j]>a[j+1])/*如果前面的大于后面的*/ {flag=1;/*置交换标志*/ DrawChange(i*40+80,j);/*画交换箭头*/ setcolor(RED); outtextxy(100+j*50,i*40+80,num1); outtextxy(100+(j+1)*50,i*40+80,num2); t=a[j];/*交换*/ a[j]=a[j+1]; a[j+1]=t; sleep(1); setfillstyle(SOLID_FILL,BLACK);/*黑矩型的方式把这行给删除*/ bar(0,i*40+60,640,i*40+100);…演示效果如图5-3：图5-3冒泡排序演示5.4汉诺塔模块编码汉诺塔问题是一个经典的递归问题。它给出的圆盘移动条件是：一次仅能移动一个盘，且不允许大盘放在小盘的上面[1]。算法演示思想[10]：设要解决的的汉诺塔共有Ｎ个圆盘，对Ａ杆上的全部Ｎ个圆盘从小到大顺序编号，最小的圆盘为１号，次之为２号，依次类推，则最下面的圆盘的编号为Ｎ。第一步：先将问题简化。假设Ａ杆上只有一个圆盘，即汉诺塔只有一层Ｎ１，则只要将１号盘从Ａ杆上移到Ｂ杆上即可。第二步：对於一个有Ｎ（Ｎ＞１）个圆盘的汉诺塔，将Ｎ个圆盘分成两部分：上面的Ｎ－１个圆盘和最下面的Ｎ号圆盘。第三步：将“上面的Ｎ－１个圆盘”看成一个整体，为了解决Ｎ个圆盘的汉诺塔，可以按下面图示的方式迳行操作：将Ａ杆上面的Ｎ－１个盘子，借助Ｂ杆，移到Ｃ杆上；图5-4汉诺塔解决方法示意图（1）将Ａ杆上剩余的Ｎ号盘子移到Ｂ杆上；图5-5汉诺塔解决方法示意图（2）将Ｃ杆上的Ｎ－１个盘子，借助Ａ杆，移到Ｂ杆上。图5-6汉诺塔解决方法示意图（3）按照上面的想法，我们要演示的就是具体的移盘操作。关键技术：画盘子、移盘、显示移盘步骤实现步骤：1、画盘子；2、移盘、显示移盘步骤。核心代码实现如下：画盘子首先定义一下盘子的结构：structH{intdata[15];/*存放每个盘的代号*/inttop;/*每个塔的具体高度*/}num[3];/*三个塔*/接下来要定义一些标志变量来判断运行方式，比如：intcomputer=1;/*自动控制与手动控制的标志*/intspeed=0;/*全局变量speed主要是演示过程的速度*/然后要处理输入数据越界的情况，因为盘子个数过多，将很难实现，因此这里以0<n<10为界限，越界的话n当10处理。代码如下：…if(n<1||n>10)n=10;/*越界的话n当10处理*/…下面来开始画盘子：首先初始化三个地方塔的高度，代码如下：…for(i=0;i<3;i++)num[i].top=-1;/*三个地方的高度开始都为-1*/…然后画一开始的塔座A上的盘子，代码如下：…for(i=0;i<n;i++)/*画一开始的塔座A上的盘子*/{num[0].top++;/*栈的高度加1*/num[0].data[num[0].top]=i;/*最大的盘子代号为0，依次为1，2，…n-1*/color=num[0].data[num[0].top]+1;/*盘子的颜色代码为栈顶盘子代号加1*/setfillstyle(SOLID_FILL,color);bar(100-(33-3*num[0].data[num[0].top]),400-20*i-8,100+(33-3*num[0].data[num[0].top]),400-20*i+8);/*画矩形*/}setcolor(YELLOW);outtextxy(180,450,"anykeytocontinue");settextstyle(0,0,2);outtextxy(90,420,"A");/*塔座标志*/outtextxy(240,420,"B");outtextxy(390,420,"C");…移盘、显示移盘步骤接下来要做的解决移盘问题并显示移盘步骤，这个过程的代码如下：…inti;charnum1[3],num2[3];sprintf(num1,"%c",x-32);/*将小写变成大写，并转换成字符串输出*/sprintf(num2,"%c",y-32);setfillstyle(SOLID_FILL,BLACK);/*把原来的地方移去涂黑*/bar(0,0,640,60);setcolor(RED);outtextxy(150,30,num1);/*输出移动过程*/outtextxy(200,30,">");outtextxy(310,30,num2);settextstyle(0,0,2);setfillstyle(SOLID_FILL,BLACK);/*把原来的地方移去涂黑*/bar(100+150*(x-97)-(33-3*num[x-97].data[num[x-97].top]),400-20*num[x-97].top-8,100+150*(x-97)+(33-3*num[x-97].data[num[x-97].top]),400-20*num[x-97].top+8);num[y-97].top++;/*入栈，目标点的top加1*/num[y-97].data[num[y-97].top]=num[x-97].data[num[x-97].top];/*在目标点盘子的代号与源点盘子的代号相同*/num[x-97].top--;/*出栈，原来地方的top减1*/setfillstyle(SOLID_FILL,num[y-97].data[num[y-97].top]+1);/*盘子颜色代码是栈顶盘子代号加1*/bar(100+150*(y-97)-(33-3*num[y-97].data[num[y-97].top]),400-20*num[y-97].top-8,100+150*(y-97)+(33-3*num[y-97].data[num[y-97].top]),400-20*num[y-97].top+8);…有个问题要注意的是怎么实现手动控制，其实用下面的代码就可以了：…if(computer)/*自动控制就用sleep延时函数*/sleep(speed);/*延时函数*/elsegetch();/*手动控制的话就自己按键盘来控制*/…演示效果如图5-7：图5-7汉诺塔演示5.5二叉树遍历模块编码本模块演示思想[10]：由系统或者手动建立一棵二叉树，然后依次对其进行三种遍历，每遍历到一个结点，将那个结点亮点显示，并在屏幕上输出遍历序列[2]。关键技术：画二叉树、图形模式下显示创建好的树、遍历时显示每个结点模块实现步骤：1、画二叉树；2、图形模式下显示创建好的树；3、清除二叉树区域；4、遍历时显示每个结点。核心代码实现如下：画二叉树首先定义一下二叉树接点的结构以及一些基本变量标志位：intnodeNUM=0;/*统计当前的结点数字,最多26个*/charway;/*自动建立树和手动建立树的标志,2手动,1自动*/intflag;/*单步执行与自动执行的标志*/charstr[3];/*显示结点数据的字符串*/typedefstructTREE{chardata;/*树的结点数据*/structTREE*lchild;structTREE*rchild;intx;/*树的x坐标*/inty;/*树的y坐标*/}Tree;structOUTPUT{intx;/*三种遍历的x坐标*/inty;/*三种遍历的y坐标*/intnum;}s;要进行二叉树的遍历，首先得创建一棵树，这里我们分两步走：一、我们先进行文本模式下的创建树；二、用图形显示创建好的树。接下来我们先进行第一步，代码如下：首先我们对数据越界进行处理，如下：…if(h==5||nodeNUM==9)/*如果树的层次已经到5或者结点数到达9个就自动返回NULL*/ {returnNULL;}…具体建树过程代码：Tree*InitTree(inth,intt,intw){charch;Tree*node;if(way=='1')/*自动建立的赋值*/{ch=65+random(25);node=(Tree*)malloc(sizeof(Tree));node->data=ch;node->x=t;/*树的x坐标是传递过来的横坐标*/node->y=h*50;/*树的y坐标与层次大小有关*/nodeNUM++;node->lchild=InitTree(h+1,t-w,w/2);node->rchild=InitTree(h+1,t+w,w/2);}if(way=='2')/*手动建立需要自己输入*/{if(h==5||nodeNUM==9)/*如果树的层次已经到5或者结点树到达9就自动返回NULL*/ {returnNULL;}ch=getch();printf("%c",ch);node=(Tree*)malloc(sizeof(Tree));node->data=ch;node->x=t;/*树的x坐标是传递过来的横坐标*/node->y=h*50;/*树的y坐标与层次大小有关*/nodeNUM++;node->lchild=InitTree(h+1,t-w,w/2);node->rchild=InitTree(h+1,t+w,w/2);}returnnode;}图形模式下显示创建好的树用图形显示创建好的树代码如下：voidDrawTree(Tree*t){if(t!=NULL){setcolor(BLACK);setfillstyle(SOLID_FILL,BLACK);fillellipse(t->x,t->y,9,9);setcolor(WHITE);circle(t->x,t->y,10);/*画圆*/sprintf(str,"%c",t->data);/*将内容转换成字符串输出*/outtextxy(t->x-3,t->y-2,str);if(t->lchild!=NULL)/*左子树*/{ line(t->x-5,t->y+12,t->lchild->x+5,t->lchild->y-12); DrawTree(t->lchild);}if(t->rchild!=NULL)/*右子树*/{ line(t->x+5,t->y+12,t->rchild->x-5,t->rchild->y-12); DrawTree(t->rchild);}}}清除二叉树区域在遍历二叉树之前，我们要注意或者是思考一个问题，当我们对一棵二叉树进行了先序遍历之后，我们马上还要对它进行余下的中序遍历和后序遍历操作，因此要求二叉树恢复到遍历前的样子，因此要求我们局部清屏，这里我们用画黑矩形的方式实现[10]，代码如下：voidClrScr();/*清空树的区域*/{setcolor(BLACK);setfillstyle(SOLID_FILL,BLACK);bar(0,20,640,280);}遍历时显示每个结点这个过程要做的事情是填充结点、将遍历次序用数字显示在树的结点上和输出遍历序列。它的具体代码如下：voidDrawNode(Tree*t,intcolor){setfillstyle(SOLID_FILL,color);fillellipse(t->x,t->y,10,10);setcolor(RED);sprintf(str,"%c",t->data);/*将内容转换成字符串输出*/outtextxy(t->x-3,t->y-2,str);setcolor(color);outtextxy(s.x,s.y,str);setcolor(RED);sprintf(str,"%d",s.num);/*将遍历次序用数字显示在树的结点上*/outtextxy(t->x-3,t->y-20,str);s.num++;sleep(1);}演示效果如图5-8：图5-8二叉树演示5.6链表模块编码算法演示思想：用户每输入一个结点字符，产生一个结点，显示过程。关键技术[10]：画结点框、结点之间的连线模块实现步骤：1、对创建链表前的界面进行设计和初始化；2、画结点框和连线3、对数据溢出进行处理。核心代码以及相关演示界面如下：对创建链表前的界面进行设计和初始化首先定义一下链表结点的数据结构[4]：typedefcharElemType;typedefstructLNode{ ElemTypedata; structLNode*next; }LNode,*LinkList;接下来对创建链表前的界面进行设计和初始化，核心代码如下：…DestroyList_L(head); InitList_L(head); length=ListLength_L(head); setfillstyle(SOLID_FILL,WHITE); setbkcolor(2); HZ16(10,460,20,14,"单链表的建立"); setfillstyle(SOLID_FILL,GREEN); setcolor(YELLOW); rectangle(2,100,10,120); line(11,115,19,115);line(19,115,15,112);line(19,115,15,118); HZ16(10,52,20,14,"请输入结点的字符（按ＥＳＣ结束）：");…此处演示效果如图5-9图5-9单链表的建立(1)画结点框和连线然后来画结点框和连线，核心代码如下：…ch=getch(); while(ch!=ESC&&length<7) { if(length!=0)/*画结点与结点之间的连线*/[6] { line(60+83*(length-1),145,80+83*(length-1),145); line(80+83*(length-1),145,80+83*(length-1),115); line(80+83*(length-1),115,100+83*(length-1),115);line(96+83*(length-1),112,100+83*(length-1),115);line(96+83*(length-1),118,100+83*(length-1),115); } for(j=200;j>=0;j--) { bar(20+83*length,101+j,60+83*length,161+j); rectangle(20+83*length,100+j,60+83*length,160+j); line(20+83*length,130+j,60+83*length,130+j); sound(1000-30*j); delay(1); nosound(); } str[0]=ch; outtextxy(24+83*(length),103,str); ListInsert_L(head,length+1,ch); length=ListLength_L(head);…此处演示效果如图5-10图5-10单链表的建立(2)对数据溢出进行处理。最后，我们要对数据溢出进行处理，将最后接点的指针域置空，核心代码如下：…settextstyle(0,HORIZ_DIR,1); outtextxy(24+83*(length-1),141,"NULL"); sleep(1); if(length==7) { bar(10,52,640,75);/*清除前面的文字*/ HZ16(10,52,20,YELLOW,"单链表长度超出屏幕长度，即将退出。");sleep(1); }…此处演示效果如图5-11图5-11单链表的建立(3)5.7退出模块编码关键技术：画星星核心代码实现如下[6]：首先先定义星星的一些基本参数：structStar/*星星的一些参数*/{intx;inty;intcolor;}star[200];然后定义一个函数用来画灿烂星空[5]，代码如下：voidDrawStar(void){inti;cleardevice();setcolor(GREEN);settextstyle(0,0,2);while(!kbhit()){for(i=0;i<200;i++)/*随机生成星星*/{ star[i].x=random(640); star[i].y=random(480); star[i].color=random(13)+1;