第3章 栈和队列.ppt

第三章栈和队列 栈和队列是两种特殊的线性表 是操作受限的线性表 称限定性DS3 1栈 stack 栈的定义和特点定义 限定仅在表尾进行插入或删除操作的线性表 表尾 栈顶 表头 栈底 不含元素的空表称空栈特点 先进后出 FILO 或后进先出 LIFO 栈的存储结构顺序栈实现 一维数组s M 栈顶指针top 指向实际栈顶后的空位置 初值为0 进栈 A 出栈 栈满 B C D E F 设数组维数为Mtop 0 栈空 此时出栈 则下溢 underflow top M 栈满 此时入栈 则上溢 overflow 栈空 已知入栈序列为 出栈序列为 写出他们的操作序列 其中 用X表示入栈操作 用S表示出栈操作 答案 XXSXXSSSXS 还有那些可能的输出序列 哪些是不可能的输出序列 举一例 3 1 1抽象数据类型栈的定义 ADTStack 数据对象 D ai ai ElemSet i 0 1 n 1 n 0 数据关系 R1 ai 1 ai D i 1 n 1 约定an 1端为栈顶 a0端为栈底 基本操作 InitStack ADTStack 基本操作 InitStack S 操作结果 构造一个空栈S DestroyStack S 初始条件 栈S已存在 操作结果 栈S被销毁 StackEmpty S 初始条件 栈S已存在 操作结果 若栈S为空栈 则返回TRUE 否则FALSE StackLength S 初始条件 栈S已存在 操作结果 返回S的元素个数 即栈的长度 ClearStack S 初始条件 栈S已存在 操作结果 将S清为空栈 未完待续 续前 GetTop S e 初始条件 栈S已存在且非空 操作结果 用e返回S的栈顶元素 Push S e 初始条件 栈S已存在 操作结果 插入元素e为新的栈顶元素 除GetTop Push Pop操作外 与一般线性表没有多少区别 因此后面主要讨论这三个操作 续前 Pop S e 初始条件 栈S已存在且非空 操作结果 删除S的栈顶元素 并用e返回其值 1 置空栈voidinitstack seqstack s s top 1 2 判断栈空intstackempty seqstack s return s top 1 有顺序栈和链栈二种存储方法 3 1 2栈的表示和实现 顺序栈 类似于线性表的顺序映象实现 指向表尾的指针可以作为栈顶指针 栈的顺序存储表示 defineSTACK INIT SIZE100 defineSTACKINCREMENT10 typedefstruct SElemType base SElemType top intstacksize SqStack StatusInitStack SqStack 在此存储结构下的基本操作实现 StatusPush SqStack StatusPop SqStack 小结1栈是限定仅能在表尾一端进行插入 删除操作的线性表 2栈的元素具有后进先出的特点 3栈顶元素的位置由一个称为栈顶指针的变量指示 进栈 出栈操作要修改栈顶指针 3 2栈的应用举例 3 2 1数制转换对于输入的任意一个非负十进制数 显示输出与其等值的八进制数 数制转换方法N Ndiv8 10 8 Nmod8N 十进制数 div 整除运算 mod 求余运算 1348 10 2 83 5 82 0 8 4 2504 8N1348168212Ndiv81682120Nmod84052 计算时从低位到高位顺序产生八进制数的各个数位 结果 2504 显示时按从高位到低位的顺序输出 voidconversion InitStack s 建空栈scanf d 3 2 2括号匹配的检验假设在表达式中 或 等为正确的格式 或 或 均为不正确的格式 则检验括号是否匹配的方法可用 期待的急迫程度 这个概念来描述 例如 考虑下列括号序列 12345678 到来的右括弧并非是所 期待 的 到来的是 不速之客 直到结束 也没有到来所 期待 的括弧 分析可能出现的不匹配的情况 算法的设计思想 1 凡出现左括弧 则进栈 2 凡出现右括弧 首先检查栈是否空若栈空 则表明该 右括弧 多余 否则和栈顶元素比较 若相匹配 则 左括弧出栈 否则表明不匹配 3 表达式检验结束时 若栈空 则表明表达式中匹配正确 否则表明 左括弧 有余 Statusmatching SELemType p intflag 1 SELemTypec Stack1S InitStack1 S while p 3 2 3行编辑程序问题 如何实现 每接受一个字符即存入存储器 并不恰当 设立一个输入缓冲区 用以接受用户输入的一行字符 然后逐行存入用户数据区 并假设 为退格符 为退行符 在用户输入一行的过程中 允许用户输入出差错 并在发现有误时可以及时更正 合理的作法是 假设从终端接受了这样两行字符 whli ilr es s outcha putchar s 则实际有效的是下列两行 while s putchar s voidLineEdit InitStack S 构造空栈Sch getchar 从终端接收第一字符while ch EOF EOF为全文结束符while ch EOF 3 2 4迷宫求解入口 出口 迷宫问题 求迷宫中从入口点到出口点所有可能的简单路径 所谓的简单路径是指 在求出的任何一条路径上 不能重现某一通道块 否则总有任意多条路径迷宫问题是许多实际问题的抽象 求解这类问题时 没有现成的数学公式可以套用 只能采用系统化的试探方法 下面规定 通道用空格 表示墙壁用 表示足迹用 0 表示从入口点到当前立足点间 具有足迹标志的相连的通道块构成的简单路径叫当前路径将迷宫模型用二维字符型数组表示 charmaze n 1 n 1 并假定入口为maze 0 0 出口为maze n n 考虑一般情况 设maze i j 为当前立足点 并纳入当前路径 即印上足迹标志 0 则从当前立足点继续试探的算法如下 ifmaze i j 是出口then打印刚找到的一条简单路径 并回溯一步 elseif东面的是通道块then前进一步elseif南面的是通道块then前进一步elseif西面的是通道块then前进一步elseif北面的是通道块then前进一步else回溯一步 i j 东 南 西 北 前进一步 将下一通道块印上 0 作为当前立足点 切换当前立足点 并保存原立足点的信息以便回溯 回溯一步 去掉当前立足点的足迹 0 把最近的原立足点重新切换为当前立足点 试探尚未试探过的方向 上述的活动均需要在迷宫中移动 并且具有方向性 这种活动可以使用二维数组下标增量技术来实现 行下标增量di k 列下标增量dj k 方向及其序号k东0南1西2北3intdi 4 0 1 0 1 intdj 4 1 0 1 0 0 1 1 0 0 1 1 0 在上述的规定下 k 0时 maze i di k j dj k 为立足点的东面下一块 k 1时 maze i di k j dj k 为立足点的南面下一块 k 2时 maze i di k j dj k 为立足点的西面下一块 k 3时 maze i di k j dj k 为立足点的北面下一块 客体的表示方法设计 从上述的用试探法走迷宫的过程可知 其中所管理的信息是立足点的信息 可以用三元组 i j k 来表示立足点 其中 i j 表示立足点的位置信息 k表示立足点的下一个试探方向 可以将三元组定义成一个结构 structitems inti j k 数据的组织方法设计 考察上述用试探法走迷宫的过程 前进一步时 需要保存原立足点的信息 回溯一步时 需要取出最近的原立足点的信息 并且遵循后保存的先取出的原则 即 后进先出 的原则 因此可以用栈来记录立足点的信息 迷宫问题的算法框架 1Stacks sz 栈初始化 创建一个大小为sz的栈 其数据元素类型为items2itemse intk 3e i 0 e j 0 e k 0 s Push e maze e i e j 0 将入口作为立足点并入栈4while s IsEmpty 若栈不空则继续循环试探 若空表示已找到所有简单路径 可以结束程序5 e s Pop 出栈 准备试探下一方向或实现回溯一步操作6if e k 4 maze e i e j 四个方向均试探完毕 消足迹 当再执行到5时回溯一步elseif e i n 3 2 5表达式求值1 问题的提出设计一个小计算器 对键入的表达式进行求值 高级语言中的赋值语句 变量 表达式 2 表达式的构成操作数 运算符 界符 如括号 3 表达式的求值 例5 6 1 2 4按照四则运算法则 上述表达式的计算过程为 5 6 1 2 4 5 6 3 4 5 18 4 23 4 19 1 2 3 4 4 算符优先关系表表达式中任何相邻运算符c1 c2的优先关系有 c1c2 c1的优先级高于c2 算符间的优先关系表 注 c1c2是相邻算符 c1在左 c2在右 算符的优先级设置 3 2栈的应用举例 5算符优先算法 从左向右扫描表达式 遇操作数 保存 遇运算符号cj 与前面的刚扫描过的运算符ci比较若cicj则说明ci是已扫描的运算符中优先级最高者 可进行运算 若ci cj则ci为 cj为 说明括号内的式子已计算完 需要消去括号 5 4 1 2 6 后面也许有优先级更高的算符 后保存的算符有优先级高 用两个栈分别保存扫描过程中遇到的操作数和运算符 3 2栈的应用举例 在算符优先算法中 建立了两个工作栈 一个是OPTR栈 用以保存运算符一个是OPND栈 用以保存操作数或运算结果 intEvaluateExpression 运算数栈 OP为运算符集合 InitStack OPTR Push OPTR InitStack OPND c qetchar While c GetTop OPTR if In c OP Push OPND c c getchar 不是运算符则进栈else In w OP 判断c是否是运算符的函数 3 2栈的应用举例 续switch Precede GetTop OPTR c case 新输入的算符c优先级低 即栈顶算符优先权高 出栈并将运算结果入栈OPNDPop OPTR theta Pop OPND b Pop OPND a Push OPND Operate a theta b break returnGetTop OPND 表达式求值示意图 5 6 1 2 4 5 6 1 2 3 18 23 4 19 5 读入表达式过程 6 1 2 4 19 1 2 3 6 3 18 5 18 23 23 4 19 栈与递归的实现过程的嵌套调用 例递归的执行情况分析 递归过程及其实现递归 函数直接或间接的调用自身叫 实现 建立递归工作栈 voidprint intw inti if w 0 print w 1 for i 1 i w i printf 3d w printf n Ch3 10 c 运行结果 1 2 2 3 3 3 递归调用执行情况如下 TowerofHanoi问题问题描述 有A B C三个塔座 A上套有n个直径不同的圆盘 按直径从小到大叠放 形如宝塔 编号1 2 3 n 要求将n个圆盘从A移到C 叠放顺序不变 移动过程中遵循下列原则 每次只能移一个圆盘圆盘可在三个塔座上任意移动任何时刻 每个塔座上不能将大盘压到小盘上 解决方法 n 1时 直接把圆盘从A移到Cn 1时 先把上面n 1个圆盘从A移到B 然后将n号盘从A移到C 再将n 1个盘从B移到C 即把求解n个圆盘的Hanoi问题转化为求解n 1个圆盘的Hanoi问题 依次类推 直至转化成只有一个圆盘的Hanoi问题算法 执行情况 递归工作栈保存内容 形参n x y z和返回地址返回地址用行编号表示 main Hanoi txt intm printf Inputthenumberofdisks scanf d voidmove inth charc charf printf d c c n h c f main intm printf Inputnumberofdisks scanf d 8 9 main intm printf Inputthenumberofdisksscanf d 8 9 main intm printf Inputthenumberofdisksscanf d 8 9 main intm printf Inputthenumberofdisksscanf d 8 9 回文游戏 顺读与逆读字符串一样 不含空格 1 读入字符串2 去掉空格 原串 3 压入栈4 原串字符与出栈字符依次比较若不等 非回文若直到栈空都相等 回文 字符串 madamimadam 地图四染色问题 1 2 2 3 4 1 4 3 3 4 2 3 1 紫色2 黄色3 红色4 绿色 四染色 定理是计算机科学中著名定理之一 即可以用不多于四色对地图着色 使相邻的行政区域不重色 我们应用这个定理的结论 用回溯算法对一幅给定的地图染色 算法思想 从第一号行政区开始逐一染色 每一个区域逐次用颜色1 2 3 4进行试探 若当前所取的色数与周围已染色的行政区不重色 则用栈记下该行政区的色数 否则依次用下一色数进行试探 若出现用1至4色均与相邻区域发生重色 则需退栈回溯 修改当前栈顶的色数 再进行试探 直至所有行政区域都已分配合适的颜色 3 4队列队列的定义及特点定义 队列是限定只能在表的一端进行插入 在表的另一端进行删除的线性表队尾 rear 允许插入的一端队头 front 允许删除的一端队列特点 先进先出 FIFO 双端队列 抽象数据类型队列的定义ADTQueue 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 约定其中a1端为队列头 an端为队列尾基本操作 InitQueue Q DestroyQueue Q QueueEmpty Q QueueLength Q GetHead Q e ClearQueue Q ADTQueue 队列的基本操作 InitQueue Q 操作结果 构造一个空队列Q DestroyQueue Q 初始条件 队列Q已存在 操作结果 队列Q被销毁 不再存在 QueueEmpty Q 初始条件 队列Q已存在 操作结果 若Q为空 返回TRUE 否则返回FALSEQueueLength Q 初始条件 队列Q已存在 操作结果 返回Q的元素个数 即队列的长度 ClearQueue Q 初始条件 队列Q已存在 操作结果 将Q清为空队列 GetHead Q e 初始条件 Q为非空队列 操作结果 用e返回Q的队头元素 EnQueue Q e 初始条件 队列Q已存在 操作结果 插入元素e为Q的新的队尾元素 DeQueue Q e 初始条件 Q为非空队列 操作结果 删除Q的队头元素 并用e返回其值 队列的顺序存储结构实现 用一维数组实现sq M J1 J2 J3 设两个指针front rear 约定 rear指示队尾元素 front指示队头元素前一位置初值front rear 1 空队列条件 front rear入队列 sq rear x 出队列 x sq front 存在问题设数组维数为M 则 当front 1 rear M 1时 再有元素入队发生溢出 真溢出当front 1 rear M 1时 再有元素入队发生溢出 假溢出解决方案队首固定 每次出队剩余元素向下移动 浪费时间