- 1、本文档共17页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
实验2堆栈ADT
实验2 堆栈ADT
目标
在这个实验中
·创建两个堆栈ADT的实现一个基于数组表示,另一个基于单链表表示
·使用模板产生一个通用的堆栈数据结构
·创建一个程序计算后缀形式的算术表达式
·创建一个可以正确地处理成对的小括号和大括弧的计算表达式的程序
·分析通过使用一个堆栈可以提供的排列种类
概述
一些使用线性数据结构的应用程序并不需要列表ADT提供所支持的所有运算。虽然我们可以使用列表ADT 创建这些应用程序,但是,最后产生的程序会有些笨重,而且效率较低。一个可选方法是定义一个新的线性数据结构,它支持更加紧凑的运算集。通过仔细定义这些ADT,可以使我们定义的ADT适合一系列不同的应用程序,产生的数据结构比列表ADT更容易应用,并且更有效。
堆栈是一种限定的线性数据结构的例子。在一个堆栈中,数据项是从最后人栈(栈顶top)到最先入栈(栈底bottom)排列,所有的插人和删除运算都限定在栈顶。我们可以使用Push 运算在栈顶插入一个数据项,或使用pop运算删除一个栈顶数据项,一个push和pop运算的序列如下所示。
Push a Push b Push c Pop Pop
c
b b b
a a a a a
_ _ _ _ _
这些插入和删除运算的限制造成了“后进先出”( LIFO)的行为,这是堆栈的特性。虽然堆栈数据结构定义得很窄,但是,它在系统软件中使用得非常多,对基本堆栈的支持是大多数计算机体系结构的基本组成要素之一。
堆栈是一种被频繁使用的数据结构。虽然所有的程序共享相同的堆栈的定义: 一个相同类型的数据项序列,在其一端进行插人和删除。但是堆栈中存储的数据项的类型在各个程序中是各不相同的,一些程序使用整数型的堆栈,一些使用字符型的、浮点数型的、指针型的等等。
通过使用C++的typedef语句解决这个问题。那种方法可以使用,但是它是费力的并且易于出错。
这种更好的方法是C++的模板类(template class)。一个模板是用来作为一个模式,这个模式不是最后的产品,但可以用来更快地产生最后的产品。C++的模板类(其中堆栈是一个例子), 可以使我们不因为每一个堆栈数据项的类型不同而创建不同的堆栈实现,而且不需要频繁地使用typedef语句。相应地,我们可以创建一个数据类型是一般类型的堆栈实现。在我们的代码中必须指定数据类型的地方,我们可以用一个任意的字符串代替以后可能希望使用的实际的数据类型。我们将会使用一个字符串“DT” ( Data Type )代表一般类型的数据类型。现在在类声明(class.h文件)中或在类定义(class.cpp文件)中指定一个实际的C++数据类型。可以延期指定实际的数据类型,直到产生这个类一个对象的实例时再指定。
下面是一些新的用于创建和使用一个模板类的简单规则。
字符串template class DT必须正确地在类声明之前和每一个类成员函数之前。请记住,DT是我们用来代表模板类中任一数据类型的任意标识符。
语句
class Stack
{
public;
…
可以修改成
template class DT
class Stack
{
Public;
…
一个函数定义的开始原来是
Stack :: Stack (int maxNumber) throw (bad_alloc)
现在成为
Template class DT
StackDT:: Stack (int maxNumber) throw (bad_alloc)
现在类名的每一次使用必须包括被尖括号括起来的一般类型的数据类型名。每一个字符串“Stack”的使用都变成了字符串“StackDT”。在构造函数定义的例子中,类标识由“Stack::”变成“StackDT::”。还请注意,一个例外情况是构造函数名没有被修改,还是“Stack”。
Template class DT
StackDT:: Stack (int maxNumber) throw (bad_alloc)
在类声明和类定义文件中出现的数据类型名应被选择用来代表一般类型的字符串代替。
例如,语句
int *dataItems; // Array containing the stack data items
// (integers)
成为
DT *dataItems; //Array containing the stack data items
// (generic)
当实例化类的一个对象时,真实的数据类型(在尖括号里)附在类名之后
文档评论(0)