欢迎来到三一办公! | 帮助中心 三一办公31ppt.com(应用文档模板下载平台)
三一办公
全部分类
  • 办公文档>
  • PPT模板>
  • 建筑/施工/环境>
  • 毕业设计>
  • 工程图纸>
  • 教育教学>
  • 素材源码>
  • 生活休闲>
  • 临时分类>
  • ImageVerifierCode 换一换
    首页 三一办公 > 资源分类 > PPT文档下载  

    数据结构队列ppt课件.ppt

    • 资源ID:1925921       资源大小:203KB        全文页数:38页
    • 资源格式: PPT        下载积分:16金币
    快捷下载 游客一键下载
    会员登录下载
    三方登录下载: 微信开放平台登录 QQ登录  
    下载资源需要16金币
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    数据结构队列ppt课件.ppt

    第二章 队列,吉林大学计算机学院谷方明,例子:电话号码,向计算机专业的同学要电话号码,他(她)不会直接给你的,原因你懂的。他(她)会告诉你一串加密过的数字,同时告诉你解密的规则。规则是这样的:首先将第1个数删除,紧接着将第2个数放到这串数的末尾,再将第3个数删除并将第4个数放到这串数的末尾,直到剩下最后一个数,把这个数也删除。按删除的顺序将删除的数连在一起,就是电话号了。例如:58659146,1. 队列的定义,队列(queue)是一种操作受限的线性表,它的所有插入都在表的一端进行,所有的删除都在表的另一端进行。例子食堂窗口进程调度队列的特性:先进先出。栈也称作后进先出表(First In First Out,FIFO)。,队头(front) :进行删除的一端;队尾(rear) :进行插入的一端;空队列:没有元素的队列。插入:入队删除:出队,术语,队列的基本操作,(1)队列初始化(2)入队 (插入)(3)出队(删除)(4)读取队首元素(5)判断队列是否空 (6)确定队列中元素个数 (7)置空队列,2.队列的顺序存储,按顺序存储方式存放队列元素,称为顺序队。存放队列元素的数组:T qlistMaxQSize front 队首元素的下标 rear 队尾元素的下标加 1队列空: front = rear队列满: rear = MaxQSize,插入队尾元素: rear=rear+1,删除队首元素:front=front+1,假溢出,循环队列,插入元素 : rear顺时针移动一位,rear = (rear+1) MOD MaxQSize,删除元素:front顺时针移动一位,front = (front+1) MOD MaxQSize;,循环队列,front指定队首位置,删除一个元素就将front顺 时针移动一位; rear指向元素要插入的位置,插入一个元素就将rear顺时针移动一位; count存放队列中元素的个数,当count等于MaxQSize时,不可再向队列中插入元素。 队空:count=0队满:count= MaxQSize,顺序队列类AQueue的类声明template class AQueueprivate: int front ;/ 队首所在数组元素下标 int rear ; / 新元素要插入的位置(下标) int count ; / 队列中元素个数 T *QArray ; / 存放队列元素的数组 int Size ;/ 存放队列的数组规模public: AQueue ( int MaxQueueSize = 10 ); / 构造函数 AQueue () delete QArray ; / 析构,void QInsert ( const T/ 清空队列;,插入算法ADL描述,算法QInsert (A, item)/ 在队列A中将元素item插入队尾QI1. 队列满?IF countsize THEN (PRINT“队列已满无法插入”. RETURN. )QI2. 元素插入 Arear item. / 将新元素插入队尾QI3. 更新 rearMOD(rear1, size). / 更新队尾下标 countcount1. / 更新队列长度 ,C+实现,template void AQueue:QInsert ( const T,删除算法ADL描述,算法QDelete (A. item)/ 删除队列A的队首元素,并将其元素值赋给变量itemQD1. 队列空?IF count0 THEN (PRINT “队列空无法删除”. RETURN. )QD2. 出队 item Afront. / 将队首元素保存至itemQD3. 更新 frontMOD(front1, size). / 更新队首元素下标 countcount -1. / 更新队列长度 ,C+实现,template void AQueue:QDelete (T,取队首算法ADL描述,算法QFront (A. item) / 读取队列A的队首元素值,并将其赋给变量itemQF1. 队列空?IF count0 THEN (PRINT “队列空无法读取”. RETURN. )QF2. 存取 item Afront. / 将队首元素保存至item ,C+实现,template T AQueue:QFront () constreturn QArrayfront;,验证:#include aqueue.h,int main()int n,i,x;AQueue s(100);cinn;for(i=1;i=n;i+) s.QInsert(i);for(i=1;i=n;i+) s.QDelete(x); coutxendl; ,队列运行示意图,3.队列的链接存储,template class NodeT data; Node* next;,链队LQueue的类定义,template class LQueue private:Node * front, * rear ; / 指向队首和队尾的指针public:LQueue ( void ) front = rear = NULL; / 构造函数 LQueue ( void ) QClear ( ) ; / 析构函数,void QInsert ( const T/ 清空队列;,插入算法ADL描述,算法QInsert (item) / 将元素item插入队尾QI1. 创建新结点 s AVAIL. data(s)item. next(s)NULL. / 为新结点申请空间,令其字段值为item,指针域为空QI2. 队空? IF frontNULL THEN fronts. /若队列为空,令队首指针指向s ELSE next(rear)s. /若队列非空,令表尾结点的next指针指向sQI3. 更新队尾指针 rears. / 更新表尾指针,C+实现,void LQueue:QInsert ( const T,删除算法ADL描述,算法QDelete (item) / 删除队首结点并将其字段值存于itemQD1. 队列空? IF frontNULL THEN (PRINT “队列为空”. RETURN. )QD2. 出队 qfront. itemdata(q). / 令指针q指向队首,并保存其字段值 frontnext(front). / 令队首指针指向原队首结点之后继结点 AVAILq. / 释放原队首结点的存储空间QD3. 出队后队列空? IF frontNULL THEN rearNULL. / 若删除队首结点后队列为空,则令队尾指针修为空,C+实现,template void LQueue:QDelete (T,取队首算法ADL描述,算法QFront (item) / 读取队首元素值,并将其赋给变量itemQF1. 队列空? IF frontNULL THEN (PRINT “队列空无法读取”. RETURN. )QF2. 存取 item data(front). / 将队首元素保存至item,C+实现,template T LQueue:QFront () const if(front) return front-data;,验证:#include “lqueue.h,int main()int n,i,x;LQueue s;cinn;for(i=1;i=n;i+) s.QInsert(i);for(i=1;i=n;i+) s.QDelete(x); coutxendl; ,顺序队列与链式队列的比较,在空间复杂性上,顺序队列必须初始就申请固定的空间,当队列不满时,必然造成空间的浪费;链式队列所需空间是根据需要随时申请的,其代价是为每个元素提供空间以存储其next指针域。在时间复杂性上,对于队列的基本操作(入队、出队和存取),顺序队列和链式队列的时间复杂性均为O(1) .,STL中关于栈的实现,#include queue s; /不用声明大小s.push(x);s.front(); /取队首s.pop(); /只弹出队首,与front合用,课后练习,oj.org 注册数据较大时,使用scanf和printfpoj1363 railspoj3250 Bad Hair Day,

    注意事项

    本文(数据结构队列ppt课件.ppt)为本站会员(小飞机)主动上传,三一办公仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一办公(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    备案号:宁ICP备20000045号-2

    经营许可证:宁B2-20210002

    宁公网安备 64010402000987号

    三一办公
    收起
    展开