队列的应用BFS.ppt

保定二中 NOIP2009——数据结构 队列的应用
网络中心 刘中一
QQ: 30144166

队列（FIFO）
1 队列的定义
所谓队列，就是允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾。规则：先进先出！
初始化一般头：open=0；尾：closed=0；
3
2
6
5
4
1
9
队列头 open
队列尾 closed
当 open>=closed时,队列空
非空：open<closed
队列数组a下标： 0 1 2 3 4 5 6 7……
我们按照如下方式定义队列：
Const
m=队列元素的上限；
Var
q ：array[1…m] of integer； {定义队列}
open，closed：integer； {队尾指针和队首指针}
2、队列的基本运算
队列的运算主要有两种：入队（ADD）和出队（DEL）
1、过程ADD(x)—在队列q的尾端插入元素x
procedure ADD( x：qtyper)；
begin
{后移队尾指针并插入元素x}
closed:=closed+1；
q[closed]←x；
end；{ADD}
注意：实际操作，可以不使用过程！
2、函数DEL—取出q队列的队首元素
function DEL；
begin
open:=open+1;
del:=q[open]；
end；{DEL}
注意：实际操作，可以不使用过程！
例：　　 一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。
输入：整数m,n(m行，n列)
矩阵
输出：细胞的个数。
样例:
输入:
4 100234500067103456050020456006710000000089
输出:4
02345000671034560500204560067189
共4个细胞
算法步骤： 1、从文件中读入m*n矩阵，将其转换为0、1矩阵存入pic数组中； 2、沿pic数组矩阵从上到下，从左到右，找到遇到的第一个细胞；将细胞的位置入队h，并沿其上、下、左、右四个方向上搜索，如果遇到细胞(pic[I,j]=1)则将其位置入队，入队后的位置pic[I,j]数组置为0； 3、将h队的队头出队，沿其上、下、左、右四个方向上搜索，如果遇到细胞则将其位置入队，入队后的位置pic数组置为0； 4、重复3，直至h队空为止，则此时找出了一个细胞； 5、重复2，直至矩阵找不到细胞； 6、输出找到的细胞数。
const dx:array[1..4] of -1..1=(-1,0,1,0);
dy:array[1..4] of -1..1=(0,1,0,-1);
var
s:string;
pic:array[1..50,1..80] of 0..1; {0:无细胞；1：有细胞}
m,n,i,j,num:integer;
h:array[1..4000,1..2] of byte; {队列：存细胞的坐标，1：行；2：列}
procedure doing(i,j:integer);
var k,open,closed,x,y:integer;
begin
inc(num); pic[i,j]:=0;
open:=0; {队列头} closed:=1; {队列尾}
h[1,1]:=i; h[1,2]:=j;{遇到的第一个细胞入队}
while open<closed do {队不空}
begin
inc(open);
for k:=1 to 4 do {沿细胞的上下左右四个方向搜索细胞}
begin
x:=h[open,1]+dx[k]; y:=h[open,2]+dy[k]; {进入位置（x，y）}