队列的基本操作(xinn).ppt

队列的基本操作,举例1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。举例2：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。,一、队列的定义队列就是允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针r指向队尾元素，即r总是指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指针f指向排头元素的前面。初始时f=r=0。,结论：在队列这种数据结构中，最先插入在元素将是最先被删除；反之最后插入的元素将最后被删除，因此队列又称为“先进先出”（FIFOfirstinfirstout）的线性表。,队列的基本操作：（1）初始化队列Qini(Q)（2）入队QADD(Q,X)（3）出队QDel(Q,X)（4）判断队列是否为空qempty(Q)（5）判断队列是否为满qfull(Q),二、队列的存储结构,1、顺序存储,Constm=队列元素的上限；Typequeue=record队列的类型定义data:array1.mofelemtypef,r:integer;队尾指针和队首指针end;Varq：queue；队列,Constm=队列元素的上限；Typequeue=array1.mofelemtypeVarq：queue；队列f,r:integer;队尾指针和队首指针,二、队列的存储结构,2、链式存储,typelink=celltype;celltype=recorddata:elemtype;next:link;end;varf,r:link;,三、队列的基本运算,1、初始化：设定Q为一空队列：,procedureQini(varQ:queue);beginQ.f:=0;Q.r:=0;end;,2、判队列空：若队列Q为空，则返回值true，否则返回值false。,functionqempty(Q:queue):Boolean;beginqempty:=(Q.f=q.r)end;,functionqfull(Q:queue):Boolean;beginQfull:=（Q.rm);end;,3、判队满：若队列满，则返回值true，否则返回值false。,4、元素进队：若队列Q不满时，把元素X插入到队列Q的队尾，否则返回信息“Overflow”：,procedureQADD(varq:queue;x:elemtype);beginifqfull(Q)thenwriteln(overflow)上溢elsebegin后移队尾指针并插入元素xQ.R:=Q.r+1；Q.dataQ.r:=x；end；elseend；ADD,5、元素出队：若队列Q不空，则把队头元素删除并返回值给X，否则输出信息“Underflow”：,procedureQdel(varQ:queue;varX:elemtype);beginifqempty(Q)thenwriteln(Underflow)下溢elsebegin后移队首指针并取出队首元素Q.fQ.f+1;XQ.dataQ.f；end；elseend;,例1假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。输入：第一行两队的人数第二行舞曲的数目,应用举例,分析：设计两个队列分别存放男士和女士。每对跳舞的人一旦跳完后就回到队尾等待下次被选。如m=3n=2k=6,constmax=10000;vara,b: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;,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.,例2.集合的前N个元素：编一个程序，按递增次序生成集合M的最小的N个数，M的定义如下：(1)数1属于M；(2)如果X属于M，则Y=2*X+1和Z=3*x+1也属于M；(3)此外再没有别的数属于M。,分析：可以用两个队列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,(3)将队列a和队列b的头结点进行比较，可能有三种情况：(A)ahabhb(B)aha=bhb(C)ahabhb将比较的小者取出送入X，取出数的队列的头指针相应加1。(4)重复(2)，(3)直至取出第N项为止。,算法二：,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;,m:=1;i:=1;whilem0thenbeginwrite(i,);m:=m+1;end;i:=i+1;end;end.,编一个程序，找出一条通过迷宫的路径。这里有兰色方块的单元表示走不通，将一只老鼠从入口处经过迷宫到出口处的最短的一条通路打印出来。,例4迷宫问题,入口,出口,分析（1）怎样来存储迷宫？将它变成0，1二维数组。这样上述迷宫可转化为：,（2）老鼠在迷宫中怎样探索路径？有几个方向可以探索呢？*只有三个探索方向的位置。如mg1,1*有五个探索方向的位置。如mg3,1*有八个探索方向的位置。如mg3,2思考：能否都转化为八个方向的探索呢？,这样存储的迷宫数组就转化成：,因此，数组定义为: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）,01,11,10,1-1,0-1,-1-1,-10,-11,这样可以定义一个二维数组记录探索方向。,（3）如何才能记录踪迹，并把探索的踪迹记忆下来呢？,踪迹一般应包括来处和当前位置，可以需要用记录类型Node=recordX,y:integer;Pre:0.r;End;,用一个对队列记忆探索的踪迹：Sqtype=array1.rofnode;,例如：从（1，1）入口到达（6，8），往下探索时队列的情况,（4）如何防止重复探索：将迷宫中的0替换为-1,procedureQini(varsQ:sqtype);beginsQ1.x:=1;sq1.y:=1;Sq1.pre:=0F:=1;r:=1;mg1,1:=-1;end;,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.pre:=f;mgi,j:=-1;end;if(i=m)and(j=n)thenprint;exitend;,F:=f+1End;Writeln(迷宫无路径);End;,如何打印路径？,Procedureprint(varsq:sqtype,r:integer);Begini:=r;repeatwriteln(,sqi.x,sqi.y,);i:=sqi.preuntili=0End;,产生问题：由于顺序存储结构的存储空间属于静态分配，所以，在添加数据元素时，可能会出现没有剩余单元的情况。下面我们讨论一下下图所示的队列，称为“假溢出”现象。,解决方法：将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。采用首尾相接的结构后，形成一个环状，解决假溢出问题，避免数据元素的移动。如图所示。我们将这种形式表示的队列称之为循环队列。,Am-1,Am,Am+1,F,R,空闲区,1,2,3,m-1,m,am,Am-1,F,R,Am+1,循环队列的操作,procedureiniqueue(varQ:equeue);beginQ.f:=m;Q.r:=m;end;,1、初始化：设定Q为一空队列，队首指针和队尾指针均指向存储空间的最后一个位置,2、判队列空：若队列Q为空，则返回值true，否则返回值false。,functionqempty(Q:equeue):Boolean;beginqempty:=(Q.f=Q.r)end;,3、判队满：若队列满，则返回值true，否则返回值false。为了区分队列空和队列满，改用“队尾指针追上队首指针”这一特征作为队列满标志。,functionqfull(Q:equeue):Boolean;beginqfull:=(Q.rmodm)+1=Q.f);end;,4、元素进队：若队列Q不满时，把元素X插入到队列Q的队尾，否则返回信息“Overflow”：,procedureadd(varQ:equeue;X:elemtype);beginifqfull(Q)thenwriteln(Overflow)elsebeginQ.r:=Q.rmodm+1;Q.dataQ.r:=X;endend;,5、元素出队：若队列Q不空，则把队头元素删除并返回值给X，否则输出信息“Underflow”：,proceduredel(varQ:equeue;varX:elemtype);beginifqempty(Q)thenwriteln(Underflow)elsebegin后移队首指针并取出队首元素Q.f:=Q.fmodm+1;X:=Q.dataQ.f；end;end;,例5约瑟夫问题：编号为1，2，n个人按顺时针方向围坐一圈，每人持一个正整数密码，开始给定一个正整数m，从第一个人按顺时针方向自1开始顺序报数，报到m者出围坐的圈子，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人都出围坐的圈子为止，输出出列者的序列。,例如有5人M=18,序号,密码,（1）开始取m=18，从1报数，则序号为3的人出列。,（2）开始取m=3，从4报数，则序号为1的人出列。,（3）开始取m=8，从2报数，则序号为4的人出列。,（4）开始取m=6，从5报数，则序号为2的人出列。,（5）开始取m=5，从5报数，则序号为5的人出列。,出列顺序为：3,1,4,2,5,constmax=30;typepeople=recordnumber,code:array1.maxofintegerend;vara:people;m,n,i,j,s,w,p:integer;beginreadln(m,n);fori:=1tondoa.numberi:=i;fori:=1tondoread(a.codei);,s:=1;forj:=ndownto1dobegins:=(s+m-1)modj;ifs=0thens:=j;w:=s;p:=a.numberw;write(p,);m:=a.codep;fori:=stoj-1doa.numberi:=a.numberi+1;end;end.,综合举例例6问题描述求一棵树的深度与宽度。算法说明树可用数组tree:array1.n,1.5ofinteger;如上图可表示为：1234025670380004910005000060000711120080000900001000001100001213000130000,（1）,（2）,（3）,（4）,（5）,（6）,（7）,（8）,（9）,（10）,（11）,（12）,（13）,本题的数据结构含义，首先要搞清楚：treei,j存储编号为i的结点的第j号孩子（2=jjmaxthenjmax:=j;writeln(max1=,jmax);end.,GI,2=k,j:=1,打印深度,同层次个数累加放在j中,j与jmax打擂台，找出最大值,注意一层完了，j值要还原，宽度至少为1,例7有10升油在10升的容器中，另有两个7升和3升的空容器，现要求用这三个容器倒油，使得最后在10升和7升的容器中各有5升油。分析：三个容器可以看作三个变量C10，C7，C3，每次倒油的可能性只有如下六种情况：C10向C7倒油C10向C3倒油C7向C10倒油C7向C3倒油C3向C10倒油C3向C7倒油,从一个容器状态（三个容器中油的容量）看，虽然有可能经过上述六种倒油的方法产生六种容器状态，但实际上这六种新产生的容器状态，许多是已经出现过的状态。例如初始状态（10,0,0）表示C10=10，C7=0，C3=0，经过上述六种倒油方法只能产生出两种新的容器状态（3,7,0）和（7,0,3），再增加一个变量记录当前状态是由什么状态产生的，这样就形成了一个不断扩张新结点的过程，因此这个倒油的过程就可以用队列来记录了。,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;,Procedurepush;入队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;,Procedurecup;产生新结点的过程Beginout;c10c7Ifw100thenbeginifw10+w7=7thenbeginw10:=w10+w7-7;w7:=7;End;elsebeginw7:=w10+w7;w10:=0;end;push;if(qr.c10=5)and(qr.c7=5)thenbeginflag:=true;exit;end;end;,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;,out;c7c10Ifw70thenbeginw10:=w10+w7;w7:=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;,out;c3c10Ifw30thenbeginw10:=w10+w3;w3:=0;push;if(qr.c10=5)and(qr.c7=5)thenbeginflag:=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;,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;,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.,