《C++课程设计栈类的封装.doc》由会员分享，可在线阅读，更多相关《C++课程设计栈类的封装.doc（20页珍藏版）》请在三一办公上搜索。
1、 报告编号：综合课程设计报告栈类的设计与使用学生姓名： 马啸 唐啸 李明 王飞 张少华 张俊 指导教师： 李杰 所 在 系： 电 子 信 息 系所学专业： 计算机科学与技术 年 级： 08级计算机(1)班 2010年6月目 录摘 要1第一章 前言2第二章 需求分析3第三章 设计研究的主要工作43.1 总体设计43.2 详细设计63.2.1 用顺序链表实现63.2.2 用单链表实现73.2.3 用双向链表实现10第四章 系统实现13第五章 总结17参考文献：17栈类的设计与使用摘 要本小组在这次课程设计中选择了“栈类的设计与运用”这个课题，主要目的是要利用C+程序设计语言实现栈类的封装，使得整个
2、程序可以完成出栈、进栈、获取栈顶元素、清空栈等一系列基本操作，也可以通过此次实训巩固C+和数据结构中的很多知识点。在实训过程中，我们通过分工合作完成了一个个独立的模块，并将这些模块整合起来，完成了这次设计。在设计中，我们考虑了封装栈的多种形式，采用了顺序链表、单链表、双向链表三种方法实现了栈的封装，并运用了多层菜单的模式，利用类模板实现了对多种类型数据的进、入栈，方便了用户的选择，实现了完全用户操作的目的，整个界面简洁却不失全面，层层递进，可以返回，并在实现出栈、入栈功能的基础上，可以按照用户的意愿来控制入栈、出栈的元素个数，更体现出程序的人性化。通过此次实训，我们不仅巩固了专业课的知识点，而
3、且在平时查阅资料的过程中学到了很多新的知识，收获颇丰。关键词：栈 类的封装 函数模板 第一章 前言我们这组所选的课题是“栈的设计与使用”，也就是将栈封装成一个类，完成栈的一些基本操作，例如入栈、出栈、获取栈顶元素、获取栈内元素个数等。在本学期所学的数据结构课程里，我们已经学过了关于栈的一些基本知识，栈是限制在表的一端进行插入和删除运算的线性表，通常称插入，删除的这一端为栈顶，另一端为栈底。栈分为两种类型，顺序栈和链式栈。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。栈顶位置是随着进栈和退栈操作而变化的栈的链式存储结构称为链栈，它的运算是受限的单链表，插入和删除
4、操作仅限制在表头位置上进行。所以为了能让用户可以使用多种方式封装的栈，我们准备在设计中，采用了三种实现方式：顺序链表、单链表和双向链表，以满足各种不同的需求。由于栈结构具有的后进先出的固有特性，使得栈在程序设计中得到广泛地运用。利用栈可以进行数制转换、文字编辑和表达式计算等很多应用。由此可以看出栈在程序设计中的重要地位，所以我们这一组专门选择了这一课题，为了让程序员在编程中多次使用栈且不必考虑入栈、出栈等操作细节，减少程序员程序设计中的工作量。我们准备用类模板实现栈类的封装，程序员就在使用栈类新建栈对象时只要传入数据类型就可以方便地对各种类型的数据进行入栈、出栈等操作，提高程序员程序设计的效率
5、。第二章 需求分析2.1 完成数据元素的入栈在设计中，我们可以让用户对四种类型的数据元素进行入栈操作，int double string char类型，首先，用户可以选择某一种类型的数据，然后可以自定义入栈元素的个数并输入相应数据，使元素入栈。2.2 实现数据元素的出栈出栈时，用户可以选择出栈元素的个数，按照栈的“后入先出”原则，使相应个数的元素出栈，这时，用户仍可以继续输入元素出栈的个数，使剩下的元素依次出栈，如果栈空了，会返回栈已空，无法再对元素进行出栈操作了。2.3 获取栈顶元素当用户将一批元素入栈后，可以通过菜单上的选项完成获取栈顶元素的功能，更方便的是，在用户对元素进行随意出栈的过程
6、中，也可随时获得相应的栈顶元素，当栈为空时，还可返回获取失败的信息。2.4 获取栈内元素个数当用户将一批元素入栈后，可以通过菜单上的选项完成获取栈内元素个数的功能，而且，在用户对元素进行随意出栈的过程中，也可随时获得相应的栈内元素个数，当栈为空时，还可返回获取失败的信息。第三章 设计研究的主要工作3.1 总体设计我们为了这次课程设计，在工作开始前就画了流程图，使得整个系统更加明了化，系统采用三级选择操作，由用户进行操作选择不同结构的栈类、选择测试的数据类型、选择该数据的操作。流程图如下：图 3.1.1图3.1.1流程图说明了主函数调用其他函数的总体规划,根据用户的选择，选择使用不同结构封装的栈
7、，当用户选择了要测试的结构的栈时，进入第二层选择。图 3.1.2图3.1.2显示第二级菜单，根据用户的选择，测试不同类型的数据。选择后会进入第三级菜单,即进入图3.1.3的流程图 3.1.3图3.1.3显示了底层菜单的流程图，根据用户的选择，运行入栈、出栈等不同的操作。3.2 详细设计3.2.1 用顺序链表实现根据需要定义了一个栈类，class SqStack，用以实现的功能有：初始化一个栈、数据元素的入栈（int Push(T num)）和出栈（int Pop(T &num)）、获取栈顶元素（int GetTop(T &num)）和栈的长度（int size()）、判断栈是否为空（int E
8、mpty( )）；下图显示了栈动态分配空间和指针指向的变化 图3.2.1.13.2.2 用单链表实现在单链表程序中定义了两个类，结点类（class node）和栈类（class stack），可以实现的功能有：初始化一个栈、数据元素的入栈（void Push(T e)）和出栈（T Pop( )）、获取栈顶元素（T GetTop( )）和栈的长度（int Getlength( )）、判断栈是否为空（bool Empty( )）。在栈类里，定义了一个构造函数stack( )，完成栈的初始化，在这个功能的实现中，利用运算符new给栈的头指针动态分配空间head=new node，在申请内存成功的情况
9、下，利用语句head-next=NULL；length=0，即可完成栈的初始化。入栈时，可执行以下操作：将待入元素放入待入结点内，然后修改头指针，使其指向待入结点，并将待入结点的指针指向空，这时，即完成一个元素的入栈操作，流程图和示意图如下：图3.2.2.1Head NULL1Head NULL1待入栈元素图3.2.2.2出栈时，可执行以下操作：修改头指针的指向，使其指向它所指结点的下一个结点，并同时释放它原先所指的结点，这样，即完成一个元素的出栈操作，流程图和示意图如下：图3.2.2.3Head21 NULL待出栈元素Head21 NULL图3.2.2.43.2.3 用双向链表实现在实现栈封
10、装中，使用到了两个类，分别是class Node和class Stack。Node类表示双向链表中单个结点的结构。Stack类中封装了对双向链表结点的操作完成栈的基本功能。入栈主要是申请一个新的Node大小的空间，申请时通过必要的数据完成Node结点的初始化，申请到的空间的基地址给end-next，然后将end指针指向end-next。最后进行len+1操作，记录下栈中元素个数。图3.2.3.1图3.2.3.2出栈时，将尾结点（end指向的结点）的值赋给e，使e将尾结点的值带回。使temp指向尾结点，然后通过其前趋prio找到尾结点的前一结点，调整end的地址，使指向尾指点的前趋结点，然后将t
11、emp指向的空间(原尾结点空间)释放掉。进行len-1操作，记录下栈中元素个数。图3.2.3.3图3.2.3.第四章 系统实现图 4.1图4.1展现了程序运行时的初始画面，也就是给用户提供了三种封装栈的方式，用户可以自行选择图 4.2图4.2展示了用户随意进入一种实现方法后的画面，在这级菜单上，用户可以选择所要用的数据元素的类型，程序提供了五种图 4. 3图4.3展示的是用户随意选择一种数据类型后所进入的画面，这时用户可以选择执行哪项基本操作图 4.4图4.4展示的是执行入栈的过程图 4.5图4.5展示了数据出栈的过程，此时，用户可按自己意愿选择出栈的元素个数，当元素全部出栈后，会显示栈已空图
12、 4.6 图4.6展示了获取栈内元素个数和栈顶元素的过程，当栈内元素为空时，执行上两步操作时，会提示操作失败！第五章 总结 本次实验，我们小组运用了3种方法来实现栈类的设计，分别为：顺序链表法、单链表法、双向链表法。在实验初，我们小组仅仅只实现了数据元素简单的一次性入栈、出栈等操作，操作过程不具有人机交互的智能性，不能决定出入栈元素的个数，而且仅仅包含两种数据类型：int、char，所含数据类型过少，程序不够茁壮。在实验中经授课老师的指导，我们对程序进行了修改。使其更具有人机交互的能力，具有多层面的选择提示，基本上能满足多种数据类型的输入输出方式。 本小组所设计的内容，具有以下优点：1. 对栈
13、封装后，可以便于用户的多次使用；2. 多种类型数据元素的设置和类模板的使用，使用户的操作更具全面化与简便化；3. 多级菜单的设置，让人机交互的好处得到了充分展示；4. 用户在定义所要操作的元素个数时更具人性化。 但由于我们的知识还不是很充分，所以整个程序还有着不足之处，比如： 通过此次实训，我们锻炼了自己的动手能力，巩固了本学期在C+和数据结构课程里所学的知识点，更在整个过程中加强了团队配合的能力。最后谢谢老师的指导，谢谢各位组员的努力！参考文献：1 数据结构（C语言版） 严蔚敏 吴伟民 北京：清华大学出版社 2009年9月2 C+面向对象程序设计谭浩强 北京：清华大学出版社 2006年1月3 C+面向对象程序设计题解与上机指导谭浩强 北京：清华大学出版社 2006年1月4 数据结构教程上机实验指导李春葆 北京：清华大学出版社 2005年7月安徽师范大学皖江学院课程设计成绩评定单题目：学生姓名指导教师指导教师评语：指导教师评定设计成绩等级指导教师（签章）： 200 年 月 日
