《2007第五讲队列的基本操作(xinn).ppt》由会员分享，可在线阅读，更多相关《2007第五讲队列的基本操作(xinn).ppt（56页珍藏版）》请在三一文库上搜索。
1、队列的基本操作,举例1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。 举例2：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。,一、队列的定义 队列就是允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针r指向队尾元素，即r总是指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指针f指向排头元素的前面。初始时f=r=0。,结论：在队列这种数据结构中，最先插入在元素将是最先被删除；反之最后插入的元素将最后被删除，因此队列又称为“先进先出”（FIFOfirst in first out）的线性表。,队列的基本操作： （1）初始化队列 Q
2、ini (Q) （2）入队 QADD(Q,X) （3）出队 QDel(Q,X) （4）判断队列是否为空 qempty(Q) （5）判断队列是否为满qfull(Q),二、队列的存储结构,1、顺序存储,Const m=队列元素的上限； Type queue=record 队列的类型定义 data : array1m of elemtype f, r: integer ; 队尾指针和队首指针 end; Var q：queue； 队列,Const m=队列元素的上限； Type queue=array1m of elemtype Var q：queue； 队列 f, r: integer ; 队尾指针
3、和队首指针,二、队列的存储结构,2、链式存储,type link= celltype ; celltype=record data:elemtype; next:link; end; var f,r:link;,三、队列的基本运算,1、初始化：设定Q为一空队列：,procedure Qini (var Q:queue); begin Q.f:=0; Q.r:=0; end;,2、判队列空：若队列Q为空，则返回值true，否则返回值false。,function qempty(Q:queue):Boolean; begin qempty:=(Q.f=q.r) end;,function qful
4、l(Q:queue):Boolean; begin Qfull:=（Q.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；else end；ADD,5、元素出队：若队列Q不空，则把队头元素删除并
5、返回值给X，否则输出信息“Underflow”：,procedure Qdel(var 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:array1max 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)
7、; r1:=r1+1;ar1:=af1; f1:=f1+1 ; r2:=r2+1;br2:=bf2; f2:=f2+1; k1:=k1+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
8、分别放入队列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项为止。,算法二：,var a:array130000 of 01; 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:=
9、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 write(i, ); m:=m+1; end; i:=i+1; end; end.,编一个程序，找出一条通过迷宫的路径。这里有兰色方块的单元表示走不通，将一只老鼠从入口处经过迷宫到出口处的最短的一条通路打印出来。,例4迷宫问题,入口,出口,分析（1）怎样来存储迷宫？将它变成0，1二维数组。这样上述迷宫可转化为：,（2）老鼠在迷宫中怎样探索路径？有几个方向可以探索呢？ *只有三个探索方向的位置。如mg1,1 *有五个探索方
10、向的位置。如mg3,1 *有八个探索方向的位置。如mg3,2 思考：能否都转化为八个方向的探索呢？,这样存储的迷宫数组就转化成：,因此，数组定义为: Mg:array0m+1,0n+1 of 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）如何才能记录踪迹，并把探索的踪迹记忆下来呢？,踪迹一般应包括来处
11、和当前位置，可以需要用记录类型 Node=record X,y:integer; Pre:0r; End;,用一个对队列记忆探索的踪迹： Sqtype=array1r of node;,例如：从（1，1）入口到达（6，8），往下探索时队列的情况,（4）如何防止重复探索：将迷宫中的0替换为-1,procedure Qini(var sQ:sqtype); begin sQ1.x:=1;sq1.y:=1; Sq1.pre:=0 F:=1;r:=1;mg1,1:=-1; end;,Procedure mglj(var sq:sqtype); Begin Sqini; While f=r do Beg
12、in 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.y:=j;sqr.pre:=f; mgi,j:=-1; end; if (i=m) and (j=n) then print;exit end;,F:=f+1 End; Writeln(迷宫无路径); End;,如何打印路径？,Procedure print(var sq:sqtype,r:integer); Begin i:=r; repeat writeln(,sqi.
13、x,sqi.y,); i:=sqi.pre until i=0 End;,产生问题：由于顺序存储结构的存储空间属于静态分配，所以，在添加数据元素时，可能会出现没有剩余单元的情况。下面我们讨论一下下图所示的队列，称为“假溢出”现象。,解决方法：将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。采用首尾相接的结构后，形成一个环状，解决假溢出问题，避免数据元素的移动。如图所示。我们将这种形式表示的队列称之为循环队列。,Am-1,Am,Am+1,F,R,空闲区,1,2,3,m-1,m,am,Am-1,F,R,Am+1,循环队列的操作,procedure iniqueue(var Q:equeu
14、e); begin Q.f:=m;Q.r:=m; end;,1、初始化：设定Q为一空队列，队首指针和队尾指针均指向存储空间的最后一个位置,2、判队列空：若队列Q为空，则返回值true，否则返回值false。,function qempty(Q:equeue):Boolean; begin qempty:=(Q.f=Q.r) end;,3、判队满：若队列满，则返回值true，否则返回值false。为了区分队列空和队列满，改用“队尾指针追上队首指针” 这一特征作为队列满标志。,function qfull(Q:equeue):Boolean; begin qfull:=(Q.r mod m)+1=
15、Q.f); end;,4、元素进队：若队列Q不满时，把元素X插入到队列Q的队尾，否则返回信息“Overflow”：,procedure add(var Q:equeue;X:elemtype); begin if qfull(Q) then writeln(Overflow) else begin Q.r:=Q.r mod m+1; Q.dataQ.r:=X; end end;,5、元素出队：若队列Q不空，则把队头元素删除并返回值给X，否则输出信息“Underflow”：,procedure del(var Q:equeue;var X:elemtype); begin if qempty(Q
16、) then writeln(Underflow) else begin后移队首指针并取出队首元素 Q.f:=Q.f mod m+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
17、，从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 number,code:array1max 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);
18、,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; end.,综合举例例6问题描述求一棵树的深度与宽度。 算法说明树可用数组 tree:array1n,15of integer; 如上图可表示为： 1 2 3 4 0 2 5 6 7 0 3 8 0 0 0 4 9 10 0 0 5 0 0 0 0 6 0 0 0 0 7 11 1
19、2 0 0 8 0 0 0 0 9 0 0 0 0 10 0 0 0 0 11 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个孩子），treei,j=0表示不存在；,在求解的过程中，用到数组G:ARRAY1N,17 OF INTEGER； 其中：GI,1表示父结点， GI,2表示层次， GI,3表示本结点号， GI,4GI,7 表示子女结点； 同时，设2个指针SP1（
20、取数指针）， SP2（存数指针）,注意：gi,k实质上是一个队列，sp1为队列头指针,sp2为队列尾指针。,程序清单： program exp3; const n=13; var i,j,k,sp1,sp2,n1,n2,jmax,p:integer; tree:array1n,15of integer; g :array1n,17of integer; begin for 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,
21、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:=treen1,i+1; end; _; end;,sp1=sp2,p:=p+1,gsp1,j0,sp2:=sp2+1,sp1:=sp1+1,表示队列非空时做,变量p是用来存放层次的,遍历本结点的所有孩子
22、,移动队尾指针,为下一个结点的遍历操作作准备移动队头指针,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.,GI,2=k,j:=1,打印深度,同层次个数累加放在j中,j与jmax打擂台，找出最大值,注意一层完了，j值要还原，宽度至少为1,例7有10升油在10升的容器中，另有两个7升和3升的空容
23、器，现要求用这三个容器倒油，使得最后在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），再增加
24、一个变量记录当前状态是由什么状态产生的，这样就形成了一个不断扩张新结点的过程，因此这个倒油的过程就可以用队列来记录了。,Type node=record c10,c7,c3:integer; pre:0100; end; Var q:array 1100 of node; f,r:integer; w10,w7,w3:integer; flag:boolean;,Procedure out; 取队头结点 Begin w10:=qf.c10;w7:=qf.c7;w3:=qf.c3; End;,Procedure push; 入队 Var flag1:boolean; 队中是否已有同结点的标志 B
25、egin 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; c10c7 If w100 then begin if w10+w7=7 then begin w10:=w10+w7-7;w7:=7; End; else begin
26、 w7:=w10+w7; w10:=0; end; push; if (qr.c10=5) and (qr.c7=5) then begin flag:=true; exit; end; end;,out; c10c3 If 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 flag:=true; exit; end; end;,out; c7c10 If
27、 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; c7c3 If 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;,out; c3c10 I
28、f 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; c3c7 If 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 pri
29、nt; Var s:array1100 of 0100; 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.,