《数据结构—队列及其应用.ppt》由会员分享，可在线阅读，更多相关《数据结构—队列及其应用.ppt（29页珍藏版）》请在三一办公上搜索。
1、队列及其应用,队列,所谓队列,就是允许在一端进行插入,在另一端进行删除的线性表。允许插入的一端称为队尾。队列是一种先进先出(FIFO)的线性表队列的顺序存储结构和链式存储结构队列必须构造成循环队列的形式,否则会出现“假溢出”#define maxsize 队列最大容量；struct line int amaxsize-1;int rear,front;/front队头;rear队尾,队列操作,举例食堂排队排队买票吸管里的饮料作用：维持顺序数组实现：元素a0.maxn-1，队首front，队尾rear入队：rear+;arear=x;出队：ele=afront;front+;队空条件：front
2、rear问题：出队的元素还在数组里，不是很浪费吗？循环队列把队列看成环行的，则入队：rear=(rear+1)%maxn;不定义为a1.maxn的原因出队：front=(front+1)%maxn;可能存在队满的情况：条件也是front rear,用队列实现图的宽度优先搜索算法,我们要对图进行分层次遍历,遍历的序列为1，2，7，,宽度优先搜索算法遍历序列图,分析,要对图进行按层次遍历，我们可采用逐层标号法进行。方法如下：第一步：将初始点放入队列，并将该点设置为已标号的点。第二步：从队列中取出已标号而未检查的点，访问该点的所有邻接顶点，放入队列，并进行标号，该顶点为已检查的点。第三步：检查队列中
3、是否还有未标号的点，若有，转第二步，否则，图便历完毕，算法终止。,void bfs(v);/从v开始宽度有先遍历图 inicycque(q);/初始化队列qq.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
4、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：细胞的个数,0234
5、500067103456050020456006710000000089,算法步骤：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
6、)int first,last,i,h,ll;first=1;last=1;total+;hang1=x;lie1=y;while(first0,【培训试题】走迷宫 2349,Description 有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。Input 第一行是两个数m，n，接下来是m行
7、n列由1和0组成的数据，最后两行是起始点和结束点(m,n1 且 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,【问题描述】：在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣
8、，就想试一试，在一个（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)目标点的最少步数。虽然两条路径的起点不一样，但是它们的终点却是一
9、样的。如果我们将终点(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-
10、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步”。这看上去是荒谬
11、的，但可以简单而有效地避免马再次落入这些界外点。该点在以前的扩展中没有到达过。如果曾经到达过，则根据广度优先搜索的原理，先前到达该点所需的步数一定小于当前步数，因此完全没有必要再扩展下去。由此得出，马的跳后位置（x,y）是否可以入队的约束条件是sxy0,海上葬礼,有一片被大海包围的群岛，岛上居住着一个食人部族。很多年前部落里有一位巫师接受了神的召唤跳入海中，从此，那一片海域就被打上了神的烙印，被这片海域所包围的陆地也被赋予了神圣的意义（包围关系满足传递性，即海域A包围了岛B，岛B包围了海域C，而海域C中包含了岛D，则我们说海域A也包含了岛D）。从那以后，部落里的巫师死后都必须葬在这片神圣海域所
12、包围的岛上，而且每一个岛都只能埋葬一位巫师（否则就会被视为对神的不敬，从而给部族带来灾难）。现在给你群岛的地图和最初那位巫师跳海的地方，请你计算一下最多可以埋葬多少巫师。,地图是一个n*m的字符矩阵，#代表陆地，.代表海洋。连通的一片陆地为一个岛，连通的一片海洋为一个海域。其中，陆地从上、下、左、右4个方向连通，海洋从上、下、左、右、左上、左下、右上、右下8个方向连通。如下图。图3中有4个岛，2片海域。如果在A处落水，则落水的海域包围了除右上、左下两个顶角外的3个岛屿；如果在B处落水，则只包含了中间的2个岛。数据范围是n,m=500。,分 析,这道题目的思路比较简单。根据题意,可分三个步骤处理
13、问题：做一遍floodfill,将最初的巫师落水的海域设立标记,假设为S再做一遍floodfill，将S区域所包围的所有区域（包括海洋和陆地）设立标记，假设为E。在E区域中做一遍floodfill，统计有多少块连通的陆地（即岛的个数）现在的问题就是，用什么样的算法实现floodfill。我们很容易想到深度优先遍历(DFS)的递归算法。由于要用递归，使用系统堆栈，因此对于500*500个结点的最坏情况下，会造成堆栈溢出，而且所需空间1000kb，无法满足题设的空间限制。在这种情况下，我们考虑深度优先遍历的非递归过程。,分析,首先给8个方向矢量定一个序号，用一个常量数组进行记录：CONST d:a
14、rray1.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_xstartX Current_ystartY top1;stop0;初始结点入栈 标记(Current_x,Current_y
15、)为已扩展结点 while top0 do【stopsttop+1 if（stop0 then【Current_xCurrent_x dstop,1 Current_yCurrent_y dstop,2】ENDP,【培训试题】最大子序和,问题描述 输入一个长度为的整数序列（A1,A2,An），从中找出一段连续的长度不超过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,一个简化的问题,序列的最大连续和 输入一个
16、长度为的整数序列（A1,A2,An），从中找出一段连续的子序列，使得这个序列的和最大。,和原问题相比没有M这个序列长度的限制！,分析：,设 F(i)表示以第i个数结尾的最大连续和,以第i个数结尾的最大连续和序列，可能存在两种选择：情形一：只包含Ai 情形二：包含Ai和以Ai-1结尾的最大连续和序列,动态规划：,转移方程：F(i)=maxAi,F(i-1)+Ai边界：F(1)=A1要求的结果为maxF(i)|1=i=n,该算法的时间复杂度为O(n),一个简化的问题,枚举算法,设 F(i)为以Ai结尾长度不超过M的最大子序和,对于每个F(i)，从1到m枚举k的值，完成Aj的累加和取最大值。,该算法
17、的时间复杂度为O(n2),问题初步分析,简化方程,队列优化,在算法中，考虑用队列来维护决策值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)永远不会被用到）。此时的队列中
18、的元素构成了一个单调递增的序列，即：,S1S2S3Sk,我们来整理在求F(i)的时候，用队列维护S(i-k)所需要的操作：,若当前队首元素S(x)，有x=i-m为止。,若当前队尾元素S(k)=S(i-1)，则S(k)出队；直到S(k)S(i-1)为止。,在队尾插入S(i-1),取出队列中的最小值，即队首元素。,由于对于求每个F(i)的时候，进队和出队的元素不止一个。但是我们可以通过分摊分析得知，每一个元素S(i)只进队一次、出队一次，所以队列维护的时间复杂度是O(n)。而每次求F(i)的时候取最小值操作的复杂度是O(1)，所以这一步的总复杂度也是O(n)。综上所述，该算法的总复杂度是O(n),
