[课件资料]栈

3栈与递归,第四章栈和队列从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。通过本章的学习，应掌握栈和队列的逻辑结构和存储结构，以及栈和队列的基本运算以及实现算法。,4队列,2算术表达式的计算,1栈,编程任务简单编译器（括号配对检查）,问题描述：在程序调试时都有对源代码编译的过程，而判断左右括号是否匹配也是其中的一个重要环节。设计程序对任意输入的表达式进行检查，判断左右括号是否配对。基本要求：利用栈来实现算法。以圆括号为例来判断输入的表达式中左右括号是否匹配。,编程任务排队看病系统,要求实现的功能：病人到达，交病历卡，取号入队叫到号时，取出病历，患者就诊不接受新病人，已排队病人依次就诊以上三种情况用输入命令来模拟：命令“A”：病人到达命令“N”：护士让下一位病人就诊命令“Q”：剩余病人依次就诊，然后结束,4.1栈,栈的例子：洗盘子：一叠盘子相当于是一个栈。放盘子和取盘子都只能从顶上开始进行，将盘子放到顶端，即为进栈；从顶端取出盘子，即为出栈。学生交本子：一叠本子也相当于一个栈，后交者先批，即后进栈者先出栈。装子弹：子弹压入即为进栈；子弹射出即为出栈。栈在计算机系统中也非常有用：常用栈来保存一些尚未处理和等待处理的数据项，对数据项的处理遵循“后进先出”的原则。汉诺塔游戏,4.1.1栈的定义及其运算,1栈的定义栈（stack）是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。栈的插入操作通常称为入栈或进栈(push)，而栈的删除操作则称为出栈或退栈(pop)。当栈中无数据元素时，称为空栈。根据栈的定义可知，这种表是按照后进先出（LIFO，lastinfirstout）的原则组织数据的，因此，栈也被称为“后进先出”的线性表。,a0,a1,an-1,入栈,出栈,栈顶top,栈的示意图,下图是一个栈的示意图，通常用指针top指示栈顶的位置，栈顶指针top动态反映栈顶的当前位置。,4.1.1栈的定义及其运算,2栈的基本运算（1）InitStack(s)初始化：初始化一个新的栈s，即置为空。（2）ClearStack(s)清空栈：清除栈中所有元素，并置栈s为空栈。（3）EmptyStack(s)栈的空判断：若栈s为空，则返回true；否则，返回false。（4）Peek(s)读取栈顶元素：若栈s不空，则返回栈顶元素。但不删除栈顶元素，故栈顶指针不移动。（5）Push(s,x)进栈：在栈s的顶部插入元素x。（6）Pop(s)出栈：若栈s不空，则返回栈顶元素，并从栈顶中删除该元素。栈是一种特殊的线性表，因此栈可采用顺序存储结构存储，也可以使用链式存储结构存储。,4.2栈的顺序存储结构和操作实现,1顺序栈的数组表示与第二章讨论的顺序表一样，利用一块连续内存空间依次存放自栈底到栈顶的数据元素，这种形式的栈称为顺序栈。因此，我们可以用一维数组来作为栈的顺序存储空间。设指针top指向栈顶元素的当前位置。对数组而言，这个top指针就是一个整型变量，即栈顶元素所对应的数组下标。以数组小下标的一端作为栈底。由于C语言中数组下标从0开始，因此用一维数组作为栈时，应设栈顶指针top=-1时为空栈。在元素进栈时指针top不断地加1，当top等于数组的最大下标值时则栈满。,top=-1,top=0,A,top=4,A,B,E,top=2,栈的存储结构（a）空栈；（b）插入元素A后；（c）插入元素B、C、D、E后；（d）删除元素E、D后,（a）,（b）,（c）,（d）,下图展示了顺序栈中数据元素与栈顶指针的变化。,C,D,A,B,C,用C或C+定义的顺序栈如下：structStackElemTypestackMaxSize;inttop;,包括两个成员：数组：用于存储栈中元素。数组的大小决定了栈的最大深度。2.栈顶指针top：是一个整型变量，用于指示栈顶的位置。top=-1时顺序栈空；top=MaxSize-1时顺序栈满。进栈操作时，top加1，出栈操作时top减1。,2.顺序栈的操作实现（1）初始化栈函数名：InitStack形参：顺序栈S返回值：无功能：置栈为空，即令top1（2）清空栈函数名：ClearStack形参：顺序栈S返回值：无功能：对静态顺序栈而言，此算法与初始化栈完全相同，即置栈为空。,2.顺序栈的操作实现（3）判别栈空函数名：EmptyStack形参：顺序栈S返回值：若栈空返回true，否则返回false功能：判断栈是否为空，即判断top是否为1（4）读取栈顶元素函数名：Peek形参：顺序栈S返回值：栈顶元素的值功能：若栈非空，则返回栈顶元素的值，即数组stack中，下标为top的元素的值。,2.顺序栈的操作实现（5）元素进栈函数名：Push形参：顺序栈S，待进栈元素item返回值：无功能：若栈未满，先令栈顶指针加1，然后赋item的值到新的栈顶。（6）元素出栈函数名：Pop形参：顺序栈S返回值：栈顶元素功能：若栈未空，先取出栈顶元素，然后令栈顶指针减1。,4.3栈的链式存储结构和操作实现1.链栈的表示栈也可以采用链式存储结构（即单链表)表示，这种结构的栈简称为链栈。在一个链栈中，栈底就是链表的最后一个结点，而栈顶总是链表的第一个结点。因此，栈顶指针即为单链表的表头指针，指针方向从栈顶往下链接，直到链表的最后一个结点（即栈底）。插入元素时，新入栈的元素即为链表新的表头结点，只要系统还有存储空间，就不会有栈满的情况发生。删除元素时，也即删除链表的表头结点。因此，对链栈的插入和删除都是在单链表的表头进行，时间复杂度均为O(1)。,链栈中结点的C语言（或C+）定义与单链表中结点的定义相同，即为：structSNodeElemTypedata;SNode*next;,我们知道，一个单链表可由表头指针HL来表示。同样地，一个链栈也可由栈顶指针HS（相当于前面讲的top）来表示，当HS为NULL时，是一个空栈。下图给出了链栈中数据元素与栈顶指针HS的关系。,2.链栈的操作实现（1）初始化栈函数名：InitStack形参：链栈HS返回值：无功能：置栈为空，即令HSNULL（2）清空栈函数名：ClearStack形参：链栈HS返回值：无功能：从栈顶开始，依次删除各结点，并回收每个结点所占的空间。最后置栈为空。,2.链栈的操作实现（3）判别栈空函数名：EmptyStack形参：链栈HS返回值：若栈空返回true，否则返回false功能：判断栈是否为空，即判断HS是否为NULL（4）读取栈顶元素函数名：Peek形参：链栈HS返回值：栈顶元素的值功能：若栈非空，则返回栈顶元素的值，即表头结点的data值。,2.链栈的操作实现（5）元素进栈函数名：Push形参：链栈HS，待进栈元素item返回值：无功能：把新元素item插入到栈顶，即单链表的表头。分两步：1)为新元素分配内存空间；2)修改表头指针：newptr-next=HS;HS=newptr;,2.链栈的操作实现（6）元素出栈函数名：Pop形参：链栈HS返回值：栈顶元素功能：若栈未空，先暂存原栈顶指针和原栈顶元素，然后删除单链表的表头结点（即栈顶结点）。删除分两步：1)修改表头指针：HS=HS-next;2)回收原栈顶结点所占的空间，用delete语句。,4.5栈应用之一算术表达式的计算,计算机是如何对表达式进行求值的？如(A+B)*D+E/(F+A*D)+C，计算机怎么知道先做哪一步，后做哪一步呢？4.5.1算术表达式的两种表示在计算机中，任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的。其中操作数可以是常数、变量、函数或表达式；运算符可以是算术运算符、关系运算符和逻辑符；界限符为左右括号。在本节中，仅讨论简单算术表达式的求值问题。在这种表达式中只含加、减、乘、除四则运算，所有的运算对象均为常数或简单变量。,中缀表达式：我们所常见的表达式都是双目运算符在两个操作数中间，这种表达式被称为中缀表达式。处理规则（也即算术四则运算的规则）如下：（1）先括号内，后括号外；（2）先乘除、后加减；（3）同级运算时先左后右。计算机并不具备人工智能，因此，处理这类问题只能多次扫描表达式，从中找出优先计算的部分。这种处理方法效率很低。能否将中缀表达式转换一个形式，使计算机处理时只需要根据先左后右的原则即可，则处理表达式时只需从左往右扫描一次就行了。,2.后缀表达式：运算符置于两个运算对象的后面，这种表达式被称为后缀表达式。后缀表达式不需要括号，也不必考虑运算符优先级，只要根据从左往右的原则进行计算。因此计算机仅需扫描表达式一次就可完成计算。变换规则：先变换括号内的部分，再根据优先级由高到低逐级变换各部分。每次变换时，将运算符移到它的两个运算对象后面。这种变换在计算机中利用栈来实现。对后缀表达式的求值在计算机中也利用栈来实现。,4.5.2后缀表达式求值的算法需要使用一个栈，存放数据(操作数,中间结果,最终结果)基本思想：从左到右扫描后缀表达式，若遇到操作数就进栈；若遇到运算符则从栈中退出相应个数的操作数，运算后，结果进栈。程序结构：while(当前字符!=0)if(空格)不管，取下一个字符if(运算符)弹出相应操作数完成计算结果入栈else将操作数从字符串转换为double型后，数据入栈,4.5.3将中缀变为后缀的算法假设有中缀表达式S1，后缀表达式S2，一个运算符栈，怎样把S1转换为S2。基本思想：从左至右扫描S1，当遇到空格：不管运算对象：直接输出到S2左括号：直接进栈右括号：从栈顶直到相应左括号之间的全部运算符依次出栈，并输出到S2运算符：进栈原则是保持栈顶的运算符优先级最高。,若遇到的运算符优先级栈顶运算符优先级，直接进栈若小于或等于，栈顶运算符出栈输出到S2，再与新栈顶运算符比较,最后，依次出栈。,longf(intn)if(n=0)return1;elsereturnn*f(n-1);若求4!，则有voidmain()coutf(4);,4.6栈应用之二栈和递归,函数可以调用自身，这种调用关系就是递归。以求阶乘的递归方法为例：,下图给出了递归调用执行过程。从图中可看到f函数共被调用5次，即f(4)、f(3)、f(2)、f(1)、f(0)。其中，f(4)为主函数调用，其它则为在f函数内的调用。每一次递归调用并未立即得到结果，而是进一步向深处递归调用，直到n=0时，函数f才有结果为1，然后再一