《队列的基本操作(xinn).ppt》由会员分享，可在线阅读，更多相关《队列的基本操作(xinn).ppt（56页珍藏版）》请在三一办公上搜索。
1、队列的基本操作,举例1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。举例2：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。,一、队列的定义队列就是允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针r指向队尾元素，即r总是指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指针f指向排头元素的前面。初始时f=r=0。,结论：在队列这种数据结构中，最先插入在元素将是最先被删除；反之最后插入的元素将最后被删除，因此队列又称为“先进先出”（FIFOfirst in first out）的线性表。,队列的基本操作：（1）初始化队列 Qini
2、(Q)（2）入队 QADD(Q,X)（3）出队 QDel(Q,X)（4）判断队列是否为空 qempty(Q)（5）判断队列是否为满qfull(Q),二、队列的存储结构,1、顺序存储,Const m=队列元素的上限；Type queue=record 队列的类型定义 data:array1.m of elemtype f,r:integer;队尾指针和队首指针 end;Var q：queue；队列,Const m=队列元素的上限；Type queue=array1.m of elemtype Var q：queue；队列 f,r:integer;队尾指针和队首指针,二、队列的存储结构,2、链式存
3、储,type link=celltype;celltype=record data:elemtype;next:link;end;var f,r:link;,三、队列的基本运算,1、初始化：设定Q为一空队列：,procedure Qini(var Q:queue);beginQ.f:=0;Q.r:=0;end;,2、判队列空：若队列Q为空，则返回值true，否则返回值false。,function qempty(Q:queue):Boolean;begin qempty:=(Q.f=q.r)end;,function qfull(Q:queue):Boolean;beginQfull:=（Q.
4、rm);end;,3、判队满：若队列满，则返回值true，否则返回值false。,4、元素进队：若队列Q不满时，把元素X插入到队列Q的队尾，否则返回信息“Overflow”：,procedure QADD(var q:queue;x:elemtype);begin if qfull(Q)then writeln(overflow)上溢 else begin 后移队尾指针并插入元素x Q.R:=Q.r+1；Q.dataQ.r:=x；end；elseend；ADD,5、元素出队：若队列Q不空，则把队头元素删除并返回值给X，否则输出信息“Underflow”：,procedure Qdel(var
5、Q:queue;var X:elemtype);begin if qempty(Q)then writeln(Underflow)下溢 else begin 后移队首指针并取出队首元素 Q.fQ.f+1;XQ.dataQ.f；end；else end;,例1假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。输入：第一行两队的人数 第二行舞曲的数目,应用举例,分析：设计两个队列分别存放男士和女士。每对跳舞的
6、人一旦跳完后就回到队尾等待下次被选。如m=3 n=2 k=6,const max=10000;var a,b:array1.max of integer;m,n,k1,k,i,f1,r1,f2,r2:integer;begin readln(m，n);for i:=1 to m do ai:=i;for i:=1 to n do bi:=i;readln(k);k1:=1;f1:=1;r1:=m;f2:=1;r2:=n;,repeat writeln(af1:3,bf1:3);r1:=r1+1;ar1:=af1;f1:=f1+1;r2:=r2+1;br2:=bf2;f2:=f2+1;k1:=k
7、1+1;until k1k end.,例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的头结点进行比较，可能有三种情况：
8、(A)ahabhb(B)aha=bhb(C)ahabhb 将比较的小者取出送入X，取出数的队列的头指针相应加1。(4)重复(2)，(3)直至取出第N项为止。,算法二：,var a:array1.30000 of 0.1;f,t,n,m,i:integer;begin readln(n);for i:=1 to 30000 do ai:=0;a1:=1;f:=1;k:=1;t:=0;while t=n do begin af*2+1:=1;af*3+1:=1;f:=f+1;while af=0 do f:=f+1;T:=t+1;end;,m:=1;i:=1;while m0 then begin
9、 write(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+1 of
10、 integer;,而探索方向则变成了统一的情况，都探索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）,0 1,1 1,1 0,1-1,0-1,-1-1,-1 0,-1 1,这样可以定义一个二维数组记录探索方向。,（3）如何才能记录踪迹，并把探索的踪迹记忆下来呢？,踪迹一般应包括来处和当前位置，可以需要用记录类型Node=record X,y:integer;Pre:0.r;End;,用一个对队列记忆探索的踪迹：Sqtype=array1.r of node;,例如：从（1，
11、1）入口到达（6，8），往下探索时队列的情况,（4）如何防止重复探索：将迷宫中的0替换为-1,procedure Qini(var sQ:sqtype);beginsQ1.x:=1;sq1.y:=1;Sq1.pre:=0F:=1;r:=1;mg1,1:=-1;end;,Procedure mglj(var sq:sqtype);Begin Sqini;While f=r do Begin x:=sqf.x;y:=sqf.y;for v:=1 to 8 do begin i:=x+zlv,1;j:=y+zlv,2;if mgi,j=0 then begin r:=r+1;sqr.x:=i;sqr
12、.y:=j;sqr.pre:=f;mgi,j:=-1;end;if(i=m)and(j=n)then print;exit end;,F:=f+1End;Writeln(迷宫无路径);End;,如何打印路径？,Procedure print(var sq:sqtype,r:integer);Begin i:=r;repeat writeln(,sqi.x,sqi.y,);i:=sqi.pre until i=0End;,产生问题：由于顺序存储结构的存储空间属于静态分配，所以，在添加数据元素时，可能会出现没有剩余单元的情况。下面我们讨论一下下图所示的队列，称为“假溢出”现象。,解决方法：将元素加
13、入到第一个位置，即将存储空间的第一个位置作为队尾。采用首尾相接的结构后，形成一个环状，解决假溢出问题，避免数据元素的移动。如图所示。我们将这种形式表示的队列称之为循环队列。,Am-1,Am,Am+1,F,R,空闲区,1,2,3,m-1,m,am,Am-1,F,R,Am+1,循环队列的操作,procedure iniqueue(var Q:equeue);beginQ.f:=m;Q.r:=m;end;,1、初始化：设定Q为一空队列，队首指针和队尾指针均指向存储空间的最后一个位置,2、判队列空：若队列Q为空，则返回值true，否则返回值false。,function qempty(Q:equeue
14、):Boolean;beginqempty:=(Q.f=Q.r)end;,3、判队满：若队列满，则返回值true，否则返回值false。为了区分队列空和队列满，改用“队尾指针追上队首指针”这一特征作为队列满标志。,function qfull(Q:equeue):Boolean;beginqfull:=(Q.r mod m)+1=Q.f);end;,4、元素进队：若队列Q不满时，把元素X插入到队列Q的队尾，否则返回信息“Overflow”：,procedure add(var Q:equeue;X:elemtype);begin if qfull(Q)then writeln(Overflow
15、)else begin Q.r:=Q.r mod m+1;Q.dataQ.r:=X;endend;,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;,例5约瑟夫问题：编号为1，2，n个人按顺时针方向围坐一圈，每人持一个正整数密码，开始给定一个正整数m，从第一个
16、人按顺时针方向自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,const max=30;type people=record numbe
17、r,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);,s:=1;for j:=n downto 1 do begin s:=(s+m-1)mod j;if s=0 then s:=j;w:=s;p:=a.numberw;write(p,);m:=a.codep;for i:=s to j-1 do a.numberi:=a.numberi+1;end;en
18、d.,综合举例例6问题描述求一棵树的深度与宽度。算法说明树可用数组 tree:array1.n,1.5of integer;如上图可表示为：1 2 3 4 02 5 6 7 03 8 0 0 049 10 0 050 0 0 060 0 0 0711 12 0 080 0 0 090 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）,（12）,（13）,本题的数据结构含义，首先要搞清楚：treei,j存储编号为i的结点的第j号孩子（2=j=5,即最多4个孩
19、子），treei,j=0表示不存在；,在求解的过程中，用到数组G:ARRAY1.N,1.7 OF INTEGER；其中：GI,1表示父结点，GI,2表示层次，GI,3表示本结点号，GI,4GI,7 表示子女结点；同时，设2个指针SP1（取数指针），SP2（存数指针）,注意：gi,k实质上是一个队列，sp1为队列头指针,sp2为队列尾指针。,程序清单：program exp3;const n=13;var i,j,k,sp1,sp2,n1,n2,jmax,p:integer;tree:array1.n,1.5of integer;g:array1.n,1.7of integer;begin fo
20、r i:=1 to n do begin treei,1:=i;for j:=2 to 5 do read(treei,j);readln;end;,treei,j=0表示i结点不存在,sp1:=1;sp2:=1;g1,1:=0;g1,2:=1;g1,3:=1;for i:=4 to 7 do g1,i:=tree1,i-2;while_do begin p:=gsp1,2;n2:=gsp1,3;_;j:=4;while _do begin n1:=gsp1,j;j:=j+1;_;gsp2,1:=n2;gsp2,2:=p;gsp2,3:=n1;for i:=1 to 4 do gsp2,i+3
21、:=treen1,i+1;end;_;end;,sp1=sp2,p:=p+1,gsp1,j0,sp2:=sp2+1,sp1:=sp1+1,表示队列非空时做,变量p是用来存放层次的,遍历本结点的所有孩子,移动队尾指针,为下一个结点的遍历操作作准备移动队头指针,writeln(maxd=,gsp2,2);j:=1;k:=g1,2;jmax:=0;for i:=2 to sp2 do if then j:=j+1 else begin if jjmax then jmax:=j;_;k:=g,2;end;if jjmax then jmax:=j;writeln(max1=,jmax);end.,G
22、I,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 倒油,从一个容器状态（三个容器中油的容量）看，虽然有可能经过上述六种倒油的方法产生六种容器状态，但实际上这六种新产生的容器状态
23、，许多是已经出现过的状态。例如初始状态（10,0,0）表示 C10=10，C7=0，C3=0，经过上述六种倒油方法只能产生出两种新的容器状态（3,7,0）和（7,0,3），再增加一个变量记录当前状态是由什么状态产生的，这样就形成了一个不断扩张新结点的过程，因此这个倒油的过程就可以用队列来记录了。,Type node=record c10,c7,c3:integer;pre:0.100;end;Var q:array 1.100 of node;f,r:integer;w10,w7,w3:integer;flag:boolean;,Procedure out;取队头结点Begin w10:=qf
24、.c10;w7:=qf.c7;w3:=qf.c3;End;,Procedure push;入队Var flag1:boolean;队中是否已有同结点的标志Begin flag1:=true;for k:=1 to r do if(qk.c10=w10)and(qk.c7=w7)and(qk.c3=w3)then flag1:=false;If flag1 then begin r:=r+1;qr.c10:=w10;qr.c7:=w7;qr.c3:=w3 qr.pre:=f end;End;,Procedure cup;产生新结点的过程Begin out;c10c7If w100 then be
25、gin if w10+w7=7 then begin w10:=w10+w7-7;w7:=7;End;else begin w7:=w10+w7;w10:=0;end;push;if(qr.c10=5)and(qr.c7=5)then begin flag:=true;exit;end;end;,out;c10c3If w100 then begin if w10+w3=3 then begin w10:=w10+w7-3;w3:=3;End;else begin w3:=w10+w3;w10:=0;end;push;if(qr.c10=5)and(qr.c7=5)then begin fla
26、g:=true;exit;end;end;,out;c7c10If w70 then begin w10:=w10+w7;w7:=0;push;if(qr.c10=5)and(qr.c7=5)then begin flag:=true;exit;end;end;,out;c7c3If w70 then begin if w7+w3=3 then begin w7:=w7+w3-3;w3:=3;End;else begin w3:=w7+w3;w7:=0;end push;if(qr.c10=5)and(qr.c7=5)then begin flag:=true;exit;end;end;,ou
27、t;c3c10If w30 then begin w10:=w10+w3;w3:=0;push;if(qr.c10=5)and(qr.c7=5)then begin flag:=true;exit;end;end;,out;c3c7If w30 then begin if w3+w7=7then begin w3:=w3+w7-7;w3:=0;end else begin w7:=w7+w3;w3:=0;end;push;if(qr.c10=5)and(qr.c7=5)then begin flag:=true;exit;end;end;,Procedure print;Var s:array
28、1.100 of 0.100;begin write(queue:);for i:=1 to r do write(qi.c10:3,qi.c7:3,qi.c3:3,qi.pre:3);s1:=r;i:=1;writeln;while si0 do begin i:=i+1;si:=qsi-1.pre;end;for k:=i-1 downto 1 do writeln(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;Repeat cup;f:=f+1;until flag or(fr);If fr then write(no)else print;End.,
