数据结构第三章Cppt课件.ppt

第三章栈和队列 第三章栈和队列 3 1栈3 1 1栈的概念及运算3 1 2顺序栈3 1 2链栈3 2栈的应用举例3 3队列3 4队列的应用举例 本章主题 栈和队列的应用教学目的 掌握栈和队列的应用方法 理解栈的重要作用教学重点 利用栈实现行编辑 利用栈实现表达式求值教学难点 利用栈实现表达式求值 线性表栈队列Insert L i x 1 i n 1 Insert S n 1 x Insert Q n 1 x Delete L i 1 i n Delete S n Delete Q 1 栈和队列是两种特殊的线性表 它们是运算时要受到某些限制的线性表 故也称为限定性的数据结构 从数据结构的角度看 它们和线性表相同从数据类型的角度看 它们和线性表不同 3 1栈3 1 1栈的概念及运算栈 Stack 是限制仅在表的一端进行插入和删除运算的线性表 通常称插入 删除的这一端为栈顶 Top 另一端为栈底 Bottom 当表中没有元素时称为空栈 假设栈S a1 a2 a3 an 则a1称为栈底元素 an为栈顶元素 栈中元素按a1 a2 a3 an的次序进栈 退栈的第一个元素应为栈顶元素 换句话说 栈的修改是按后进先出的原则进行的 因此 栈称为后进先出表 LIFO 堆栈操作 出 例 一个栈的进栈序列是a b c d e 则栈的不可能的输出序列是 A edcbaB decbaC dceabD abcde 栈的基本运算有五种 1 置栈空SETNULL s 2 判栈空EMPTY s 3 入栈PUSH s x 4 出栈POP s 5 取栈顶TOP s 3 1 2顺序栈由于栈是运算受限的线性表 因此线性表的存储结构对栈也适应 栈的顺序存储结构简称为顺序栈 它是运算受限的线性表 因此 可用数组来实现顺序栈 因为栈底位置是固定不变的 所以可以将栈底位置设置在数组的两端的任何一端 栈顶位置是随着进栈和退栈操作而变化的 故需用一个整型变量top来指示当前栈顶位置 通常称top为栈顶指针 因此 顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可 顺序栈的类型定义如下 definemaxSize100typedefchardatatype typedefstruct datatypedata maxSize inttop seqstack seqstack s 例 一叠书或一叠盘子 6543210 设S是SeqStack类型的指针变量 若栈底位置在向量的低端 即s data 0 是栈底元素 那么栈顶指针s top是正向增加的 即进栈时需将s top加1 退栈时需将s top减1 因此 s toptop maxsize 1表示栈满 当栈满时再做进栈运算必定产生空间溢出 简称 上溢 当栈空时再做退栈运算也将产生溢出 简称 下溢 上溢是一种出错状态 应该设法避免之 下溢则可能是正常现象 因为栈在程序中使用时 其初态或终态都是空栈 所以下溢常常用来作为程序控制转移的条件 1 置空栈SETNULL seqstack s s top 1 2 判栈空intEMPTY seqstack s if s top 0 returnFALSE elsereturnTRUE 3 进栈seqstack PUSH seqstack s datatypex if s top maxsize 1 returnNULL elses data s top x returns 4 退栈datatypePOP seqstack s if EMPTY s returnNULL elses top return s data s top 5 取栈顶DatatypeTOP seqstack s if EMPTY s returnNULL elsereturn s data s top 两栈共享 栈1底STACK 0 栈1顶top1 栈2顶top2 栈2底STACK M 1 栈1 栈2 上溢 top2 top1 1 3 1 3链栈栈的链式存储结构称为链栈 它是运算受限的单链表 其插入和删除操作仅限制在表头位置上进行 由于只能在链表头部进行操作 故链表没有必要像单链表那样附加头结点 栈顶指针就是链表的头指针 链栈的类型说明如下 typedefintdatatype typedefstructnode datatypedatastructnode next linkstack linkstack top 当top NULL时 该链栈是空栈 链栈的进栈算法 Linkstack PUSHLSTACK linkstack p datatypex Linkstack pP malloc sizeof linkstack p data x p next top returnp 进栈元素x p malloc sizeof linkstack p data x p next top top p return p top p malloc sizeof linkstack p data x p next top top p return p x top p malloc sizeof linkstack p data x p next top top p return p x top top p malloc sizeof linkstack p data x p next top top p return p x 链栈的出栈算法 linkstackPOPLSTACK linkstack top datatype datap linkstack p if top NULL printf stackunderflow else datap top data p top top top next free p returntop 3 2栈的应用举例由于栈结构具有的后进先出的固有特性 致使栈成为程序设计中常用的工具 以下是几个栈应用的例子 例1行编辑程序一个简单的行编辑程序的功能是 接受用户从终端输入的程序或数据 并存入用户的数据区 每接受一个字符即存入用户数据区 不恰当 较好的做法是 设立一个输入缓冲区 用以接受用户输入的一行字符 如果正确再存入用户数据区 在用户输入一行的过程中 允许用户输入出差错 并在发现有误时可以及时更正 缓冲区 用栈实现 例如 可用一个退格符 表示前一个字符无效 可用一个退行符 表示当前行中 之前的的字符均无效 假设从终端接受了这样两行字符 whli ilr e s s while s outcha putchar s putchar s Seqstacks EDIT charc SETNULL 例2数制转换十进制数N和其他d进制数的转换是计算机实现计算的基本问题 其解决方法很多 其中一个简单算法基于下列原理 N Ndivd d Nmodd 其中 div为整除运算 mod为求余运算 例如 1348 10 2504 8 其运算过程如下 NNdiv8Nmod813481684输168210出2125顺202序 分析 假设现要编制一个满足下列要求的程序 对于输入的任意一个非负十进制整数 打印输出与其等值的八进制数 由于上述计算过程是从低位到高位顺序产生八进制数的各个数位 而打印输出 一般来说应从高位到低位进行 恰好和计算过程相反 因此 若将计算过程中得到的八进制数的各位顺序进栈 则按出栈序列打印输出的即为与输入对应的八进制数 voidconversion 对于输入的任意一个非负十进制整数 打印输出与其等值的八进制数 SETNULL S 构造空栈scanf d N while N 当N 0时循环结束 Push S N 8 N N 8 while EMPTY S Pop S e printf d e 表达式求值是程序设计语言编译中的一个最基本问题 它的实现方法是栈的一个典型的应用实例 在计算机中 任何一个表达式都是由操作数 运算符和界限符组成的 其中操作数可以是常数 也可以是变量或常量的标识符 运算符可以是算术运算符 关系运算符和逻辑运算符 界限符为左右括号和标识表达式结束的结束符 在本例中 仅讨论简单算术表达式的求值问题 在这种表达式中只含加 减 乘 除四则运算 所有的运算对象均为单变量 表达式的结束符为 算术四则运算的规则为 1 先乘除 后加减 2 同级运算时先左后右 3 先括号内 后括号外 例3表达式求值 把运算符和界限符统称为算符 可以将它们构成的集合命名为OP 在运算的每一步中 任意两个相继出现的算符c1和c2之间的优先关系至多是下面三种关系之一 c1c2c1的优先权高于c2由规则 3 和 为c1时的优先性均低于 但高于 由规则 2 当c1 c2时 令c1 c2 为了算法简洁 在表达式的最左边也虚设一个 构成整个表达式的一对括号 表示当左右括号相遇时 括号内的运算已经完成 同理 表示整个表达式求值完毕 计算机系统在处理表达式前 首先设置两个栈 1 操作数栈 NS 存放处理表达式过程中的操作数 2 运算符栈 OS 存放处理表达式过程中的运算符 开始时 在运算符栈中先在栈底压入一个表达式的结束符 以表达式A B C D为例说明利用栈的求值过程 思想 从左到右扫描表达式1假如是操作数 则将其压入操作数栈 并依次读下一个符号 2假如是运算符 则 1 假如读出的运算符的优先级大于运算符栈栈顶运算符的优先级 则将其压入运算符栈 并依次读下一个符号 2 假如读出的是表达式结束符 且运算符栈栈顶的运算符也为 则表达式处理结束 最后的表达式的计算结果在操作数栈的栈顶位置 3 假如读出的是 则将其压入运算符栈 4 假如读出的是 则 A运算符栈栈顶不是 则从操作数栈连续退出两个操作数 从运算符栈中退出一个运算符 然后作相应的运算 并将运算结果压入操作数栈 然后继续执行A B若运算符栈栈顶为 则从运算符栈退出 依次读下一个符号 5 假如读出的运算符的优先级不大于运算符栈栈顶运算符的优先级 则从操作数栈连续退出两个操作数 从运算符栈中退出一个运算符 然后作相应的运算 并将运算结果压入操作数栈 此时读出的运算符下次重新考虑 即不读入下一个符号 A B C D 如 x 3 7 2 执行过程 3 7 2 如 x 3 7 2 执行过程 3 7 2 如 x 3 7 2 执行过程 3 7 2 表达式计算的程序实现 OperandtyEvaluateExpression Initstack OS Initstack NS push OS c getchar while c Top OS if In c OP Push NS c c getchar In c OP 为假 则为操作数进栈 elseswitch Precede Top OS c case pop OS theta pop NS b pop NS a push NS Operate a theta b c getchar break returntop NS 表达式求值结束 以上讨论的表达式一般都是运算符在两个操作数中间 除单目运算符外 这种表达式被称为中缀表达式 中缀表达式有时必须借助括号才能将运算顺序表达清楚 处理起来比较复杂 在编译系统中 对表达式的处理采用的是另外一种方法 即将中缀表达式转变为后缀表达式 然后对后缀表达式进行处理 后缀表达式也称为逆波兰式 波兰表示法 也称为前缀表达式 是由波兰逻辑学家 Lukasiewicz 提出的 其特点是将运算符置于运算对象的前面 如a b表示为 ab 逆波兰式则是将运算符置于运算对象的后面 如a b表示为ab 中缀表达式处理成逆波兰式后 运算时按从左到右的顺序进行 不需要括号 得到后缀表达式后 我们在计算表达式时 可以设置一个栈 从左到右扫描后缀表达式 每读到一个操作数就将其压入栈中 每到一个运算符时 则从栈顶取出两个操作数进行运算 并将结果压入栈中 一直到后缀表达式读完 最后栈顶就是计算结果 在计算机中 表达式可以有三种不同的标识方法设Exp S1 OP S2则称OP S1 S2为表达式的前缀表示法称S1 OP S2为表达式的中缀表示法称S1 S2 OP为表达式的后缀表示法可见 它以运算符所在不同位置命名的 限于二元运算符的表达式定义 表达式 操作数 运算符 操作数 操作数 简单变量 表达式简单变量 标识符 无符号整数 结论 1 操作数之间的相对次序不变 以前在前的还在前 2 运算符的相对次序不同 3 中缀式丢失了括弧信息 致使运算的次序不确定 中缀式是无意义的 4 前缀式的运算规则为 连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式 5 后缀式的运算规则为 A 运算符在式中出现的顺序恰为表达式的运算顺序 B 每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式 如何从后缀式求值 先找运算符 后找操作数 如何从原表达式求得后缀式 分析 原表达式 和 后缀式 中的运算符 例如 表达式 a b c d e f后缀表达式 abc de f 这里的最小表达式可以看成是a b 也可以看成是b c 也就是说b是前一个运算符的第二操作数呢 还是后一个运算符的第一操作数 这取决于 和 这两个次序关系 对人一目了然 知道先作 后作 对计算机要扫描 所以 每个运算符的运算次序要由它之后的一个运算符来定 若当前运算符的优先数小 则暂不进行 否则立即进行 从原表达式求得后缀式的规律为 设立运算符栈 设表达式的结束符为 为了第一个操作符有比较 预设运算符栈的栈底为 若当前字符是操作数 则直接发送给后缀式 若当前运算符的优先数高于栈顶运算符 则进栈 否则 退出栈顶运算符发送给后缀式 然后当前运算符进栈 对它之前后的运算符起隔离作用 所以 总是进栈 可视为自相应左括弧开始的表达式的结束符 中缀表达式 后缀表达式 1 5 6 2 3 中缀表达式 后缀表达式 1 5 6 2 3 1 7 后缀表达式的处理过程 1562 3 5 6 2 3 2 6 3 7 r 主程序 过程的嵌套 分析 在高级语言编制的程序中 调用函数与被调用函数之间的链接和信息交换必须通过栈来进行 当在一个函数的运行期间调用另一个函数时 在运行该被调用函数之前 需先完成三件事 1 将所有的实在参数 返回地址等信息传递给被调用函数保存 2 为被调用函数的局部变量分配存储区 3 将控制转移到被调用函数的入口 由此可看出 栈中要存三类参数 返回地址 实参 临时变量从被调用函数返回调用函数之前 应该完成 1 保存被调函数的计算结果 2 释放被调函数的数据区 3 依照被调函数保存的返回地址将控制转移到调用函数多个函数嵌套调用的规则是 后调用先返回 此时的内存管理实行 栈式管理 例 函数的递归调用 定义 在调用一个函数的过程中直接或间接地调用该函数本身 直接调用intf x intx inty z z f x return 2 z f函数 调用f函数 intf1 x intx inty z z f2 y return 2 z intf2 t intt inta c c f1 a return 3 c 间接调用 递归是算法设计中最常用的手段 它通常把一个大型复杂的问题转化为一个与原问题相似的规模较小的问题来求解 往往通过少量的语句 实现重复计算 起到事半功倍的作用 在以下三种情况下 常常要用到递归的方法 floatfac intn floatf if n 0 printf n 0 dataerror n elseif n 0 n 1 f 1 elsef fac n 1 n returnf 例如 写一函数求n 1 n 0 1 n n n 1 n 1 以求4的阶乘为例 fac 4 4 fac 3 fac 3 3 fac 2 fac 2 2 fac 1 fac 1 1 fac 4 4 3 2 1 fac 2 2 1 fac 3 3 2 1 下推 回代 利用栈实现递归调用 调用结果为 1231412 例 n阶Hanoi 汉诺 塔问题假设有三个分别命名为X Y和Z的塔座 在塔座上X上插有n个直径大小各不相同 从小到大依次编号为1 2 n的圆盘 现要求将X轴上的n个圆盘移到塔座Z上 并仍按同样的顺序叠放 移动过程中一次只能移动一个圆盘 不允许大圆盘放在小圆盘上面 而只能借助于中间的塔座 分析 1 要把n个圆盘从X塔移动到Z塔 首先借用Y塔作为存放圆盘的临时塔 把塔座上面的n 1个圆盘移动到Y塔 2 把X塔座上的第n个圆盘移动到Z塔 3 现在问题变成如何把Y塔上的n 1个圆盘移动到Z 可以把X作为临时塔 把第n 1个圆盘上面的n 2个圆盘从Y移动到X 再把第n 1个圆盘移动到Z 这样n 2个圆盘又回到了X上了 4 以此类推 下面n 2个圆盘的移动是在重复第一 二步操作 变成了典型的递归问题 voidhanoi intn charx chary charz 将塔座x上按直径由小到大且至上而下编号为1至n的n个圆盘按规则搬到塔座z上 y可用作辅助塔座 1 2if n 1 3move x 1 z 将编号为 的圆盘从x移到z4else 5hanoi n 1 x z y 将x上编号为 至n 1的圆盘移到y z作辅助塔6move x n z 将编号为n的圆盘从x移到z7hanoi n 1 y x z 将y上编号为 至n 1的圆盘移到z x作辅助塔8 9 假定某主程序调用haoni子程序Haoni 3 A B C 这个语句向Haoni函数提供 实参 n 3以及3个柱子的名字 递归子程序的执行顺序为 Haoni 3 A B C 首先调用Haoni 2 A C B 进入Haoni 2 A C B 后调用Haoni 1 A B C move A B 和Haoni 1 C A B 当以上语句执行的时候 栈进入三层 它们执行完毕后 依次返回 栈弹出到第一层 返回到第一层的Haoni 3 A B C 程序 执行语句move A C 接着调用Haoni 2 B A C 进入Haoni 2 B A C 后调用Haoni 1 B C A move B C 和Haoni 1 A B C 当执行以上语句时 栈进入三层 而当它们执行完毕后 依次返回 栈弹出到第一层 最后完成n 3的Haoni任务 注意 当n 10时 完成任务需要移动圆盘约1000次 当n 30时 完成任务则需要移动圆盘超过1000万次 完成Haoni任务所需要的时间是随着n的增长而指数性增长的 因此 这个算法的时间复杂性是指数爆炸的 3 3队列3 3 1队列的概念及运算队列 Queue 也是一种运算受限的线性表 它只允许在表的一端进行插入 而在另一端进行删除 允许删除的一端称为队头 front 允许插入的一端称为队尾 rear 例如 排队购物 操作系统中的作业排队 先进入队列的成员总是先离开队列 因此队列亦称作先进先出 FirstInFirstOut 的线性表 简称FIFO表 当队列中没有元素时称为空队列 在空队列中依次加入元素a1 a2 an之后 a1是队头元素 an是队尾元素 显然退出队列的次序也只能是a1 a2 an 也就是说队列的修改是依先进先出的原则进行的 下图是队列的示意图 a1a2 an 队列的基本运算有五种 1 置队空SETNULL 2 判队空EMPTY 3 入队ENQUEUE Q x 4 出队DEQUEUE Q 5 取队头FRONT Q 3 3 2顺序队列队列的顺序存储结构称为顺序队列 顺序队列实际上是运算受限的顺序表 和顺序表一样 顺序队列也是必须用一个向量空间来存放当前队列中的元素 由于队列的队头和队尾的位置是变化的 因而要设两个指针分别指示队头和队尾元素在队列中的位置 队列初始化时均应置为 1 入队时将新元素插入所指的位置 然后尾指针将加 出队时 删去所指的元素 然后将队头指针加 并返回被删元素 由此可见 当头尾指针相等时队列为空 顺序队列 队空时 令rear front 1 当有新元素入队时 尾指针加1 当有元素出队时 头指针加1 故在非空队列中 头指针始终指向队头元素前一个位置 而尾指针始终指向队尾元素的位置 和栈类似 队列中亦有上溢和下溢现象 此外 顺序队列中还存在 假上溢 现象 因为在入队和出队的操作中 头尾指针只增加不减小 致使被删除元素的空间永远无法重新利用 因此 尽管队列中实际的元素个数远远小于向量空间的规模 但却可能由于尾指针巳超出向量空间的上界而不能做入队操作 该现象称为假上溢 为充分利用向量空间 克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环 并称这种向量为循环向量 存储在其中的队列称为循环队列 CircularQueue 在循环队列中进行出队 入队操作时 头尾指针仍要加1 朝前移动 只不过当头尾指针指向向量上界 maxsize 1 时 其加1操作的结果是指向向量的下界0 这种循环意义下入队操作时 尾指针加1操作可以描述为 if sq rear 1 maxSize sq rear 0 elsesq rear 利用模运算可简化为 sq rear sq rear 1 maxSize同理出队操作时 头指针加1操作利用模运算可描述为 sq front sq front 1 maxSize显然 因为循环队列元素的空间可以被利用 除非向量空间真的被队列元素全部占用 否则不会上溢 因此 除一些简单的应用外 真正实用的顺序队列是循环队列 如图所示 由于入队时尾指针向前追赶头指针 出队时头指针向前追赶尾指针 故队空和队满时头尾指针均相等 因此 我们无法通过front rear来判断队列 空 还是 满 解决此问题的方法至少有两种 其一是另设一个布尔变量以判别队列的空和满 其二是约定入队前 测试尾指针在循环意义下加1后是否等于头指针 若相等则认为队满 注意 front所指的单元始终为空 循环队列 rear 队满条件 Q rear 1 MAX Q front注 实际上为了避免与队空标志冲突 还留有一个空间 将头尾连接成一个环 形成循环队列 在循环队列上实现的五种基本运算如下 1 置空队SETNULL sq sq front maxsize 1 sq rear maxsize 1 2 判断队空intEMPTY sq sequeue sq if sq rear sq front return TRUE elsereturn FALSE 3 取队头元素datatypeFRONT sq sequeue sq if EMPTY sq returnNULL elsereturn sq fron 1 maxsize 4 入队ENQUEUE sq x sequeue sq datatypex if sq front sq rear 1 maxsize error queueoverflow elsesq rear sq rear 1 maxsize sq data sq rear x return TRUE sq rear sq rear 1 maxsize sq data sq rear x return 1 rear x 5 出队datatypeDEQUEUE sq sequeue sq if EMPTY sq error queueunderflow elsesq front sq front 1 maxsize return sq data sq front 3 3 3链队列队列的链式存储结构简称为链队列 它是限制仅在表头删除和表尾插入的单链表 显然仅有单链表的头指针不便于在表尾做插入操作 为此再增加一个尾指针 指向链表的最后一个结点 于是 一个链队列由一个头指针和一个尾指针唯一确定 和顺序队列类似 也是将这两个指针封装在一起 将链队列的类型LinkQueue定义为一个结构类型 typedefstruct linklist front rear linkqueue linkqueue q 下面给出链队列上实现的基本运算 voidSETNULL linkqueue q q front q rear null intEMPTY linkqueue q returnq front null voidENQUEUE linkqueue q datatypex linkqueue pp malloc sizeof linklist p data x p next NULL if EMPTY q q front q rear p else q rear next p q rear p DatatypeDEQUEUE linkqueue q datatypex linklist pif EMPTY q error queueunderflow p q front x p data q front p next if q rear p q rear NULL free p returnx datatypeFRONT linkqueue q if EMPTY q error queueisempty returnq front next data 注意 在出队算法中 一般只需修改队头指针 但当原队中只有一个结点时 该结点既是队头也是队尾 故删去此结点时亦需修改尾指针 且删去此结点后队列变空 删除 一个元素 添加一个元素 e 链队列 Q front Q rear Q rear Q front 3 4队列的应用举例 由于队列的操作满足FIFO原则 因而具有FIFO特性的问题均可利用队列作为数据结构 例如在允许多道程序的计算机系统中 同时有几道作业运行 如果运行的结果都需要通过通道输出 那么就可以按请示输出的先后次序 将这些作业排成一个队列 每当通道传输完毕可以接受新的输出任务时 将队头的作业出队 作输出操作 凡是申请输出的作业都是从队尾进入队列 计算机系统中输入输出缓冲区的结构也是队列的应用 在计算机系统中经常会遇到两个设备之间的数据传输 不同的设备通常处理数据的速度是不同的 当需要在它们之间连续处理一批数据时 高速设备总是要等待低速设备 这就造成计算机处理效率的大大降低 为了解决这一速度不匹配的矛盾 通常就是在这两个设备之间设置一个缓冲区 这样 高速设备就不必每次等待低速设备处理完一个数据 而是把要处理的数据依次从一端加入缓冲区 而低速设备从另一端取走要处理的数据 例 求迷宫的最短路径入口 出口 思想 从迷宫入口点 1 1 出发 向四周搜索 记下所有一步能通达的坐标点p11 p1k1 0 k1 3 然后依次从p11 p1k1出发 向四周搜索 记下所有从入口点出发 经过二步能通达的坐标点p21 p2k2 0 k2 5 依次进行下去 直至到达迷宫出口点 m n 为止 然后从出口点沿搜索路径回溯直至入口 就找到了从入口到出口的一条最短路径 分析 1 如何从某一坐标点 x y 出发搜索其四周的邻点 i j 将迷宫四周各镶上一条取值均为1的边 以此表示受阻 于是 对于迷宫中任一点 x y 其搜索方位均为8个 将