053栈应用+队列概论.ppt

* 迷宫求解 迷宫求解一般采用“穷举法” 逐一沿顺时针方向查找相邻块（一共四块－东(右)、南(下)，西(左)、北(上)）是否可通，即该相邻块既是通道块，且不在当前路径上 用一个栈来记录已走过的路径 3.2 栈的应用 * 迷宫求解 举例 3.2 栈的应用 # # # # # # # # # # # # # * 迷宫求解 求解算法 设定当前位置为入口位置 　do {若当前位置可通，则 { 　将该位置插入栈顶(Push)；若该位置是出口，则结束 　否则切换当前位置的东邻方块为当前位置； } 否则 { 　若栈不空则｛ 　 如果栈顶位置的四周均不可通,则删除栈顶位置(Pop) 　并重新测试新的栈顶位置 　　如果找到栈顶位置的下一方向未经探索，则将该方向 　　方块设为当前位置 } } }while(栈不空)；找不到路径 3.2 栈的应用 * 表达式求值 模拟表达式的运算过程，利用堆栈实现运算的优先级和运算顺序 表达式的输入是一个字符串，要从中分解出操作数和操作符 难点1：识别操作符的优先级，括号 乘除 加减 难点2：从字符串中识别一个浮点数 3.2 栈的应用 * 第3章总结 堆栈与队列都是在线性表的基础上，加入特定的操作规则 栈是限定操作的线性表，特点先进后出，常用数组实现 堆栈包括top栈顶、base栈底，插入、删除、访问都在top进行 插入就是进栈push，top+1 删除就是出栈pop，top-1 访问就是取栈顶元素GetTop top=base栈空，base=NULL栈不存在，topstacksize时，栈满 队列是只允许在表的一端进行插入，在另一端删除元素，特点是先进先出 队列包括队头front和队尾rear，队头只允许删除和访问，队尾只允许插入 插入就是进队，rear+1 删除就是出队，front+1 链表队列，无队列满的问题，动态分配空间 循环队列，通过取模运算解决顺序队列的问题，只浪费1个空间 OS * 数据结构 深圳大学 计算机与软件学院 白鉴聪 * 第三章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列 3.5 离散事件模拟 * 上节小结 栈是限定操作的性表，特点先进后出 堆栈包括栈空间elem、top栈顶、base栈底 插入、删除、取栈顶都在top进行 插入是把e进栈push(e)，elem[top]=e，top++ 删除是弹出栈顶，出栈pop()，e=elem[top-1],top-- 取栈顶是读栈顶元素GetTop()，e=elem[top-1], top不变 top=base或top-next = NULL表示栈空 base=NULL栈不存在 topstacksize时，栈满 链栈，采用头插法，top是一个指针，指向首结点 * 已知堆栈SS从栈底到栈顶的元素排列为：A、B、C、D，堆栈操作包括以下函数，参数CS是栈对象，ct是元素变量。 Push(Stack CS, char ct)，将元素ct压入堆栈CS Pop(Stack CS)，将堆栈CS的栈顶元素弹出 GetTop(Stack CS, char ct)，将栈顶元素放入到变量ct中 在执行以下函数后，请按栈底到栈顶的顺序写出堆栈的元素排列，并写出变量CA的值 POP (SS)；D Push(SS, E’)；ABCE POP(SS)；ABC POP(SS)；AB GetTop(SS, CA) ；B Push(SS, ‘F’)；AF 练习 * 设将整数1,2,3,4依次进栈，可将出入栈操作按任何次序排列，请回答下述问题： 若出入栈次序为Push(1)，Pop()，Push(2)，Push(3)，Pop()，Pop()，Push(4)，Pop()，则出栈的数字序列是什么？ 1 3 2 4 能否得到出栈结果1423和1432？并说明为什么不能得到或者如何得到。 NO YES 请分析1,2,3,4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 1234 1243 1432 1324 1342 2134 2143 2314 2341 2431 3214 3241 3421 4321 共14种 练习 * 数制转换 将十进制转换为其它进制(d)，其原理为： N = (N/d)*d + N mod d 例如：（1348)10 = (2504)8 ，其运算过程如下： N N /8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 3.2 栈的应用 * 数制转换 实现函数 voi