数据结构2队列及其应用教案资料.ppt

《数据结构2队列及其应用教案资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构2队列及其应用用队列实现图的宽度优先搜索算法我们要对图进行分层次遍历,遍历的序列为1，2，…，7，…宽度优先搜索算法遍历序列图分析要对图进行按层次遍历，我们可采用逐层标号法进行。方法如下：第一步：将初始点放入队列，并将该点设置为已标号的点。第二步：从队列中取出已标号而未检查的点，访问该点的所有邻接顶点，放入队列，并进行标号，该顶点为已检查的点。第三步：检查队列中是否还有未标号的点，若有，转第二步，否则，图便历完毕，算法终止。voidbfs(v);//从v开始宽度有先遍历图{inicycque(q);//初始化队列qq.encycque

2、(v);visted[v]:=true;//初始点v放入队列,并标号while(!q.empty)//直到队列不为空while(v的邻接顶点存在){q.encycque(v的邻接顶点);visted[v的邻接顶点]:=true;}q.dlcycque(v);}①已知队列(13,2,11,34,41,77,5,7,18,26,15),第一个进入队列的元素是13,则第五个出队列的元素是( )。(NOIP9)   A)5    B)41     C)77   D)13  E)18②设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e

3、6依次通过栈S,一个元素出栈后即进入队列Q,若出队的顺序为e2,e4,e3,e6,e5,e1,则栈S的容量至少应该为()。(NOIP8)A)2B)3C)4D)5队列练习试题【培训试题】细胞统计1611Description：一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。Input：第一行为整数m,n(m<=100,n<=100分别表示m行和n列)，以下为一个mxn的矩阵Output：细胞的个数0234500067103456050020456006710000

4、000089算法步骤：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、输出找到的细胞数。voidwork(intx,inty)

5、{intfirst,last,i,h,ll;first=1;last=1;total++;hang[1]=x;lie[1]=y;while(first0&&h<=m&&ll>0&&ll<=n&&a[h][ll]){last++;hang[last]=h;lie[last]=ll;//入队a[h][ll]=false;}}first++;//出队}}intmain(){init();for(i=1;i<=m;

6、i++)for(j=1;j<=n;j++)if(a[i][j])work(i,j);cout<

7、m，n，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点(m,n>1且m,n<15)。Output输出所有可能路路径条数，如果没有一条可行的路则输出０。SampleInput561001011111110011101111101110111156SampleOutput：12【模拟试题】最少步数1800【问题描述】：在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一

8、试，在一个（100*100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。