C++数据结构算法演示系统（论文）.doc

中北大学毕业设计（论文）题目：数据结构算法演示系统英文题目： data structure algorithms demonstration system学 院: 专 业: xxx 班 级: 计算机xxx 学生姓名: 学 号: 指导教师: 完成日期: 毕业设计（论文）诚信声明本人郑重声明：所呈交的毕业设计（论文）是我个人在导师指导下进行的研究工作及取得的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写的研究成果，也不包含为获得华东交通大学或其他教育机构的学位或证书所使用过的材料。如在文中涉及抄袭或剽窃行为，本人愿承担由此而造成的一切后果及责任。本人签名 导师签名 200x年 x 月xx 日xx大学毕业设计（论文）任务书姓名学号毕业届别 专业计算机科学与技术毕业设计（论文）题目数据结构算法演示系统指导教师学 历职 称具体要求：a. 使用c+builder6.0开发工具，设计一个关于数据结构的算法演示系统。建立一个form窗口，其中包括：程序（w）、数据结构（x）、操作（y）、帮助（z）四个下拉菜单。此演示系统包括了线形表、栈和队列、树、图四个模块。并附有四个演示模块的相关说明，以及在帮助里的提示操作步骤。b. 开发平台的选择：使用windows xp系统开发操作系统，c+builder6.0开发环境。系统功能要求：a 主界面模块 欢迎语，点击“数据结构”选择所要演示的数据结构算法；b. 线形表模块包括链表的概念、模型、操作以及一个双向链表；c. 栈和队列模块 包括基本堆栈、基本队列、环行队列； d. 树模块数据二叉树、结构二叉树、类二叉树；e 图模块 图表示、图搜索、最短路径。进度安排：2.8 3.9 查网络资料，收集相关书籍3.103.24 复习c+语言，学会用c+builder完成一些小程序3.254.1 程序与数据库的联结运行，初步完成演示系统4.2 4.15 系统基本成型，查找错误，优化代码4.165.14 系统测试与修改维护5.155.21 撰写论文5.286.3 论文修改及打印装订 指导教师签字： 年 月 日教研室意见： 教研室主任签字： 年 月 日题目发出日期 设计（论文）起止时间 附注：xxx大学毕业设计（论文）开题报告书课题名称数据结构算法演示系统课题来源学校提供课题类型cx导 师学生姓名学 号专 业计算机科学与技术开题报告内容：数据结构算法演示系统是一个动态演示数据结构算法执行过程的辅助教学系统，它可适应用户对算法的输入数据和过程执行的控制的不同需求，在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行过程中栈的变化状况。整个系统使用菜单驱动方式，每个菜单包括若干选项。每个菜单项对应一个动作或一个子菜单。系统一直处于选择菜单项或执行动作状态，直到选择了退出动作为止，它分别演示了数组、堆栈、队列、线形表、树、图等基本数据结构的概念。方法及预期目的：方法：本数据结构算法演示系统是基于c、c+语言，在c+builder6.0软件环境下，开发出来的一种算法演示系统。该系统可以用于展示数据结构课程中的相关算法，能为学习数据结构的同学理解其中的算法。数据结构作为计算机应用和计算机网络专业的一门必修的专业基础课程，应使学生在掌握常用的基本算法的同时，学会设计简单的算法，并能够在实际应用中得到应用。目的：在数据结构中包含了大量的算法，由于这些算法都很抽象，不易于理解，使得同学在学习这些算法的时候，往往走很多弯路。为了能使同学更好的理解数据结构算法，本人开发了“数据结构算法演示系统”，该系统包括：线性表、堆栈、队列、图和树等算法的演示，可以给同学在学习这些算法的时候，不再抽象。更生动，更具体的描绘了这些算法。 指导教师签名： 日期：课题类型：（1）a工程设计；b技术开发；c软件工程；d理论研究； （2）x真实课题；y模拟课题；z虚拟课题 （1）、（2）均要填，如ay、bx等。大学毕业设计(论文)评阅书(1)姓名学号专业计算机科学与技术毕业设计(论文)题目数据结构算法演示系统指导教师评语：得分指导教师签字：年 月 日评阅人评语：得分评阅人签字：年 月 日等级xxx大学毕业设计(论文)评阅书(2)姓名学号专业计算机科学与技术毕业设计(论文)题目数据结构算法演示系统答辩小组评语：等级 组长签字：年 月 日答辩委员会综合评语： 等级 答辩委员会主任签字：年 月 日（学院公章）注：答辩小组根据评阅人的评阅签署意见、初步评定成绩，交答辩委员会审定，盖学院公章。“等级”用优、良、中、及、不及五级制（可按学院制定的毕业设计(论文)成绩评定办法评定最后成绩）。xxx大学毕业设计（论文）答辩记录姓名学号毕业届别2006专业计算机科学与技术题目数据结构算法演示系统答辩时间答辩组成员（签字）：答辩记录： 记录人（签字）： 年 月 日 答辩小组组长（签字）：年 月 日附注：摘要数据结构算法演示系统本文根据平常上课所学的数据结构与c+课程，设计了一套常见数据结构算法的演示系统,此系统具有操作方面、直观、容易理解等特点，对更好的学习数据结构，加深算法的理解有很大帮助。这是基于c、c+语言开发出来的一种算法演示系统，可以用于展示数据结构课程中的各种核心算法。“数据结构”是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课程。“数据结构”是一门专业技术基础课，可以帮助我们了解各种算法，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步学会算法的时间分析和空间分析的技术，但数据结构中的一些算法（线性表、栈和队列、树、图等）在理解上会有些困难，数据结构算法演示系统正是解决这个困难的一种有效方法，通过图示的方法，方便直观的理解各种数据结构的算法。 数据结构算法演示系统在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行过程中栈的变化状况。整个系统使用菜单驱动方式，每个菜单包括若干选项。每个菜单项对应一个动作或一个子菜单。系统一直处于选择菜单项或执行动作状态，直到选择了退出动作为止，它分别演示了数组、堆栈、队列、线形表、树、图等基本数据结构。关键字：数据结构、算法演示 abstractdata structure algorithms demonstration systemaccording to the course of data structure and c+ programming language,build a common data structure algorithms demonstration system. the system is operated convenient, vivid image and easily understanding.the algorithm system provides a great help to deepen the understanding of the data structure, enhance the level of computer programming.data structure algorithms demonstration system is based on c+ programming language, developed a demonstration system algorithms, the system can be used to display data structure courses related algorithms, the system can provide data to study the structure of the students understanding of the algorithm. data structure is an important theoretical computer programming technical basis, it is not only the core curriculum of computer disciplines, and has become a popular elective courses in other professional polytechnic. data structure is helpful for us to learn variety of algorithms, and he can help you learn computer analysis of the data processing structure characteristics, in order to choose the appropriate application of the logic of data structures, storage structures and the corresponding algorithms, and preliminary analysis of algorithms of time and space analysis techniques, but some algorithm data structure (linear scales, warehouse and accounts, string, etc.) will be some difficulty in understanding the data structure algorithms demonstration system is an effective way to resolve this difficult, and it gives a more intuitive understanding for us to learn the data structure algorithms.data structure algorithms demonstration system is a dynamic demonstration of data structure algorithms implementation process aided teaching system, algorithms in the computer screen shows the logical structure of the implementation process or store data changes in the structure or status of the implementation process warehouse digui algorithm changes situation. use menu-driven system as a whole, each menu includes several options. each menu item or a sub-menu corresponding one moves. system has been implemented in select menu items or state moves until chose to withdraw from the action so far, it sends a separate demonstration, duizhan, italy, bar tables, trees,maps,and other basic data structure concepts.key words: data structure、algorithm demonstration 目 录1绪论11.1系统简介11.2本文所做的主要工作12系统的开发工具及环境22.1 c+ builder介绍22.2常用文本输入组件简介42.3 bcb的调试52.4 开发工具和环境：63系统设计73.1系统组成73.2系统实现：93.2.1主菜单的设计：93.2.2堆栈模块的设计113.2.3基本队列模块的设计163.2.4循环队列模块的设计193.2.5基本队列模块的设计图模块的设计233.2.6帮助模块设计29结束语31谢 辞32参考文献33附录34附录a 外文翻译原文部分34附录b 外文翻译译文部分38 1绪论1.1系统简介数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。数据结构所讨论的有关问题主要集中在解决系统程序所面临的具体技术上,数据结构几乎就是图论,特别是表和树的理论的同义词。随后,数据结构这个概念被扩充到包括网络、集合代数论和关系等方面。与此同时,人们不仅关心数据本身的数学性质,而且也关心数据在计算机中的表示方式,这就扩大了数据结构的内容。到七十年代，在数据结构中又增加了文件管理等方面的内容。近年来 ,多维图形的数据结构也取得很大进展。数据结构，作为计算机学科的基础性专业课程，其在计算机科学中的及其重要，课程学习的好坏，直接关系到学生后期计算机水平的高低。而这门课程一直因为过于抽象，难以理解，而让人望而止步。如果能够把这门抽象的课程变得具体而生动，必将提高学习者兴趣，增加其积极性和主动性，也有利于学习者对此课程的学习。数据结构作为一门独立的课程在国外是从1968年才开始设立的。在这之前，它的某些内容曾在其它课程，如表处理语言中有所阐述。1968年在美国一些大学的计算机系的教学计划中，虽然把数据结构规定为一门课程，但对课程的范围没有作明确规定。当时,数据结构几乎和图论,特别是和表、树的理论为同义语。随后,数据结构这个概念被扩充到包括网络、集合代数论、格、关系等方面，从而变成了现在称之为离散数学的内容。然而，由于数据结构在计算机中进行处理，因此，不仅考虑数据本身的数学性质，而且还考虑数据的存储结构，这就进一步扩大了数据结构的内容。进年来，随着数据库系统的不断发展，在数据结构课程中又增加了文件管理（特别是大型文件的组织等）的内容。1.2本文所做的主要工作本文所作的研究工作主要包括：1、详细分析了系统需求，提出了系统设计方案，并进行了论证；2、分析了rad设计方法的利弊，并选定了设计方案。3、设计并完成了数据结构算法演示系统；2系统的开发工具及环境2.1 c+ builder介绍c+ builder既适用于基于orb的分布式开发，又适用于基于com的windows开发。c+ builder内置了visibroker3.3，并且包含了event service和namingservice等标准corba服务，从而为开发corba应用提供了可能。c+ builder 将corba idl 编译器集成在其开发环境中，通过配合各种向导(wizard)，可以快速生成corba client和server的源程序代码框架，这对于开发corba产品的朋友来说，确实是非常方便的。在microsoft com方面，c+ builder 同样提供了各种向导，可以一步生成com标准组件、ole automation组件及activex组件。c+ builder 提供的midas2同时支持corbaiiop、dcom、dce rpc以及tcp/ip等多种连接方式，适用于分布式系统的开发。比如，非windows环境上的java应用程序，可以通过corba iiop使用c+ builder开发出来的应用程序服务器。从而使用户可以在原有系统基础之上构建跨平台、跨程序语言的分布式应用系统。对于过去开发的基于borland c+ owl和microsoft mfc的程序，c+ builder是能够兼容的。c+ builder的另一特性就是提供了mfc4.2版的函数库，强化了对microsoft visual c+源代码的兼容性，可以直接编译msdn与各种sdk中的范例程序。通过mfc向导，还可以生成mfc的代码框架。除此之外，c+ builder能够编译原有的borlandc+ owl程序码，因此就不必担心以前的工作白做了！c+ builder中提供了符合ansi/iso标准的c+编辑器，还能够开发可移植于非windows平台的c+程序。c+ builder提供了对oracle8、microsoft sqlserver 7、informix 9、sybase、ibm db 2 universalserver、interbase 5.5等大型数据库的高速驱动程序，并支持oracle8的对象关联延伸功能，如abstract data type、nested tables、variable lengtharrays、object pointers(refs)及external filereference等。同时c+ builder还保留了对microsoftaccess 97、foxpro、visual dbase及paradox等本地数据库的处理能力。因此，无论是大型的数据库应用系统开发，还是小型的数据库管理系统，c+ builder都有其用武之地。c+ builder还提供了mts 组件向导，用于快速生成支持microsoft transaction server的com组件。bderesource dispenser使用户可以在mts中使用bde存取数据库，保证了mts对数据库的两阶段提交(two phasecommit)及资源管理的能力。c+ builder强化了原有的module view、eventlog view及inspect local variable等调试窗口的功能，并在windows nt环境中提供多线程调试的新功能，使用户可以在某一特定过程中跟踪程序代码。c+ builder针对多层分布式开发环境提供了远程调试能力，开发人员可以通过网络直接对远端的应用程序服务器进行调试，从而简化了多层应用系统的开发和维护工作。2.2常用文本输入组件简介c+builder常用文本输入组件来实现文本输入，常用的文本输入组件有edit、maskedit 、memo和richedit。他们的主要不同在于edit和maskedit用于输入单行文本，而memo和richedit可以输入多行文本。此外label组件也可用来进行文本显示。edit和maskedit是一个窗口控件，它可以获得输入焦点。当用户需要输入单行文本时，就应该使用编辑框。它通常与标签组件一起使用。编辑框常用的几个属性如下：text属性是一个string类型的数据，它决定了在编辑框中出现的文本字符串。在编程中，我们经常要通过text属性获取编辑框中的文本字符串；maxlength是一个integer类型的数据，它指定编辑框所能容纳的最大字符数。缺省情况下为0，表示长度不限。标签的常用属性有caption和focuscontrol。caption属性是字符串类型，用来指定标签的标题，也就是标签的显示内容。focuscontrol属性是窗口控件类，用来指定一个与标签相连的窗口控件。从而允许这个控件使用快捷键来获得输入焦点。memo组件：memo与edit的属性有很多相似的，下面只来说一下memo组件的重要属性。lines属性是一个tstrings类的一个对象，它是由多个字符串组成的，每一个字符串就是lines中的一个元素。memo组件的每一行文本都是lines中的一个字符串。richedit组件，只要能够把设置缺省字符格式defattributes、设置选中字符格式selattributes与设置段落paragraph三个属性掌握好就差不多了，因为她的其它属性与memo差不多。2.3 bcb的调试程序的bugs越少，最终用户对这个程序的评价越高。而开发人员事先对bugs的处理越多，最终用户能提供的关于bugs的信息就越多，也越准确，这样，开发人员在接到最终用户反映之后，就能够快速找到出现bugs的那部分代码，并以最快速度发布程序的升级包。 （1）写易读的代码 第一点，大概也是最重要的一点，就是写干净易读的代码。易读的代码是很有价值的。请想象一下，如果随便扫视一眼代码或注释，就能立刻知道这段代码的的作用，以及在写代码的时候为什么要这样写，当时的思路是什么，那么就可以节约大量时间。这样的代码，在写的时候可能会稍稍慢一些，不过，当你调试程序时，就不会花上几个小时来寻找bugs，相反，你可以快速，简单的完成除错工作。这时，你就会觉得多花一些时间使程序易读是很值得的。所以，在写程序的时候，应该养成自己的风格，或是读一读scott的关于代码风格的文章。 （2）使用exceptions和exception的处理方法 除去一些少数的情况，开发人员不可能总是依靠于集成的调试工具。所以，学会用其它的方法来找到bugs是很重要的。一些重要的、处理的错误可能会在窗体之外发生。在c+标准制定出来之前的黑暗日子里，在程序里面发出发生错误的信号，通常是通过返回错误代码完成的（现在这种方法仍然应用于ole技术和一些winapi函数），这样的处理方法很容易就会被忽略。所以，出现问题的可能性并不小。由于以上的原因，我们需要一个这样的机制，它能让我们不能忽略这些错误，而且，这个机制应该能被我们控制和自定义的。在这样的需求下，异常处理机制出现了。需要一个特殊的错误类型吗？简单，定义一个新的异常类型就行了，然后抛出它。 c+builder定义了try catch () 机制。这和刚刚定义的异常机制的结构很相似。这个机制完全可以按照需要自定义。要使用异常处理了，只要把要执行的代码放到try块里面，为了让程序知道出现异常后应该做什么，还需要定义一个catch()或是_finally块。catch()语句里面可以指定一个要捕捉的类型或是变量。 /* 异常处理代码/这个机制很强大，甚至可以用它来捕捉树结构或是继承类的异常，如果捕捉了基类的异常，它就能捕捉到继承这个基类的所有的类的异常。比如，在vcl中，所有的异常都是继承于exception类。所以，catch(exception& e)可以捕捉到除了esocketerror的所有vcl异常。为了让这个机制更强大，c+builder中还定义了catch()语句。使用这条语句可以捕捉到所有的异常。还有更多的功能，可以添加更多的catch()语句，可以向使用ifelse if语句那样使用它。在一系列的catch()语句中，错误不会被重复的捕捉，也就是说，如果前面的catch()语句捕捉到了错误，后面的catch()语句将不会捕捉这条错误。 （3）使用记录机制 不可能总是用调试器来调试代码，在某些情况下，可能无法使用内部集成的调试器，这时候，就不得不依靠其他手段调试程序了。（比如：windows nt服务程序,isapi/cgi程序，实时应用程序等等）。这时候，有经验的程序员可能会借助古老的调试方法，例如，使用一些分类的记录机制来确定程序实际运行的过程。很幸运，现在有一系列的方法可以简单的完成这样的工作。 （4）将记录和异常处理结合使用 不用总是担心可能会发生什么偶然的异常。一般来说，通过很多的bugs测试后，应用程序在运行是应该不会出现什么错误。下面的这个技术，组件开发者在第一次把组件放在ide环境测试的时候，很应该遵守。一个在ide中产生的异常会导致很多问题，甚至可能无法重新启动ide也不能恢复。这个技术很简单。在代码中每一个函数或是主要的函数中加入： try /函数的代码 catch(exception &e) senddebugmessage(“exception caught in classname:functionname of type:” +e.classname() +” with the message:”+e.message); ; 把字符串中classname 和 functionname 替换成相应的类名和函数名。在出现错误时，会立刻知道错误发生的位置。这样也就不至于强制重起ide的了。 2.4 开发工具和环境：c+builder6.0。基于上述的c+builder的优点，以及和其他软件的对比，所以我决定使用windownsxp作为操作系统、c/c+做为开发语言，c+builder6.0做为开发工具，易于实现这个系统，对于数据结构的学习和教学都是相当合适的。3系统设计3.1系统组成系统由现分述如下：本系统包括：程序、数据结构、操作、帮助四个下拉菜单。其中：程序菜单部分由退出组成，完成系统的终止数据结构菜单由线性表、堆栈和队列、树、图等四个部分组成，也是此系统的核心部分，分别对应数据结构的四大部分。线性表又分为链表概念、链表模型、链表操作、双向链表四个部分，分别对应表的算法演示；堆栈和队列分为基本堆栈、基本队列、循环队列三个部分，分别对应堆栈和队列的算法演示；树分为数据二叉树、结构二叉树、类二叉树，分别对应树的算法演示；图分为图表示、图搜索、最短路径，分别对应图的算法演示。操作菜单由线性表说明、堆栈说明、队列说明、树说明、图说明组成，对各数据结构进行了简单说明。帮助菜单由关于和帮助组成，是本系统的一些简单帮助信息。 下图为本算法演示系统的结构图：链表概念链表模型退出程序链表操作双向链表线性表基本堆栈基本队列堆栈和队列数据结构循环队列数组二叉树树结构二叉树操作二叉树图图表示进入系统线性表说明图搜索最短路径操作堆栈说明队列说明树说明图说明关于帮助帮助图3-1 系统模块图3.2系统实现：3.2.1主菜单的设计：主菜单位于窗体的标题栏下面，而弹出式菜单则是当鼠标右击某控件的时候自动弹出来。tmainmenu组件：主菜单位于standard组件中，用它可以来设计应用程序菜单栏中的菜单，tmainmenu的主要属性、方法如下：（1） autohotkey属性用来设置菜单选项的快捷键是否可以自动重置。（2） handle属性可以用来为菜单提供一个对windows菜单句柄的访问。（3） images属性，用来指定在各个菜单选项旁边的图象列表。（4） items属性，该属性提供了可以访问菜单选项元素的描述，用它可以来访问选项的各个信息。设计的时候可以在object inspector里单击items属性右边的按钮，然后对其属性进行设计。（5） merge方法，将非mdi应用程序中窗体的主菜单合并到另外一个窗体的主菜单。（6） unmerge方法，用来将非mdi应用程序中已经合并的主菜单分开，回复到合并前的状态。设计主菜单：（1） 单击standard组件中的tmainmenu，放到form框中；（2） 对其属性进行相应的设置；（3） 单击【文件】选项可以看到下拉了一个其子菜单，支持点击其子菜单的话可以增加其子菜单选项。或者点击其右边的菜单的话可以设计其下一个选项，如果在caption中设置标题为减号，则会得到一个分界线；（4） 双击菜单选项可以得到其click事件，当用户选中了该选项的时候即发生该事件，在这里加特殊处理的代码。比如双击【退出】控件，加代码如下：void_fastcall tform1:s1click(tobject*sender)showmessage(“选项中退出选项”)现在主菜单已经有个雏形了。弹出式菜单的设计：tpopupmenu组件，弹出式菜单，位于standard组件页中，用于设计当鼠标右击某些控件的时候弹出的菜单，弹出式菜单的设计与主菜单非常类似，因此以下只讨论它的属性方法和事件。tpopupmenu的主要属性、方法和事件：（1） alignment属性，用来设置当用户右击时，弹出菜单显示的位置，它的取值分别为：paleft、pacenter、paright，其含义分别为：弹出式菜单左上角位于鼠标指针下（alignment的默认值）、弹出式彩旦中央位于鼠标指针下、弹出式菜单右上角位于鼠标指针下；（2） autopopup属性，为true时，当用户右击控件的时候，自动弹出菜单，true是autopopup的默认值，为false时，当用户右击控件的时候，必须通过代码来控制菜单的弹出，用popup方法实现之；（3） popup方法，用来将弹出式菜单显示到屏幕上；（4） onpopup事件，在菜单刚要显示到屏幕上之前发生该事件。在应用程序中建立如下菜单系统：主菜单含有四个项，分别为“程序”、“数据结构”、“操作”、“帮助”，如图3-2所示。 图3-2 数据结构算法演示系统界面图其中“程序”下拉菜单有“退出”一项；“数据结构”中包括“线性链表”、“堆栈和队列”、“树”、“图”等四项；“操作”下拉菜单中包括“线性表说明”、“堆栈说明”、“队列说明”、“树说明”、“图说明”等五项；“帮助”下拉菜单中包括“关于”和“帮助”两项。我们希望该菜单系统能实现以下的功能：当选择“退出”按钮时即可退出该程序。当选择“数据结构”-“图”-“图表示”时，能打开图表示的算法模块。在设计过程中，考虑到在“操作”菜单的相关说明，要在系统中有相应的显示位置，为此我们在模块的中间部分设计了两个备注框，用来显示各种算法的操作说明。在外观上，我们选择了菜单的结构设计，其中第一用做显示说明的对话框，下一个用来显示修改说明的对话框，以及在顶部设计了一条“欢迎使用数据结构演示系统”的欢迎语。为了能即时的修改操作说明中的相关内容，我们设计了修改，保存等相关按钮。 3.2.2堆栈模块的设计栈是限定仅在表尾进行插入或删除操作的线性表。表尾称为栈顶，表头称为栈底，不含元素的空表称空栈。栈的修改是按后进先出的原则进行的，因此，栈又称为后进先出的线性表（简称lifo结构），它的特点可用图3-3来形象地表示。栈的基本操作除了在栈顶进行插入或删除之外，还有栈的初始化、判空及取栈顶元素等。ana1a2.栈底栈顶顶.出栈进栈 图3-3 栈的示意图栈的基本操作算法描述如下：1.建立一个空栈status initstack(sqstack &s)/构造一个空栈ss.base=(elemtype *)malloc(stack_init_size*sizeof(elemtype);if(!s.base)exit(overflow); /存储分配失效s.top=s.base;s.stacksize=stack_init_size;return ok;/initstack 2.取栈顶元素status gettoplstack (linkstack &s,elemtype &e)/若栈不为空，则用e返回s的栈顶元素，并返回ok,否则返回error.if(s=null) return error;e=s-data;return(ok);/gettoplstack 3.压栈pushstatus push(sqstack &s,elemtype e)/插入元素e为新的栈顶元素if(s.top-s.base=s.stacksize)/栈满，追加存储空间s.base=(elemtype*)realloc(s.base,(s.stacksize+ stackincrement)*sizeof(elemtype);if(!s.base)exit(overflow);/存储分配失败s.top=s.base+s.stacksize;s.stacksize+=stackincrement;*s.top+=e;return ok;/push4.出栈popstatus pop(sqstack &s,elemtype &e) /若栈不为空，则删除s的栈顶元素，用e返回其值，并返回ok；否则返回errorif(s.top=s.base)return error;e=*-s.top;return ok;/pop 5.判栈空int empty(sqstack s)/若栈为空，则返回0，否则返回1if(s.top=s.base) return (0);else return (1); 6.判栈满int full(sqstack s)/若栈为满，则返回0，否则返回1if(s.top-s.base)=s.stacksize return (0);else return (1); 根据以上的算法操作现设计如下：在堆栈模块中首先引入一个stringgrid1来代替堆栈中的存储栈，为能判断栈是空的还是满的，设计了两个标签“full”和“empty”来显示此时栈的情况，为了使用者能更好的理解指针在栈操作中的定义，设计了label来显示指针情况，以及显示取出值，建立的edit用来输入进栈元素，要使堆栈能满足出栈操作，设计了一个“取出”按钮，来完成出栈操作，每点击一次，指针先减1，然后取出栈内元素。步骤如下：打开一个form1，将其caption设置为：“堆栈基本概念”，并分别在form1中添加stringgrid1，11个label标签，一个文本编辑框（edit），两个按钮。 建立stringgrid1，分别设置name为：ssg；colcount为：1；rowcount为：5；font为：设置字体大小为12；label16，分别设置name为：t_1、t_2、 t_3、t_4；caption为：t_1为top=-1其余为空白；autosize为：false；label7，设置caption为：按enter键输入；label8，设置name为：le；caption为：empty； color为：c1red；label911，设置name为：if、outr、outv；caption为：空白；edit1，设置name为：inp；text为：空白；button1，设置name为：pop；caption为：取出；button2，设置name为：end；caption为：结束。根据以上的控件及其属性值，设计了如图3-4的界面： 图3-4 堆栈界面图在菜单中，我们通过调用winexec函数，以执行外部命令的方式，调用堆栈.exe程序，来完成基本堆栈的演示。单击窗体中的edit对象inp，再单击对象检视窗口面板中onkeyup事件进入程序编辑窗口，输入程序。在初步编写完本程序后，在经过几次调试，堆栈的程序设计结构就已经设计好了，以下是窗体及控件的运行结果： 图3-5 进栈操作 图3-6 栈满当输入的元素超过栈的存储范围时，就会出现栈满的情况，即top=base，如图3-6所示 图 3-7 堆栈取出图 图3-8栈空当把栈内的所有元素全部取出后，栈为空，即top-base=m，如图3-8所示。开 始输入数据是否溢出栈 满yes取 出noyes停 止no是否栈 空 图3-9 基本堆栈流程图如图3-5所示，并按照图3-9的流程操作。在模块左下的空白框里输入堆栈内容后，安“enter”，接着系统自动判断栈是否满，当栈满时，程序会显示红色的“full”，如果栈未满，可以继续输入元素到堆栈里。点一次“取出”按钮，系统会按照“后进先出”的原则，取出栈内的一个元素，直到栈被取空为止。点击结束退出该模块。堆栈（stack）是有序列表（order list）。堆栈具有先进后出的特性（first in last out），其输入与输出都在同一端，可以想象成是堆积木或洗碗盘一样；于是利用bcb图形用户接口，设计出这个具有互动效果的程序。3.2.3基本队列模块的设计和栈相反，队列是一种先进先出（first in first out，缩写为fifo）的线性表。它只允许在表的一端进行插入，而在另一端删除元素。在队列中，允许插入的一端本叫做队尾（rear），允许删除的一端则称为队头（front）。假设队列为q=（a1，a2，an），那么，a1就是队头元素，an则是队尾元素。队列中的元素是按照a1，a2，an的顺序进入的，退出队列也只能按照这个次序依次退出，也就是说，只有在