2011数据结构之队列

搜索过程，a.city记录经过的城市,a.pre记录前趋元素，这样就可以倒推出最短线路。 具体过程如下： （1） 将城市A入队，队首、队尾都为1。 （2） 将队首所指的城市所有可直通的城市入队（如果这个城市在队中出现过就不入队，可用一个集合来判断），将入队城市的pre指向队首的位置。然后将队首加1，得到新的队首城市。重复以上步骤，直到城市H入队为止。当搜到城市H时，搜索结束。利用pre可倒推出最少城市线路。 null　const ju:array[1..8,1..8] of 0..1= ((1,0,0,0,1,0,1,1), 　　　　　　　　(0,1,1,1,1,0,1,1), 　　　　　　　　　(0,1,1,0,0,1,1,1), 　　　　　　　　　(0,1,0,1,1,1,0,1), 　　　　　　　　　(1,1,0,1,1,1,0,0), 　　　　　　　　　(0,0,1,1,1,1,1,0), 　　　　　 (1,1,1,0,0,1,1,0), 　　　　　　 (1,1,1,1,0,0,0,1)); 　　type r=record {记录定义} 　　　　　　city:array[1..100] of char; 　　　　　　pre:array[1..100] of integer; 　　　　　end; 　　var h,d,i:integer; 　　　　a:r; 　　　　s:set of 'A'..'H';null　procedure out; {输出过程} 　　begin 　　　write(a.city[d]); 　　　　repeat 　　　　　d:=a.pre[d]; 　　　　　write('--',a.city[d]); 　　　　until a.pre[d]=0; 　　　writeln; 　　　halt; 　　end; nullprocedure doit; begin h:=0; d:=1; a.city[1]:=‘A’; a.pre[1]:=0; s:=[‘A’]; repeat {步骤2} 　inc(h); {队首加一，出队} 　for i:=1 to 8 do {搜索可直通的城市} 　if （ju[ord(a.city[h])-64,i]=0） and (not(chr(i+64) in s))then {判断城市是否走过} 　begin 　　inc(d); {队尾加一，入队} 　　a.city[d]:=chr(64+i); 　　a.pre[d]:=h; 　　s:=s+[a.city[d]]; 　　if a.city[d]='H' then out; 　　end; until h=d; end; begin {主程序} 　　　doit; 　　end.null 编一个程序，找出一条通过迷宫的路径。在任何一个格子中，可以向8个方向前进，这里有兰色方块的单元表示走不通，将从入口处经过迷宫到出口处的最短的一条通路打印出来。　　例4迷宫问题null分析（1）怎样来存储迷宫？将它变成0，1二维数组。这样上述迷宫可转化为：null（2）在迷宫中怎样探索路径？有几个方向可以探索呢？ *只有三个探索方向的位置。如mg[1,1] *有五个探索方向的位置。如mg[3,1] *有八个探索方向的位置。如mg[3,2] 思考：能否都转化为八个方向的探索呢？ null这样存储的迷宫数组就转化成：null因此，数组定义为: Mg:array[0..m+1,0..n+1] of integer;而探索方向则变成了统一的情况，都探索8个方向：（x,y）0 11 11 01 -10 -1-1 -1-1 0-1 1这样可以定义一个二维数组记录探索方向。null（3）如何才能记录踪迹，并把探索的踪迹记忆下来呢？踪迹一般应包括来处和当前位置，可以需要用记录类型 Node=record X,y:integer; Pre:0..r; End;用一个对队列记忆探索的踪迹： Sqtype=array[1..r] of node;null例如：从（1，1）入口到达（6，8），往下探索时队列的情况null（4）如何防止重复探索：将迷宫中的0替换为-1procedure Qini(var sQ:sqtype); begin sQ[1].x:=1;sq[1].y:=1; Sq[1].pre:=0 F:=1;r:=1;mg[1,1]:=-1; end;nullProcedure mglj(var sq:sqtype); Begin Sqini; While f<=r do Begin x:=sq[f].x;y:=sq[f].y; for v:=1 to 8 do begin i:=x+zl[v,1]; j:=y+zl[v,2]; if mg[i,j]=0 then begin r:=r+1; sq[r].x:=I;sq[r].y:=j;sq[r].pre:=f; mg[i,j]:=-1; end; if (i=m) and (j=n) then [print;exit] end; nullF:=f+1 End; Writeln(‘迷宫无路径’); End;如何打印路径？Procedure print(var sq:sqtype,r:integer); Begin i:=r; repeat writeln(‘(‘,sq[i].x,’,’,sq[i].y,’)’); i:=sq[i].pre until i=0 End;null产生问题：由于顺序存储结构的存储空间属于静态分配，所以，在添加数据元素时，可能会出现没有剩余单元的情况。下面我们讨论一下下图所示的队列，称为“假溢出”现象。null解决方法：将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。采用首尾相接的结构后，形成一个环状，解决假溢出问题，避免数据元素的移动。如图所示。我们将这种形式表示的队列称之为循环队列。null循环队列的操作 procedure iniqueue(var Q:equeue); begin Q.f:=m;Q.r:=m; end;1、初始化：设定Q为一空队列，队首指针和队尾指针均指向存储空间的最后一个位置null2、判队列空：若队列Q为空，则返回值true，否则返回值false。 function qempty(Q:equeue):Boolean; begin qempty:=(Q.f=Q.r) end;null3、判队满：若队列满，则返回值true，否则返回值false。为了区分队列空和队列满，改用“队尾指针追上队首指针” 这一特征作为队列满标志。 function qfull(Q:equeue):Boolean; begin qfull:=((Q.r mod m)+1=Q.f); end;null4、元素进队：若队列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.data[Q.r]:=X; end end;null5、元素出队：若队列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.data[Q.f]； end; end;null例5约瑟夫问题：编号为1，2，……n个人按顺时针方向围坐一圈，每人持一个正整数密码，开始给定一个正整数m，从第一个人按顺时针方向自1开始顺序报数，报到m者出围坐的圈子，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人都出围坐的圈子为止，输出出列者的序列。null例如有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,5nullconst max=30; type people=record number,code:array[1..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.number[i]:=i; for i:=1 to n do read(a.code[i]); nulls:=1; for j:=n downto 1 do begin s:=(s+m-1) mod j; if s=0 then s:=j; w:=s;p:=a.number[w];write(p,' '); m:=a.code[p]; for i:=s to j-1 do begin a.number[i]:=a.number[i+1]; a.code[i]:=a.code[i+1]; end; end; end.null综合举例例6[问题描述]求一棵树的深度与宽度。 [算法说明]树可用数组 tree:array[1..n,1..5]of 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 12 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 本题的数据结构含义，首先要搞清楚：tree[i,j]存储编号为i的结点的第j号孩子（2<=j<=5,即最多4个孩子），tree[i,j]=0表示不存在；null在求解的过程中，用到数组G:ARRAY[1..N,1..7] OF INTEGER； 其中：G[I,1]表示父结点， G[I,2]表示层次， G[I,3]表示本结点号， G[I,4]——G[I,7] 表示子女结点； 同时，设2个指针SP1（取数指针）， SP2（存数指针）注意：g[i,k]实质上是一个队列，sp1为队列头指针,sp2为队列尾指针。null[程序清单]： program exＧp3; const n=13; var i,j,k,sp1,sp2,n1,n2,jmax,p:integer; tree:array[1..n,1..5]of integer; g :array[1..n,1..7]of integer; begin for i:=1 to n do begin tree[i,1]:=i; for j:=2 to 5 do read (tree[i,j]); readln; end;tree[i,j]=0表示i结点不存在nullsp1:=1;sp2:=1;g[1,1]:=0;g[1,2]:=1;g[1,3]:=1; for i:=4 to 7 do g[1,i]:=tree[1,i-2]; while__________________do begin p:=g[sp1,2];n2:=g[sp1,3]; {读队顶} ____________;j:=4; while ________________do begin n1:=g[sp1,j];j:=j+1; ___________________; g[sp2,1]:=n2;g[sp2,2]:=p;g[sp2,3]:=n1; for i:=1 to 4 do g[sp2,i+3]:=tree[n1,i+1]; end; ___________________; end; sp1<=sp2p:=p+1g[sp1,j]<>0sp2:=sp2+1sp1:=sp1+1表示队列非空时做……变量p是用来存放层次的遍历本结点的所有孩子移动队尾指针为下一个结点的遍历操作作准备移动队头指针null writeln('maxd=',g[sp2,2]); j:=1;k:=g[1,2];jmax:=0; for i:=2 to sp2 do if then j:=j+1 else begin if j>jmax then jmax:=j; _______; k:=g[Ｉ,2]; end; if j>jmax then jmax:=j; writeln('max1=',jmax); end. g[i,2]=kj:=1打印深度同层次个数累加放在j中j与jmax打擂台，找出最大值注意一层完了，j值要还原，宽度至少为1null例7有10升油在10升的容器中，另有两个7升和3升的空容器，现要求用这三个容器倒油，使得最后在10升和7升的容器中各有5升油。 分析： 三个容器可以看作三个变量 C10，C7，C3，每次倒油的可能性只有如下六种情况： ① C10 向 C7 倒油 ② C10 向 C3 倒油 ③ C7 向 C10 倒油 ④ C7 向 C3 倒油 ⑤ C3 向 C10 倒油 ⑥ C3 向 C7 倒油 null 从一个容器状态（三个容器中油的容量）看，虽然有可能经过上述六种倒油的方法产生六种容器状态，但实际上这六种新产生的容器状态，许多是已经出现过的状态。例如初始状态（10,0,0）表示 C10=10，C7=0，C3=0，经过上述六种倒油方法只能产生出两种新的容器状态（3,7,0）和（7,0,3），再增加一个变量记录当前状态是由什么状态产生的，这样就形成了一个不断扩张新结点的过程，因此这个倒油的过程就可以用队列来记录了。null队列可以理解为一个数组，数组元素是如下记录： RECORD C10,C7,C3,pre:integer; END; 数组下标为容器状态号。下面是倒油过程的队列图示： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 C10 C7 C3 PRE 当倒油产生出第19个容器状态时已达到了题解的目的。这时只要根据pre中的状态号17可以回溯到第17个容器状态的pre值为15，依次可再获得13，11，9，7，5，2，1容器状态号，从而即可得到解题的倒油过程（共倒9次）。 null 请注意,从一个容器中向另一个容器中倒油,人操作是很直观的,对编程来说则必须考虑: 1) 有没有油可倒? 2) 究竟倒多少?可能要全部倒入另一容器,也可能只要倒一部分另一容器已经满了. 队列元素说明了100个,为什么？ 变量fp,rp在程序中用作队列的头指针和尾指针;flag在程序中是否已倒出了需要的容器状态(C10=5,C7=5);下面是程序清单: nullType 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:=q[f].c10;w7:=q[f].c7;w3:=q[f].c3; End;nullProcedure push; {入队} Var flag1:boolean; {队中是否已有同结点的标志} Begin flag1:=true; for k:=1 to r do if (q[k].c10=w10) and (q[k].c7=w7) and (q[k].c3=w3) then flag1:=false; If flag1 then begin r:=r+1; q[r].c10:=w10; q[r].c7:=w7; q[r].c3:=w3 q[r].pre:=f end; End;nullProcedure cup;{产生新结点的过程} Begin out; {c10→c7} If w10>0 then begin if w10+w7>=7 then begin w10:=w10+w7-7;w7:=7; End; else begin w7:=w10+w7; w10:=0; end; push; if (q[r].c10=5) and (q[r].c7=5) then begin flag:=true; exit; end; end;nullout; {c10→c3} If w10>0 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 (q[r].c10=5) and (q[r].c7=5) then begin flag:=true; exit; end; end; nullout; {c7→c10} If w7>0 then begin w10:=w10+w7;w7:=0; push; if (q[r].c10=5) and (q[r].c7=5) then begin flag:=true; exit; end; end; out; {c7→c3} If w7>0 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 (q[r].c10=5) and (q[r].c7=5) then begin flag:=true; exit; end; end; nullout; {c3→c10} If w3>0 then begin w10:=w10+w3;w3:=0; push; if (q[r].c10=5) and (q[r].c7=5) then begin flag:=true; exit; end; end; out; {c3→c7} If w3>0 then begin if w3+w7>=7then begin w3:=w3+w7-7;w3:=0;end else begin w7:=w7+w3; w3:=0; end; push; if (q[r].c10=5) and (q[r].c7=5) then begin flag:=true; exit; end; end; nullProcedure print; Var s:array[1..100] of 0..100; begin write('queue:'); for i:=1 to r do write(q[i].c10:3,q[i].c7:3, q[i].c3:3, q[i].pre:3); s[1]:=r;i:=1; writeln; while s[i]<>0 do begin i:=i+1;s[i]:=q[s[i-1]].pre; end; for k:=i-1 downto 1 do writeln(q[s[k]].c10:5,q[s[k]].c7:5, q[s[k]].c3:5); end;nullBegin{主程序} f:=1;r:=1; q[1].c10:=10;q[1].c7:=0;q[1].c3:=0; q[1].pre:=0;Flag:=false; Repeat cup; f:=f+1;until flag or (f>r); If f>r then write(‘no’) else print; End.思 考思 考有没有其他判重，判定到达了目标状态！