下载

2下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 队列的基本知识及应用

队列的基本知识及应用.doc

队列的基本知识及应用

supergod
2012-08-09 0人阅读 举报 0 0 暂无简介

简介:本文档为《队列的基本知识及应用doc》,可适用于IT/计算机领域

中学计算机中级教练员培训教材队列的基本知识及应用内容提要.通过本章学习掌握队列的定义及队列的存储结构.掌握队列的基本操作运算:建队、插入、删除、队列空等用数组、链接方式所建立队列及操作运算.掌握循环队列概念及运算.能够利用队列解决一些实际问题:广度优先搜索算法重点难点.队列、循环队列概念及存储结构.队列的基本操作.综合运用队列结构解决实际问题内容讲授一、队列的基本知识队列(Queue)是一种特殊的线性表。它是一种运算受限的线性表。它只允许在表的一端进行插入而在另一端进行删除。允许删除的一端称为队头(front)允许插入的一端称为队尾(rear)。因此队列亦称作先进先出(FirstInFirstOut)的线性表简称FIFO表。.队列的性质假设队列为a,a,,an那么a就是队头元素an为队尾元素。队列中的元素是按a,a,,an的顺序进入的退出队列也只能按照这个次序依次退出。也就是说只有在a离开队列之后a才能退出队列只有在a,a,,an都离开队列之后an才能退出队列。图是队列的示意图。图队列的先进先出示意图.队列的存储结构()顺序存储:可用记录数组实现()链接存储:用链接存储方式实现如图所示:frontrearAAA………………AnAn顺序存储结构数组.基本术语:()队空:当队列中没有元素时称为空队列。()队满:当队列中单元全部被占用()队列操作规则:在队列中依次加入元素a,a,…an之后a是队头元素an是队尾元素。其出队操作规定从队头进行进队操作从队尾进行。即队列的操作是依先进先出的原则进行的。()上溢、下溢:真溢、假溢.队列的基本操作用顺序队列存储结构的表示方法:typequeue=recordvec:arraymofelemtypef,r:integerendf,r分别指向队列的头和尾()进队操作(插入运算)Procedureinsert(q,x)begin①ifqr=mthen输出上溢②qr:=qr③qvecqr:=x{进入队尾}④ifqf=thenqf:=end()出队操作:删除操作proceduredele(q,x)begin①ifqf=then输出下溢②x=qvecqf③ifqf=qrthenqf=qr=elseqf:=qfend()置空队算法procedureset(Q)beginqf:=qr:=end循环队列为充分利用向量空间克服"假上溢"现象的方法是:将向量空间想象为一个首尾相接的圆环并称这种向量为循环向量。存储在其中的队列称为循环队列(CircularQueue)。()定义:将队列的首、尾连接起来形成一个环状。队尾指向m队首指向。对循环队列的操作:()插入操作:procedureinsert(qx)begin·if(qrmodm)=qfthen溢出elseqr:=(qrmodm)qvecqr:=xend()删除操作:proceduredelete(q,x)beginifqf=qrthen输出队空elseqf=(qfmodm)x=qvecqfend()循环队列的长度:(rfn)modn链队列 链队是指队列的链接存储表示也就是说它只允许在表尾进行插入和在表头进行删除的单链表。一个链队需要队首、队尾两个指针一个指向表头一个指向表尾如下图所示:设有如下的数据类型定义:typelinklist=^dynanodedynanode=recorddata:elemtypenext:linklistendtypelinkqueue=recordf,r:linklistend链接队列的操作运算如下:()插入算法procedureinsert(HQ,x)begin·new(p)p^data:=xp^next:=nil·ifHQr=nilthenHQf:=pHQr:=pelseHQr^next:=pHQr:=pend()删除算法proceduredelete(HQ,x)begin·ifHQf=nilthenerror(‘underflow‘){队为空}·x:=HQf^data·p:=HQf·ifHQf=HQrthenHQf:=nilHQr:=nil{删除结点}elseHQf:=HQf^next·dispose(p)end二、队列的应用队列在日常生活中应用很多特别是在计算机科学领域中所起的作用很大。例如在解决主机与外部设备之间速度不匹配问题解决多用户引起的资源竞争问题等都运用了队列这样的数据结构算法下面通过一些实例了解运用队列解决问题方法。运用队列解决广度优先搜索算法中的最短路径问题是一种比较好的算法。例题年高中组基础题第题从入口()到出口()的可行路线图中数字标号表示关卡:现将上面的路线图按记录结构存储如下:请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。()该题是一个路径搜索问题根据图示从入口()到出口()可以有多种途径其中最短的路径只有一条那么如何找最短路径是问题的关键。()根据题意用一维数组存储各关卡号(设NO)用另一个数组存储访问到某关卡号的前趋关卡号(设PRE)。()由于本题是一个典型的图的遍历问题此题可以采用图的广度优先遍历算法并利用队列的方式存储顶点之间的联系。即访问一个点将其后继结点入队并存储它的前趋结点直到最后从()点出口。()从最后出口的关卡号()开始回访它的前趋关卡号则回返的搜索路径便是最短路径。(跳过许多不必要搜索的关卡)。()从列表中可以看出出口关卡号()的被访问路径最短的是:()←()←()←()←()←开始由此我们得到广度优先遍历求最短路径的基本方法:访问一个点将其后继结点入队并存储它的前趋结点直到所需要到达的地然后通过最终目标点的结点的前驱记录返回搜索最短路径的轨迹。例题:如下图表示的是从城市A到城市H的交通图。从图中可以看出从城市A到城市H要经过若干个城市。现要找出一条经过城市最少的一条路线。城市交通图矩阵存储结构算法如下:用队列的方法。用a记录搜索过程acity记录经过的城市,apre记录前趋元素这样就可以倒推出最短线路。具体过程如下:()将城市A入队队首、队尾都为。()将队首所指的城市所有可直通的城市入队(如果这个城市在队中出现过就不入队可用一个集合来判断)将入队城市的pre指向队首的位置。然后将队首加得到新的队首城市。重复以上步骤直到城市H入队为止。当搜到城市H时搜索结束。利用pre可倒推出最少城市线路。程序如下:programexpconstju:array,of=((,,,,,,,),             (,,,,,,,),             (,,,,,,,),             (,,,,,,,),             (,,,,,,,),             (,,,,,,,),             (,,,,,,,),(,,,,,,,))                                    typeR=record{记录定义}   city:arrayofchar   pre:arrayofinteger  endvarh,d,i:integer    a:R    s:setof'A''H'procedureout{输出过程}  begin   write(acityd)    repeat     d:=apred     write('',acityd)    untilapred=   writeln   halt  endproceduredoit begin  h:=d:=  acity:='A'  apre:=  s:='A'repeat{步骤}inc(h){队首加一出队}fori:=todo{搜索直通的城市}if(juord(acityh),I=)and(not(chr(i)ins))then{判断城市是否走过}begin inc(d){队尾加一入队}   acityd:=chr(i)apred:=h   s:=sacityd   ifacityd='H'thenout  enduntilh=d endbegin{主程序} doitend 输出:HFA例题迷宫问题:设有一个n*n方格的迷宫入口和出口分别在左上角和右下角如图所示其走路规则是:在任何一个格子中可以向个方向前进格子中表示可以走表示不通当迷宫给定后找出一条从入口到出口的通路。入口出口迷宫图搜索的个方向算法分析:()本题采用回溯算法应用队列存放走过的路径:即先进先出后进后出原理输出走迷宫的路径。AI,J:=表示可以走了表示不可以走()超界条件为:x<=x>n,y<,y>n,ax,y=,入口处条件:x=,y=,x=n,y=()增量和文字的方向:用数组表示程序如下:programexpvarA:array,of…c:array,of…b:arrayoofintegerdx,dy:array,of…n,m,k,I,x,y:integerbeginwrite(‘n=‘)readln(n)fory:=tondobegin{初始化程序段}forx:=tondobeginread(axy)cx,y:=oenddx:=dy:=dx:=dy:=dx:=dy:=dx:=dy:=dx:=dy:=dx:=dy:=dx:=dy:=dx:=dy:=x:=y:=m:=k:=forI:=todobI:=while(x<>n)or(y<>)do{按八个方向搜索}begink:=kifk>thenbegin{八个方向均搜索后无法前进}k:=bmm:=m{退回到上一步}x:=xdxk{清当前所走的记录内容}y:=ydykendelsebegin{可以向前走一步}x:=xdxky:=ydykif(x<)or(x>n)or(y<)or(y>n)or(ax,y=)or(cx,y=)thenbeginx:=xdxky:=ydyk{超界或已经访问过回退}endelsebeginm:=mcx,y:=bm:=kk:={进队记录所访问的格子}endendendx:=y:=write(‘(‘,x,‘,‘,y,‘)‘)forI:=tomdobeginx:=xdxbIy:=ydybIwrite(‘(‘,x,‘,‘,y,‘)‘)endwritelnend程序运行结果:(,)()()()()()()()()()()()()例题有升油在升的容器中另有两个升和升的空容器现要求用这三个容器倒油使得最后在升和升的容器中各有升油。提示:三个容器可以看作三个变量CCC每次倒油的可能性只有如下六种情况:①C向C倒油②C向C倒油③C向C倒油④C向C倒油⑤C向C倒油⑥C向C倒油算法分析:()从一个容器的状态(三个容器中油的容量)看虽然有可能经过上述六种倒油的方法产生六种容器状态但实际上这六种新产生的容器状态许多是已经出现过的状态。例如初始状态(,,)表示C=C=C=经过上述六种倒油方法只能产生出两种新的容器状态(,,)表示C向C倒油的结果和(,,)表示C向C倒油的结果。如果再增加应该表示新容器状态是由什么状态产生的指示pre那么用这三个容器倒油的过程就可以用队列的技法来实现了()队列可以理解为一个数组数组元素是如下记录:RECORDC,C,C,pre:integerEND数组下标为容器状态号。下面是倒油过程的队列图示:CCCpre当倒油产生出第个容器状态时已达到了题解的目的。这时只要根据pre中的状态号可以回溯到第个容器状态的pre值为依次可再获得容器状态号从而即可得到本题的倒油过程(共倒次)而且是最少的倒油次数。注意,从一个容器中向另一个容器中倒油,人操作是很直观的,对编程来说则必须考虑:)有没有油可倒)究竟倒多少可能要全部倒入另一容器,也可能只要倒一部分另一容器已经满了队列元素说明了个是因为升容器最多有~种状态升容器最多有~种状态升容器最多有~种状态全部可能的状态为**=种但油的总量为因此种可能状态中大部分是不存在的。变量fprp在程序中用作队列的头指针和尾指针flag在程序中标识是否已倒出了需要的容器状态(C=,C=)下面是程序清单:programexpvarfp,rp,i,k,w,w,w:integerflag:booleans:arrayofq:arrayofrecordc,c,c:integerpre:endprocedureintbeginw:=qfpcw:=qfpcw:=qfpcendprocedurepush{进队操作}varflag:booleanbeginflag:=truefork:=torpdoif(qkc=w)and(qkc=w)and(qkc=w)thenflag:=falseifflagthenbeginrp:=rpqrpc:=wqrpc:=wqrpc:=wendendPROCEDUREcup{倒油的操作过程}BEGINintIFw>THENBEGIN{将升油桶中的油倒入升油桶}IFww>=THENBEGINw:=www:=ENDELSEBEGINw:=www:=ENDpushIF(qrpc=)and(qrpc=)THEN{判断是否满足问题的解}BEGINflag:=trueexitENDENDintifw>thenbegin{将升油桶向升油桶倒油}ifww>=thenbeginw:=www:=endelsebeginw:=www:=endpushif(qrpc=)and(qrpc=)thenbeginflag:=trueexitendend{判断是否满足问题求解}intIFw>THENBEGINw:=www:=push{将升倒入升油桶}IF(qrpc=)and(qrpc=THENBEGINflag:=trueexitENDEND{判断是否满足问题求解}intIFw>THENBEGIN{将升倒入升油桶}IFww>=THENBEGINw:=www:=ENDELSEBEGINw:=www:=ENDpushIF(qrpc=)and(qrpc=THENBEGINflag:=trueexitEND{判断是否满足问题求解}END{以下同理}intIFw>THENBEGINw:=www:=pushIF(qrpc=)and(qrpc=THENBEGINflag:=trueexitENDENDintIFw>THENBEGINIFww>=THENBEGINw:=www:=ENDELSEBEGINw:=www:=ENDpushIF(qrpc=)and(qrpc=)THENBEGINflag:=trueexitENDENDENDBEGIN{主程序}fp:=rp:=qc:={初始化}qc:=qc:=qpre:=flag:=falserepeatcupfp:=fpuntilflagor(fp>rp){反复倒油直到完成倒油过程或队列中所有元素都访问过}iffp>rpthenwrite('havenotsolution')elsebeginwriteln('queue')fork:=torpdo{输出进队过程}writeln(qkc:,qkc:,qkc:,qkpre:)s:=rpi:=whilesi>do{用S数组存放最少倒油过程的路径}begini:=isi:=qsipreendwriteln('solution:')fork:=idowntodo{输出倒油步骤}writeln('step',ik,':',qskc:,qskc:,qskc:)endend{主程序结束}说明:例题比较难和繁将该程序介绍给大家的目的在于供老师们辅导学生竞赛时参考希望您的学生能够用队列的特点、记录数组的结构灵活地解决问题。参考练习:.上机调试完成例题最短路径问题.上机调试完成例题迷宫问题.假设在周末舞会上男士们和女士们进入舞厅时各自排成一队。跳舞开始时依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。.设有数运算符号为*且运算符无优先级之分如*=*=。现给出任意一个整数n要求用以上的数和运算符以最少的运算次数产生出。∧afrontreara… 链队示意图�EMBEDPBrush���PAGE

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/14

队列的基本知识及应用

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利