2019数据结构C++第3章第8讲.pptx

练习 一个队列输入的序列是1,2,3，则可能的且以1为开头的输出序列有 ？个。如果是1234，则不可能的序列为？下面表达式变后缀表达式过程中14-5*（3+4)/7+9扫描过程在遇到/时，栈里面的数据是什么？其前缀表达式是什么？数据结构电子教案第三章 栈与队列本章重点：1.栈的使用2.出栈的顺序3.递归例2、括号匹配的检查假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意如（［ ］（））或［（［ ］［ ］）］等为正确的匹配，［（ ]）或（［ ］（ ）或 ( ( ) ) ）均为错误的匹配。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。即后出现的“左括弧”，它等待与其匹配的“右括弧”出现的“急迫”心情要比先出现的左括弧高。 如考虑下列括号序列：　[ ( [ ] { } ) ]　1 2 3 4 5 6 7 8 分析可能出现的不匹配的情况[()[ 1．到来的右括弧非是所“期待”的；2．到来的是“不速之客”；3．直到结束，也没有到来所期待的。 )　这三种情况对应到栈的操作即为　1．和栈顶的左括弧不相匹配；　2．栈中并没有左括弧等在哪里；　3．栈中还有左括弧没有等到和它相匹配的右括弧。 算法的设计思想1)凡出现左括弧，则进栈；2)凡出现右括弧，首先检查栈是否空 若栈空，则表明“右括弧”多了 否则和栈顶元素比较， 若匹配，则“左括弧出栈” 否则不匹配3）表达式检验结束时，若栈空，则匹配正确否则说明左括弧多了Status matching(string exp){Int state =1;While (i=Length(exp) state){Switch of exp[i]{Case ”(”：{Push(S,exp[i],i++); break;}Case ”) ”:{ if (NOT StackEmpty(S)GetTop(S)==“(”）{Pop(S,e);i++;} else {state=0;} Break;}……}If (StackEmpty(S)state) return OK；栈的应用：递归递归的定义 若一个对象部分地包含它自己，或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。以下三种情况常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的定义是递归的例如，阶乘函数求解阶乘函数的递归算法long Factorial(long n) { if (n == 0) return 1; else return n*Factorial(n-1);}求解阶乘 n! 的过程主程序 main : fact(4)参数 4计算 4*fact(3) 返回 24递归调用参数传递回归求值结果返回参数 3计算 3*fact(2) 返回 6参数 2计算 2*fact(1) 返回 2参数 1计算 1*fact(0) 返回 1参数 0直接定值 = 1 返回 1?f ?f 数据结构是递归的例如，单链表结构一个结点，它的指针域为NULL，是一个单链表;一个结点，它的指针域指向单链表，仍是一个单链表。递归找链尾a0a1a2a3a4f ?f f f f 搜索链表最后一个结点并打印其数值template class E void Print(ListNodeE *f) { if (f -link == NULL) cout f -data endl; else Print(f -link);}递归找含x值的结点xf ?f f f 在链表中寻找等于给定值的结点并打印其数值template class Evoid Print(ListNodeE *f, E value) { if (f != NULL) if (f - data == value) cout f - data endl; else Print(f - link, value);}2 递归函数： 一个直接调用自己或通过一系列调用间接调用自己的函数称为递归函数。 A（ ）{ … A( ) ; …}B( ) { C( ) { … … C( ); B( ); … … } }A 直接调用自己B间接调用自己调用调用返回返回函数调用顺序 A B C函数返回顺序 C B A一般函数的调用机制3 递归函数的实现A( ){…B( );…}C( ){……}B( ){…C( );…}后调用的函数先返回　一个递归函数的运行过