分享
分销 收藏 举报 申诉 / 25

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

  • 上传人:知****运
  • 文档编号:14665123
  • 上传时间:2026-10-27
  • 格式:PPT
  • 页数:25
  • 大小:1.67MB
  • 下载积分:10 金币
  • 配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    队列 数据结构 案例
    资源描述:
    单击此处编辑母版文本样式,第二级,第三级,第四级,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折扣优惠下载文档

    提示  咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。

    咨信网小贴示:
    1、浏览或下载可查看了解,请点击【咨信网告知】。
    2、下载文件中如有侵权或不适当内容,将立即纠正。
    3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
    4、开具发票登录电脑端申请,请点击【索取发票】。

    咨信网客服组:【微信客服】

    自信AI创作助手
    关于本文
    本文标题:第3章-栈与队列-数据结构案例.ppt
    链接地址:https://www.zixin.com.cn/doc/14665123.html

    Copyright ©2010-2026   All Rights Reserved  宁波自信网络信息技术有限公司 版权所有   |  客服电话:0574-28810668    微信客服:咨信网客服    投诉电话:18658249818   

    违法和不良信息举报邮箱:help@zixin.com.cn    文档合作和网站合作邮箱:fuwu@zixin.com.cn    意见反馈和侵权处理邮箱:1219186828@qq.com   | 证照中心

    12321jubao.png12321网络举报中心 电话:010-12321  jubao.png中国互联网举报中心 电话:12377   gongan.png浙公网安备33021202000488号  icp.png浙ICP备2021020529号-1 浙B2-20240490   


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

    自信网络  |  ZixinNetwork