数据结构03-栈 (2)

《数据结构03-栈 (2)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构DataStructures安海忠博士中国地质大学（北京）人文经管学院院长教授博士生导师国土资源部资源环境承载力评价重点实验室主任电话：01082323793（办），13810910701电邮：ahz369@163.com教学内容第一章绪论第二章线性表第三章栈和队列第四章串第六章树和二叉树第七章图第九章查找第十章内部排序第三章栈和队列3.1栈栈的定义、实现和应用3.2队列队列的定义、实现和应用3.1栈(stack)栈的定义3.1栈(stack)栈的定义栈(Stack)只允许在一端插入和删除的线性表

2、允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)后进先出(LIFO)出/退栈进/压栈a0an-1an-2topbottom3.1栈(stack)实例列车调度若进站的4辆列车顺序如上所述,那么是否能够得到4312,3241,1423和1342的出站序列子弹夹后来者居上3.1栈(stack)实例进栈示例3.1栈(stack)实例出栈示例3.1栈(stack)基本运算3.1栈(stack)举例回文游戏：顺读与逆读字符串一样（不含空格）用栈来解决回文游戏：每个同学拿出办法（写出步骤）判断是

3、否是回文，如“madam”3.1栈(stack)举例回文游戏：顺读与逆读字符串一样（不含空格）用栈来解决回文游戏：每个同学拿出办法判断是否是回文，如“madam”第一步？读入字符串第二步？去掉空格第三步？压入栈第四步？原串字符与出栈字符依次比较，若不等，则不是回文；若相等，则是回文madam栈顶3.1栈(stack)栈的存储结构用数组实现栈：顺序栈3.1栈(stack)栈的存储结构用数组实现栈结构定义3.1栈(stack)算法入栈算法出栈算法用数组实现栈：顺序栈3.1栈(stack)顺序栈的基本运算3.1

4、栈(stack)顺序栈的基本运算3.1栈(stack)顺序栈的基本运算3.1栈(stack)顺序栈的基本运算3.1栈(stack)顺序栈的基本运算3.1栈(stack)栈的存储结构用指针实现栈：链栈链栈的结构类型定义3.1栈(stack)栈的存储结构用指针实现的链栈定义3.1栈(stack)算法入栈算法出栈算法3.1栈(stack)应用(1)算术表达式求值3.1栈(stack)应用(1)算术表达式求值3.1栈(stack)应用(1)算术表达式求值3.1栈(stack)应用(1)算术表达式求值3.1栈(st

5、ack)应用(2)迷宫求解００01234567890123456789入口出口穷举求解从入口出发，顺着某一方向向前探索，若能走通，则继续往前走，否则原路返回，换一个方向再继续探索，直至所有可能的通路都探索到为止用栈来求解3.1栈(stack)应用(2)迷宫求解００01234567890123456789入口出口图中是方块或为通道（空白），或为墙（阴影）所求路径必须是简单路径，不能重复同一通道块。3.1栈(stack)应用(2)迷宫求解基本思想若当前位置“可通”，则纳入“当前路径”，并继续“下一位置”探索，

6、即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周方块均“不可通”，则从“当前路径”上删除该通道块下一位置：当前位置四周四个方向（东南西北）上相邻的方块(2)迷宫求解：流程图当前位置(初值）←入口位置开始若当前位置可通若当前位置为出口位置结束是否当前位置←东邻方块否栈顶←当前位置若栈不空且栈顶位置尚有其他方向未探索是否当前位置←下一相邻方块若栈不空且栈顶位置四周都不通否删去栈顶位置是

7、若栈不空重设栈顶位置是否是作业：亚克星上的军队亚克星上住着许多神奇的生物。其中有聪慧的人族、优雅的精灵、彪悍的野蛮猪、粗鲁的首任驻….有一天，住在湛蓝球上的恶魔们突破空间的封锁入侵这个美丽的星球。为了保卫共同的家园，亚克星各族不得不摒弃前嫌，组成联盟。为了更有利的反击恶魔们的入侵，他们建立了统一的军事指挥中心。在前期，指挥中心会不停的发布军队调动命令，可是，麻烦来了。为了更好的做出决策，指挥中心必须迅速了解己方的各地区的军事力量详情。你能否帮帮这些可怜的种族呢？实验任务作业：亚克星上的军队每个地区有一个编

8、号（从1到N），如果一个地区有军队的话，这些军队将组成一个军团。指挥中心将发布命令如下：Uab:将b地区军团的调到a地区，从而组成一个新的军团。为了便于管理，每次新加入的军队将按顺序加入到a军团后面。数据保证a与b不相同Iax:将一支人数为x的军队调到a地区。为了便于管理，每次新加入的军队将加入到a军团前面Dax:将a地区中军队人数为x的调走。若不存在，则不执行Qa：询问a地区的具体军事信息（即按顺序输出该军团中每个军队的人数