实验2堆栈ADT

1、实验 2 堆栈 ADT目标在这个实验中创建两个堆栈ADT勺实现一个基于数组表示，另一个基于单链表表示使用模板产生一个通用的堆栈数据结构创建一个程序计算后缀形式的算术表达式创建一个可以正确地处理成对的小括号和大括弧的计算表达式的程序分析通过使用一个堆栈可以提供的排列种类概述一些使用线性数据结构的应用程序并不需要列表 ADT 提供所支持的所有运 算。虽然我们可以使用列表 ADT 创建这些应用程序，但是，最后产生的程序会 有些笨重， 而且效率较低。 一个可选方法是定义一个新的线性数据结构， 它支持 更加紧凑的运算集。通过仔细定义这些 ADT，可以使我们定义的ADT适合一系 列不同的应用程序，产生的数

2、据结构比列表 ADT 更容易应用，并且更有效。堆栈是一种限定的线性数据结构的例子。 在一个堆栈中， 数据项是从最后人 栈（栈顶top）到最先入栈（栈底bottom ）排列，所有的插人和删除运算都限定 在栈顶。我们可以使用 Push 运算在栈顶插入一个数据项，或使用 pop 运算删 除一个栈顶数据项，一个 push 和 pop 运算的序列如下所示。Push aPush bPush cPopcbbbaaaaPop这些插入和删除运算的限制造成了 后进先出”（LIFO的行为，这是堆栈的 特性。虽然堆栈数据结构定义得很窄，但是，它在系统软件中使用得非常多，对 基本堆栈的支持是大多数计算机体系结构的基本组

3、成要素之一。堆栈是一种被频繁使用的数据结构。 虽然所有的程序共享相同的堆栈的定义 一个相同类型的数据项序列， 在其一端进行插人和删除。 但是堆栈中存储的数据 项的类型在各个程序中是各不相同的， 一些程序使用整数型的堆栈， 一些使用字 符型的、浮点数型的、指针型的等等。通过使用C+的typedef语句解决这个问题。那种方法可以使用，但是它是 费力的并且易于出错。这种更好的方法是C+的模板类（template class ）。一个模板是用来作为一个模式，这个模式不是最后的产品，但可以用来更快地产生最后的产品。C+的模板类(其中堆栈是一个例子 ), 可以使我们不因为每一个堆栈数据项的类型不同 而创建

4、不同的堆栈实现，而且不需要频繁地使用 typedef 语句。相应地，我们可 以创建一个数据类型是一般类型的堆栈实现。 在我们的代码中必须指定数据类型 的地方，我们可以用一个任意的字符串代替以后可能希望使用的实际的数据类 型。我们将会使用一个字符串“DT ( Data Type代表一般类型的数据类型。现 在在类声明( class.h 文件)中或在类定义( class.cpp 文件)中指定一个实际的 C+数据类型。可以延期指定实际的数据类型，直到产生这个类一个对象的实例 时再指定。面是一些新的用于创建和使用一个模板类的简单规则。字符串template vclass DT必须正确地在类声明之前和每一

5、个类成 员函数之前。请记住， DT 是我们用来代表模板类中任一数据类型的任 意标识符。语句class Stackpublic;可以修改成template class StackPublic;一个函数定义的开始原来是Stack : Stack (int maxNumber) throw (bad_alloc)现在成为Template Stack: Stack (int maxNumber) throw (bad_alloc)现在类名的每一次使用必须包括被尖括号括起来的一般类型的数据类型名。 每一个字符串“ Stack ”的使用都变成了字符串“ Stack ”。在构造函数定 义的例子中，类标识由“

6、 Stack: ”变成“ Stack: ”。还请注意，一个例 外情况是构造函数名没有被修改，还是“ Stack ”。Template Stack: Stack (int maxNumber) throw (bad_alloc)在类声明和类定义文件中出现的数据类型名应被选择用来代表一般类 型的字符串代替。int *dataItems;/ Array containing the stack data items / (integers)例如，语句成为DT *dataItems;/Array containing the stack data items / (generic)当实例化类的一个对象

7、时，真实的数据类型（在尖括号里）附在类名之 后。语句/A separate stack implementation just for integersIntStack samples（10）;/ Data type specified elsewhere by using typedefStack line（80）;现在成为/We tell the compiler to make a copy of the generic stack just /for integers and to make another just for characters.Stack sample（10）;St

8、ack line（80）;实现文件中的代码（ classname.cpp 文件中）提供了一系列 ADT 类实 现的模板（或框架） 。在这个框架中数据项的类型故意地不指定，直到 类的一个对象被实例化时再指定。因此，编译器在遇到一列声明时必须 访问 .cpp 文件中的代码，以便根据声明的数据项的类型创建一个实现。 复杂的程序开发环境提供了一系列的机制确保访问代码。遗憾的是，这 些机制还不是标准的交叉系统。在本书中我们可以使用一种简单而有效 的机制，在一个使用了类的程序中， 应该包括实现文件 （classname.cpp 文件）而不是头文件 classname.h 。这种方法违反了我们从来不应该使

9、用伽elude 语句直接包含代码的规则。然而，在大多数的系统中，没 有提供其他使用模板类的方法，这些方法把一个程序的所有代码放在一 个文件中（一个更差的方法） 。堆栈 ADT 的一个部分的模板类声明显示如下 （完整的声明在试验前练习中给 出）。template class Stackpublic:Stack (int maxNumber=defMaxStackSize) throw ( bad_alloc ); void push ( const DT &newDataItem ) throw ( logic_error ); DT pop( ) throw (logic_error );pr

10、ivate:Dt *dataItems;/Array containing the stack data items;请注意在类声明中出现的模板参数 DT这个参数用来标记明确引用堆栈数 据项类型的位置。堆栈 ADT数据项一个堆栈中数据项的数据类型是一般类型DT。结构堆栈中数据项是从最后入栈(栈顶)到最先入栈(栈底)线性排列的。数据 项在栈顶插入( pushed )或删除( popped )。运算Stack (int maxNumber=defMaxStacksize)throw (bad_alloc)要求： 无结果： 构造函数。创建一个空的堆栈。为一个包含maxNumber 个数据项的堆栈分配

11、足够的内存(如有必要)。Stack ()要求： 无结果：解析函数。释放(free)存储一个堆栈的内存。void Push ( const DT &newDataItem ) throw (logic_error) 要求： 堆栈非满。结果： 把 newDataItem 插人到栈顶。DT pop ( ) throw ( logic_error ) 要求： 堆栈非空。结果：删除最后加入到栈顶(top)的数据项并且返回void clear ( )要求： 无结果： 删除堆栈中所有数据项。bool isEmpty ( ) const 要求： 无结果： 如果堆栈为空，则返回 true ，否则，返回 fals

12、e 。bool isFull ( ) const 要求： 无 结果： 如果栈满，则返回 true ，否则，返回 false 。void showStructure ( ) const 要求： 无结果：输出堆栈中的数据项。如果堆栈为空，输出“Empty stack。”请注意，这个运算只用于测试/调试目的，仅仅支持数据项是C+预先定义的一种数据类型( int,char ，等等)的堆栈数据项。实验2作业单日期姓名小组请在教师布置的练习对应的已布置列上打一个钩（ 话。在提交这个实验的 一组材料前面附上这个作业单。练习已布置：打钩或 列出练习编号已完成实验前练习过渡练习实验中练习1实验中练习2实验中练习

13、3实验后练习1实验后练习2总计实验2实验前练习日期姓名小组如果一个ADT要在各种操作环境中都有效地执行，这个ADT的多重实现是 必要的。依赖于硬件和应用程序，我们可能希望一个实现减少一些（或全部） ADT运算执行时间，或者我们可能希望一个实现减少存储 ADT数据项的内存数 量。在这个实验中，我们开发两种堆栈 ADT的实现。一种实现在一个数组中存 储堆栈，另一种实现单独存储每个数据项并把这些数据项链接起来构成一个堆 栈。第一步： 使用一个数组存储堆栈数据项，来实现堆栈 ADT 中的运算。堆栈 大小可变， 因此，我们需要存储堆栈中可以存储数据项的最大数目 (maxSize) ， 最顶端数据项的数组

14、索引 (top) ，以及堆栈数据项本身( dataItems )。基于文件 stackarr.h 中的声明，在文件 show5.cpp 中给出了 showStructure 运算的一个实 现。const int defMaxStackSize = 10;/Default maximum stack sizetemplate class Stackpublic:/ConstructorStack ( int maxNumber = defMaxStackSize ) throw (bad_alloc); /DestructorStack();throw (logic_error);/Stack

15、is empty/Stack is full/Stack manipulation operations void push (const DT &newDataItem) DT pop() throw (logic_error);void clear();/Stack status operations bool isEmpty () const;bool isFull () const;/Output the stack structure - used in testing/debugging void showStructure () const;private:/Data membe

16、rsint maxSize,top;DT *dataItems;/Maximum number of data items in the stack /Index of the top data items/Array containing the stack data items;第二步： 在文件 stackarr.cpp 中保存堆栈 ADT 的数组实现，并确认形成代 码文档。在堆栈 ADT 的数组实现中，当声明(构造)堆栈时，我们需要为堆栈 分配内存。 分配的数组必须足够大， 以便满足在一个特定应用程序中可能用到的 最大的堆栈。遗憾的是，大部分时间内，不会用到最大的堆栈，额外的内存没有 使

17、用。一个改进的方法是，随着把新数据项加人到堆栈中，按数据项分配内存。用 这种方法，只有当我们确实需要时，才分配内存。然而，由于随时在分配内存， 所以，数据项占据一段不连续的内存。 其结果是， 我们需要把这些数据项链接在 一起，构成堆栈的链表表示。创建一个堆栈ADT的链表实现与开发一个数组实现相比较，编程任务更具有挑战性。简化这个任务的一种方法是把这个实现分为两个模板化的类：一个类集中在整个堆栈结构（类Stack ）上，另一个类集中在链表的单个结点（类StackNode ）上。从类StackNode开始。链表的每一个结点包括一个堆栈数据项和一个指向 链表下一个数据项节点的指针。类 StackNO

18、de提供的仅有一个函数是创建一个 指定节点的构造函数。对类StackNode的访向只限于 Stack类的成员函数。通过把所有的 StackNode的成员声明为私有的，可以阻止别的类直接指向链表节点，通过把 Stack类声明为StackNode类的友元（friend）可以使StackNode类的成员成为 Stack类可访问的。这些属性反映在下面的类声明中，这些类声明在文件 stacklnk.h 中。Template class Stack;template class StackNodeprivate:/ Con structorStackNode （const DT &n odeData, S

19、tackNode *n extptr ）;/ Data membersDT dataltem;/ Stack data itemStackNode *n ext;/ Poin ter to the next data itemfriend class Stack;请注意上面StackNode声明中的头两行。这种前向式声明是C+用来解决典型的编译难题。在 StackNode语句中引用Stack。Frie nd class Stack ;但是编译器没有遇到Stack类，通常会发出一个指向一个未知数据类型的出 错消息。我们可以把Stack的声明移到StackNode的声明之前，这样就可以确 保编译器

20、在指向StackNode之前已经看到Stack。问题马上又出现了，在StackNode的声明之前Stack的声明中包含对StackNode的引用。这是一个令 人左右为难的规定，因为我们无法让两者在程序中同时首先出现。C+通过允许一个数据类型在真正声明之前宣称它的存在来解决这个问题。 编译器注意到它会在后面继续声明。这与我们在遇到一个函数定义之前而在程序 的开始介绍这个函数的原型是类似的。类StackNode的构造函数用于向堆栈增加节点。例如，下面的语句向一个 字符堆栈中增加一个包含d的节点。请注意，模板参数 DT必须是char类型，d o)；new运算为链表节点分配内存，并且调用类StackN

21、ode的构造函数，传递一个插人的数据项（6 和一个指向链表下一个节点的指针（top）。最后，赋值运算符把top指针赋给新分配的节点，从而完成节点的创建和连 接。top 是 StackNode 类型。top = new StackNode (类Stack的成员函数也实现了堆栈ADT中的运算。一个指针始终指向链表 的开始节点，或者，也可以说是堆栈的顶部。文件 stacklnk.h中给出了如下所 示的类Stack的声明。tesplate class Stackpublic:/ Con structorStack ( int ignored = 0 ); / DestructorStack ();/

22、Stack mani pulati on operati onsvoid push ( const DT &newDataItem ) throw ( bad_alloc);DT pop () throw (logic_error ); void clear ();/ Stack status operati onsbool isEmpty () con st;bool isFull () con st;/ Clear stack/ Is stack empty?/ Is stack full?/ Output the stack structure - used in test in g/d

23、ebugg ing void showStructure () con st;private:/ Data memberStackNode *top;/ Poi nter to the top data item;第三步：通过使用一个单链表存储堆栈数据项，实现堆栈ADT中的运算。链表的每一个节点应该包括一个堆栈数据项（dataltem）和一个指向堆栈中下一个数据项节点的指针。我们的实现还应该包含一个指向堆栈的最顶部数据项节点 的指针（top）。我们的实现基于文件stacklnk.h中类的声明，在文件show5.cpp 中给出了 showStructure运算的一个实现。第四步：把堆栈ADT的链

24、表实现保存在文件stacklnk.cpp中，确认形成代 码文档。实验2过渡练习日期姓名小组文件test2.cpp中的测试程序允许我们使用下面的命令交互式地测试堆栈 ADT的实现。命令操作+X压入数据项X到栈顶弹出栈顶数据项并输出E报告堆栈是否为空F报告堆栈是否已满C清空堆栈Q退出测试程序第一步：编译并链接测试程序。注意到编译这个程序将会把堆栈ADT的数组实现（在文件stackarr.cpp中）编译为一个字符堆栈的数组实现。第二步：增加测试项目完成下面的测试计划 从一个仅包含一个数据项的堆栈中弹出一个数据项。 向一个经过一系列弹出运算已为空的堆栈中压人一个数据项。 从一个已满的堆栈中弹出一个数据

25、项（数组实现）。 清空堆栈。第三步：执行测试程序，如果在堆栈 ADT的数组实现中发现了错误，改正 这些错误并且重新执行测试计划。第四步：修改测试程序，使文件stackarr.cpp中的堆栈ADT的链表实现代 替数组实现。第五步：重新编译并链接测试程序。注意到编译这个程序将会把堆栈ADT链表实现（在文件stackarr.cpp中）编译为一个字符堆栈的链表实现。第六步：使用测试程序检查堆栈ADT的链表实现，如果在堆栈 ADT的链表 实现中发现了错误，改正这些错误并且重新执行测试计划。堆栈ADT中运算的测试计划测试项目命令预期结果检杳一系列压入运算 一系列弹出运算 多压入运算 多弹出运算 栈空？栈满

26、？清空堆栈 栈空？栈满？+a +b +c +d +e +f E F E Fa b c daa e fafalse false 空堆栈 true false注：栈顶数据项以黑体显示实验 2 实验中练习 1姓名小组日期我们一般使用中缀形式书写算术表达式，即每一个运算符在它的运算数中 间，如下面的表达式： (3+4)*(5/2)虽然我们习惯于表达式中缀形式，但是，中缀形式有一个缺点，必须使用圆 括号指定运算顺序，这些圆括号极大地增加了运算过程的复杂性。如果我们简单地从左到右对运算数进行运算，那么运算会简单的多。遗憾的 是，这种从左到右的运算策略不能应用在中缀形式的算术表达式上。 不过， 可以 应用在

27、后缀形式的表达式上。 在后缀形式的算术表达式中， 每一个运算符紧跟在 它的运算数之后，上面的表达式的后缀形式可以写成： 34 + 52/* 注意到在这两种形式中，运算数的次序是相同的（从左到右地读） ，而运算 符的次序不同， 但是， 后缀形式的运算符的次序和他们运算的次序是相同的， 一 开始后缀形式的表达式的结果难以读取， 但是容易运算。 我们所需要做的就是建 立一个堆栈存放中间结果。假设我们有一个后缀形式的算术表达式， 包括单数字的非负整数和四个基本 的算术运算符（加，减，乘和除） 。这个表达式可以通过下面的与一个浮点数字 堆栈相连结的运算法则进行运算。逐字符地读表达式，每一个字符被读取时

28、, 做以下工作。 如果字符是一个单数字的（字符 0 到9 ）, 则把相应的浮点数字存 人堆栈中。如果字符是一个算术运算符（字符+, -, *, / ） ，那么从堆栈中弹出一个数字，称为 operand1。从堆栈中弹出一个数字，称为 operand2。 使用算术运算符计算这两个运算数，如下 Result = operand2 运算符 operand1 把 result 压入堆栈。 当表达式结束时， 从堆栈中弹出剩下的数字， 这个 数字就是表达式的值。在下面的算术表达式上应用这个运算法，则34+52/*产生下面的计算：3 :压入 3.04 :压入 4.0+ :弹出， operand1=4.0 弹出

29、， operand2=3.0 计算， result=3.0+4.0=7.0 压入 7.05 :压入 5.02 :压入 2.0/ :弹出， operand1=2.0 弹出， operand2=5.0 计算， result=5.0/2.0=2.5 压入 2.5* :弹出， operand1=2.5 弹出， operand2=7.0 计算， result=7.0*2.5=17.5 压入 17.5n : 弹出，表达式的值 =17.5第一步： 创建一个应用程序，该程序可以读取一个后缀形式的算术表达式，进行运算，并且显示结果。假设这个后缀形式的算术表达式，包括单数字的、非 负的整数（侄9）和四个基本的算术

30、运算符（ +-,和还可以假设 算术表达式从键盘输人并且所有的字符都在一行，把程序保存在 postfix.cpp文 件中。第二步：填充每一个算术表达式的预期结果，完成下面的测试计划。我们可 能想在这个测试计划中增加一些算术表达式。第三步：执行测试计划。如果发现程序中有错误，改正这些错误并且重新执 行测试计划。后缀形式的算术表达式的运算程序测试计划测试项目算术表达式预期结果检杳一个运算符嵌套运算不对称运算所有运算符在最后零除单个数字34+34+52/*34+52/* 4675-+* 02/7实验2实验中练习2姓名小组日期相对于一个堆栈从数组下标 0到下标maxSize-1的向上的数组实现，我们 可

31、以容易地构造一个从数组下标 maxSize-1至汁标0的向下的数组实现。我们 可以把这种 向下”的数组实现和在实验前创建的 向上”的数组实现结合起来，形 成一个双堆栈ADT的实现。在此实现中，两个堆栈共用同一个数组一假设两个 堆栈的数据项数之和不会超过 maxSize。如果这看起来是一个双堆栈的奇异类型，它不是我们构造的。它是一个著名的处理操作系统中进程内存部分的方法。第一步： 创建一个堆栈 ADT 的向下增长的数组实现。我们的实现应该基于 文件 stackdwn.h 中的声明(拥有和文件 stackarr.h 同样的声明) 。在文件 Show5.cpp 中给出了 showStructure

32、运算的一个实现。第二步： 把堆栈 ADT 的“向下 ”的数组实现保存在文件 stackdwn.cpp 中。第三步：修改测试程序 test2.cpp ，使文件 stackdwn.cpp 中的堆栈 ADT 的“向 下”的数组实现代替堆栈 ADT 的“向上 ”的数组实现。第四步：使用在实验中练习 1 中创建的测试计划检查堆栈 ADT 的“向下 ”数组 实现。如果在实现中发现错误，修改这些错误并且重新执行测试计划。实验 2 实验中练习 3日期姓名小组编译器和解释器的一个任务是频繁地执行判断一些成对的表达式分界符是 否正确配对，即使是多重嵌套配对也能正确判断。考虑下面的C+ 表达式。a = ( fb-(

33、c+d) ) / 2; 编译器必须能够判断成对的开和闭的圆括号、方括号等，继而判断整个表达 式是否正确地分界。 由于不配对的分界符， 或分界符使用的位置不对都会出现一 系列可能的错误。例如，下面的表达式缺少一个闭的圆括号。a = ( fb-(c+d) / 2; 下面的表达式也是无效的，虽然圆括号和方括号的数目是正确的，但是匹配 不正确。第一个闭圆括号不能与最近的开分界符(方括号)相匹配。a=( fb)-(c+d) / 2;由于堆栈具有LIFO(后进先出)的特性，所以堆栈对实现解决这种类型的问题 特别有帮助。一个闭的分界符必须正确地匹配最近遇到的开分界符。处理方法是把遇到的开分界符压入一个堆栈中，但遇到一个闭分界符时，从对堆栈中弹出的应该是一个匹配的开分界符。如果每一个闭分界符都有一个匹配的开分界符，那 么整个表达式是有