据结构2—队列及其应用.pptVIP

队列及其应用 * 队列 所谓队列,就是允许在一端进行插入,在另一端进行删除的线性表。允许插入的一端称为队尾。 队列是一种先进先出(FIFO)的线性表 队列的顺序存储结构和链式存储结构 队列必须构造成循环队列的形式,否则会出现“假溢出” #define maxsize 队列最大容量； struct line { int a[maxsize-1]; int rear, front;//front队头;rear队尾 } * 队列操作 举例 食堂排队 排队买票 吸管里的饮料 作用：维持顺序 数组实现：元素a[0..maxn-1]，队首front，队尾rear 入队：rear++; a[rear]=x; 出队：ele=a[front];front++; 队空条件：frontrear 问题：出队的元素还在数组里，不是很浪费吗？ 循环队列 把队列看成环行的，则 入队：rear= (rear + 1)%maxn; 不定义为a[1..maxn]的原因 出队：front= (front + 1) %maxn; 可能存在队满的情况：条件也是front rear * 用队列实现图的宽度优先有哪些信誉好的足球投注网站算法 我们要对图进行分层次遍历,遍历的序列为1，2，…，7，… 宽度优先有哪些信誉好的足球投注网站算法遍历序列图 * 分析 要对图进行按层次遍历，我们可采用逐层标号法进行。方法如下： 第一步：将初始点放入队列，并将该点设置为已标号的点。 第二步：从队列中取出已标号而未检查的点，访问该点的所有邻接顶点，放入队列，并进行标号，该顶点为已检查的点。 第三步：检查队列中是否还有未标号的点，若有，转第二步，否则，图便历完毕，算法终止。 * void bfs(v); //从v开始宽度有先遍历图 { inicycque(q); //初始化队列q q.encycque(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的初始状态为空,元素e 1 ,e 2 ,e 3 ,e 4 ,e 5 ,e 6依次通过栈S,一个元素出栈后即进入队列Q,若出队的顺序为e 2 ,e 4 ,e 3 ,e 6 ,e 5 ,e 1 ,则栈S的容量至少应该为( )。(NOIP8) A)2 B)3 C)4 D)5 队列练习试题 * 【培训试题】细胞统计1611 Description：一矩形阵列由数字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,并沿其上、下、左、右四个方向有哪些信誉好的足球投注网站,如果遇到细胞(pic[i][j]=1)则将其位置入队,入队后的位置pic[i][j]数组置为0； 3、将h队的队头出队,沿其上、下、左、右四个方向上有哪些信誉好的足球投注网站,如果遇到细胞则将其位置入队,入队后的位置pic数组置为0； 4、重复3,直至h队空为止,则此时找出了一个细胞； 5、重复2,直至矩阵找不到细胞； 6、输出找到的细胞数。 * void work(int x,int y) { int first,last,i,h,ll; first=1;last=1;total++;hang[1]=x;lie[1]=y; while(firstlast) { for(i=0;i4;i++) { h=hang[first]+dx[i];ll=lie[first]+dy[i]; if(h0h=mll0ll=na[h][ll]) { last++; hang[last]=h;lie[las