《栈和队列XU》PPT课件.ppt

第3讲栈和队列 主要内容栈的定义及ADT 存储表示及算法栈的应用示例 表达式求值 回溯算法的栈应用 递归算法的使用技巧队列的定义及ADT 存储表示及算法队列的应用示例 栈和队列 从数据结构的角度看栈和队列也是线性表但其操作是线性表操作的子集栈只能从一端操作 后进先出 LIFO 队列一端只能进 另一端只能出 FIFO 从数据类型的角度看是与线性表不同的两类重要抽象数据类型 栈 stack 定义 限定只能在表的一端进行插入和删除的特殊的线性表设栈s a1 a2 ai an 其中a1是栈底元素 an是栈顶元素 后进先出原则LIFO lastinfirstout 栈顶 top 允许插入和删除的一端 栈底 base 不允许插入和删除的一端 注意top指向的位置 可以指向栈顶元素可以指向当前栈顶元素上相邻的空位 更常用 栈的ADT ADT见P45注意几个基本操作设置空栈插入新的栈顶元素 入栈操作 push 删除栈顶元素 出栈操作 pop 读取栈顶元素依据其存储结构分为顺序栈栈采用顺序存取结构 称为顺序栈 链栈栈采用链表存取结构 称为链栈 如何实现顺序栈 整个线性表每个元素 请你用C或其他语言写出 栈底指针栈顶指针当前栈大小P46 数据元素 可有若干个数据项 为什么要有栈底指针 设数组S是一个顺序栈 栈的最大容量stacksize 4 初始状态top 0 栈空 10进栈 30出栈 栈满 顺序栈 注意top的位置 空栈如何表达 下溢 栈满如何表达 上溢 base 进栈算法 P47 Statuspush SqStack S SElemTypee 判别栈满if S top S base S stacksize cout overflow returnERROR S top e returnOK push a2 a3 a4 9 8 7 6 5 4 3 2 1 a1 0 top base 出栈算法 P47 Statuspop SqStack S SElemType e if S top S base 判别栈空 cout stackempty returnERROR else e S top returnOK 带回出栈元素 其它操作同学自己考虑 base 链栈 top 栈底base 采用链式存储结构约定插入 删除等操作只能在表头进行可以不必像单链表那样附加头结点栈顶指针就是链表的头指针 如何实现链栈 整个线性表每个元素 请你用C或其他语言写出 栈顶指针 数据元素 可有若干个数据项指向下一个元素的指针 进栈算法Statuslpush Lstack base S 栈s 进栈元素e 其它操作同学自己思考 栈原为空 设用S和X分别表示进栈和出栈操作 则对输入序列a b c d和e进行一系列栈操作SSXSXSSXXX之后 得到的输出序列为 栈已经为空 输出序列为 bceda 设栈的初始状态和结束状态均为空栈 用S和X分别表示进栈和出栈操作 SXSX合法吗 SXXS合法吗 合法 不合法 设进栈序列为123 则可能的出栈序列有 123132213231321 设进栈序列为123456 下面出栈序列合法吗 135426435612 合法 不合法 设有一个顺序栈S 元素S1 S2 S3 S4 S5 S6依次进栈 如果6个元素的出栈顺序为S2 S3 S4 S6 S5 S1 则顺序栈的容量至少应为多少 3 栈的应用举例 表达式求值 算符优先法理解表达式 先只考虑算术四则运算 先乘除 后加减从左到右 结合律 先括号内 后括号外一个表达式由下面组成操作数 常量 变量等 操作符 只考虑 左右括号 和表达式结束符 表达式中相继出现算符间的优先关系无非三种 P53表 3X 7 2 算法思路使用两个栈 运算符栈OPTR和运算数及运算结果栈OPND首先置OPND为空栈 置OPTR栈只有一个栈底元素为 依次读入表达式中字符若是操作数 进OPND栈若操作符 和OPTR栈栈顶元素比较优先级当栈顶元素优先级低 则此操作符出OPTR栈 从OPND栈出两个数 进行操作符指定元素 结果进OPND栈 当栈顶元素优先级一样 则OPTR栈栈顶元素出栈 整个表达式求值完毕 当前读入字符为 栈顶元素也为 OPND栈中元素为表达式结果 表达式求值算法 见P53算法运行过程分析 见P54 例 有两个栈s1和s2共享存储空间c 1 m 其中一个栈底设在c 1 处 另一个栈底设在c m 处 试编写算法 对其中任一栈进行push和pop运算 要求只有整个空间占满时才产生上溢 1 m S1栈底 S2栈底 S1栈顶 S2栈顶 s top 0 表示s1栈顶 s top 1 表示s2栈顶栈满条件 s top 1 s top 0 1栈空条件 s top 0 1 s top 1 m constMAX m typedefstruct ElemTypedata MAX inttop 2 DStack Statuspush DStack push Statuspop dStack pop 例二 括号匹配的检验假设在表达式中 或 等为正确的格式 或 或 均为不正确的格式 则检验括号是否匹配的方法可用 期待的急迫程度 这个概念来描述 分析可能出现的不匹配的情况 到来的右括弧并非是所 期待 的 例如 考虑下列括号序列 12345678 到来的是 不速之客 直到结束 也没有到来所 期待 的括弧 算法的设计思想 1 凡出现左括弧 则进栈 2 凡出现右括弧 首先检查栈是否空若栈空 则表明该 右括弧 多余 否则和栈顶元素比较 若相匹配 则 左括弧出栈 否则表明不匹配 3 表达式检验结束时 若栈空 则表明表达式中匹配正确 否则表明 左括弧 有余 Statusmatching string case if NOTStackEmpty S matching 栈与回溯算法 背包问题描述有一个背包 能盛放的物品总重量为S 设有N件物品 其重量分别为w1 w2 wn 希望从N件物品中选择若干件物品 所选物品的重量之和恰能放入该背包 即所选物品的重量之和等于S 案例能放的总重量 S 10各件物体重量 1 8 4 3 5 2 012345 数组中位置可能的解 1 4 3 2 1 4 5 8 2 3 5 2 回溯的设计思想 栈与回溯算法 回溯的设计思想 先将物品排成一列 然后顺序装入背包 选到第j件时 背包未满 但第j 1件时正好 则是一个解太大 则弃之 继续装下一件 如剩余的物品中没有了合适的 说明刚刚装入的物品不合适 将其取出 放在一边 继续从它之后选取 重复 过程 直到求出满足要求的解 或无解 从背包中取出物品再搜索的策略 称为回溯 后进先出 应用栈 include stdafx h include iostream h constN 6 物品数目constS 10 背包能装总重量typedefstruct intweight 每个物品的重量intposition 物品所排的位置 article intw N 1 8 4 3 5 2 intmain inti j 0 intsum S 背包剩余总重量intk 0 栈顶 在顶元素的上面intb 0 栈底 栈空时为k b 0articlestack N 初始化一个栈 do while sum 0 栈与递归算法 用递归算法求解背包问题递归算法的特征为求解规模为N的问题 设法将它分解成较小规模的问题 而这较小规模的问题可以得出需要的解 这较小规模的问题 还能分解成更小的 如此往复 最后能直接得到解 注意以下几点找到继续递归的条件 和递归结束的条件想法将处理对象的规模变小注意理解递归返回后 下一个语句的作用理解递归函数的作用 选择使用递归函数的位置 include stdafx h include iostream h constN 6 constS 10 背包总重量typedefstruct intweight 每个物品的重量intposition 物品所排的位置 article articlestack N 初始化一个栈intw N 1 8 4 3 5 2 voidknap intsum intk intb inti staticintj 0 while sum 0 while if sum 0 输出一组解 for i 0 i b knap sum k b intmain intk 0 栈顶位置intb 0 栈底 栈空时为k b 0knap S k b return0 队列 queue 限定只能在表的一端插入 另一端删除的特殊的线性表 a1 a2 a3 a4 an 1 an 队头front 队尾rear 删除 插入 请你举一个实例 FIFO 队列的主要操作 1 设置一个空队列 2 插入一个新的队尾元素 称为进队 3 删除队头元素 称为出队 4 读取队头元素 队列的ADT P59 队列的顺序存储结构 defineMAXQSIZE100 最大队列长度typedefstruct QElemType base 动态分配存储空间intfront 头指针 若队列不空 指向队列头元素intrear 尾指针 若队列不空 指向 队列尾元素的下一个位置 SqQueue 队列的顺序存储结构 Q rear Q front 0 1 2 3 4 5 J1 J2 J3 Q rear Q front 0 1 2 3 4 5 J3 Q rear Q front 0 1 2 3 4 5 J5 J6 Q rear Q front 0 1 2 3 4 5 空队 front rear 0 入队 填数据尾指针增1 出队 取数据头指针增1 若非空队列头指针在队列的第1位 尾指针在队尾的下一个位置 队未满 却溢出了 另一种情况 循环队列 队列的顺序表示和实现 以存储空间大小为模取余 形成循环队列 rear 空队 front rear 0 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 front J2 J1 J3 front rear 入队 rear front J3 出队 J1 J2 J3 J4 front rear 队满条件 Q rear 1 maxsize Q front与队空条件相同 解决方法 1 尾指针的下一个位置是头指针时是队满 即空一个位置 2 另设标志区别队空和队满 循环队列基本算法描述 StatusInitQueue SqQueue 循环队列基本算法描述 StatusEnQueue SqQueue 循环队列基本算法描述 StatusDeQueue SqQueue typedefstructQNode 结点类型QElemTypedata structQNode next QNode QueuePtr 链队列 链式映象 typedefstruct 链队列类型QueuePtrfront 队头指针QueuePtrrear 队尾指针 LinkQueue a1 an Q frontQ rear Q frontQ rear 空队列 删除 一个元素 添加一个元素 e 队列的链式存储结构 链队列 Q front Q rear 队头 队尾