第3章 栈和队列.ppt

计算机学院 第2章线性表第3章栈和队列第4章串第5章数组和广义表 可表示为 a1 a2 an 线性结构 计算机学院 3 1栈3 2栈的应用举例3 3栈与递归的实现3 4队列 教学内容 计算机学院 第3章栈和队列 掌握栈和队列的特点 并能在相应的应用问题中正确选用熟练掌握栈的两种存储结构的基本操作实现算法 特别应注意栈满和栈空的条件熟练掌握循环队列和链队列的基本操作实现算法 特别注意队满和队空的条件理解递归算法执行过程中栈的状态变化过程 教学目标 计算机学院 栈 Stack 1 定义2 逻辑结构3 存储结构4 运算规则5 实现方式 队列 Queue 1 定义2 逻辑结构3 存储结构4 运算规则5 实现方式 计算机学院 3 1栈 1 定义 只能在表的一端 栈顶 进行插入和删除运算的线性表 计算机学院 只能在栈顶运算 且访问结点时依照后进先出 LIFO 或先进后出 FILO 的原则 4 运算规则 计算机学院 栈是一种特殊的线性表 它只能在表的一端 栈顶 进行插入和删除运算栈与一般线性表的区别 仅在于运算规则不同 进 压入 PUSH 出 弹出 POP 栈与一般线性表的区别 计算机学院 进 压入 PUSH 出 弹出 POP 计算机学院 写入 v i ai读出 x v i 压入 PUSH an 1 弹出 POP x 前提 一定要预设栈顶指针top an 1 顺序栈与顺序表 计算机学院 顺序栈的表示 空栈base top是栈空标志stacksize 4 top指示真正的栈顶元素之上的下标地址 栈满时的处理方法 1 报错 返回操作系统 2 分配更大的空间 作为栈的存储空间 将原栈的内容移入新栈 计算机学院 defineSTACK INIT SIZE100typedefstruct SElemType base SElemType top intstacksize SqStack 顺序栈的表示 存储空间分配增量 STACKINCREMENT 存储空间初始分配量 计算机学院 构造一个空栈步骤 1 分配空间并检查空间是否分配失败 若失败则返回错误 顺序栈初始化 s 2 设置栈底和栈顶指针S top S base 3 设置栈大小 计算机学院 StatusInitStack SqStack 顺序栈初始化 计算机学院 判断顺序栈是否为空 StatusStackEmpty SqStackS if S top S base returnTRUE elsereturnFALSE 计算机学院 求顺序栈的长度 intStackLength SqStackS returnS top S base 计算机学院 StatusClearStack SqStackS if S base S top S base returnOK 清空顺序栈 计算机学院 StatusDestroyStack SqStack 销毁顺序栈 计算机学院 1 判断是否栈满 若满则出错 2 元素e压入栈顶 3 栈顶指针加1 顺序栈进栈 StatusPush SqStack S top e top 计算机学院 StatusPush SqStack 计算机学院 1 判断是否栈空 若空则出错 2 获取栈顶元素e 3 栈顶指针减1 顺序栈出栈 StatusPop SqStack top e S top 计算机学院 判断是否空栈 若空则返回错误否则通过栈顶指针获取栈顶元素 取顺序栈栈顶元素 StatusGetTop SqStackS SElemType e S top 计算机学院 435612中到了12顺序不能实现 135426可以实现 1 如果一个栈的输入序列为123456 能否得到435612和135426的出栈序列 练习 计算机学院 练习 i n i n i 1 不确定 2 若已知一个栈的入栈序列是1 2 3 n 其输出序列为p1 p2 p3 pn 若p1 n 则pi为 计算机学院 练习 top不变 top 0 top top D 3 在一个具有n个单元的顺序栈中 假设以地址高端作为栈底 以top作为栈顶指针 则当作进栈处理时 top的变化为 计算机学院 考研试题 双栈共享一个栈空间 优点 互相调剂 灵活性强 减少溢出机会 计算机学院 将编号为0和1的两个栈存放于一个数组空间V m 中 栈底分别处于数组的两端 当第0号栈的栈顶指针top 0 等于 1时该栈为空 当第1号栈的栈顶指针top 1 等于m时该栈为空 两个栈均从两端向中间增长 如下图所示 考研试题 计算机学院 typedefstruct inttop 2 bot 2 栈顶和栈底指针SElemType V 栈数组intm 栈最大可容纳元素个数 DblStack 数据结构定义如下 考研试题 计算机学院 voidDblpush DblStack s SElemTypex inti 把x插入到栈i的栈intDblpop DblStack s inti SElemType x 退掉位于栈i栈顶的元素intIsEmpty DblStacks inti 判栈i空否 空返回1 否则返回0intIsFull DblStacks 判栈满否 满返回1 否则返回0 试编写判断栈空 栈满 进栈和出栈四个算法的函数 函数定义方式如下 考研试题 计算机学院 栈空 top i bot i i表示栈的编号栈满 top 0 1 top 1 或top 1 1 top 0 提示 计算机学院 链栈的表示 运算是受限的单链表 只能在链表头部进行操作 故没有必要附加头结点 栈顶指针就是链表的头指针 typedefstructSnode SElemTypedata structSnode next Snode LinkStack LinkStackS 计算机学院 链栈的初始化 voidInitStack LinkStack 计算机学院 判断链栈是否为空 StatusStackEmpty LinkStackS if S NULL returnTRUE elsereturnFALSE 计算机学院 链栈进栈 StatusPush LinkStack 计算机学院 链栈进栈 StatusPush LinkStack e 计算机学院 链栈进栈 StatusPush LinkStack e 计算机学院 链栈进栈 StatusPush LinkStack e S 计算机学院 链栈出栈 Statuspop LinkStack e A 计算机学院 链栈出栈 Statuspop LinkStack e A p 计算机学院 链栈出栈 Statuspop LinkStack e A p S 计算机学院 链栈出栈 Statuspop LinkStack e A S 计算机学院 取链栈栈顶元素 SElemTypeGetTop LinkStackS if StackEmpty S exit Stackisempty elsereturnS data 计算机学院 3 2栈的应用举例 例1 数制转换 十转N 用栈暂存低位值例2 括号匹配的检验用栈暂存左括号例3 行编辑程序用栈暂存字符例4 迷宫求解用栈实现递归调用例5 表达式求值用栈暂存运算符 简化了程序设计的问题 计算机学院 迷宫求解 计算机学院 从入口出发 按某一方向向未走过的前方探索若能走通 则到达新点 否则试探下一方向 若所有的方向均没有通路 则沿原路返回前一点 换下一个方向再继续试探直到所有可能的通路都探索到 或找到一条通路 或无路可走又返回到入口点 求解思想 回溯法 迷宫求解 计算机学院 需要解决的问题 1 表示迷宫的数据结构2 试探方向3 栈的设计4 防止重复到达某点 避免发生死循环 迷宫求解 计算机学院 1 表示迷宫的数据结构表示一个m行n列迷宫 用maze m n 表示 0 i m 0 j nmaze i j 0通路maze i j 1不通改进 用maze m 2 n 2 表示且maze i j 1 i 0或m 1 j 0或n 1入口坐标为 1 1 出口坐标为 m n 迷宫求解 计算机学院 计算机学院 迷宫的定义 definem8 迷宫的实际行 definen8 迷宫的实际列 intmaze m 2 n 2 2 试探方向表示位置的类型PosType定义如下 typedefstruct intx y PosType 迷宫求解 计算机学院 试探顺序规定为 从正东沿顺时针方向 与点 x y 相邻的4个点及坐标 x y x y 1 x y 1 x 1 y x 1 y 迷宫求解 计算机学院 3 栈的设计栈中每个元素的组成 通道块在路径上的序号坐标位置前进方向 东为1 南为2 西为3 北为4 栈元素的类型定义 typedefstruct intord PosTypeseat intdi SElemType 迷宫求解 计算机学院 4 防止重复到达某点走过不通之处要加以标记 MarkPrint操作 迷宫求解算法思想及算法参见P51 迷宫求解 计算机学院 表达式求值 算术四则运算规则 1 先乘除 后加减 2 从左算到右 3 先括号内 后括号外 计算机学院 表达式 计算机学院 x x x 表3 1算符间的优先关系 计算机学院 1 2 OPND置空 入OPTR 依次读入字符ch 直到表达式求值完毕 OPTR的栈顶元素和当前读入的字符均为 if ch是操作数 则ch进OPND栈 else比较OPTR栈顶元素和ch的优先级 case 运算符ch进OPTR栈 case 脱括号 弹出左括号 case 栈顶运算符退栈 计算 结果进OPND栈 算符优先算法 设定两栈 OPND 操作数或运算结果OPTR 运算符 计算机学院 OperandTypeEvaluateExpression InitStack OPTR Push OPTR InitStack OPND c getchar while c GetTop OPTR ch if In c OP Push OPND c c getchar 非运算符 则进栈elseswitch Precede GetTop OPTR c case 栈顶元素优先权低Push OPTR c c getchar break case 脱括号Pop OPTR x c getchar break 计算机学院 case 退栈 并将运算结果入栈Pop OPTR theta Pop OPND b Pop OPND a Push OPND Operate a theta b break switch whilereturnGetTop OPND 计算机学院 计算机学院 3 3栈与递归的实现 递归的定义若一个对象部分地包含它自己 或用它自己给自己定义 则称这个对象是递归的 若一个过程直接地或间接地调用自己 则称这个过程是递归的过程 计算机学院 栈 计算机学院 以下三种情况常常用到递归方法递归定义的数学函数具有递归特性的数据结构可递归求解的问题 计算机学院 1 递归定义的数学函数 阶乘函数 2阶Fibonaci数列 计算机学院 树 2 具有递归特性的数据结构 Root Lchild Rchild 广义表 A a A 3 可递归求解的问题 迷宫问题Hanoi塔问题 计算机学院 分治法 对于一个较为复杂的问题 能够分解成几个相对简单的且解法相同或类似的子问题来求解 1 能将一个问题转变成一个新问题 而新问题与原问题的解法相同或类同 不同的仅是处理的对象 且这些处理对象是变化有规律的2 可以通过上述转化而使问题简化3 必须有一个明确的递归出口 或称递归的边界 用分治法求解递归问题 必备的三个条件 计算机学院 分治法求解递归问题算法的一般形式 voidp 参数表 if 递归结束条件 可直接求解步骤 基本项elsep 较小的参数 归纳项 longFactorial longn if n 0 return1 基本项elsereturnn Factorial n 1 归纳项 计算机学院 返回2参数2计算2 fact 1 返回1参数1计算1 fact 0 返回1参数0直接定值 1 if n 0 return1 elsereturnn Factorial n 1 求解阶乘n 的过程 主程序main fact 4 返回6参数3计算3 fact 2 计算机学院 设有一个递归算法如下 intX intn if n 3 return1 elsereturnX n 2 X n 4 1 则计算X X 8 时需要计算X函数次 D 练习 A 8B 9C 16D 18 计算机学院 规则 1 每次只能移动一个圆盘 2 圆盘可以插在A B和C中的任一塔座上 3 任何时刻不可将较大圆盘压在较小圆盘之上 Hanoi塔问题 计算机学院 Hanoi塔问题 n 1 则直接从A移到C 否则 1 用C柱做过渡 将A的 n 1 个移到B 2 将A最后一个直接移到C 3 用A做过渡 将B的 n 1 个移到C 计算机学院 includeintc 0 voidmove charx intn charz cout c n x z endl voidHanoi intn charx chary charz if n 1 move x 1 z else Hanoi n 1 x z y move x n z Hanoi n 1 y x z voidmain Hanoi 3 a b c 跟踪程序 给出下列程序的运行结果 以深刻地理解递归的调用和返回过程 计算机学院 函数调用过程 计算机学院 层次 递归工作栈 工作记录 实在参数 局部变量 返回地址 递归函数调用的实现 计算机学院 程序的具体执行过程参见 Hanoi塔执行过程 ppt 计算机学院 优点 结构清晰 程序易读缺点 每次调用要生成工作记录 保存状态信息 入栈 返回时要出栈 恢复状态信息 时间开销大 递归的优缺点 递归 非递归 计算机学院 队列是一种先进先出 FIFO 的线性表 它只允许在表的一端进行插入 而在另一端删除元素 a1 a2 a3 an 入队列 队头 队尾 队列 计算机学院 队列是一种先进先出 FIFO 的线性表 它只允许在表的一端进行插入 而在另一端删除元素 a1 a2 a3 an 队头 队尾 队列 出队列 计算机学院 队列是一种先进先出 FIFO 的线性表 它只允许在表的一端进行插入 而在另一端删除元素 a1 a2 a3 an 队尾 队列 出队列 计算机学院 队列是一种先进先出 FIFO 的线性表 它只允许在表的一端进行插入 而在另一端删除元素 a1 a2 a3 an 队尾 队列 出队列 计算机学院 设栈S和队列Q的初始状态为空 元素e1 e2 e3 e4 e5和e6依次通过S 一个元素出栈后即进入Q 若6个元素出队的序列是e2 e4 e3 e6 e5和e1 则栈S的容量至少应该是 A 2 B 3 C 4 D 6 练习 B 计算机学院 a1 a2 a3 an 插入 删除 插入 删除 输出受限的双端队列 端1 端2 双端队列 计算机学院 a1 a2 a3 an 插入 删除 插入 删除 输出受限的双端队列 输入受限的双端队列 端1 端2 双端队列 计算机学院 数据对象 数据关系 基本操作 1 InitQueue Q 构造空队列 2 DestroyQueue Q 销毁队列 3 ClearQueue S 清空队列 4 QueueEmpty S 判空 空 TRUE ADTQueue 队列的抽象数据类型 计算机学院 5 QueueLength Q 取队列长度 6 GetHead Q e 取队头元素 7 EnQueue Q e 入队列 8 DeQueue Q e 出队列 9 QueueTraverse Q visit 遍历 ADTQueue 队列的抽象数据类型 计算机学院 链队列 计算机学院 typedefstructQNode QElemTypedata structQnode next Qnode QueuePtr typedefstruct QueuePtrfront 队头指针QueuePtrrear 队尾指针 LinkQueue 链队列 计算机学院 a 空队列 b 元素x入队列 d 元素x出队列 c 元素y入队列 链队列 计算机学院 StatusInitQueue LinkQueue 链队列初始化 计算机学院 StatusDestroyQueue LinkQueue 销毁链队列 计算机学院 StatusQueueEmpty LinkQueueQ return Q front Q rear 判断链队列是否为空 计算机学院 StatusGetHead LinkQueueQ QElemType 求链队列的队头元素 计算机学院 StatusEnQueue LinkQueue 链队列入队 p 计算机学院 StatusDeQueue LinkQueue 链队列出队 p 计算机学院 defineM100 最大队列长度Typedefstruct QElemType base 初始化的动态分配存储空间intfront 头指针intrear 尾指针 SqQueue 队列的顺序表示 用一维数组base M 计算机学院 队列的顺序表示 用一维数组base M front rear 0 空队标志 front rear入队 base rear x 出队 x base front 计算机学院 存在的问题 设数组大小为M front 0rear M 1时再入队 真溢出 front 0rear M 1时再入队 假溢出 计算机学院 解决的方法 循环队列 base 0 接在base M 1 之后若rear 1 M则令rear 0 实现 利用 模 运算入队 base rear x rear rear 1 M 出队 x base front front front 1 M 计算机学院 队空 front rear队满 front rear 解决方案 1 另外设一个标志以区别队空 队满2 少用一个元素空间 队空 front rear队满 rear 1 M front rear front 计算机学院 循环队列 defineMAXQSIZE100 最大队列长度Typedefstruct QElemType base 初始化的动态分配存储空间intfront 头指针intrear 尾指针 SqQueue 计算机学院 StatusInitQueue SqQueue 循环队列初始化 计算机学院 StatusQueueEmpty SqQueueQ return Q front Q rear 判断循环队列是否为空 计算机学院 求循环队列的长度 intQueueLength SqQueueQ return Q rear Q front MAXQSIZE MAXQSIZE 计算机学院 StatusGetHead SqQueueQ QElemType 取循环队列的队头元素 计算机学院 StatusEnQueue SqQueue 循环队列入队 计算机学院 StatusDeQueue LinkQueue 循环队列出队 计算机学院 队列应用举例 例1 汽车加油站随着城市里汽车数量的急速增长 汽车加油站也渐渐多了起来 通常汽车加油站的结构基本上是 入口和出口为单行道 加油车道可能有若干条 每辆车加油都要经过三段路程 第一段是在入口处排队等候进入加油车道 第二段是在加油车道排队等候加油 第三段是进入出口处排队等候离开 实际上 这三段都是队列结构 若用算法模拟这个过程 就需要设置加油车道数加2个队列 计算机学院 例2 模拟打印机缓冲区在主机将数据输出到打印机时 会出现主机速度与打印机的打印速度不匹配的问题 这时主机就要停下来等待打印机 显然 这样会降低主机的使用效率 为此人们设想了一种办法 为打印机设置一个打印数据缓冲区 当主机需要打印数据时 先将数据依次写入这个缓冲区 写满后主机转去做其他的事情 而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印 这样做即保证了打印数据的正确性 又提高了主机的使用效率 由此可见 打印机缓冲区实际上就是一个队列结构 队列应用举例 计算机学院 例3 CPU分时系统在一个带有多个终端的计算机系统中 同时有多个用户需要使用CPU运行各自的应用程序 它们分别通过各自的终端向操作系统提出使用CPU的请求 操作系统通常按照每个请求在时间上的先后顺序 将它们排成一个队列 每次把CPU分配给当前队首的请求用户 即将该用户的应用程序投入运行 当该程序运行完毕或用完规定的时间片后 操作系统再将CPU分配给新的队首请求用户 这样即可以满足每个用户的请求 又可以使CPU正常工作 队列应用举例 计算机学