数据结构与算法 （C+语言版）,第3章 栈与队列,栈,栈的定义 栈（stack）是限制在表的一端进行插入和删除的线性表，又称为后进先出（last in first out）的线性表（简称LIFO结构）。进行插入和删除的一端是浮动端，称为栈顶（top），并用一个“栈顶指针”指示；另一端是固定端，称为栈底（bottom）。如图所示，栈S=(k1, k2, , kn)，其中k1为栈底元素，kn 为栈顶元素。栈中元素按k1, k2, , kn的次序进栈，退栈的第一个元素 为栈顶元素。,例3.1 设有4个元素a、b、c、d进栈,给出它们所有可能的出栈次序。 答:所有可能的出栈次序如下: abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba,例3.2 设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是 。 (A) A,B,C,D (B) D,C,B,A (C) A,C,D,B (D) D,A,B,C,答:可以简单地推算,得容易得出D,A,B,C是不可能的,因为D先出来,说明A,B,C,D均在栈中,按照入栈顺序,在栈中顺序应为D,C,B,A,出栈的顺序只能是D,C,B,A。所以本题答案为D。,例3.3 已知一个栈的进栈序列是1,2,3,n,其输出序列是p1,p2,pn,若p1=n,则pi的值 。 (A) i (B) n-i (C) n-i+1 (D) 不确定 答:当p1=n时,输出序列必是n,n-1,3,2,1,则有: p2=n-1, p3=n-2, , pn=1 推断出pi=n-i+1,所以本题答案为C。,例3.4 设n个元素进栈序列是1,2,3,n,其输出序列是p1,p2,pn,若p1=3,则p2的值 。 (A) 一定是2 (B) 一定是1 (C) 不可能是1 (D) 以上都不对 答:当p1=3时,说明1,2,3先进栈,立即出栈3,然后可能出栈,即为2,也可能4或后面的元素进栈,再出栈。因此,p2可能是2,也可能是4,n,但一定不能是1。所以本题答案为C。,栈,在栈顶插入元素的操作通常称为入栈，删除栈顶元素的操作称为出栈。除此之外，栈的基本操作还包括栈的初始化、判空及取栈顶元素等。栈的抽象数据类型定义见以下ADT 。,栈,栈,栈的抽象类 程序给出了栈的抽象类定义，从面向对象的观点定义了栈的属性、方法，后面将介绍栈的顺序存储和链式存储所对应的类均是该抽象类的派生类。,栈,栈,栈的顺序存储结构 栈的顺序存储结构称为顺序栈，它利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素，并用一个变量记录栈顶元素的位置。通常采用数组来存放，习惯上将栈底放在数组下标小的那端。以下程序给出了顺序栈的类描述。由于栈在使用过程中所需的最大空间很难估计。因此，一般来说，在初始化设空栈时不应限定栈的最大容量。,栈,栈,栈,栈,栈的初始化操作为：按设定的初始分配量进行第一次存储分配，top为栈顶指针，其初值指向栈底，值为1，即top=1可作为栈空的标记。每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1。因此，非空栈中的栈顶指针始终在栈顶第一个元素的位置上。下图展示了顺序栈中数据元素进栈和出栈时与栈指针之间的对应关系。,栈,栈,栈的链式存储结构 栈的链式表示，即链栈，如图所示。由 于栈的操作是线性表操作的特例，因此 链栈可看成运算受限的单链表。其操作 易于实现，因此不作详细讨论。其特点 如下： 链栈无栈满问题，空间可扩 充； 插入与删除仅在栈顶处执行； 链式栈的栈顶在链头； 适合于多 栈操作。以下程序给出了链栈的类描述。,栈,栈,栈的应用举例 例3-1,表达式求值。表达式求值是程序设计语言编译过程中的一个最基本问题。下面介绍一种简单直观、广为使用的“算符优先法”。 任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的式子。操作数既可以是常数也可以是变量或常量。运算符从运算类型上可分为算术运算符、关系运算符和逻辑运算符三类。基本界限符包括左、右括号和表达式结束符等。运算符和界限符常被统称为算符。在运算规则中，表达式的算符之间有一定优先关系（见下表），同时结合算术四则运算规则： 先乘除，后加减； 从左算到右； 先括号内，后括号外，则一个表达式的执行过程就能够被计算机正确地翻译并执行了。例如，对于算术表达式8+12/32*4进行求值时，该表达式的计算顺序应为8+12/32*4=8+42*4=12 2*4=128=4。,例3-1,例3-1,在算法的实现过程中用到两个工作栈来分别存储算符和操作数或运算结果，其基本思想是：初始化操作数栈和算符栈，表达式起始符“#”为算符栈的栈底元素；自左向右扫描表达式，若是操作数则进操作数栈，若是算符则和算符栈的栈顶运算符比较优先权后进行相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。以下程序给出了算法的实现过程。,例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千克的背包携运物品，希望知道能否从这些物品中选出几件，使其总重量恰为目标值t。 下面的程序给出了上述背包问题的一种递归解法。其中，函数knapsack的操作对象是由权值构成的数组weightsn；knapsack(t, i)将回答是否能从权值weightsiweightsn之间选出一些数，使其总和为t，并在可能的情况下打印输出所选定的这些权值。,例3-2,下面的程序给出了上述背包问题的一种递归解法。其中，函数knapsack的操作对象是由权值构成的数组weightsn；knapsack(t, i)将回答是否能从权值weightsiweightsn之间选出一些数，使其总和为t，并在可能的情况下打印输出所选定的这些权值。 当不是上述3种情况时，调用knapsack(twi, i+1)可验证是否存在包含wi的解。如果调用的结果为true，则说明问题有解，且wi是解中选定的一个权值。因此，应将wi 打印输出；如果调用的结果为false，则说明不存在包含wi的解，那么解只可能选自wi+1wn之间，因此调用knapsack(t, i+1)即可。,例3-2,例3-3,地图四染色问题。“四染色”定理是计算机科学中著名定理之一，定理告诉我们，可用不多于4种颜色对地图进行染色（着色），使相邻的行政区域不重色。现在要用这个定理的结论，利用回溯算法对一张给定的地图染色。如图所示，对每个行政区进行编号，1色、2色、3色、4色表示各个行政区域的颜色，称为色数。 从编号为01的区域开始逐一进行染色。对每个区域用色数1、2、3、4依次进行试探，并尽可能取小色数。若当前所取色数与周围已染色的区域不重色，则进栈记下该区域的色数；否则，依次用下一色数进行试探。若从1色到4色均与相邻某区域发生重色，则需退栈回溯，修改栈顶区域的色数。,例3-3,例3-3,栈 与 递 归,递归 若在一个函数、过程或者数据结构定义的内部，直接（或间接）出现定义本身的应用，则称它们是递归的，或者是递归定义的。递归函数是指一个直接调用自己或通过一系列的调用语句间接调用自己的函数。递归是一种强有力的数学工具，它可使问题的描述和求解变得简捷和清晰。递归算法常常比非递归算法更容易设计，尤其是当问题本身或所涉及的数据结构是递归定义时，使用递归算法特别合适。,栈 与 递 归,递归算法的设计步骤 将规模较大的原问题分解为一个或多个规模更小、但具有类似于原问题特性的子问题，即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题。 确定一个或多个无须分解、可直接求解的最小子问题（称为递归的终止条件）。例如，非负整数n的阶乘可递归定义为：,栈 与 递 归,栈在递归算法的内部实现中所起的作用 调用函数时，系统将为调用者构造一个由参数表和返回地址组成的活动记录，并将其压入到由系统提供的运行时刻栈的栈顶，然后将程序的控制权转移到被调函数。若被调函数有局部变量，则在运行时刻，在栈的栈顶也要为其分配相应的空间。因此，活动记录和这些局部变量形成了一个可供被调函数使用的活动结构。 被调函数执行完毕时，系统将运行时刻栈的栈顶的活动结构退栈，并根据退栈的活动结构中所保存的返回地址将程序的控制权转移给调用者继续执行。,队 列,队列的定义 队列（Queue）是只允许在一端进行插入、在另一端进行删除的运算受限的线性表。被允许删除的一端称为队头（front），被允许插入的一端称为队尾（rear）。队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。当队列中没有元素时，称为空队列。如图所示，队列中的元素a1, a2, , an必须按照从队头删除或从队尾加入的次序离开或进入队列。下面的程序分别给出了队列的ADT定义及其类描述。,队 列,队 列,队 列,队 列,队列的顺序存储结构 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。与顺序栈类似，在队列的顺序存储结构中，用一组地址连续的存储单元依次存放从队列头到队列尾的元素。指针front和rear被分别用来指示队列头元素和尾元素的位置。由于这两个指针可有多种指示队列状态的方法，为了便于描述，在本书中统一约定为：初始化建空队列时，front=rear=0；有新元素插入队尾时，rear=rear+1；从队列中删除头元素时，front=front+1；当队列非空时，头指针始终指向头元素，而尾指针始终指向队尾元素的下一个位置，如图所示。,队 列,这种表示方法会遇到一个问题，假设队列的最大空间为6，则在如（d）所示的情况下，不能再向队列插入新的队尾元素，否则会导致数组越界，而此时队列的实际可用空间并未占满。对于这个问题，一个较好的解决办法是将顺序队列转换为一个循环空间，称为循环队列。,队 列,如下图所示。上图所示的队列转换为循环队列后如下一页图所示，指针和队列元素之间关系不变。,队 列,队 列,从上图中的（b）和（c）可看出，用循环队列时会出现一个问题，即队满和队空时都有Q.front=Q.rear，因此无法判断队列是“空”还是“满”。解决的办法之一就是：规定队列的最大长度始终小于存储空间大小，即留一个存储空间来区分队列空还是满。循环队列的类描述以及函数实现分别见以下程序。 循环队列的类描述：,队 列,队 列,SeqQueue的成员函数：,队 列,队 列,例3-4,在操作系统中，为了充分发挥计算机的效率，必须处理好中央处理机和外围设备在速度上不匹配的问题。信息的输入/输出都在内存中进行，需要设置输入/输出缓冲区，采用成组传送的办法，这样可实现主机与外部设备，以及外部设备与外部设备间的并行操作。在缓冲区内所有的信息都要排队，按照“先来先服务”的原则处理。因此，缓冲区实际上是一个队列的结构。下面模拟上述缓冲区的操作，当一个设备向缓冲区发送信息时，先要检查缓冲区中有无空间，有，则送入缓冲区；无，则等待。当另一个设备接收缓冲区发出的信息时，先要检查缓冲区中有无信息，有，则接收；无，则显示适当信息。 该程序应完成下述操作：,例3-4, 建立一个长度适当的队列作为缓冲器，用此缓冲器存放一组信息。 该程序对如下