《队列栈的操作》PPT课件.ppt

Page1 2020 3 26 学习目标掌握栈和队列这两种抽象数据类型的特点 并能在相应的应用问题中正确选用它们 熟练掌握栈类型的两种实现方法 熟练掌握循环队列和链队列的基本操作实现算法 理解递归算法执行过程中栈的状态变化过程 重点和难点栈和队列是在程序设计中被广泛使用的两种线性数据结构 本章的学习重点是掌握这两种结构的特点 以便能在应用问题中正确使用 知识点顺序栈 链栈 循环队列 链队列 第三章栈和队列 Page2 2020 3 26 栈和队列是在程序设计中被广泛使用的两种线性数据结构 与线性表相比 它们的插入和删除操作受更多的约束和限定 故又称为限定性的线性表结构 线性表允许在表内任一位置进行插入和删除 栈只允许在表尾一端进行插入和删除 队列只允许在表尾一端进行插入 在表头一端进行删除 Page3 2020 3 26 3 1栈 栈限定只能在表的一端进行插入和删除操作的线性表 栈顶 top 允许插入和删除的一端 栈底 bottom 不允许插入和删除的另一端 空栈 不含元素的空表 特点先进后出 FILO 后进先出 LIFO Page4 2020 3 26 栈的抽象数据类型定义 ADTStack 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 基本操作 InitStack S 操作结果 构造一个空栈S DestroyStack S 初始条件 栈S已存在 操作结果 栈S被销毁 Page5 2020 3 26 ClearStack S 初始条件 栈S已存在 操作结果 将S清为空栈StackEmpty S 初始条件 栈S已存在 操作结果 若栈S为空栈 则返回TRUE 否则返回FALSE StackLength S 初始条件 栈S已存在 操作结果 返回栈S中元素个数 即栈的长度 Page6 2020 3 26 GetTop S e 初始条件 栈S已存在且非空 操作结果 用e返回S的栈顶元素 Push S e 初始条件 栈S已存在 操作结果 插入元素e为新的栈顶元素 Pop S e 初始条件 栈S已存在且非空 操作结果 删除S的栈顶元素 并用e返回其值 Page7 2020 3 26 StackTraverse S visit 初始条件 栈S已存在且非空 visit 为元素的访问函数 操作结果 从栈底到栈顶依次对S的每个元素调用函数visit 一旦visit 失败 则操作失败 ADTStack Page8 2020 3 26 栈的顺序存储 顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 结构定义 defineSTACK INIT SIZE100 存储空间初始分配量 defineSTACKINCREMENT10 存储空间分配增量typedefstruct SElemType base 存储空间基址SElemType top 栈顶指针intstacksize 当前已分配的存储空间 以元素位单位 SqStack Page9 2020 3 26 base 栈空 栈顶指针top 指向实际栈顶后的空位置 top base 进栈 A 出栈 栈满 B C D E F 设数组大小为Mtop base 栈空 此时出栈 则下溢 underflow Top base 6 栈满 此时入栈 则上溢 overflow 栈空 top Page10 2020 3 26 基本操作接口 函数声明 voidInitStack SqStack 若栈不空 则删除S的栈顶元素 用e返回其值 并返回TRUE 否则返回FALSE voidStackTraverse SqStackS Status visit 依次对S的每个元素调用函数visit 一旦visit 失败 操作失败 Page11 2020 3 26 基本操作的算法描述 StatusInitStack SqStack InitStack Page12 2020 3 26 StatusGetTop SqStackS SElemType GetTop Page13 2020 3 26 StatusPush SqStack Push Page14 2020 3 26 StatusPop Stack Pop Page15 2020 3 26 链栈 栈的链式存储结构 Page16 2020 3 26 入栈算法 出栈算法 Page17 2020 3 26 3 4队列 队列只允许在一端进行插入而在另一端进行删除的线性表 队尾 允许插入的一端 队头 允许删除的一端 特点 先进先出 FIFO Page18 2020 3 26 队列的抽象数据类型定义 ADTQueue 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 基本操作 InitQueue Q 操作结果 构造一个空队列Q DestroyQueue Q 初始条件 队列Q已存在 操作结果 队列Q被销毁 不再存在 Page19 2020 3 26 ClearQueue Q 初始条件 队列Q已存在 操作结果 将Q清为空队列 QueueEmpty Q 初始条件 队列Q已存在 操作结果 若Q为空队列 则返回TRUE 否则返回FALSE QueueLength Q 初始条件 队列Q已存在 操作结果 返回Q的元素个数 即队列的长度 Page20 2020 3 26 GetHead Q e 初始条件 Q为非空队列 操作结果 用e返回Q的队头元素 EnQueue Q e 初始条件 队列Q已存在 操作结果 插入元素e为Q的新的队尾元素 DeQueue Q e 初始条件 Q为非空队列 操作结果 删除Q的队头元素 并用e返回其值 Page21 2020 3 26 队列的顺序存储结构 用一组地址连续的存储单元依次存放从队头到队尾的元素 frontrear 队空 front J1 J2 J3入队 J1 J2 J3 rear J4 J5 J6入队 J4 J5 J6 front 设两个指针front rear 约定 rear指示队尾元素 front指示队头元素前一位置初值front rear 0 空队列条件 front rear入队列 sq rear x 出队列 x sq front J1 J2 J3出队 J1 J2 J3 存在问题 设数组大小为M 则 当front 0 rear M 1时 再有元素入队发生溢出 真溢出 当front 0 rear M 1时 再有元素入队发生溢出 假溢出 Page22 2020 3 26 解决方案队首固定 每次出队剩余元素向下移动 浪费时间 循环队列基本思想 把队列设想成环形 让sq 0 接在sq M 1 之后 Page23 2020 3 26 rear 初始状态 解决方案 1 另外设一个标志以区别队空 队满2 少用一个元素空间 队空 front rear队满 rear 1 M front 队空 front rear 队满 front rear Page24 2020 3 26 2011年考研真题 Page25 2020 3 26 循环队列的结构定义 defineMAXQSIZE100 最大队列长度typedefstruct QElemType base 初始化的动态分配存储空间intrear 队尾指针 指向队尾元素intfront 队头指针 指向队头元素的前一个位置 SqQueue Page26 2020 3 26 rear 队首元素表示 出队front变化 入队rear变化 Q base Q front Q front Q front 1 maxsize Q rear Q rear 1 maxsize 队满条件 队空条件 Q rear 1 maxsize Q frontQ rear Q front Page27 2020 3 26 循环队列的基本操作的算法描述 StatusInitQueue SqQueue Q 构造一个空队列QQ base QElemType malloc MAXQSIZE sizeof QElemType 为循环队列分配存储空间if Q base exit OVERFLOW 存储分配失败Q front Q rear 0 returnOK InitQueue Page28 2020 3 26 intQueueLength SqQueueQ 返回队列Q中元素个数 即队列的长度return Q rear Q front MAXQSIZE MAXQSIZE Page29 2020 3 26 StatusEnQueue SqQueue Page30 2020 3 26 StatusDeQueue SqQueue Page31 2020 3 26 用链表表示的队列 结点定义typedefstructQNode QelemTypedata structQNode next QNode QueuePtr typedefstruct QueuePtr front 队头指针QueuePtr rear 队尾指针 LinkQueue 链队列 队列的链式表示和实现 Page32 2020 3 26 Page33 2020 3 26 StatusInitQueue LinkQueue 链队列基本操作的算法描述 部分 Page34 2020 3 26 StatusEnQueue LinkQueue 移动队尾指针 Page35 2020 3 26 StatusDeQueue LinkQueue DeQueue Page36 2020 3 26 本章小结 栈和队列都属线性结构 因此他们的存储结构和线性表非常类似 同时由于他们的基本操作要比线性表简单得多 因此它们在相应的存储结构中实现的算法都比较简单 相信对大家来说都不是难点 这一章的重点则在于栈和队列的应用 通过本章所举的例子学习分析应用问题的特点 在算法中适时应用栈和队列 Page37 2020 3 26 基础知识题 进栈序列为123 则可能得到的出栈序列是什么 如果进栈序列为123456 则能否得到435612和135426的出栈序列 并请说明为什么不能得到 简述栈和线性表的差别 简述队列和栈这两种数据类型的相同点和差异处 Page38 2020 3 26 写出下列程序段的输出结果 栈的元素类型SElemType为char voidmain StackS charx y InitStack S x c y k Push S x Push S a Push S y Pop S x Push S t Push S x Pop S x Push S s while StackEmpty S Pop S y printf y printf x Page39 2020 3 26 简述以下算法的功能 栈的元素类型SElemType为int statusalgo1 StackS inti n A 255 n 0 while StackEmpty S n Pop S A n for i 1 i n i Push S A i statusalgo2 StackS inte StackT intd InitStack T while StackEmpty S Pop S d if d e Push T d while StackEmpty T Pop T d Push S d Page40 2020 3 26 应用一 数制转换对于输入的任意一个非负十进制整数 打印输出与其等值的八进制数 例把十进制数159转换成八进制数 3 2栈的应用举例 Page41 2020 3 26 voidconversion InitStack S 构造空栈scanf d N 输入一个十进制数while N Push S N 8 余数 入栈N N 8 非零 商 继续运算 whilewhile StackEmpty s 和 求余 所得相逆的顺序输出八进制的各位数Pop S e printf d e while conversion 算法3 1对于输入的任意一个非负十进制整数 打印输出与其等值的八进制数 Page42 2020 3 26 算法思想 读入字符串 去掉空格 原串 压入栈 原串字符与出栈字符依次比较 若不等 非回文 若直到栈空都相等 回文 应用二 回文游戏 顺读与逆读字符串一样 不含空格 Page43 2020 3 26 表达式的组成操作数 operand 常数 变量 运算符 operator 算术运算符 关系运算符和逻辑运算符 界限符 delimiter 左右括弧和表达式结束符 算术运算的规则先乘除后加减先左后右先括弧内后括弧外例如 4 2 3 10 5 4 6 10 5 10 10 5 10 2 8 应用三 表达式求值 Page44 2020 3 26 算法的思想 设置两个工作栈运算符栈OPTR 运算符栈的栈底为表达式的起始符 操作数栈OPND 操作数栈为空栈 依次读入表达式中的每个字符若是操作数则进OPND栈 若是运算符 则和OPTR中的栈顶元素做比较再操作 若运算符优先级高于OPTR中的栈顶元素 则运算符入栈 若运算符优先级低于OPTR中的栈顶元素 则从OPND栈顶弹出两个操作数 与OPTR中的栈顶元素做运算 并将运算结果入OPND 若运算符优先级等于OPTR中的栈顶元素 则将OPTR中的栈顶元素出栈 直至表达式求置完毕 Page45 2020 3 26 计算2 4 3 6 Page46 2020 3 26 算法3 4算术表达式求值的算符优先算法 OperandTypeEvaluateExpression 设OPTR和OPND分别为运算符栈和运算数栈 OP为运算符集合 InitStack OPTR Push OPTR InitStack OPND c getchar while c GetTop OPTR if In c OP Push OPND c c getchar 是操作数elseswitch Precede GetTop OPTR c case 栈顶元素优先权高 退栈并将运算结果入栈Pop OPTR theta Pop OPND b Pop OPND a Push OPND Operate a theta b break switch whilereturnGetTop OPND EvaluateExpression Page47 2020 3 26 当一个函数在运行期间调用另一个函数时 在运行该被调用函数之前 需先完成三件事 将所有的实在参数 返回地址等信息传递给被调用函数保存 为被调用函数的局部变量分配存储区 将控制转移到被调用函数的入口 而从被调用函数返回调用函数之前 应该完成 保存被调函数的计算结果 释放被调函数的数据区 依照被调函数保存的返回地址将控制转移到调用函数 由于函数的运行规则是