《栈队列和递归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 872 栈的存储结构顺序栈 链式栈 顺序栈 栈的顺序存储结构 重点 如何改造数组实现栈的顺序存储 a1 确定用数组的哪一端表示栈底 附设指针top指示栈顶元素在数组中的位置 S 进栈核心语句 top S top a1 栈空 top 1 a1 a2 进栈的操作步骤如何 a1 a2 栈满 top MAX SIZE 1 栈满的如何判断 a3 a4 a5 a6 a7 a8 a9 动态栈类的定义 template 定义模板类DSeqStackclassDSeqStack public DSeqStack intsize 构造函数 栈的初始化 DSeqStack delete S 析构函数voidPush consttype 顺序栈的构造函数算法实现 templateDSeqStack DSeqStack intsize top 1 MaxSize size 建立一个最大尺寸为size的空栈S newtype MaxSize 创建存储栈的数组if S NULL 分配不成功 cerr 动态存储失败 endl exit 1 stdlib h 操作接口 templateDSeqStack DSeqStack intsize 算法实现 顺序栈的入栈操作算法实现 templatevoidDSeqStack Push consttype 操作接口 templatevoidDSeqStack Push consttype item 算法实现 时间复杂度 O 1 出栈核心语句 Item S top top 边界条件栈空 top 1 a1 a2 出栈的操作步骤如何 顺序栈的出栈操作算法实现 templatetypeDSeqStack Pop typeitem if top 1 throw 栈空 item S top 等价于item S top top returnitem 操作接口 templatetypeDSeqStack Pop 算法实现 时间复杂度 O 1 其它类型栈举例 如两栈共享空间 解决方案2 使用一个数组来存储两个栈 使用一个数组来存储两个栈 让一个栈的栈底为该数组的始端 另一个栈的栈底为该数组的末端 两个栈从各自的端点向中间延伸 在一个程序中需要同时使用具有相同数据类型的两个栈 如何顺序存储这两个栈 会出现什么问题 如何解决 栈1的栈底 固定靠下标为0的这一端 栈2的栈底 固定靠下标为MaxSize 1的这一端 top1和top2分别为栈1和栈2的栈顶指针 MaxSize 整个数组空间的大小 图中用S表示 a1a2 ai 012 S 1 bj b2b1 两栈共享空间栈顶与栈底如何设置 栈1为空条件 top1 1栈2为空条件 top2 MaxSize 什么时候两栈为空 012 S 1 a1a2 ai 012 S 1 bj b2b1 栈满条件为 top2 top1 1 什么时候栈为满 链式栈 栈的链式存储结构 如何改造链表实现栈的链接存储 链栈需要加头结点吗 将哪一端作为栈顶 注 链栈不需要附设头结点 链栈类的定义 templateclassLinkStack 声明templateclassNode friendclassLinkStack private typedata Node next 此处也可以省略 templateclassLinkStack public LinkStack 构造函数 置空链栈 LinkStack 析构函数 释放链栈中各结点的存储空间voidPush typeitem 将元素item入栈typePop 将栈顶元素出栈typeGetTop 取栈顶元素 并不删除 boolEmpty 判断链栈是否为空栈private Node top 栈顶指针即链栈的头指针 链栈的构造函数算法实现 templateLinkStack LinkStack top NULL 初始化空栈 操作接口 templateLinkStack LinkStack 算法实现 算法实现 templatevoidinkStack Push typex Node s s newNode s data x s next top top s an an 1 a1 链栈的入栈算法实现 操作接口 templatevoidLinkStack Push typex 为什么没有判断栈满 算法实现 templatetypeLinkStack Pop Node p typex if top NULL throw 栈空 x top data p top top top next deletep returnx 链栈的出栈算法实现 操作接口 templateTLinkStack Pop an an 1 a1 top 可以吗 顺序栈和链栈的比较 时间性能 相同 都是常数时间O 1 空间性能 顺序栈 有元素个数的限制和空间浪费的问题 链栈 没有栈满的问题 只有当内存没有可用空间时才会出现栈满 但是每个元素都需要一个指针域 从而产生了结构性开销 总之 采用顺序栈存储方式 可使多个栈共享空间 当栈中元素个数变化较大 且存在多个栈的情况下 链栈是栈的首选存储方式 调用函数或子程序非它莫属 递归运算的有力工具 用于保护现场和恢复现场 简化了程序设计的问题 其它应用 如括号匹配问题 表达式计算问题等 答 3 栈的应用举例 为什么要设计栈 它有什么独特用途 数制转换 十转八进制 设计思路 用栈暂存低位值算法分析 NNdiv8Nmod87492911101 栈的应用实例 如 74 10 112 8 voidconversion 对于输入的任意一个非负十进制整数 打印输出与其等值的八进制数 SeqStacks1 10 intN n inte cout N n N while n s1 Push n n n while s1 Empty e s1 Pop cout e cout endl 栈的应用实例 括号匹配的检验设计思路 用栈暂存左括号如 栈的应用实例 表达式求值设计思路 用栈暂存运算符和操作数 例如 A B C D E 1 要正确求值 首先了解算术四则运算的规则 a 括号内优先级最高b 优先级相同 从左算到右由此 此表达式的计算顺序为 T1 A BT2 T1 CT3 D ET4 T2 T3小结 正确计算需知道算符的优先级 且需要使用括号来反映优先级 参见P92 如表达式求值 典型实例 1 常用的表达式是中缀表达式 操作符在操作数之间 例如 AB C DE 后缀表达式的计算过程 操作步骤后缀表达式AB C DE T1 A BT1C DE T2 T1 CT2DE T3 D ET2T3 T4 T2 T3T4小结 后缀表示法两大优点 1 不需要使用括号 2 不用考虑操作符的优先级 2 另一种表达式表示是后缀表达式 每个操作符出现在操作数之后 后缀表达式的计算过程描述 1 从左向右扫描 遇操作数则进栈 若遇操作符 则按其性质 一元或二元 从栈中弹出相应个数的操作数 运算完后 运算结果进栈 直至整个表达式扫描完毕 表 后缀表达式计算的步骤 AB C DE 算法描述 templatevoideval postexpe postexp后缀表达式 SeqStackstack 栈对象初始化 for intj 0 e getterm j j 取表达式的每一项charx e getterm j if x 入栈 else 根据操作符x的性质 从栈中取出正确数目的操作数 Ta1 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 Tv stack Pop 最后结果出栈cout 表达式的值为 v endl 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 算法描述 templatevoidpostfix expressione SeqStackstack 初始化操作符栈stack Push 先入栈charx1 stack GetTop 读取栈顶元素intj 0 charx2 e getterm j 读取表达式的项cout 后缀表达式为 endl while stack Empty if x2 读取表达式的下一项 elseif preority comp x1 x2 x1的优先级 x2的优先级 x1 stack Pop 退栈cout x1 ends x1 stack GetTop 取栈顶元素 elseif preority comp x1 x2 x1的优先级 x2的优先级 stack Pop 去掉栈顶的左括号或 号if stack Empty x1 stack GetTop if x2 j x2 e getterm j 读取表达式的下一项 cout endl 技巧提示 巧用枚举intQW charc