数据结构-队列及其应用

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,队列及其应用,队列,所谓队列,就是允许在一端进行插入,在另一端进行删除的线性表。允许插入的一端称为队尾。,队列是一种先进先出(FIFO)的线性表,队列的顺序存储结构和链式存储结构,队列必须构造成循环队列的形式,否则会出现“假溢出”,#define maxsize 队列最大容量；,struct line,int amaxsize-1;,int rear,front;/front队头;rear队尾,队列操作,举例,食堂排队,排队买票,吸管里的饮料,作用：维持顺序,数组实现：元素a0.maxn-1，队首front，队尾rear,入队：rear+;arear=x;,出队：ele=afront;front+;,队空条件：frontrear,问题：出队的元素还在数组里，不是很浪费吗？,循环队列,把队列看成环行的，则,入队：rear=(rear+1)%maxn;不定义为a1.maxn的原因,出队：front=(front+1)%maxn;,可能存在队满的情况：条件也是front rear,用队列实现图的宽度优先搜索算法,我们要对图进行分层次遍历,遍历的序列为1，2，7，,宽度优先搜索算法遍历序列图,分析,要对图进行按层次遍历，我们可采用逐层标号法进行。方法如下：,第一步：将初始点放入队列，并将该点设置为已标号的点。,第二步：从队列中取出已标号而未检查的点，访问该点的所有邻接顶点，放入队列，并进行标号，该顶点为已检查的点。,第三步：检查队列中是否还有未标号的点，若有，转第二步，否则，图便历完毕，算法终止。,void bfs(v);/从v开始宽度有先遍历图,inicycque(q);/初始化队列q,q.encycque(v);vistedv:=true;/初始点v放入队列,并标号,while(!q.empty)/直到队列不为空,while(v的邻接顶点存在),q.encycque(v的邻接顶点);,vistedv的邻接顶点:=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,：细胞的个数,0,2345,000,67,1,0,3456,0,5,00,2,0,456,00,671,00000000,89,算法步骤：,1,、读入,m*n,矩阵,将其转换为,0,、,1,矩阵存入,pic,数组中；,2,、沿,pic,数组矩阵从上到下,从左到右,找到遇到的第一个细胞；将细胞的位置入队,h,并沿其上、下、左、右四个方向搜索,如果遇到细胞,(,picij,=1),则将其位置入队,入队后的位置,picij,数组置为,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+;hang1=x;lie1=y;,while(firstlast),for(i=0;i0&h0&ll=n&ahll),last+;,hanglast=h;lielast=ll;/入队,ahll=false;,first+;/出队,int main(),init();,for(i=1;i=m;i+),for(j=1;j=n;j+)if(aij)work(i,j);,couttotal1 且 m,n15)。,Output,输出所有可能路路径条数，如果没有一条可行的路则输出。,Sample Input,5 6,1 0 0 1 0 1,1 1 1 1 1 1,0 0 1 1 1 0,1 1 1 1 1 0,1 1 1 0 1 1,1 1,5 6,Sample Output：12,【模拟试题】最少步数1800,【,问题描述,】,：在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100*100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点的可能最少步数。,输入：,12 16,18 10,输出：,8 9,1、确定出发点,从（x,y）出发通过一次广度优先搜索，可以找到从(x,y)至棋盘上所有可达点的最少步数。而问题中要求的是黑马所在的（x1，y1）和白马所在（x2，y2）到达(1,1)目标点的最少步数。虽然两条路径的起点不一样，但是它们的终点却是一样的。如果我们将终点(1,1)作为起点，这样只需要一次广度优先搜索便可以得到（x1，y1）和（x2，y2）到达(1,1)的最少步数。,2、数据结构,设queue队列，存储从(1,1)可达的点（queuek1.2）以及到达该点所需要的最少步数（queuek3）（0k192+1）。队列的首指针为open，尾指针为closed。初始时，queue中只有一个元素为(1,1)，最少步数为0。,S记录(1,1)到每点所需要的最少步数。显然，问题的答案是sx1y2和sx2y2。初始时，s11为0，除此之外的所有元素值设为-1。,dx、dy移动后的位置增量数组。马有12种不同的扩展方向：,马走“日”：(x-2,y-1)(x-1,y-2)(x-2,y+1)(x-1,y+2)(x+2,y-1)(x+1,y-2)(x+2,y+1)(x+1,y+2),马走“田”：(x-2,y-2)(x-2,y+2)(x+2,y-2)(x+2,y+2),我们将i方向上的位置增量存入常量数组dxi、dyi中（1i12）,int dx12=-2,-2,-1,1,2,2,2,2,1,-1,-2,-2,dy12=-1,-2,-2,-2,-2,-1,1,2,2,2,2,1;,3、约束条件,不能越出界外。由于马的所有可能的落脚点s均在s的范围内，因此一旦马越出界外，就将其s值赋为0，表示“已经扩展过，且(1,1)到达其最少需要0步”。这看上去是荒谬的，但可以简单而有效地避免马再次落入这些界外点。,该点在以前的扩展中没有到达过。如果曾经到达过，则根据广度优先搜索的原理，先前到达该点所需的步数一定小于当前步数，因此完全没有必要再扩展下去。,由此得出，马的跳后位置（x,y）是否可以入队的约束条件是sxy0,海上葬礼,有一片被大海包围的群岛，岛上居住着一个食人部族。很多年前部落里有一位巫师接受了神的召唤跳入海中，从此，那一片海域就被打上了神的烙印，被这片海域所包围的陆地也被赋予了神圣的意义（包围关系满足传递性，即海域A包围了岛B，岛B包围了海域C，而海域C中包含了岛D，则我们说海域A也包含了岛D）。从那以后，部落里的巫师死后都必须葬在这片神圣海域所包围的岛上，而且每一个岛都只能埋葬一位巫师（否则就会被视为对神的不敬，从而给部族带来灾难）。现在给你群岛的地图和最初那位巫师跳海的地方，请你计算一下最多可以埋葬多少巫师。,地图是一个n*m的字符矩阵，#代表陆地，.代表海洋。连通的一片陆地为一个岛，连通的一片海洋为一个海域。其中，陆地从上、下、左、右4个方向连通，海洋从上、下、左、右、左上、左下、右上、右下8个方向连通。如下图。,图3中有4个岛，2片海域。如果在A处落水，则落水的海域包围了除右上、左下两个顶角外的3个岛屿；如果在B处落水，则只包含了中间的2个岛。,数据范围是n,m1000kb,，无法满足题设的空间限制。在这种情况下，我们考虑深度优先遍历的非递归过程。,分析,首先给8个方向矢量定一个序号，用一个常量数组进行记录：,CONST d:array1.8,1.2of shortint,=(-1,-1),(0,-1),(-1,1),(0,1),(1,1),(0,1),(1,-1),(0,-1);,建立一个顺序栈S，栈的每个元素代表深度优先遍历路径中的一个结点位置，记录该位置当前扩展到的方向矢量的序号，再用一对变量Current_x，Current_y记录栈顶元素所代表的具体位置，就可以以非递归的方式完成深度优先遍历了。,PROC Dfs(startX,startY:integer);,初始化栈,Current_x,startX,Current_y,startY,top,1;stop,0;初始结点入栈,标记(Current_x,Current_y)为已扩展结点,while top0 do,【stop,sttop+1,if（stop0 then,【Current_x,Current_x dstop,1,Current_y,Current_y dstop,2,】,】,】ENDP,【培训试题】最大子序和,问题描述,输入一个长度为的整数序列（A,1,A,2,A,n,），从中找出一段连续的长度不超过M的子序列，使得这个序列的和最大。,最大子序和,例如：,序列 1，-3，5，1，-2，3,当M=2或3时,S=5+1=6,当M=4时,S=5+1+(-2)+3=7,数据范围:,50%的数据N,M=1000,100%的数据N,M=20000,一个简化的问题,序列的最大连续和,输入一个长度为的整数序列（A,1,A,2,A,n,），从中找出一段连续的子序列，使得这个序列的和最大。,和原问题相比没有M这个序列长度的限制！,分析：,设 F(i)表示以第i个数结尾的最大连续和,以第i个数结尾的最大连续和序列，可能存在两种选择：,情形一：只包含A,i,情形二：包含A,i,和以A,i-1,结尾的最大连续和序列,动态规划：,转移方程：,F(i)=maxA,i,F(i-1)+A,i,边界：F(1)=A,1,要求的结果为maxF(i)|1=i=n,该算法的时间复杂度为O(n),一个简化的问题,枚举算法,设,F(i),为以A,i,结尾长度不超过M的最大子序和,对于每个F(i)，从1到m枚举k的值，完成A,j,的累加和取最大值。,该算法的时间复杂度为O(n,2,),问题初步分析,简化方程,队列优化,在算法中，考虑用队列来维护决策值S(i-k)。每次只需要在队首删掉S(i-m-1)，在队尾添加S(i-1)。但是取最小值操作还是需要O(n)时间复杂度的扫描。,考察在添加S(i-1)的时候，设现在队尾的元素是S(k)，由于ki-1，所以,S(k)必然比S(i-1)先出队,。若此时,S(i-1)=S(k)，,则S(k)这个决策,永远不会在以后用到,，可以将S(k)从队尾删除掉（此时队列的尾部形成了一个类似栈的结构）,队列优化,同理，若队列中两个元素S(i)和S(j)，若i=S(j)，则我们可以删掉S(i)（因为S(i)永远不会被用到）。此时的队列中的元素构成了一个单调递增的