pascal 第12讲 树与图的简介.ppt

数据结构之树图简介数据结构1.线性结构（栈、队列）的回顾栈的应用1——【括号匹配】栈的应用2——【括号匹配】从字符串中读入一个左括号时，就将其压入栈s中；
当读入一个右括号时,就从栈顶取出左括号检查比较,看是否匹配,如果匹配,就将左括号出栈;否则显示不匹配。
全部字符串读完后,最后检查栈是否为空,如果不空,左括号无右括号与之匹配,显示不匹配。vari,c:integer;
s:string;
a:array[1..2000]ofchar;
f:boolean;
procedurepush(l:char);
begin
inc(c);
a[c]:=l;
end;
procedurepop;
begin
dec(c);
end;begin
f:=true;
readln(s);
c:=0;
fori:=1tolength(s)do
begin
iff=falsethenbreak;
ifs[i]='{'thenpush('{');
ifs[i]='['thenpush('[');
ifs[i]='<'thenpush('<');
ifs[i]='('thenpush('(');
ifs[i]='}'thenbeginifa[c]='{'thenpopelsef:=false;end;
ifs[i]=']'thenbeginifa[c]='['thenpopelsef:=false;end;
ifs[i]='>'thenbeginifa[c]='<'thenpopelsef:=false;end;
ifs[i]=')'thenbeginifa[c]='('thenpopelsef:=false;end;
end;
iffand(c=0)thenwriteln('yes')elsewriteln('no');
end.
一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。
输入：整数m,n(m行，n列)（1<=m<=80,1<=n<=50）
矩阵
输出：细胞的个数。
样例:
输入:
4100234500067103456050020456006710000000089
输出:4

0234500067103456050020456006710000000089
算法步骤：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、输出找到的细胞数。
constdx: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..80,1..50]of0..1;{0:无细胞；1:有细胞}
m,n,i,j,num:integer;
h:array[1..4000,1..2]ofbyte;
{队列:存细胞的坐标，1：行；2：列}proceduredoing(p,q:integer);{处理坐标（p,q）的细胞}
vari,t,w,x,y:integer;
begin
inc(num);{细胞数量加1}
pic[p,q]:=0;
t:=1;{队列头}
w:=1;{队列尾}
h[1,1]:=p;h[1,2]:=q;{遇到的第一个细胞入队}
repeat
fori:=1to4do{沿细胞的上下左右四个方向搜索细胞}
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(pic[x,y]=1)
then
begin
inc(w);h[w,1]:=x;h[w,2]:=y;pic[x,y]:=0;
end;{为细胞的入队}
end;
inc(t);{队头指针加1，出队列}
untilt>w;{直至队空为止}
end;begin
fillchar(pic,sizeof(pic),0);num:=0;
fillchar(h,sizeof(h),0);
readln(m,n);
fori:=1tomdo
begin
readln(s);
forj:=1tondo
ifs[j]='0'thenpic[i,j]:=0elsepic[i,j]:=1;
end;
fo