最新数据结构2队列及其应用教学讲义PPT课件.ppt

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

1、数据结构2队列及其应用队列操作举例食堂排队排队买票吸管里的饮料作用：维持顺序数组实现：元素a[0..maxn-1]，队首front，队尾rear入队：rear++;a[rear]=x;出队：ele=a[front];front++;队空条件：front>rear问题：出队的元素还在数组里，不是很浪费吗？循环队列把队列看成环行的，则入队：rear=(rear+1)%maxn;不定义为a[1..maxn]的原因出队：front=(front+1)%maxn;可能存在队满的情况：条件也是front>rear用队列实现图的宽度优先搜索算法我们要对图进行分层次遍历,遍历的序列为1，2，…，7，…宽度

2、优先搜索算法遍历序列图【培训试题】细胞统计1611Description：一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。Input：第一行为整数m,n(m<=100,n<=100分别表示m行和n列)，以下为一个mxn的矩阵Output：细胞的个数0234500067103456050020456006710000000089算法步骤：1、读入m*n矩阵,将其转换为0、1矩阵存入pic数组中；2、沿pic数组矩阵从上到下,从左到右,找到遇到的第一个细胞；将细胞的位置入队h,并沿其上、下、左、右四个方向搜索,如

3、果遇到细胞(pic[i][j]=1)则将其位置入队,入队后的位置pic[i][j]数组置为0；3、将h队的队头出队,沿其上、下、左、右四个方向上搜索,如果遇到细胞则将其位置入队,入队后的位置pic数组置为0；4、重复3,直至h队空为止,则此时找出了一个细胞；5、重复2,直至矩阵找不到细胞；6、输出找到的细胞数。voidwork(intx,inty){intfirst,last,i,h,ll;first=1;last=1;total++;hang[1]=x;lie[1]=y;while(first

4、ie[first]+dy[i];if(h>0&&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;i++)for(j=1;j<=n;j++)if(a[i][j])work(i,j);cout<

5、据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。Input第一行是两个数m，n，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点(m,n>1且m,n<15)。Output输出所有可能路路径条数，如果没有一条可行的路则输出０。SampleInput561001011111110011101111101110111156SampleOutput：12【模拟试题】最少步数1800【问题描述】：在各种棋中，

6、棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100*100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点的可能最少步数。输入：12161810输出：891、确定出发点从（x,y）出发通过一次广度优先搜索，可

7、以找到从(x,y)至棋盘上所有可达点的最少步数。而问题中要求的是黑马所在的（x1，y1）和白马所在（x2，y2）到达(1,1)目标点的最少步数。虽然两条路径的起点不一样，但是它们的终点却是一样的。如果我们将终点(1,1)作为起点，这样只需要一次广度优先搜索便可以得到（x1，y1）和（x2，y2）到达(1,1)的最少步数。2、数据结构设queue—队列，存储从(1,1)可达的点（queue[k][1..2]）以及到达该点所