在趣谈数据结构（二）中，我们介绍了"队"及"队"的应用，在这一讲中，我们将再通过两道例题，进一步的了解的学习"队"的灵活使用。

例2、

　　设有ｎ个人依次围成一圈，从第１个人开始报数，数到第ｍ个人出列，然后从出列的下一个人开始报数，数到第ｍ个人又出列，…，如此反复到所有的人全部出列为止。设ｎ个人的编号分别为1，2，…，n，打印出出列的顺序。



分析　

　　本题我们可以用数组建立标志位等方法求解，但如果用上数据结构中循环链的思想，则更贴切题意，解题效率更高。

　　ｎ人围成一圈，把一人看成一个结点，ｎ人之间的关系采用链接方式，即每一结点有一个前继结点和一个后继结点，每一个结点有一个指针指向下一个结点，最后一个结点指针指向第一个结点。这就是单循环链的数据结构。

　　当ｍ人出列时，将ｍ结点的前继结点指针指向ｍ结点的后继结点指针，即把ｍ结点驱出循环链。



　　1、建立循环链表。

　　当用数组实现本题链式结构时，数组a[i]作为"指针"变量来使用，a[i]存放下一个结点的位置。设立指针j指向当前结点，则移动结点过程为j:=a[j]，当数到m时，m结点出链，则a[j]:=a[a[j]]。

　　当直接用链来实现时，则比较直观，每个结点有两个域：一个数值域，一个指针域，当数到m时，m出链，将m结点的前继结点指针指向其后继结点；

　　2、设立指针，指向当前结点，设立计数器，计数数到多少人；

　　3、沿链移动指针，每移动一个结点，计数器值加１，当计数器值为ｍ时，则ｍ结点出链。计数器值置为１；

　　4、重复３、直到n个结点均出链为止。



源程序一：用数组实现链式结构

program ex11-6a;

　const n=14;m=4;{设有10个人,报到4的人出列}

　var a:array[1..n] of integer;

　　i,j,k,p:integer;

　begin

　　for i:=1 to n-1 do a[i]:=i+1;{建立链表}

　　a[n]:=1;j:=n;k:=1;p:=0;{第n人指向第1人,并置初始}

　　repeat

　　　j:=a[j];k:=k+1;{报数,计数器加1}

　　　if k=m then {数到m,m人出队,计数器置1}

　　　　begin

　　　　　write(a[j]:4);p:=p+1;a[j]:=a[a[j]];k:=1;

　　　　end

　　　until p=n;{直到n个人均出队为止}

　end.



源程序二：单链环实现

program ex11-6b;

　type pointer=^node;

　　node=record

　　　val:integer;

　　　link:pointer

　　　end;

　var ptr,ptb:pointer;

　　i,j,n,m:integer;

　begin

　　readln(n,m);

　　new(ptb);ptb^.val:=1;ptr:=ptb;{申请第1个结点}

　　for i:=2 to n do

　　　begin

　　　　new(ptr^.link);ptr:=ptr^.link; {申请第2到n结点}

　　　　ptr^.val:=i;

　　　end;

　　ptr^.link:=ptb;j:=0;{第n结点指针指向第1个结点}

　　repeat

　　　i:=1;

　　　repeat {报数,报到m人出列}

　　　　ptr:=ptb;ptb:=ptb^.link;i:=i+1;

　　　until i=m;

　　　write(ptb^.val:2);

　　　ptb:=ptb^.link;ptr^.link:=ptb;j:=j+1;{将m结点驱出链表}

　　until j=n-1;{直到n个人均出队为止}

　　writeln(ptb^.val:4)

　end.

例3、

　　 一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。

如:阵列 0234500067

1034560500

2045600671

0000000089

有4个细胞。



算法步骤：



1． 从文件中读入m*n矩阵阵列，将其转换为boolean矩阵存入bz数组中；

2． 沿bz数组矩阵从上到下，从左到右，找到遇到的第一个细胞；

3． 将细胞的位置入队h，并沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为FLASE；

4． 将h队的队头出队，沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为FLASE；

5． 重复4，直至h队空为止，则此时找出了一个细胞；

6． 重复2，直至矩阵找不到细胞；

7． 输出找到的细胞数。



program xibao;

const dx:array[1..4] of -1..1=(-1,0,1,0);

　　　dy:array[1..4] of -1..1=(0,1,0,-1);

var int:text;

　　name,s:string;

　　pic:array[1..50,1..79] of byte;

　　bz:array[1..50,1..79] of boolean;

　　m,n,i,j,num:integer;

　　h:array[1..4000,1..2] of byte;

procedure doing(p,q:integer);

　var i,t,w,x,y:integer;

　begin

　　inc(num);bz[p,q]:=false;

　　t:=1;w:=1;h[1,1]:=p;h[1,2]:=q;{遇到的第一个细胞入队}

　　repeat

　　　for i:=1 to 4 do{沿细胞的上下左右四个方向搜索细胞}

　　　　begin　

　　　　　x:=h[t,1]+dx[i];y:=h[t,2]+dy[i];

　　　　　if (x>0) and (x<=m) and (y>0) and (y<=n) and bz[x,y]

　　　　　　then begin inc(w);h[w,1]:=x;h[w,2]:=y;bz[x,y]:=false;end;{为细胞的入队}

　　　　　end;

　　　　inc(t);{队头指针加1}

　　　until t>w;{直至队空为止}

　　end;

　begin

　　fillchar(bz,sizeof(bz),true);num:=0;

　　write('input file:');readln(name);

　　assign(int,name);reset(int);

　　readln(int,m,n);

　　for i:=1 to m do

　　　begin readln(int,s);

　　　for j:=1 to n do

　　　　begin pic[i,j]:=ord(s[j])-ord('0');

　　　　　if pic[i,j]=0 then bz[i,j]:=false;

　　　　end;

　　　end;

　　close(int);

　　for i:=1 to m do

　　　for j:=1 to n do if bz[i,j] then doing(i,j);{在矩阵中寻找细胞}

　　writeln('NUMBER of cells=',num);readln;

　end.