队列的基本操作.pptx

《队列的基本操作.pptx》由会员分享，可在线阅读，更多相关《队列的基本操作.pptx（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、结论：在队列这种数据结构中，最先插入在元素将是最先被删除；反之最后插入的元素将最后被删除，因此队列又称为“先进先出”（FIFOfirst in first out）的线性表。第1页/共55页队列的基本操作：（1）初始化队列 Qini(Q)（2）入队 QADD(Q,X)（3）出队 QDel(Q,X)（4）判断队列是否为空 qempty(Q)（5）判断队列是否为满qfull(Q)第2页/共55页二、队列的存储结构 1、顺序存储Constm=队列元素的上限；Typequeue=record队列的类型定义data:array1.mofelemtypef,r:integer;队尾指针和队首指针end;V

2、arq：queue；队列Constm=队列元素的上限；Typequeue=array1.mofelemtypeVarq：queue；队列f,r:integer;队尾指针和队首指针第3页/共55页二、队列的存储结构 2、链式存储FA1A2ANRtypelink=celltype;celltype=recorddata:elemtype;next:link;end;varf,r:link;第4页/共55页三、队列的基本运算1、初始化：设定Q为一空队列：procedure Qini(var Q:queue);procedure Qini(var Q:queue);beginbeginQ.f:=0;Q

3、.f:=0;Q.r:=0;Q.r:=0;end;end;第5页/共55页2 2、判队列空：若队列Q Q为空，则返回值truetrue，否则返回值falsefalse。functionqempty(Q:queue):Boolean;beginqempty:=(Q.f=q.r)end;第6页/共55页functionqfull(Q:queue):Boolean;beginQfull:=（Q.rm);end;3、判队满：若队列满，则返回值true，否则返回值false。第7页/共55页4、元素进队：若队列Q不满时，把元素X插入到队列Q的队尾，否则返回信息“Overflow”：procedureQAD

4、D(varq:queue;x:elemtype);beginifqfull(Q)thenwriteln(overflow)上溢elsebegin后移队尾指针并插入元素xQ.R:=Q.r+1；Q.dataQ.r:=x；end；elseend；ADD第8页/共55页5、元素出队：若队列Q不空，则把队头元素删除并返回值给X，否则输出信息“Underflow”：procedure Qdel(var Q:queue;var X:elemtype);begin if qempty(Q)then writeln(Underflow)下溢 else begin 后移队首指针并取出队首元素 Q.fQ.f+1;X

5、Q.dataQ.f；end；else end;第9页/共55页例1假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。输入：第一行两队的人数第二行舞曲的数目应用举例第10页/共55页分析：设计两个队列分别存放男士和女士。每对跳舞的人一旦跳完后就回到队尾等待下次被选。如m=3n=2k=6A1 2 3 1 2 31 2 1 2 1 2BF1R1F2R2第11页/共55页constmax=10000;vara,b

6、:array1.maxofinteger;m,n,k1,k,i,f1,r1,f2,r2:integer;beginreadln(m，n);fori:=1tomdoai:=i;fori:=1tondobi:=i;readln(k);k1:=1;f1:=1;r1:=m;f2:=1;r2:=n;第12页/共55页repeatwriteln(af1:3,bf1:3);r1:=r1+1;ar1:=af1;f1:=f1+1;r2:=r2+1;br2:=bf2;f2:=f2+1;k1:=k1+1;untilk1kend.第13页/共55页例2.集合的前N个元素：编一个程序，按递增次序生成集合M的最小的N个数

7、，M的定义如下：(1)数1属于M；(2)如果X属于M，则Y=2*X+1和Z=3*x+1也属于M；(3)此外再没有别的数属于M。第14页/共55页分析：可以用两个队列a和b来存放新产生的数，然后通过比较大小决定是否输出，具体方法如下：(1)令fa和fb分别为队列a和队列b的头指针，它们的尾指针为r。初始时，X=1，fa=fb=r=1；(2)将2*x+1和3*x+1分别放入队列a和队列b的队尾，尾指针加1。即：rr+1；ar2*x+1，br3*x+1第15页/共55页(3)将队列a和队列b的头结点进行比较，可能有三种情况：(A)ahabhb(B)aha=bhb(C)ahabhb将比较的小者取出送入

8、X，取出数的队列的头指针相应加1。(4)重复(2)，(3)直至取出第N项为止。第16页/共55页算法二：vara:array1.30000of0.1;f,t,n,m,i:integer;beginreadln(n);fori:=1to30000doai:=0;a1:=1;f:=1;k:=1;t:=0;whilet=ndobeginaf*2+1:=1;af*3+1:=1;f:=f+1;whileaf=0dof:=f+1;T:=t+1;end;第17页/共55页m:=1;i:=1;whilem=ndobeginifai0thenbeginwrite(i,);m:=m+1;end;i:=i+1;en

9、d;end.第18页/共55页 编一个程序，找出一条通过迷宫的路径。这里有兰色方块的单元表示走不通，将一只老鼠从入口处经过迷宫到出口处的最短的一条通路打印出来。例4迷宫问题入口出口第19页/共55页分析（1）怎样来存储迷宫？将它变成0，1二维数组。这样上述迷宫可转化为：011101111010101001001111011100111001100001100110第20页/共55页（2）老鼠在迷宫中怎样探索路径？有几个方向可以探索呢？*只有三个探索方向的位置。如mg1,1*有五个探索方向的位置。如mg3,1*有八个探索方向的位置。如mg3,2思考：能否都转化为八个方向的探索呢？第21页/共55

10、页这样存储的迷宫数组就转化成：11111111111011101111110101010110100111111011100111110011000110110011011111111111第22页/共55页因此，数组定义为:Mg:array0.m+1,0.n+1ofinteger;而探索方向则变成了统一的情况，都探索8个方向：（x-1,y+1）（x,y）（x-1,y）（x+1,y）（x,y+1）（x+1,y+1）（x-1,y-1）（x,y-1）（x+1,y-1）DxDy0111101-10-1-1-1-10-11这样可以定义一个二维数组记录探索方向。第23页/共55页（3）如何才能记录踪迹，

11、并把探索的踪迹记忆下来呢？踪迹一般应包括来处和当前位置，可以需要用记录类型Node=recordX,y:integer;Pre:0.r;End;用一个对队列记忆探索的踪迹：Sqtype=array1.rofnode;第24页/共55页例如：从（1，1）入口到达（6，8），往下探索时队列的情况11111111111011101111110101010110100111111011100111110011000110110011011111111111第25页/共55页（4）如何防止重复探索：将迷宫中的0替换为-1procedure Qini(var sQ:sqtype);procedure Qi

12、ni(var sQ:sqtype);beginbeginsQ1.x:=1;sq1.y:=1;sQ1.x:=1;sq1.y:=1;Sq1.pre:=0Sq1.pre:=0F:=1;r:=1;mg1,1:=-1;F:=1;r:=1;mg1,1:=-1;end;end;第26页/共55页Proceduremglj(varsq:sqtype);BeginSqini;Whilef=rdoBeginx:=sqf.x;y:=sqf.y;forv:=1to8dobegini:=x+zlv,1;j:=y+zlv,2;ifmgi,j=0thenbeginr:=r+1;sqr.x:=i;sqr.y:=j;sqr.p

13、re:=f;mgi,j:=-1;end;if(i=m)and(j=n)thenprint;exitend;第27页/共55页F:=f+1End;Writeln(迷宫无路径);End;如何打印路径？Procedureprint(varsq:sqtype,r:integer);Begini:=r;repeatwriteln(,sqi.x,sqi.y,);i:=sqi.preuntili=0End;第28页/共55页产生问题：由于顺序存储结构的存储空间属于静态分配，所以，在添加数据元素时，可能会出现没有剩余单元的情况。下面我们讨论一下下图所示的队列，称为“假溢出”现象。第29页/共55页解决方法：将

14、元素加入到第一个位置，即将存储空间的第一个位置作为队尾。采用首尾相接的结构后，形成一个环状，解决假溢出问题，避免数据元素的移动。如图所示。我们将这种形式表示的队列称之为循环队列。1234mAm-1AmAm+1FR空闲区123m-1mamAm-1FRAm+1第30页/共55页循环队列的操作procedureiniqueue(varQ:equeue);beginQ.f:=m;Q.r:=m;end;1、初始化：设定Q为一空队列，队首指针和队尾指针均指向存储空间的最后一个位置第31页/共55页2、判队列空：若队列Q为空，则返回值true，否则返回值false。functionqempty(Q:eque

15、ue):Boolean;beginqempty:=(Q.f=Q.r)end;第32页/共55页3、判队满：若队列满，则返回值true，否则返回值false。为了区分队列空和队列满，改用“队尾指针追上队首指针”这一特征作为队列满标志。functionqfull(Q:equeue):Boolean;beginqfull:=(Q.rmodm)+1=Q.f);end;第33页/共55页4、元素进队：若队列Q不满时，把元素X插入到队列Q的队尾，否则返回信息“Overflow”：procedure add(var Q:equeue;X:elemtype);begin if qfull(Q)then wri

16、teln(Overflow)else begin Q.r:=Q.r mod m+1;Q.dataQ.r:=X;endend;第34页/共55页5、元素出队：若队列Q不空，则把队头元素删除并返回值给X，否则输出信息“Underflow”：procedure del(var Q:equeue;var X:elemtype);begin if qempty(Q)then writeln(Underflow)else begin后移队首指针并取出队首元素 Q.f:=Q.f mod m+1;X:=Q.dataQ.f；end;end;第35页/共55页例5约瑟夫问题：编号为1，2，n个人按顺时针方向围坐一

17、圈，每人持一个正整数密码，开始给定一个正整数m，从第一个人按顺时针方向自1开始顺序报数，报到m者出围坐的圈子，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人都出围坐的圈子为止，输出出列者的序列。第36页/共55页例如有5人M=181234587365序号密码（1）开始取m=18，从1报数，则序号为3的人出列。12458765（2）开始取m=3，从4报数，则序号为1的人出列。245765（3）开始取m=8，从2报数，则序号为4的人出列。2575（4）开始取m=6，从5报数，则序号为2的人出列。55（5）开始取m=5，从5报数，则序号为5

18、的人出列。出列顺序为：3,1,4,2,5第37页/共55页const max=30;type people=record number,code:array1.max of integer end;var a:people;m,n,i,j,s,w,p:integer;begin readln(m,n);for i:=1 to n do a.numberi:=i;for i:=1 to n do read(a.codei);第38页/共55页s:=1;forj:=ndownto1dobegins:=(s+m-1)modj;ifs=0thens:=j;w:=s;p:=a.numberw;write

19、(p,);m:=a.codep;fori:=stoj-1doa.numberi:=a.numberi+1;end;end.第39页/共55页综合举例例6问题描述求一棵树的深度与宽度。算法说明树可用数组 tree:array1.n,1.5of integer;如上图可表示为：1 2 3 4 02 5 6 7 03 8 0 0 04 9 10 0 05 0 0 0 06 0 0 0 07 11 12 0 08 0 0 0 09 0 0 0 010 0 0 0 011 0 0 0 0 12 13 0 0 0 13 0 0 0 0（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（

20、12）（13）本题的数据结构含义，首先要搞清楚：treei,j存储编号为i的结点的第j号孩子（2=j=5,即最多4个孩子），treei,j=0表示不存在；第40页/共55页在求解的过程中，用到数组G:ARRAY1.N,1.7 OF INTEGER；其中：GI,1表示父结点，GI,2表示层次，GI,3表示本结点号，GI,4GI,7 表示子女结点；同时，设2个指针SP1（取数指针），SP2（存数指针）注意：gi,k实质上是一个队列，sp1为队列头指针,sp2为队列尾指针。第41页/共55页 程序清单：program exprogram exp3;p3;const n=13;const n=13;v

21、ar i,j,k,sp1,sp2,n1,n2,jmax,p:integer;var i,j,k,sp1,sp2,n1,n2,jmax,p:integer;tree:array1.n,1.5of integer;tree:array1.n,1.5of integer;g :array1.n,1.7of integer;g :array1.n,1.7of integer;beginbegin for i:=1 to n do for i:=1 to n do begin treei,1:=i;begin treei,1:=i;for j:=2 to 5 do for j:=2 to 5 do re

22、ad(treei,j);read(treei,j);readln;readln;end;end;treei,j=0表示i结点不存在第42页/共55页sp1:=1;sp2:=1;g1,1:=0;g1,2:=1;g1,3:=1;sp1:=1;sp2:=1;g1,1:=0;g1,2:=1;g1,3:=1;for i:=4 to 7 do g1,i:=tree1,i-2;for i:=4 to 7 do g1,i:=tree1,i-2;while_dowhile_do begin begin p:=gsp1,2;n2:=gsp1,3;p:=gsp1,2;n2:=gsp1,3;_;j:=4;_;j:=4

23、;while _do while _do begin n1:=gsp1,j;j:=j+1;begin n1:=gsp1,j;j:=j+1;_;_;gsp2,1:=n2;gsp2,2:=p;gsp2,3:=n1;gsp2,1:=n2;gsp2,2:=p;gsp2,3:=n1;for i:=1 to 4 do gsp2,i+3:=treen1,i+1;for i:=1 to 4 do gsp2,i+3:=treen1,i+1;end;end;_;_;end;end;sp1=sp2sp1=sp2p:=p+1p:=p+1gsp1,j0gsp1,j0sp2:=sp2+1sp2:=sp2+1sp1:=sp

24、1+1sp1:=sp1+1表示队列非空时做变量p是用来存放层次的遍历本结点的所有孩子移动队尾指针为下一个结点的遍历操作作准备移动队头指针第43页/共55页 writeln(maxd=,gsp2,2);writeln(maxd=,gsp2,2);j:=1;k:=g1,2;jmax:=0;j:=1;k:=g1,2;jmax:=0;for i:=2 to sp2 do for i:=2 to sp2 do if if then j:=j+1then j:=j+1 else begin else begin if jjmax then jmax:=j;if jjmax then jmax:=j;_;_

25、;k:=g k:=g,2;,2;end;end;if jjmax then jmax:=j;if jjmax then jmax:=j;writeln(max1=,jmax);writeln(max1=,jmax);end.end.GI,2=kGI,2=kj:=1j:=1打印深度同层次个数累加放在j中j与jmax打擂台，找出最大值注意一层完了，j值要还原，宽度至少为1第44页/共55页例7 7有1010升油在1010升的容器中，另有两个7 7升和3 3升的空容器，现要求用这三个容器倒油，使得最后在1010升和7 7升的容器中各有5 5升油。分析：三个容器可以看作三个变量 C10C10，C7C7

26、，C3C3，每次倒油的可能性只有如下六种情况：C10 C10 向 C7 C7 倒油 C10 C10 向 C3 C3 倒油 C7 C7 向 C10 C10 倒油 C7 C7 向 C3 C3 倒油 C3 C3 向 C10 C10 倒油 C3 C3 向 C7 C7 倒油 第45页/共55页 从一个容器状态（三个容器中油的容量）看，虽然有可能经过上述六种倒油的方法产生六种容器状态，但实际上这六种新产生的容器状态，许多是已经出现过的状态。例如初始状态（10,0,010,0,0）表示 C10=10C10=10，C7=0C7=0，C3=0C3=0，经过上述六种倒油方法只能产生出两种新的容器状态（3,7,03

27、,7,0）和（7,0,37,0,3），再增加一个变量记录当前状态是由什么状态产生的，这样就形成了一个不断扩张新结点的过程，因此这个倒油的过程就可以用队列来记录了。第46页/共55页Typenode=recordc10,c7,c3:integer;pre:0.100;end;Varq:array1.100ofnode;f,r:integer;w10,w7,w3:integer;flag:boolean;三种容器中实际装油量达到目标状态的标志Procedureout;取队头结点Beginw10:=qf.c10;w7:=qf.c7;w3:=qf.c3;End;第47页/共55页Procedurepu

28、sh;入队Varflag1:boolean;队中是否已有同结点的标志Beginflag1:=true;fork:=1tordoif(qk.c10=w10)and(qk.c7=w7)and(qk.c3=w3)thenflag1:=false;Ifflag1thenbeginr:=r+1;qr.c10:=w10;qr.c7:=w7;qr.c3:=w3qr.pre:=fend;End;第48页/共55页Procedurecup;产生新结点的过程Beginout;c10c7Ifw100thenbeginifw10+w7=7thenbeginw10:=w10+w7-7;w7:=7;End;elsebeg

29、inw7:=w10+w7;w10:=0;end;push;if(qr.c10=5)and(qr.c7=5)thenbeginflag:=true;exit;end;end;第49页/共55页out;c10c3Ifw100thenbeginifw10+w3=3thenbeginw10:=w10+w7-3;w3:=3;End;elsebeginw3:=w10+w3;w10:=0;end;push;if(qr.c10=5)and(qr.c7=5)thenbeginflag:=true;exit;end;end;第50页/共55页out;c7c10Ifw70thenbeginw10:=w10+w7;w

30、7:=0;push;if(qr.c10=5)and(qr.c7=5)thenbeginflag:=true;exit;end;end;out;c7c3Ifw70thenbeginifw7+w3=3thenbeginw7:=w7+w3-3;w3:=3;End;elsebeginw3:=w7+w3;w7:=0;endpush;if(qr.c10=5)and(qr.c7=5)thenbeginflag:=true;exit;end;end;第51页/共55页out;c3c10Ifw30thenbeginw10:=w10+w3;w3:=0;push;if(qr.c10=5)and(qr.c7=5)th

31、enbeginflag:=true;exit;end;end;out;c3c7Ifw30thenbeginifw3+w7=7thenbeginw3:=w3+w7-7;w3:=0;endelsebeginw7:=w7+w3;w3:=0;end;push;if(qr.c10=5)and(qr.c7=5)thenbeginflag:=true;exit;end;end;第52页/共55页Procedureprint;Vars:array1.100of0.100;beginwrite(queue:);fori:=1tordowrite(qi.c10:3,qi.c7:3,qi.c3:3,qi.pre:3);s1:=r;i:=1;writeln;whilesi0dobegini:=i+1;si:=qsi-1.pre;end;fork:=i-1downto1dowriteln(qsk.c10:5,qsk.c7:5,qsk.c3:5);end;第53页/共55页Begin主程序f:=1;r:=1;q1.c10:=10;q1.c7:=0;q1.c3:=0;q1.pre:=0;Flag:=false;Repeatcup;f:=f+1;untilflagor(fr);Iffrthenwrite(no)elseprint;End.第54页/共55页感谢您的观看！第55页/共55页