第三章栈队列和递归A.ppt

3.1栈（Stack） 思考题１：一个栈的输入序列为123，若在入栈的过程中允许出栈，且每个元素只允许进一次栈，则可能得到的出栈序列有哪些？ 思考题２： 设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是： Ａ）a，b，c，d Ｂ）c，d，a，b Ｃ）b，c，d，a Ｄ）a，c，d，b template class type DSeqStacktype::DSeqStack(int size ) :top(-1),MaxSize(size) {//建立一个最大尺寸为size的空栈 S=new type[MaxSize];//创建存储栈的数组 if(S==NULL) //分配不成功 { cerr动态存储失败！endl; exit(1); //stdlib.h } } template class type void DSeqStacktype::Push(const type item) { if (top==MaxSize-1) throw 栈满！; top++; //栈未满，则入栈 S[top]=item; } template class type type DSeqStacktype::Pop( ) { type item; if (top==-1) throw 栈空！; item=S[top--];//等价于item=S[top];top--; return item; } template class type LinkStacktype::LinkStack( ) { top=NULL; //初始化空栈 } 调用函数或子程序非它莫属； 递归运算的有力工具； 用于保护现场和恢复现场； 简化了程序设计的问题； 其它应用：如括号匹配问题、表达式计算问题等。 例如:(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）另一种表达式表示是后缀表达式：每个操作符出现在操作数之后。 * 特殊线性表 栈 队 列 串 ⑴栈的定义 ⑵操作特性 ⑶ADT定义 ⑴队列定义 ⑵操作特性 ⑶ADT定义 ⑴串的定义 ⑵基本概念 ⑶ADT定义 顺序栈 链 栈 循环队列 链队列 顺序存储 链接存储 逻辑结构 存储结构 逻辑 结构 逻辑 结构 存储 结构 存储 结构 比 较 模式匹配 比较 比较 ⑴基本操作的实现 ⑵时间复杂度 ⑴基本操作的实现 ⑵时间复杂度 3.2 队列 （Queue） １. 逻辑结构 ２. 存储结构与实现 ３. 应用实例 １. 逻辑结构 ２. 存储结构与实现 ３. 应用实例 ３.1 栈 1、栈的逻辑结构 空栈：不含任何数据元素的栈。 （a1, a2, ……, an） 栈：限定仅在一端进行插入和删除操作的线性表。 栈顶 栈底 允许插入和删除的一端称为栈顶，另一端称为栈底。 数据元素之间的逻辑关系：一对一 。 注： 栈的运算规则 　　只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。 入栈：插入元素到栈顶（即表尾）的操作。 出栈：从栈顶（即表尾）删除最后一个