版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
4.1ADT队列队列是另一种特殊的表,也是操作受限4.1ADT队列队列是另一种特殊的表,也是操作受限队尾(rear)——允许插入的一队头(front)——允许删除的一特点:先进先出例如:排队上车2BusStop3BusStop3BusStop4BusStop4BusStop5BusStop5BusStop6BusStop6假设队列,,,则就是队首元素,为队尾元素。队列中的元素按,,的次序进出假设队列,,,则就是队首元素,为队尾元素。队列中的元素按,,的次序进出 入队列7ADT测试队列QQueueFull(Q):测试队列Q返回队列Q返回队列QADT测试队列QQueueFull(Q):测试队列Q返回队列Q返回队列QEnterQueue(x,Q):在队列Q的队尾插入元素DeleteQueue(Q):删除并返回队列Q8用指针实现队与栈的情形相同,任何一种实用指针实现队与栈的情形相同,任何一种实现表的方法都可以用9typedefstructqnode*qlink;typedefstructqnode{QItemelement; }用指针实现的队列Queuetypedefstructlque*Queue;typedefstructlque{qlinkfront; 用指针实现的队列Queuetypedefstructlque*Queue;typedefstructlque{qlinkfront; qlinkrear; 1、创将队首指针和队尾指针均置为空指针,创建一个空队列,实现方法如下:1、创将队首指针和队尾指针均置为空指针,创建一个空队列,实现方法如下:QueueQueueInit({QueueQ=malloc(sizeof*Q);returnQ;}2、判检测frontintQueueEmpty(Queue{returnQ-2、判检测frontintQueueEmpty(Queue{returnQ-}3、判为队列QintQueueFull(Queue{returnQMemFull(}int3、判为队列QintQueueFull(Queue{returnQMemFull(}intQMemFull({qlinkreturn{return}4、返QItemQueueFirst(Queue{ Error(“Queue4、返QItemQueueFirst(Queue{ Error(“Queueis returnQ->front-}5、返QItemQueueLast(Queue{ Error(“Queue5、返QItemQueueLast(Queue{ Error(“Queueis returnQ->rear-}6、在队列Q的队尾插入元素6、在队列Q的队尾插入元素voidEnterQueue(QItemx,Queue{qlinkp; elseQ–>front=p;}7、删除并返回队列Q7、删除并返回队列QQItemDeleteQueue(Queue{qlink QItem Error(“Queueisreturn}用循环数组实现队个游标来指示队尾,使得Et用循环数组实现队个游标来指示队尾,使得Ete运算在1时间内完成,但在执行e时,为了删除队首元素,必须将数组中其他所有元素都前移一个位置,很浪费时间。设想数组queue[0:maxsize-1]而是围成一个首尾相接的圆环,即queue[0]queue[maxsize-1]的后面。这种意义下的数组称为数组0Maxsize-设想数组queue[0:maxsize-1]而是围成一个首尾相接的圆环,即queue[0]queue[maxsize-1]的后面。这种意义下的数组称为数组0Maxsize-实现:利用“模”出队:将队首游标front队满、队空判定条5 43012543015243012初始解决5 43012543015243012初始解决方案另外设一个布尔量用循环数组实现的队列Queuetypedefstructaque*Queue;typedefstructaque{intmaxsize; 用循环数组实现的队列Queuetypedefstructaque*Queue;typedefstructaque{intmaxsize; intfront; intrear; QItem*queue; 1、创为队列分配一个容量为sizefront和队尾游标rear均置为0,创1、创为队列分配一个容量为sizefront和队尾游标rear均置为0,创QueueQueueInit(int{QueueQ=malloc(sizeofreturnQ;}2、判通过检测队列Q的队首游标front与队尾游标rear是否合来判断队列Q2、判通过检测队列Q的队首游标front与队尾游标rear是否合来判断队列QintQueueEmpty(Queue{returnQ->front==Q-}3、判通过在队列Q的队尾插入一个元素后队首游标front尾游标rear是否重合,来判断队列Q3、判通过在队列Q的队尾插入一个元素后队首游标front尾游标rear是否重合,来判断队列QintQueueFull(Queue{return(((Q->rear+1)%Q->maxsize==Q-}4、返回队列Q的队4、返回队列Q的队QItemQueueFirst(Queue{ Error(“QueueisreturnQ->queue[(Q->front+1)%Q-}5、返回队列Q的队QItemQueueLast(Queue5、返回队列Q的队QItemQueueLast(Queue{ Error(“Queueis returnQ->queue[Q-}6、在队列Q的队尾插入元素先计算出在循环的意义队列的队尾元素在循环数组中的下一个位置(z6、在队列Q的队尾插入元素先计算出在循环的意义队列的队尾元素在循环数组中的下一个位置(ze,然后在该位置插入元素。voidEnterQueue(QItemx,Queue{ Error(“QueueisFull”);Q->rear=(Q->rear+1)%Q->maxsize;}7、删除并返回队列Q7、删除并返回队列QQItemDeleteQueue(Queue{ Error(“Queueisempty”);Q->front=(Q->front+1)%Q->maxsize;returnQ->queue[Q->front];}队列的应用举例1在主机将数据输出到打印机时,会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然,这样会降低主机的使用效率。为此人们设想了一种办法:为打印机设置一个打印数据缓冲区,当主机需要打印数据时,先将数据依次写入这个缓冲区,写满后主机转去做其他的事情,而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印,这样做即保证了打印数据的正确性,又提高了主机的使用效率。由此可见,打印机缓冲区队列的应用举例1在主机将数据输出到打印机时,会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然,这样会降低主机的使用效率。为此人们设想了一种办法:为打印机设置一个打印数据缓冲区,当主机需要打印数据时,先将数据依次写入这个缓冲区,写满后主机转去做其他的事情,而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印,这样做即保证了打印数据的正确性,又提高了主机的使用效率。由此可见,打印机缓冲区实际上就是一个队列结队列的应用举例2CPU在一个带有多个终端的计算机系统中,同时有多个用户需要使用U运行各自的应用程序,它们分别通过各自的终端向操作系统提出使用队列的应用举例2CPU在一个带有多个终端的计算机系统中,同时有多个用户需要使用U运行各自的应用程序,它们分别通过各自的终端向操作系统提出使用P的请求,操作系统通常按每次把CPU分配给当前队首的请求用户,即将该用户用程序投入运行,当该程序运行完毕或用完规定的时间片后,操作系统再将PU分配给新的队首请求用户,这样即可以满足每个用户的请求,又可以使P正常工作。例3例3R={(ai,aj)|ai,aj∈A,i≠j},其中(ai,aj)表示ai与aj间存在冲系,同时要求分子集个数尽可能少R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)可行的子集A1={1,3,4,8A2={2,7A3={5A4={6,9算法思想:利用循环筛选算法思想:利用循环筛选冲突关系矩r[i][j]=1,i,jr[i][j]=0,i,j循环队列数组result[n]存放每个元素分组工作数组初始状态:A中元素放于q中,t和w初始状态:A中元素放于q中,t和wr数组清零,组号第一个元素出队,将r矩阵中第一行“”拷入r中对应位置,这样,凡与第一个元素有冲突的元素在wr中对应位置处均为“下一个元素出队若其在ner中对应位置为“1”,有冲突,重新插入cq队尾,参加下一次分组若其在newr中对应位置为“0”,无冲突,可划归本组;再将r如此反复,直到个元素依次出队,由中为“的单元对应的元素构成第组将组号u值“写入l对应单元中令group=2,newr清零,对cq中元素重复上述操作,直cq中front==rear,即队空,运算结R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)0123456780100000001000110110000011000000100010101011010110101000R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf初012345678012345678000000000000000000123456789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000fr01234567801234567810000000001000000023456789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf01234567801234567810000000001000000023456789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf0123456780123456781010000000100011002456789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf012345678012345678101100000010011101256789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf012345678012345678101100000010011101256789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000fr012345678012345678101100000010011101256789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf012345678012345678101100000010011101256789R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)01234567801000000010001101100000110000001000101010110101101010R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000f7r0123456801234567810110001001001110125679R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf01234567801234567810110001001001110125679R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000fr0123456780123456781211000101000110115679R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000fr0123456780123456781211000101000110116795R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)01234 78010000000100011011000001100000010001010101101011010R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)01234 78010000000100011011000001100000010001010101101011010100001011000010000000010110000fr01234 780123456781211000101000110117956R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)01234 78010000000100011011000001100000010001010101101011010R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)01234 78010000000100011011000001100000010001010101101011010100001011000010000000010110000fr01234 78012345678121100210101011011956R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf012345678012345678121100210101011011569R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)0123 678010000000100011011000001100000010001010101101011010R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)0123 678010000000100011011000001100000010001010101101011010100001011000010000000010110000fr0123 67801234567812113021001010110169R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000000100011011000001100000010001010101101011010100001011000010000000010110000rf01234567801234567812113021001010110196R={(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)012345678010000
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 烟台大学《工程制图》2021-2022学年第一学期期末试卷
- 许昌学院《跆拳道》2021-2022学年第一学期期末试卷
- 许昌学院《材料与施工工艺》2022-2023学年第一学期期末试卷
- 衣柜销售合同范本
- 长途客运服务协议
- 如何做职业规划
- 人教版-六年级上册数学-百分数(一)单元测试(含答案)
- 小学升初中天立试卷
- 湖北省黄石市下陆区四校2024-2025学年九年级上学期期中联考物理试题(含答案)
- 外研社初中九年级英语词汇
- 2024年新疆能源集团有限责任公司招聘笔试参考题库含答案解析
- PDCA降低护士针刺伤发生率
- 新员工环保基础知识培训
- 劳动标准培训课件
- 四川省成都市温江区2023-2024学年英语九年级第一学期期末经典试题含解析
- 人教部编版语文四年级上册第六单元课外阅读练习及答案
- 《电气接线规范》课件
- 申请失业保险金承诺书
- 社区妇女保健知识讲座
- 习作:《生活万花筒》(课件)四年级上册语文部编版
- 辅助生殖护理质量控制管理
评论
0/150
提交评论