数据结构与算法C++语言版第3章 栈与 队列.ppt

《数据结构与算法C++语言版第3章 栈与 队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构与算法（C++语言版）第3章栈与队列栈栈的定义栈（stack）是限制在表的一端进行插入和删除的线性表，又称为后进先出（lastinfirstout）的线性表（简称LIFO结构）。进行插入和删除的一端是浮动端，称为栈顶（top），并用一个“栈顶指针”指示；另一端是固定端，称为栈底（bottom）。如图所示，栈S=(k1,k2,…,kn)，其中k1为栈底元素，kn为栈顶元素。栈中元素按k1,k2,…,kn的次序进栈，退栈的第一个元素为栈顶元素。栈在栈顶插入元素的操作通常称为入栈，删除栈顶元素的操作称为出栈。除此之外，栈的基本操作还包括栈的初始化、判空及取栈顶元素等。栈的抽象数据

2、类型定义见以下ADT。栈栈栈的抽象类程序给出了栈的抽象类定义，从面向对象的观点定义了栈的属性、方法，后面将介绍栈的顺序存储和链式存储所对应的类均是该抽象类的派生类。从基本操作上看，栈是线性表的子集，故应当是线性表的父类。这样，线性表类也可共享栈的方法。栈栈栈的顺序存储结构栈的顺序存储结构称为顺序栈，它利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素，并用一个变量记录栈顶元素的位置。通常采用数组来存放，习惯上将栈底放在数组下标小的那端。以下程序给出了顺序栈的类描述。由于栈在使用过程中所需的最大空间很难估计。因此，一般来说，在初始化设空栈时不应限定栈的最大容量。栈栈栈栈类的数据

3、成员stacksize指示栈的当前可使用的最大容量。栈的初始化操作为：按设定的初始分配量进行第一次存储分配，top为栈顶指针，其初值指向栈底，值为1，即top=1可作为栈空的标记。每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1。因此，非空栈中的栈顶指针始终在栈顶第一个元素的位置上。下图展示了顺序栈中数据元素进栈和出栈时与栈指针之间的对应关系。栈栈栈的链式存储结构栈的链式表示，即链栈，如图所示。由于栈的操作是线性表操作的特例，因此链栈可看成运算受限的单链表。其操作易于实现，因此不作详细讨论。其特点如下：①链栈无栈满问题，空间可扩充；②插入与删除仅在栈顶处执

4、行；③链式栈的栈顶在链头；④适合于多栈操作。以下程序给出了链栈的类描述。栈栈栈的应用举例例3-1表达式求值。表达式求值是程序设计语言编译过程中的一个最基本问题。下面介绍一种简单直观、广为使用的“算符优先法”。任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的式子。操作数既可以是常数也可以是变量或常量。运算符从运算类型上可分为算术运算符、关系运算符和逻辑运算符三类。基本界限符包括左、右括号和表达式结束符等。运算符和界限符常被统称为算符。在运算规则中，表达式的算符之间有一定优先关系（见下表），同时结合算术四则运算规则：①先乘除，

5、后加减；②从左算到右；③先括号内，后括号外，则一个表达式的执行过程就能够被计算机正确地翻译并执行了。例如，对于算术表达式8+12/32*4进行求值时，该表达式的计算顺序应为8+12/32*4=8+42*4=122*4=128=4。例3-1例3-1在算法的实现过程中用到两个工作栈来分别存储算符和操作数或运算结果，其基本思想是：初始化操作数栈和算符栈，表达式起始符“#”为算符栈的栈底元素；自左向右扫描表达式，若是操作数则进操作数栈，若是算符则和算符栈的栈顶运算符比较优先权后进行相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。以下程序给出

6、了算法的实现过程。例3-1例3-1算法中，Precede函数用来判定运算符栈的栈顶运算符与读入的运算符之间的优先关系，Operate函数进行二元运算。利用上述算法对表达式9/(1+2)求值的操作过程如下：例3-2背包问题。给定一组正整数权值w1,w2,w3,…,wn，以及一个目标值t（整数）。试问：能否从这组权中选出若干个数，使它们的和等于t。这就是所谓的“背包问题”。例如，当目标值t=10，权值为7,5,4,4,1时，可选中第2,3,5这3个数作为解，这3个数之和为10。如果设想权值分别是物品的重量，假设要用一个载重限度为t千克的背包携运物品，希望知道能否从这些物品中选出几件，使

7、其总重量恰为目标值t。下面的程序给出了上述背包问题的一种递归解法。其中，函数knapsack的操作对象是由权值构成的数组weights[n]；knapsack(t,i)将回答是否能从权值weights[i]～weights[n]之间选出一些数，使其总和为t，并在可能的情况下打印输出所选定的这些权值。例3-2下面的程序给出了上述背包问题的一种递归解法。其中，函数knapsack的操作对象是由权值构成的数组weights[n]；knapsack(t,i)将回答是否能从权值