收藏 分销(赏)

第3章-栈与队列-数据结构案例.ppt

上传人:知****运 文档编号:14665123 上传时间:2026-10-27 格式:PPT 页数:25 大小:1.67MB 下载积分:10 金币
下载 相关
第3章-栈与队列-数据结构案例.ppt_第1页
第1页 / 共25页
第3章-栈与队列-数据结构案例.ppt_第2页
第2页 / 共25页


点击查看更多>>
资源描述
单击此处编辑母版文本样式,第二级,第三级,第四级,Page,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,单击此处编辑母版标题样式,第,3,章 栈和队列,数据结构案例教程,Page,2,案例提出,迷宫问题,迷宫问题是取自心理学的一个经典实验。在该实验中,把一只老鼠从一个无顶大盒子的门中放入,在盒子中设置了许多墙,对行进方向形成了多处阻挡。盒子仅有一个出口,在出口处放置以块奶酪,吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验,一直到老鼠从入口走到出口,而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。,设计一个计算机程序对任意设定的矩形迷宫如下图所示,求出一条从入口到出口的通路,或得出没有通路的结论。,Page,3,3.2,知识点学习,3.2.1,栈,栈是一种特殊的线性表,用途十分广泛。将递归算法转换成非递归算法时常常会用到栈,实现二叉树的算法中也会使用栈。,栈是一种只能在一端进行插入或删除的线性表。表中允许进行插入、删除操作的一端称为栈顶(,top,),表的另一端称为栈底(,bottom,)。当栈中没有数据元素时,称为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。,Page,4,入栈,Page,6,3.2.1.3 栈的链式存储结构及其基本运算的实现,Page,7,(链栈中数据结点的类型,LinkStack,定义如下:,typedef int ElemType;,typedef struct linknode,ElemType data;/,数据域,struct linknode*next;/,指针域,LinkStack;,Page,8,前缀转后缀算法演示,Page,10,后缀转前缀算法演示,Page,11,栈解决迷宫问题算法演示,Page,13,3.2.2.2 队列的顺序存储结构及其基本运算的实现,顺序队列类型,SqQueue,定义如下:,#define MaxSize 100,typedef int ElemType;,typedef struct,ElemType elemMaxSize;,int front,rear;/,队首和队尾指针,SqQueue;,Page,15,队列操作,Page,16,循环队列满和空指针判断冲突,Page,18,3.2.2.3 队列的链式存储结构及其基本运算的实现,队列的链式存储结构是仅在表头删除和表尾插入的单链表,因此一个栈队列需要使用两个指针:指向队头元素的队首指针,front,和指向队尾元素的队尾指针,rear,。用于存储队列的单链表简称链队。如图,3.11,所示的链队列。,Page,19,链队中数据结点的类型,QNode,定义,typedef int ElemType;,typedef struct qnode,ElemType data;,struct qnode*next;,QNode;/,链队数据结点类型定义,Page,20,一个链队的动态变化过程,Page,21,3.2.2.4,队列的应用举例,求解报数问题,设有,n,个人站成一排,从左向右的编号分别为,1,n,,现在从左往右报数“,1,,,2,,,1,,,2,”,数到“,1,”的人出列,数到“,2,”的立即站到队伍的最右端。报数过程反复进行,直到,n,个人都出列为止。要求给出他们的出列顺序。,Page,22,3.3.2,用队列来解决迷宫问题,【算法思路】,用队列解决迷宫问题,本质上是一个广度优先算法(在教材的树和图章节中将学到)。这里不能用循环队列,只能用普通的顺序队列。原因是在找到出口后,程序要根据队列中保存的数据,通过回溯寻找迷宫的路径。而循环队列中的数据在出队和入队操作时被覆盖的。普通队列不会将出队元素真正从队列中删除,因为要利用它输出路径。,Page,24,谢谢观赏,谢谢观赏,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 包罗万象 > 大杂烩

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服