SGXDZX数据结构之树图简介王桐林寿光现代中学潍坊市2009信息学奥林匹克夏令营寿光现代中学数据结构1.线性结构（栈、队列）的回顾2.非线性结构（树）的简介3.非线性结构（图）的简介4.数据结构之简单总结寿光现代中学1.线性结构（栈、队列）的回顾什么是栈？什么是队列？寿光现代中学栈的应用1——【括号匹配】1、栈S初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在栈S上一次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是______（noip1998）(A){5,4,3,2,1}(B){2,1}(C){2,3}(D){3,4}寿光现代中学栈的应用2——【括号匹配】判断包含有括号{，[，<，（，），>，]，}的字符串是否匹配。【样例1】输入：abc{a[bb]m}aa输出：yes【样例2】输入：abc{a[bb]maa输出：no寿光现代中学从字符串中读入一个左括号时，就将其压入栈s中；当读入一个右括号时,就从栈顶取出左括号检查比较,看是否匹配,如果匹配,就将左括号出栈;否则显示不匹配。全部字符串读完后,最后检查栈是否为空,如果不空,左括号无右括号与之匹配,显示不匹配。【问题分析】寿光现代中学vari,c:integer;s:string;a:array[1..2000]ofchar;f:boolean;procedurepush(l:char);begininc(c);a[c]:=l;end;procedurepop;begindec(c);end;【参考程序】寿光现代中学beginf:=true;readln(s);c:=0;fori:=1tolength(s)dobeginiff=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.n寿光现代中学一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。输入：整数m,n(m行，n列)（1<=m<=80,1<=n<=50）矩阵输出：细胞的个数。样例:输入:4100234500067103456050020456006710000000089输出:4队列的应用——【细胞】寿光现代中学0234500067103456050020456006710000000089共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、输出找到的细胞数。寿光现代中学constdx:array[1..4]of-1..1=(-1,0,1,0);dy:array[1..4]of-1..1=(0,1,0,-1);vars: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;begininc(num);{细胞数量加1}pic[p,q]:=0;t:=1;{队列头}w:=1;{队列尾}h[1,1]:=p;h[1,2]:=q;{遇到的第一个细胞入队}repeatfori:=1to4do{沿细胞的上下左右四个方向搜索细胞}beginx:=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)thenbegininc(w);h[w,1]:=x;h[w,2]:=y;pic[x,y]:=0;end;{为细胞的入队}end;inc(t);{队头指针加1，出队列}untilt>w;{直至队空为止}end;寿光现代中学beginfillchar(pic,sizeof(pic),0);num:=0;fillchar(h,sizeof(h),0);readln(m,n);fori:=1tomdobeginreadln(s);forj:=1tondoifs[j]='0'thenpic[i,j]:=0elsepic[i,j]:=1;end;fori:=1tomdoforj:=1tondoifpic[i,j]=1thendoing(i,j);{在矩阵中寻找细胞}writeln(num);end.寿光现代...
