数据结构2-队列及其应用

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

1、队列及其应用队列所谓队列,就是允许在一端进行插入,在另一端进行删除的线性表。允许插入的一端称为队尾。队列是一种先进先出(FIFO)的线性表队列的顺序存储结构和链式存储结构队列必须构造成循环队列的形式,否则会出现“假溢出”#definemaxsize队列最大容量；structline{inta[maxsize-1];intrear,front;//front队头;rear队尾}队列操作举例食堂排队排队买票吸管里的饮料作用：维持顺序数组实现：元素a[0..maxn-1]，队首front，队尾rear入队：rear++;a[rear]=x;出队：e

2、le=a[front];front++;队空条件：front>rear问题：出队的元素还在数组里，不是很浪费吗？循环队列把队列看成环行的，则入队：rear=(rear+1)%maxn;不定义为a[1..maxn]的原因出队：front=(front+1)%maxn;可能存在队满的情况：条件也是front>rear用队列实现图的宽度优先搜索算法我们要对图进行分层次遍历,遍历的序列为1，2，…，7，…宽度优先搜索算法遍历序列图分析要对图进行按层次遍历，我们可采用逐层标号法进行。方法如下：第一步：将初始点放入队列，并将该点设置为已标号的点。第二步：

3、从队列中取出已标号而未检查的点，访问该点的所有邻接顶点，放入队列，并进行标号，该顶点为已检查的点。第三步：检查队列中是否还有未标号的点，若有，转第二步，否则，图便历完毕，算法终止。voidbfs(v);//从v开始宽度有先遍历图{inicycque(q);//初始化队列qq.encycque(v);visted[v]:=true;//初始点v放入队列,并标号while(!q.empty)//直到队列不为空while(v的邻接顶点存在){q.encycque(v的邻接顶点);visted[v的邻接顶点]:=true;}q.dlcycque(v)

4、;}①已知队列(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,e6依次通过栈S,一个元素出栈后即进入队列Q,若出队的顺序为e2,e4,e3,e6,e5,e1,则栈S的容量至少应该为()。(NOIP8)A)2B)3C)4D)5队列练习试题【培训试题】细胞统计1611Description：一矩形阵列由数字0到9组成,数字

5、1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。Input：第一行为整数m,n(m<=100,n<=100分别表示m行和n列)，以下为一个mxn的矩阵Output：细胞的个数0234500067103456050020456006710000000089算法步骤：1、读入m*n矩阵,将其转换为0、1矩阵存入pic数组中；2、沿pic数组矩阵从上到下,从左到右,找到遇到的第一个细胞；将细胞的位置入队h,并沿其上、下、左、右四个方向搜索,如果遇到细胞(pic[i][j]=1)则将其位置入队,入队后

6、的位置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

7、rst]+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<

8、，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所