队列的基本操作xinn课件

《队列的基本操作xinn课件》由会员分享，可在线阅读，更多相关《队列的基本操作xinn课件（56页珍藏版）》请在金锄头文库上搜索。

1、第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营队列的基本操作队列的基本操作 举例举例1：到医院看病，首先需要到挂：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。号处挂号，然后，按号码顺序救诊。举例举例2：乘坐公共汽车，应该在车站：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。排队，车来后，按顺序上车。出队出队进队进队A1 A2 A3 A4AN-1 ANF（队头）（队头）R（队尾）（队尾）第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营一、队列的定义

2、一、队列的定义队列就是允许在一端进行插入，在另一队列就是允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针称为队尾，通常用一个队尾指针r r指向指向队尾元素，即队尾元素，即r r总是指向最后被插入的总是指向最后被插入的元素；允许删除的一端称为队首，通常元素；允许删除的一端称为队首，通常也用一个队首指针也用一个队首指针f f指向排头元素的前指向排头元素的前面。初始时面。初始时f=r=0f=r=0。第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营结论：在队列这种

3、数据结构中，最先结论：在队列这种数据结构中，最先插入在元素将是最先被删除；反之最插入在元素将是最先被删除；反之最后插入的元素将最后被删除，因此队后插入的元素将最后被删除，因此队列又称为列又称为“先进先出先进先出”（FIFOfirstinfirstout）的线性表。）的线性表。第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营队列的基本操作：队列的基本操作：（1）初始化队列）初始化队列Qini(Q) （2）入队）入队QADD(Q,X) （3）出队）出队QDel(Q,X)（4）判断队列是否为空）判断队列是否为空qempty(Q)（5）

4、判断队列是否为满）判断队列是否为满qfull(Q) 第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营二、队列的存储结构二、队列的存储结构 1、顺序存储、顺序存储 Const m=队列元素的上限；队列元素的上限； Type queue=record 队列的类型定义队列的类型定义 data : array1.m of elemtype f, r: integer ; 队尾指针和队首指针队尾指针和队首指针 end;Var q：queue； 队列队列Const m=队列元素的上限；队列元素的上限；Type queue=array1.m

5、of elemtype Var q：queue； 队列队列 f, r: integer ; 队尾指针和队首指针队尾指针和队首指针第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营二、队列的存储结构二、队列的存储结构 2、链式存储、链式存储 FA1A2ANRtype link= celltype ; celltype=record data:elemtype; next:link; end; var f,r:link;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营三

6、、队列的基本运算三、队列的基本运算1、初始化：设定、初始化：设定Q为一空队列：为一空队列：procedure Qini (var Q:queue);procedure Qini (var Q:queue);beginbeginQ.f:=0;Q.f:=0;Q.r:=0;Q.r:=0;end;end;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营2 2、判队列空：若队列、判队列空：若队列Q Q为空，则返回值为空，则返回值truetrue，否则返回值，否则返回值falsefalse。function qempty(Q:queue):

7、Boolean;begin qempty:=(Q.f=q.r)end;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营function qfull(Q:queue):Boolean;beginQfull:=（Q.rm);end;3、判队满：若队列满，则返回值、判队满：若队列满，则返回值true，否，否则返回值则返回值false。第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营4、元素进队：若队列、元素进队：若队列Q不满时，把元不满时，把元素素X插入到队列插入到队列

8、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第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营5、元素出队：若队列、元素出队：若队列Q不空，则把队头不空，则把队头元素删除并返回值给元素删除并

9、返回值给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;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营例例1假设在周末舞会上，男士们和女士们假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队

10、。跳舞开始时，进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。程序，模拟上述舞伴配对问题。输入：第一行两队的人数输入：第一行两队的人数 第二行舞曲的数目第二行舞曲的数目应用举例应用举例第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬

11、令营分析：分析：设计两个队列分别存放男士和女士。设计两个队列分别存放男士和女士。每对跳舞的人一旦跳完后就回到队尾等待每对跳舞的人一旦跳完后就回到队尾等待下次被选。如下次被选。如m=3 n=2 k=6A1 2 3 1 2 31 2 1 2 1 2BF1R1F2R2第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营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

12、 ai:=i; for i:=1 to n do bi:=i;readln(k); k1:=1; f1:=1;r1:=m;f2:=1;r2:=n;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营repeat writeln(af1:3, ,bf1:3); r1:=r1+1;ar1:=af1; f1:=f1+1 ; r2:=r2+1;br2:=bf2; f2:=f2+1; k1:=k1+1; until k1k end.第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令

13、营例例2.集合的前集合的前N个元素：编一个程序，按递增个元素：编一个程序，按递增次序生成集合次序生成集合M的最小的的最小的N个数，个数，M的定义如的定义如下：下： (1)数数1属于属于M； (2)如果如果X属于属于M，则，则Y=2*X+1和和Z=3*x+1也属于也属于M； (3)此外再没有别的数属于此外再没有别的数属于M。 第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营分析：可以用两个队列分析：可以用两个队列a和和b来存放新产生来存放新产生的数，然后通过比较大小决定是否输出，的数，然后通过比较大小决定是否输出，具体方法如下：具

14、体方法如下： (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 第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营(3)将队列将队列a和队列和队列b的头结点进行比较，的头结点进行比较，可能有三种情况：可能有三种情况： (A)ahabhb (B)aha=bhb (

15、C)ahabhb 将比较的小者取出送入将比较的小者取出送入X，取出数的队，取出数的队列的头指针相应加列的头指针相应加1。(4)重复重复(2)，(3)直至取出第直至取出第N项为止。项为止。第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营算法二：算法二：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;

16、af*3+1:=1; f:=f+1; while af=0 do f:=f+1; T:=t+1; end;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营m:=1;i:=1; while m=n do begin if ai0 then begin write(i, ); m:=m+1; end; i:=i+1; end; end.第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营编一个程序，找出一条通一个程序，找出一条通过迷迷宫的路径。的路径。这里里有有兰色方色方

17、块的的单元表示走不通，将一只老鼠从入元表示走不通，将一只老鼠从入口口处经过迷迷宫到出口到出口处的最短的一条通路打印出的最短的一条通路打印出来。来。例例4迷宫问题迷宫问题入口入口 出口出口第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营分析分析（1）怎样来存储迷宫？将它变成）怎样来存储迷宫？将它变成0，1二维数组。这样上述迷宫可转化为：二维数组。这样上述迷宫可转化为：011101111010101001001111011100111001100001100110第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20

18、072007年冬令营年冬令营年冬令营年冬令营（2）老鼠在迷宫中怎样探索路径？有几）老鼠在迷宫中怎样探索路径？有几个方向可以探索呢？个方向可以探索呢？*只有三个探索方向的位置。如只有三个探索方向的位置。如mg1,1*有五个探索方向的位置。如有五个探索方向的位置。如mg3,1*有八个探索方向的位置。如有八个探索方向的位置。如mg3,2思考：能否都转化为八个方向的探索呢？思考：能否都转化为八个方向的探索呢？第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营这样存储的迷宫数组就转化成：这样存储的迷宫数组就转化成：1111111111101

19、1101111110101010110100111111011100111110011000110110011011111111111第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营因此，数组定义为因此，数组定义为:Mg:array0.m+1,0.n+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）Dx Dy0 11 11 0

20、1 -10 -1-1 -1-1 0-1 1这样可以定义一个二维数组记这样可以定义一个二维数组记录探索方向。录探索方向。第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营（3）如何才能记录踪迹，并把探索的踪）如何才能记录踪迹，并把探索的踪迹记忆下来呢？迹记忆下来呢？踪迹一般应包括来处和当前位置，可以需踪迹一般应包括来处和当前位置，可以需要用记录类型要用记录类型Node=record X,y:integer; Pre:0.r; End;用一个对队列记忆探索的踪迹：用一个对队列记忆探索的踪迹：Sqtype=array1.r of nod

21、e;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营例如：从（例如：从（1，1）入口到达（）入口到达（6，8），往下探），往下探索时队列的情况索时队列的情况11111111111011101111110101010110100111111011100111110011000110110011011111111111第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营（4）如何防止重复探索：将迷宫中的）如何防止重复探索：将迷宫中的0替换替换为为-1procedure Q

22、ini(var sQ:sqtype);procedure Qini(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;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营Procedure mglj(var sq:sqtype);Begin Sqini;While f=r do Begin x:=sqf.x;y:=sqf.y;

23、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; 第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营F:=f+1End;Writeln(迷宫无路径迷宫无路径);End;如何打印路径？如何打印路径？Procedure print(var sq:sqtype,r:

24、integer);Begin i:=r; repeat writeln(,sqi.x,sqi.y,); i:=sqi.pre until i=0End;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营产生问题：由于顺序存储结构的存储产生问题：由于顺序存储结构的存储空间属于静态分配，所以，在添加数空间属于静态分配，所以，在添加数据元素时，可能会出现没有剩余单元据元素时，可能会出现没有剩余单元的情况。下面我们讨论一下下图所示的情况。下面我们讨论一下下图所示的队列，称为的队列，称为“假溢出假溢出”现象。现象。第六讲第六讲第六讲第六讲

25、队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营解决方法：将元素加入到第一个位置，解决方法：将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。即将存储空间的第一个位置作为队尾。采用首尾相接的结构后，形成一个环状，采用首尾相接的结构后，形成一个环状，解决假溢出问题，避免数据元素的移动。解决假溢出问题，避免数据元素的移动。如图所示。我们将这种形式表示的队列如图所示。我们将这种形式表示的队列称之为循环队列。称之为循环队列。1234mAm-1AmAm+1FR空闲区空闲区123m-1mamAm-1FRAm+1第六讲第六讲第六讲第六讲 队列及应用队列及应用队

26、列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营循环队列的操作循环队列的操作 procedure iniqueue(var Q:equeue);beginQ.f:=m;Q.r:=m;end;1、初始化：设定、初始化：设定Q为一空队列，队首指为一空队列，队首指针和队尾指针均指向存储空间的最后一针和队尾指针均指向存储空间的最后一个位置个位置第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营2、判队列空：若队列、判队列空：若队列Q为空，则返回值为空，则返回值true，否则返回值，否则返回值false。 function

27、 qempty(Q:equeue):Boolean;beginqempty:=(Q.f=Q.r)end;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营3、判队满：若队列满，则返回值、判队满：若队列满，则返回值true，否则返回值否则返回值false。为了区分队列空和队。为了区分队列空和队列满，改用列满，改用“队尾指针追上队首指针队尾指针追上队首指针” 这一特征作为队列满标志。这一特征作为队列满标志。 function qfull(Q:equeue):Boolean;beginqfull:=(Q.r mod m)+1=Q.f);

28、end;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营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; endend;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应

29、用20072007年冬令营年冬令营年冬令营年冬令营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;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用

30、20072007年冬令营年冬令营年冬令营年冬令营例例5约瑟夫问题：编号为约瑟夫问题：编号为1，2，n个人个人按顺时针方向围坐一圈，每人持一个正整按顺时针方向围坐一圈，每人持一个正整数密码，开始给定一个正整数数密码，开始给定一个正整数m，从第一，从第一个人按顺时针方向自个人按顺时针方向自1开始顺序报数，报开始顺序报数，报到到m者出围坐的圈子，不再参加报数，这者出围坐的圈子，不再参加报数，这时将出列者的密码作为时将出列者的密码作为m，从出列者顺时，从出列者顺时针方向的下一个人开始重新从针方向的下一个人开始重新从1报数，如报数，如此下去，直到所有人都出围坐的圈子为止，此下去，直到所有人都出围坐的圈子

31、为止，输出出列者的序列。输出出列者的序列。第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营例如有例如有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的人出列。的人出列。

32、55（5）开始取）开始取m=5，从，从5报数，报数，则序号为则序号为5的人出列。的人出列。出列顺序为：出列顺序为：3,1,4,2,5第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营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

33、(a.codei); 第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营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:array1.

34、n,1.5ofinteger;如上图可表示为：如上图可表示为：1 2 34025 6703 8 0004 9 10005 0 0006 0 0007 1112008 0 0009 0 000100000110 0001213000130000（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）本题的数据结构含义，首本题的数据结构含义，首先要搞清楚：先要搞清楚：treei,j存储存储编号为编号为i的结点的第的结点的第j号孩号孩子（子（2=j=5,即最多即最多4个个孩子），孩子），treei,j=0表示表示不存在；不存在；第六讲第六讲第六讲第六讲 队列及应用队列及

35、应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营在求解的过程中，用到数组在求解的过程中，用到数组G:ARRAY1.N,1.7OFINTEGER；其中：其中：GI,1表示父结点，表示父结点，GI,2表示层次，表示层次，GI,3表示本结点号，表示本结点号，GI,4GI,7表示子女结点；表示子女结点；同时，设同时，设2个指针个指针SP1（取数指针），（取数指针），SP2（存数指针）（存数指针）注意：注意：gi,k实质上是实质上是一个队列，一个队列，sp1为队为队列头指针列头指针,sp2为队列为队列尾指针。尾指针。第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应

36、用20072007年冬令营年冬令营年冬令营年冬令营 程序清单程序清单 ：program exprogram exp3;p3;const n=13;const n=13;var 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 d

37、o 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 read (treei,j); read (treei,j); readln; readln; end; end;treei,j=0表示表示i结点不结点不存在存在第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营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:

38、=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; 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;

39、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:=sp1+1sp1:=sp1+1表示队列非空时做表示队列非空时做变量变量p是用来存放层次的是用来存放层次的遍历遍历本结本结点的点的所有所有孩子孩子移动队尾指针移动队尾指针为下一个结点的为下一个结点的遍历操作作准备遍历操作作准备移动队头指针移动队头指针第六讲第六讲第

40、六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营 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; _; _; k:=g k:=g,2;,2; en

41、d; 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第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营例例7 7有有1010升油在升油在1010升的容器中，另有两个升的容

42、器中，另有两个7 7升和升和3 3升升的空容器，现要求用这三个容器倒油，使得最后在的空容器，现要求用这三个容器倒油，使得最后在1010升和升和7 7升的容器中各有升的容器中各有5 5升油。升油。分析：分析： 三个容器可以看作三个变量三个容器可以看作三个变量 C10 C10，C7C7，C3C3，每次倒油的可能性只有如下六种情况：，每次倒油的可能性只有如下六种情况： C10 C10 向向 C7 C7 倒油倒油 C10 C10 向向 C3 C3 倒油倒油 C7 C7 向向 C10 C10 倒油倒油 C7 C7 向向 C3 C3 倒油倒油 C3 C3 向向 C10 C10 倒油倒油 C3 C3 向向

43、C7 C7 倒油倒油 第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营 从一个容器状从一个容器状态（三个容器中油的容量）（三个容器中油的容量）看，看，虽然有可能然有可能经过上述六种倒油的方法上述六种倒油的方法产生六种容器状生六种容器状态，但，但实际上上这六种新六种新产生的生的容器状容器状态，许多是已多是已经出出现过的状的状态。例如。例如初始状初始状态（10,0,010,0,0）表示）表示 C10=10 C10=10，C7=0C7=0，C3=0C3=0，经过上述六种倒油方法只能上述六种倒油方法只能产生出两生出两种新的容器状种新的容

44、器状态（3,7,03,7,0）和（）和（7,0,37,0,3），再），再增加一个增加一个变量量记录当前状当前状态是由什么状是由什么状态产生的，生的，这样就形成了一个不断就形成了一个不断扩张新新结点的点的过程，因此程，因此这个倒油的个倒油的过程就可以用程就可以用队列来列来记录了。了。第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营Type node=record c10,c7,c3:integer; pre:0.100; end;Var q:array 1.100 of node; f,r:integer; w10,w7,w3:i

45、nteger; flag:boolean;三种容器中实际装油量三种容器中实际装油量达到目标状态的标志达到目标状态的标志Procedure out; 取队头结点取队头结点Begin w10:=qf.c10;w7:=qf.c7;w3:=qf.c3;End;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营Procedure push; 入队入队Var flag1:boolean; 队中是否已有同结点的标志队中是否已有同结点的标志Begin flag1:=true; for k:=1 to r do if (qk.c10=w10) an

46、d (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;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营Procedure cup;产生新结点的过程产生新结点的过程Begin out; c10c7If w100 then begin if w10+w7=7 then begin w10:=w10+w7-7;w7:=7; End; el

47、se begin w7:=w10+w7; w10:=0; end; push; if (qr.c10=5) and (qr.c7=5) then begin flag:=true; exit; end; end;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营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

48、 (qr.c7=5) then begin flag:=true; exit; end; end; 第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营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;

49、else begin w3:=w7+w3; w7:=0; end push; if (qr.c10=5) and (qr.c7=5) then begin flag:=true; exit; end; end; 第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营out; 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 t

50、hen 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; 第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营Procedure print;Var s:array1.100 of 0.100;begin write(queue:); for i:=1 to r do wri

51、te(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;第六讲第六讲第六讲第六讲 队列及应用队列及应用队列及应用队列及应用20072007年冬令营年冬令营年冬令营年冬令营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.