栈及其应用PPT课件

栈及其应用 安庆四中范江文 在现实生活中 常常会出现一些特殊的线性结构的情形 例如 我们在洗碗时 总是将最后洗的碗叠在当前一列碗的最上面 而用的时候总是将最上面的碗 也就是最后洗的碗先拿去用 类似的 储蓄罐 瓷坛等只有一个开口的容器存放物品时 都是具有最后放的东西最先倒出来的特性 图1是某个火车站的车厢调度储存室 进站的火车厢只能从左端进入 并从左端出站 这个特殊的调度室也具有一端封闭的特性 因此最后调入的火车厢肯定最先调出 我们将具有 先进后出 特性的特殊装置 称之为栈 一 栈的定义从上面的例子 我们可以看出 栈 Stack 是一种特殊的线性表 它的特殊之处在于限定仅能在表的一端进行插入或删除操作 换句话说 栈的操作是按后进先出的顺序处理数据 因此栈又称后进先出表 LastnFirstOut LIFO 对于一个栈来说 我们习惯上称它的可操作端为栈顶 Top 另一端为栈底 Bottom 设栈S a1 a2 an a1端为栈底 an端为栈顶 则有 1 插入一个元素an 1后 栈更新为S a1 a2 an an 1 2 从栈中删除一个元素后 栈更新为S a1 a2 an 1 特别的 不含任何元素的栈称为空栈 二 栈的实现1 栈的顺序存储结构我们称用顺序结构存储的栈为顺序栈 array basedstack 即 利用连续的存储单元依次记录栈的所有元素 一般来说 使用一维数组B存储栈的所有元素 变量top记录栈的大小 将s 1 叫作为栈底 s top 为栈顶 顺序栈Stack定义如下 TYPEStack recordtop integer 栈顶指针 s array 1 Maxlength ofelemtype 记录栈中元素的线性表 Procedureinit 初始化栈 functionpush varst stack a elemtype boolean 压栈 若栈不满 则在栈顶插入元素a 返回true 否则返回false functionpop stack elemtype 弹栈 若栈不为空则删除栈顶元素并返回元素值 否则返回NULL procedurestack init Top 0 栈置空 functionpush varst stack a elemtype boolean Iftop maxlengththenbegininc st top st s st top a endelsepush fasle functionpop elemtype Ifst top 0then栈为空elsepop st s st top dec st top 三 栈的应用 一 堆栈具有先进后出 后进先出 的特性 凡是具有这种特性的题目我们都可以用堆栈来试一试 例1 编制一个满足下列要求的程序 对于输人的任意一个非负十进制整数 打印输出与其等值的八进制数 例如 1348 10 2504 8 例2 括弧匹配检验 假设表达式中允许包含两种括号即圆括号和方括号 其嵌套的顺序随意 如 或 等为正确的匹配 或 或 均为错误的匹配 现在的问题是 要求检验一个给定表达式中的括弧是否正确匹配 这八进制的各个数位产生的顺序是从低位到高位的 而打印输出的顺序 一般来说应从高位到低位 这恰好和计算过程相反 所以 堆栈的用武之地出来了 具体做法就是把求到的数位先依次入栈 然后再依次出栈 看是否匹配 具体是看每个左括号是否有一个右括号跟它匹配 而且括号可以嵌套 要检查外层括号是否匹配 必须先检查内层的括号是否匹配 也就是先遇到的左括号后处理 这时 堆栈又有了用武之地 具体做法是遇到左括号就入栈 遇到右括号就出栈并判断是否匹配 当括号串全部处理完毕 而且堆栈为空 则是合法的 其他情况都是非法的 例3 给定N N 100000 个数 找出每个数后面第一个比它大的数的编号 没有输出0 input 326112output 330660 先把题目要求的那个编号叫做后继编号 数列是按照从左往右的顺序编号的 在遇到比它大的元素之前 是无法知道这个元素的后继编号的 并且是离后继编号元素最近的元素先求出来 堆栈的用武之地又出现了 维护一个栈 栈里面存储所有尚未确定后继编号的数 显然这个栈里的数是单调递减的 初始栈里没有数 或者有一个 就是第一个数 然后对于每一个尚未处理的数 用它和栈顶的数比较 如果小于等于栈顶 就入栈 如果大 就把栈顶的数出栈 这时候栈顶的数的后继编号 重复这一过程直到这个数入栈或者栈为空 然后再入栈 接着继续处理剩下的数 例4 利用栈实现算术表达式求值编写一个包含有 等运算符的表达式 计算出该表达式的数值 例如 3 5 2 7 3 3 7 9 7 16 分析 对于给定的表达式计算 有一个运算符优先计算的问题 即 先算括号内 再算括号外 先算乘除 再算加减 同一级别的算符从左到右进行运算 等 因此 我们在计算过程中确定优先规则至关重要 对于任意一个表达式 我们可以将之抽象成以下形式 S D1op1D2op2D3op3 Diopi Dn 1opn 1Dn 这里Di为操作数 opi为运算符 i l 2 n l 由此 我们得到如下算法 1 对S进行扫描 从opi中找一个最高优先级别的运算符进行操作并将Di 1 Di 1opi 1Di 删除opi 1和Di 2 如果S只有一个数 那么S为答案 否则 转到第一步继续操作 上述算法 要扫描S表达式n 1次 每对S做一次扫描 需要对S的每个字符作判断 如果S用链表存储 那么可以避免删除后的移动 因此时间复杂度为O n2 进一步分析 实际上对整个表达式计算 只需要判断相邻两个操作符的优先规则即可 例如 3 4 5 6 2 按道理需要计算 但是我们可以不先计算 而是采用从左到右直接比较相邻的两个操作符 先计算优先级别高的算符即可 如下 3 4 5 6 2 比较 和 因为 优先级高 因此先计算 7 5 6 2 比较 和 因 优先级别高 因此先计算 2 6 2 比较 和 因为 优先级别高 因此先计算 2 12 14 这样 我们可以利用栈来存储算符 将算符入栈 每次将栈顶算符和当前算符比较 若栈顶算符优先规则较高 则运算后弹栈 若较低 则将当前算符压栈 继续操作 直到表达式计算结束为止 为了便于比较算符的优先规则 可以先定义一个算符优先共规则的常量表 为了程序方便 可在表达式两端添加虚拟的运算符 用操作符栈optr存储操作符 用操作栈opnd存储操作数 如图 Constop array 1 7 ofchar preddede array 1 7 1 7 char X X 算法如下 functionexp cal longint inistack optr inisiack opnd 初始化操作数和操作符栈 push optr 预处理将 压入操作符栈 read w whilenot w and gettop optr DO 表达式还没有处理完毕 Ifnotwinopthen push opnd w read w elsecasepredede op gettop optr op w of 比较optr栈顶元素和当前算符的优先级别 theta pop optr b pop opnd a pop opnd push opnd operate a theta b 栈顶算符优先级高 从opnd中取出两个操作数进行计算 X writeln thereisanerrorofexpress exit 1 Endreturn gettop opnd endF 例5 等价表达式 问题描述 明明进行了中学之后 学到了代数表达式 有一天 他碰到一道很麻烦的选择题 这个题目的提干中首先给出了一个代数表达式 然后列出了若干选项 每个选项也是一个代数表达式 题目的要求是判断选项中哪些代数表达式是和提干中的表达式等价的 这个题目手算很麻烦 以为明明对计算编程很感兴趣 所以他想是不是可以用计算机来解决这个问题 假设你是明明 能完成这个问题吗 这个选择题中的每个表达式都满足下面的性质 1 表达式只可能包含一个变量 a 2 表达式中出现的数都是正整数 而且都小于10000 3 表达式中可以包括四种运算 加 一 减 乘 乘幂 以及小括号 小括号的优先级最高 其次是 然后是 最后是 和 和 的优先级是相同的 相同优先级的运算从左到右进行 注意 运算符 都是英文字符 4 幂指数只可能是1到10之间的正整数 包括1和10 5 表达式内部 头部或者尾部都可能有一些多余的空格 下面是一些合理的表达式的例子 a 1 2 3 a a a a a a 9999 a a a 1 a a 3 1 10 9 输入 输入文件equal in的第一行给出的是提干中的表达式 第二行是一个整数n 2 n 26 表示选项的个数 后面n行 每行包括一个选项中的表达式 这n个选项的标号分别是A B C D 输入中的表达式的长度都不超过50个字符 而且保证选项中总有表达式和题干中的表达式是等价的 输出 输出文件equal out包括一行 这一行包括一系列选项的标号 表示哪些选项是和题干中的表达式等价的 选项的标号按照字母顺序排列 而且之间没有空格 样例输入 a 1 23 a 1 2 4 aa 1 aa 2 2 a 1 1 2 10 a a 样例输出 AC 数据规模l对于30 的数据 表达式中只可能出现两种运茸符 和 对于其他的数据 四种运算符在表达式中都可能出现 对于全部的数据 表达式中却可能出现小括号 分析 这道题目是要我们判断有哪些表达式和给出的表达式本质相同 如果我们将每个表达式进行化简 然后进行相等判断 很难找到同一规则 最后都变成最简表达式 即使有统一规则 程序也比较复杂 注意到数学里面的恒等式的性质 如果两个表达式相等 那么对a取任意符合表达式条件的数值 两个表达式的计算结果一致 因此我们可以用抽样取值法 也就是对表达式中的变量a随机取若干个值代入 若两个表达式的计算结果一致 则认为两个表达式等价 当然 抽样调查 并不能保证所有 但如果抽样的数值比较好的话 从概率上分析 出错率会很低 算法流程如下 1 随机取20 30个a值2 将每个a的取值代入每个表达式 计算出每个表达式的结果 3 如果对每个取值 两个表达式的结果相等 则认为它们是等价的表达式 否则不是 4 输出结果 这里需要注意一些小问题 在随机取值时 尽量取随机素数 另外 表达式可以出现连续的幂运算 这样计算的结果会很大 为了简化运算 我们可以将每次运算的中间结果对某大素数取余即可 需要注意的是幂运算的优先规则是从左到右运算 比如 A 10 2