《栈队列和递归A》PPT课件.ppt

,第三章 栈、队列和递归,(之一),3.1栈（Stack）,3.2 队列 （Queue）,. 逻辑结构 . 存储结构与实现 . 应用实例,. 逻辑结构 . 存储结构与实现 . 应用实例,.1 栈,1、栈的逻辑结构,空栈：不含任何数据元素的栈。,（a1, a2, , an）,栈：限定仅在一端进行插入和删除操作的线性表。,允许插入和删除的一端称为栈顶，另一端称为栈底。 数据元素之间的逻辑关系：一对一 。,注： 栈的运算规则 只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。 入栈：插入元素到栈顶（即表尾）的操作。 出栈：从栈顶（即表尾）删除最后一个元素的操作。 问：栈与一般线性表有什么不同？ 一般线性表 （堆）栈 逻辑结构：一对一 逻辑结构：一对一 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 运算规则：后进先出 (LIFO) 入栈操作演示 出栈操作演示,a1,a2,a3,入栈,插入：入栈、进栈、压栈,入栈的操作示图：,a1,a2,a3,删除：出栈、弹栈,出栈的操作示图：,栈的操作特性：后进先出,出栈,思考题：一个栈的输入序列为123，若在入栈的过程中允许出栈，且每个元素只允许进一次栈，则可能得到的出栈序列有哪些？,答：,可以通过穷举所有可能性来求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入3、2出， 即132； 1、2入，2出， 3入3出， 即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321； 合计有5种可能性。,思考题：,设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，b,A、D可以（ B、C不行）。,讨论：有无通用的判别原则？ 有。若输入序列i，j，k，则不存在输出序例k、i、j;,答：,栈的抽象数据类型定义参见P86-87 2、栈的存储结构 顺序栈、链式栈 （）顺序栈栈的顺序存储结构(重点),如何改造数组实现栈的顺序存储？,a1,确定用数组的哪一端表示栈底。,附设指针top指示栈顶元素在数组中的位置。,S,进栈核心语句：top+; Stop=a1;,栈空：top= = -1,a1,a2,进栈的操作步骤如何？,a1,a2,栈满：top= = MAX_SIZE-1,栈满的如何判断？,a3,a4,a5,a6,a7,a8,a9,动态栈类的定义： template /定义模板类DSeqStack class DSeqStack public: DSeqStack( int size) ; /构造函数，栈的初始化 DSeqStack( )delete S; /析构函数 void Push(const type ,顺序栈的构造函数算法实现,template DSeqStack:DSeqStack(int size ) :top(-1),MaxSize(size) /建立一个最大尺寸为size的空栈 S=new typeMaxSize;/创建存储栈的数组 if(S=NULL) /分配不成功 cerr“动态存储失败！“endl; exit(1); /stdlib.h ,操作接口： template DSeqStack:DSeqStack(int size ); 算法实现：,顺序栈的入栈操作算法实现,template void DSeqStack:Push(const type ,操作接口： template void DSeqStack:Push(const type &item) 算法实现：,时间复杂度？,O(1),出栈核心语句： Item=Stop; top-;,边界条件 栈空：top= = -1;,a1,a2,出栈的操作步骤如何？,顺序栈的出栈操作算法实现,template type DSeqStack:Pop( ) type item; if (top=-1) throw “栈空！“; item=Stop-;/等价于item=Stop;top-; return item; ,操作接口： template type DSeqStack:Pop( ); 算法实现：,时间复杂度？,O(1),其它类型栈举例：如两栈共享空间,解决方案2：,使用一个数组来存储两个栈。使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。,在一个程序中需要同时使用具有相同数据类型的两个栈，如何顺序存储这两个栈？,会出现什么问题？如何解决？,栈1的栈底:固定靠下标为0的这一端； 栈2的栈底:固定靠下标为MaxSize-1的这一端。 top1和top2分别为栈1和栈2的栈顶指针； MaxSize:整个数组空间的大小（图中用S表示）；,a1 a2 ai,0 1 2 S-1,bj b2 b1,两栈共享空间栈顶与栈底如何设置？,栈1为空条件：top1= -1 栈2为空条件：top2= MaxSize,什么时候两栈为空？,0 1 2 S-1,a1 a2 ai,0 1 2 S-1,bj b2 b1,栈满条件为：top2= top1+1,什么时候栈为满？,（）链式栈栈的链式存储结构,如何改造链表实现栈的链接存储？链栈需要加头结点吗？将哪一端作为栈顶？,注：链栈不需要附设头结点。,链栈类的定义： template class LinkStack;/声明 template class Node friend class LinkStack; private: type data; Node *next; /此处也可以省略 ; template class LinkStack public: LinkStack( ); /构造函数，置空链栈 LinkStack( ); /析构函数，释放链栈中各结点的存储空间 void Push(type item); /将元素item入栈 type Pop( ); /将栈顶元素出栈 type GetTop( ); /取栈顶元素（并不删除） bool Empty( ); /判断链栈是否为空栈 private: Node *top; /栈顶指针即链栈的头指针 ;,链栈的构造函数算法实现,template LinkStack:LinkStack( ) top=NULL; /初始化空栈 ,操作接口： template LinkStack:LinkStack( ); 算法实现：,算法实现： template void inkStack:Push(type x) Node *s; s=new Node; s-data = x; s-next = top; top=s; ,an,an-1,a1,链栈的入栈算法实现,操作接口： template void LinkStack:Push(type x)；,为 什 么 没 有 判 断 栈 满 ？,算法实现： template type LinkStack:Pop( ) Node *p; type x; if (top=NULL) throw “栈空“; x=top-data; p=top; top=top-next; delete p; return x; ,链栈的出栈算法实现：,操作接口： template T LinkStack:Pop( );,an,an-1,a1,top+可以吗？,顺序栈和链栈的比较,时间性能：相同，都是常数时间O(1)。,空间性能： 顺序栈：有元素个数的限制和空间浪费的问题。 链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。,总之，采用顺序栈存储方式，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。,调用函数或子程序非它莫属； 递归运算的有力工具； 用于保护现场和恢复现场； 简化了程序设计的问题； 其它应用：如括号匹配问题、表达式计算问题等。,答：,3、栈的应用举例,为什么要设计栈？它有什么独特用途？,数制转换（十转八进制） 设计思路：用栈暂存低位值 算法分析： N N div 8 N mod 8 74 9 2 9 1 1 1 0 1,栈的应用实例：,如：(74)10=(112)8,void conversion( ) /对于输入的任意一个非负十进制整数， /打印输出与其等值的八进制数； SeqStack s1(10); int N,n; int e; coutN; n=N; while (n) s1.Push(n%); n=n/; while (!s1.Empty() e=s1.Pop(); coute; coutendl; ,栈的应用实例： 括号匹配的检验 设计思路：用栈暂存左括号 如：（） 栈的应用实例：表达式求值 设计思路：用栈暂存运算符和操作数,例如:(A+B)*C+D/E （1）要正确求值，首先了解算术四则运算的规则： a.括号内优先级最高 b.优先级相同，从左算到右 由此，此表达式的计算顺序为： T1=A+B T2=T1*C T3=D/E T4=T2+T3 小结:正确计算需知道算符的优先级。 且需要使用括号来反映优先级。（参见P92）,如表达式求值 (典型实例 ) 1）常用的表达式是中缀表达式：操作符在操作数之间。,例如:AB+C*D E/ + 后缀表达式的计算过程： 操作步骤 后缀表达式 AB+C*D E/ + T1=A+B T1C*DE/+ T2=T1*C T2DE/+ T3=D/E T2T3+ T4=T2+T3 T4 小结: 后缀表示法两大优点 （1）不需要使用括号 （2）不用考虑操作符的优先级,2）另一种表达式表示是后缀表达式：每个操作符出现在操作数之后。,后缀表达式的计算过程描述： （1）从左向右扫描，遇操作数则进栈； （）若遇操作符，则按其性质（一元或二元）从栈中弹出相应个数的操作数运算完后，运算结果进栈。 （）直至整个表达式扫描完毕。,表后缀表达式计算的步骤： AB+C*DE/+,算法描述： template void eval(postexp e) /postexp后缀表达式 SeqStack stack;/栈对象初始化； for(int j=0; e.getterm(j)!=#;j+) /取表达式的每一项 char x=e.getterm(j); if (x!=+/入栈 ,else /根据操作符x的性质，从栈中取出正确数目的操作数； T a1,a2,temp; a2=stack.Pop(); a1=stack.Pop();/注按LIFO原则 switch(x) case +:temp=a1+a2;break; case -:temp=a1-a2;break; case /:temp=a1/a2;break; case *:temp=a1*a2;break; case %:temp=a1%a2;break; stack.Push(temp); T v=stack.Pop();/最后结果出栈 cout“表达式的值为：“vendl; ,（1）中缀表达式转换成后缀表达式方法一： A、给中缀表达式中的每一步操作加上括号； B、每个操作符移到对应该操作的右边括号外； C、删掉所有括号。 例如：（A+B）*C+D/E 加上括号：（A+B）*C）+（D/E） 把操作符移到相应括号外： （AB）+C） * （DE）/） + 去掉所有的括号：AB+C*DE/+,3）中缀转换为后缀表达式 特点:操作数的顺序相同。,（2）中缀表达式转换成后缀表达式方法二 算法步骤描述： A、操作符栈初始化，将结束符“#”进栈，读入中缀表达式的首字符放入x2;/x2存放读入的数据信息。 B、重复执行以下步骤，直到x2=“#”，且栈顶的操作符x1也是“#”时，停止循环/x1存放栈顶元素 若x2是操作数时直接输出，并接着读表达式的下一项放入x2; 若x2是操作符 若x1的优先级x2的优先级，将x1退栈并输出，然后接着比较新的栈顶运算符x1的优先级与x2的优先级； 若x1的优先级=x2的优先级，且x1为“（”, x2为“）”，将x1退栈，然后读表达式下一项放入x2。,表2中缀表达式转换成后缀表达式的步骤： （A+B）*C+D/E (优先级表参照p92),算法描述： template void postfix(expression e) SeqStack stack;/初始化操作符栈 stack.Push(#);/#先入栈 char x1=stack.GetTop();/读取栈顶元素 int j=0; char x2=e.getterm(j);/读取表达式的项 cout“后缀表达式为：“endl; while (!stack.Empty() if (x2!=#/读取表达式的下一项 ,else if(preority_comp(x1,x2)=) /x1的优先级x2的优先级 x1=stack.Pop();/退栈 coutx1ends; x1=stack.GetTop();/取栈顶元素 else if(preority_comp(x1,x2)=) /x1的优先级=x2的优先级 stack.Pop();/去掉栈顶的左括号或#号 if(!stack.Empty() x1=stack.GetTop(); if(x2!=#) j+; x2=e.getterm(j);/读取表达式的下一项 coutendl; ,技巧提示:巧用枚举 int QW(char c) enum ysf ad,sb