实验2堆栈ADT.docx

文档介绍：该【实验2堆栈ADT 】是由【爱的奉献】上传分享，文档一共【17】页，该文档可以免费在线阅读，需要了解更多关于【实验2堆栈ADT 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。实验2堆栈ADT
目标
在这个实验中
·创建两个堆栈ADT的实现一个基于数组表示,另一个基于单链表表示·使用模板产生一个通用的堆栈数据结构·创建一个程序计算后缀形式的算术表达式·创建一个可以正确地处理成对的小括号和大括弧的计算表达式的程序·分析通过使用一个堆栈可以提供的排列种类
概述
一些使用线性数据结构的应用程序并不需要列表ADT提供所支持的所有运算。虽然我们可以使用列表ADT创建这些应用程序,但是,最后产生的程序会有些笨重,而且效率较低。一个可选方法是定义一个新的线性数据结构,它支持更加紧凑的运算集。通过仔细定义这些ADT,可以使我们定义的ADT适合一系列不同的应用程序,产生的数据结构比列表ADT更容易应用,并且更有效。
堆栈是一种限定的线性数据结构的例子。在一个堆栈中,数据项是从最后人栈(栈顶top)到最先入栈(栈底bottom)排列,所有的插人和删除运算都限定在栈顶。我们可以使用Push运算在栈顶插入一个数据项,或使用pop运算删除一个栈顶数据项,一个push和pop运算的序列如下所示。
Pusha
Pushb
Pushc
Pop
Pop
c
b
b
b
a
a
a
a
a
_
_
_
_
_
这些插入和删除运算的限制造成了“后进先出”(LIFO)的行为,这是堆栈的特性。虽然堆栈数据结构定义得很窄,但是,它在系统软件中使用得非常多,对基本堆栈的支持是大多数计算机体系结构的基本组成要素之一。
堆栈是一种被频繁使用的数据结构。虽然所有的程序共享相同的堆栈的定义:一个相同类型的数据项序列,在其一端进行插人和删除。但是堆栈中存储的数据项的类型在各个程序中是各不相同的,一些程序使用整数型的堆栈,一些使用字符型的、浮点数型的、指针型的等等。
通过使用C++的typedef语句解决这个问题。那种方法可以使用,但是它是费力的并且易于出错。
这种更好的方法是 C++的模板类(templateclass)。一个模板是用来作为一
个模式,个模式不是最后的品,但可以用来更快地生最后的品。C++的模板(其中堆是一个例子),可以使我不因每一个堆数据的型不同而建不同的堆,而且不需要繁地使用typedef句。相地,我可以建一个数据型是一般型的堆。在我的代中必指定数据型的地方,我可以用一个任意的字符串代替以后可能希望使用的的数据
型。我将会使用一个字符串“DT”(DataType)代表一般型的数据型。在在声明()中或在定()中指定一个的C++数据型。可以延期指定的数据型,直到生个一个象的例再指定。
下面是一些新的用于建和使用一个模板的。
字符串template<classDT>必正确地在声明之前和每一个成函数之前。住,DT是我用来代表模板中任一数据型的任意符。
句
classStack
{
public;
⋯
可以修改成
template<classDT>
classStack
{
Public;
⋯
一个函数定的开始原来是
Stack::Stack(intmaxNumber)throw(bad_alloc)
在成
Template<classDT>
Stack<DT>::Stack(intmaxNumber)throw(bad_alloc)
在名的每一次使用必包括被尖括号括起来的一般型的数据型名。每一个字符串“Stack”的使用都成了字符串“Stack<DT>”。在构造函数定的例子中,由“Stack::”成“Stack<DT>::”。注意,一个例外情况是构造函数名没有被修改,是“Stack”。
Template<classDT>
Stack<DT>::Stack(intmaxNumber)throw(bad_alloc)
在声明和定文件中出的数据型名被用来代表一般型的字符串代替。
例如,句
int*dataItems;

//Arraycontainingthestackdataitems//(integers)
成
DT*dataItems;

//Arraycontainingthestackdataitems//(generic)
当例化的一个象,真的数据型(在尖括号里)附在名之后。
句
//Aseparatestackimplementationjustforintegers
IntStacksamples(10);
//Datatypespecifiedelsewherebyusingtypedef
Stackline(80);
在成
//Wetellthecompilertomakeacopyofthegenericstackjust//<int>sample(10);
Stack<char> line(80);
文件中的代()提供了一系列ADT的模板(或框架)。在个框架中数据的型故意地不指定,直到
的一个象被例化再指定。因此,,以便根据声明的数据的型建一个。复的程序开境提供了一系列的机制确保代。憾的是,些机制不是准的交叉系。在本中我可以使用一种而有效的机制,在一个使用了的程序中,包括文件()。种方法反了我从来不使
用#include句直接包含代的。然而,在大多数的系中,没有提供其他使用模板的方法,些方法把一个程序的所有代放在一个文件中(一个更差的方法)。
堆ADT的一个部分的模板声明示如下(完整的声明在前中出)。
template<classDT>
classStack
{
public:
⋯
Stack(intmaxNumber=defMaxStackSize)throw(bad_alloc);voidpush(constDT&newDataItem)throw(logic_error);DTpop()throw(logic_error);
⋯
private:
⋯
Dt*dataItems; //Arraycontainingthestackdataitems
};
注意在声明中出的模板参数DT。个参数用来明确引用堆数据型的位置。
堆栈ADT
数据
一个堆中数据的数据型是一般型 DT。
构
堆中数据是从最后入()到最先入(底)性排列的。数据在插入(pushed)或除(popped)。
运算
Stack(intmaxNumber=defMaxStacksize )throw(bad_alloc)
要求:无
果:构造函数。建一个空的堆。一个包含maxNumber个数据的堆分配足的内存(如有必要)。
Stack()
要求:无
果:解析函数。放(free)存一个堆的内存。
voidPush(constDT&newDataItem)throw(logic_error)
要求:堆非。
果:把newDataItem 插人到。
DTpop()throw(logic_error)
要求:堆非空。
果:除最后加入到 (top)的数据并且返回。
voidclear()
要求:无
果:除堆中所有数据。
boolisEmpty()const
要求:无
结果:如果堆栈为空,则返回 true,否则,返回false。
boolisFull()const
要求:无
结果:如果栈满,则返回 true,否则,返回false。
voidshowStructure()const
要求:无
结果:输出堆栈中的数据项。如果堆栈为空,输出 “Emptystack。”请
注意,这个运算只用于测试/调试目的,仅仅支持数据项是C++预先定义的一种数据类型(int,char,等等)的堆栈数据项。
实验2作业单
姓名小组

日期
请在教师布置的练****对应的已布置列上打一个钩(一组材料前面附上这个作业单。

√)。在提交这个实验的
练****br/>
已布置:打钩或

已完成
列出练****编号
实验前练****br/>过渡练****br/>实验中练****1
实验中练****2
实验中练****3
实验后练****1
实验后练****2
总计
实验2实验前练****br/>姓名小组 日期
如果一个ADT要在各种操作环境中都有效地执行,这个ADT的多重实现是必要的。依赖于硬件和应用程序,我们可能希望一个实现减少一些(或全部)
ADT运算执行时间,或者我们可能希望一个实现减少存储ADT数据项的内存数量。在这个实验中,我们开发两种堆栈ADT的实现。一种实现在一个数组中存储堆栈,另一种实现单独存储每个数据项并把这些数据项链接起来构成一个堆
栈。
第一步:使用一个数组存储堆栈数据项,来实现堆栈ADT中的运算。堆栈大小可变,因此,我们需要存储堆栈中可以存储数据项的最大数目(maxSize),最顶端数据项的数组索引(top),以及堆栈数据项本身(dataItems)。基于文件


中的声明,

showStructure

运算的一个实
现。
constintdefMaxStackSize=10;

//Defaultmaximumstacksize
template<classDT>
classStack
{
public:
//Constructor
Stack(intmaxNumber=defMaxStackSize)throw(bad_alloc);//Destructor
~Stack();
//Stackmanipulationoperations
voidpush(constDT&newDataItem)

throw(logic_error);
DTpop()throw(logic_error);
voidclear();
//Stackstatusoperations
boolisEmpty()const;
boolisFull()const;

//Stackisempty
//Stackisfull
//Outputthestackstructure--usedintesting/debuggingvoidshowStructure()const;
private:
//Datamembers
intmaxSize,
top;
DT*dataItems;

//Maximumnumberofdataitemsinthestack
//Indexofthetopdataitems
//Arraycontainingthestackdataitems
};
第二步:,并确认形成代码文档。在堆栈ADT的数组实现中,当声明(构造)堆栈时,我们需要为堆栈分配内存。分配的数组必须足够大,以便满足在一个特定应用程序中可能用到的最大的堆栈。遗憾的是,大部分时间内,不会用到最大的堆栈,额外的内存没有使用。
一个改进的方法是,随着把新数据项加人到堆栈中,按数据项分配内存。用这种方法,只有当我们确实需要时,才分配内存。然而,由于随时在分配内存,所以,数据项占据一段不连续的内存。其结果是,我们需要把这些数据项链接在一起,构成堆栈的链表表示。
创建一个堆栈ADT的链表实现与开发一个数组实现相比较,编程任务更具有挑战性。简化这个任务的一种方法是把这个实现分为两个模板化的类:一个类集中在整个堆栈结构(类Stack)上,另一个类集中在链表的单个结点(类StackNode)上。
从类StackNode开始。链表的每一个结点包括一个堆栈数据项和一个指向链表下一个数据项节点的指针。类StackN0de提供的仅有一个函数是创建一个指定节点的构造函数。
对类StackNode的访向只限于Stack类的成员函数。通过把所有的StackNode的成员声明为私有的,可以阻止别的类直接指向链表节点,通过把Stack类声明为StackNode类的友元(friend)可以使StackNode类的成员成为Stack类可访问的。这些属性反映在下面的类声明中,。
Template<classDT>classStack;
template<classDT> classStackNode
{
private:
//Constructor
StackNode(constDT&nodeData,StackNode*nextptr);
//Datamembers
DTdataltem;StackNode*next;friendclassStack<DT>;

//Stackdataitem
//Pointertothenextdataitem
};
请注意上面StackNode声明中的头两行。这种前向式声明是C++用来解决典型的编译难题。在StackNode语句中引用Stack。
FriendclassStack<DT>;
但是编译器没有遇到Stack类,通常会发出一个指向一个未知数据类型的出错消息。我们可以把Stack的声明移到StackNode的声明之前,这样就可以确保编译器在指向StackNode之前已经看到Stack。问题马上又出现了,在StackNode的声明之前Stack的声明中包含对StackNode的引用。这是一个令人左右为难的规定,因为我们无法让两者在程序中同时首先出现。
C++通过允许一个数据类型在真正声明之前宣称它的存在来解决这个问题。编译器注意到它会在后面继续声明。这与我们在遇到一个函数定义之前而在程序的开始介绍这个函数的原型是类似的。
类StackNode的构造函数用于向堆栈增加节点。例如,下面的语句向一个字符堆栈中增加一个包含‘d的’节点。请注意,模板参数DT必须是char类型,
top是StackNode类型。
top=newStackNode<DT>( ‘dop’);,t
new运算为链表节点分配内存,并且调用类StackNode的构造函数,传递一个插人的数据项(‘d)’和一个指向链表下一个节点的指针(top)。
最后,赋值运算符把top指针赋给新分配的节点,从而完成节点的创建和连
接。
类Stack的成员函数也实现了堆栈ADT中的运算。一个指针始终指向链表的开始节点,或者,也可以说是堆栈的顶部。。
tesplate<classDT>
classStack
{
public:
//Constructor
Stack(intignored=0);
Destructor~Stack();
Stackmanipulationoperations
voidpush(constDT&newDataItem)throw(bad_alloc);
DTpop() throw(logic_error);
voidclear(); //Clearstack
//Stackstatusoperations
boolisEmpty()const; //Isstackempty?
boolisFull()const; //Isstackfull?
Outputthestackstructure--usedintesting/debuggingvoidshowStructure()const;
private:
//Datamember
StackNode<DT>*top; //Pointertothetopdataitem
};
第三步:通过使用一个单链表存储堆栈数据项,实现堆栈ADT中的运算。链表的每一个节点应该包括一个堆栈数据项(dataItem)和一个指向堆栈中下一个数据项节点的指针。我们的实现还应该包含一个指向堆栈的最顶部数据项节点的指针(top)。,。
第四步:,确认形成代码文档。
实验

2

过渡练****br/>姓名小组

日期

ADT的实现。
命令
+x
-

中的测试程序允许我们使用下面的命令交互式地测试堆栈
操作
压入数据项x到栈顶
弹出栈顶数据项并输出