数据结构队列及其应用

数据结构队列及其应用第一页，共二十九页，2022年，8月28日队列所谓队列,就是允许在一端进行插入,在另一端进行删除的线性表。允许插入的一端称为队尾。队列是一种先进先出(FIFO)的线性表队列的顺序存储结构和链式存储结构队列必须构造成循环队列的形式,否则会出现“假溢出”#definemaxsize队列最大容量；structline{inta[maxsize-1];intrear,front;//front队头;rear队尾}第二页，共二十九页，2022年，8月28日队列操作举例食堂排队排队买票吸管里的饮料作用：维持顺序数组实现：元素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第三页，共二十九页，2022年，8月28日用队列实现图的宽度优先搜索算法我们要对图进行分层次遍历,遍历的序列为1，2，…，7，…宽度优先搜索算法遍历序列图第四页，共二十九页，2022年，8月28日分析要对图进行按层次遍历，我们可采用逐层标号法进行。方法如下：第一步：将初始点放入队列，并将该点设置为已标号的点。第二步：从队列中取出已标号而未检查的点，访问该点的所有邻接顶点，放入队列，并进行标号，该顶点为已检查的点。第三步：检查队列中是否还有未标号的点，若有，转第二步，否则，图便历完毕，算法终止。第五页，共二十九页，2022年，8月28日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);}第六页，共二十九页，2022年，8月28日①已知队列(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队列练习试题第七页，共二十九页，2022年，8月28日【培训试题】细胞统计1611Description：一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。Input：第一行为整数m,n(m<=100,n<=100分别表示m行和n列)，以下为一个mxn的矩阵Output：细胞的个数0234500067

1034560500

2045600671

0000000089第八页，共二十九页，2022年，8月28日算法步骤：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、输出找到的细胞数。第九页，共二十九页，2022年，8月28日voidwork(intx,inty){intfirst,last,i,h,ll;first=1;last=1;total++;hang[1]=x;lie[1]=y;while(first<last){for(i=0;i<4;i++){h=hang[first]+dx[i];ll=lie[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<<total<<endl;}第十页，共二十九页，2022年，8月28日【培训试题】走迷宫2349Description有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。Input第一行是两个数m，n，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点(m,n>1且m,n<15)。Output输出所有可能路路径条数，如果没有一条可行的路则输出０。SampleInput561001011111110011101111101110111156SampleOutput：12

第十一页，共二十九页，2022年，8月28日【模拟试题】最少步数1800【问题描述】：在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100*100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点的可能最少步数。输入：12161810输出：8

9第十二页，共二十九页，2022年，8月28日1、确定出发点从（x,y）出发通过一次广度优先搜索，可以找到从(x,y)至棋盘上所有可达点的最少步数。而问题中要求的是黑马所在的（x1，y1）和白马所在（x2，y2）到达(1,1)目标点的最少步数。虽然两条路径的起点不一样，但是它们的终点却是一样的。如果我们将终点(1,1)作为起点，这样只需要一次广度优先搜索便可以得到（x1，y1）和（x2，y2）到达(1,1)的最少步数。2、数据结构设queue—队列，存储从(1,1)可达的点（queue[k][1..2]）以及到达该点所需要的最少步数（queue[k][3]）（0≤k≤192+1）。队列的首指针为open，尾指针为closed。初始时，queue中只有一个元素为(1,1)，最少步数为0。S—记录(1,1)到每点所需要的最少步数。显然，问题的答案是s[x1][y2]和s[x2][y2]。初始时，s[1][1]为0，除此之外的所有元素值设为-1。第十三页，共二十九页，2022年，8月28日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方向上的位置增量存入常量数组dx[i]、dy[i]中（1≤i≤12）intdx[12]={-2,-2,-1,1,2,2,2,2,1,-1,-2,-2},dy[12]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1};3、约束条件⑴不能越出界外。由于马的所有可能的落脚点s均在s的范围内，因此一旦马越出界外，就将其s值赋为0，表示“已经扩展过，且(1,1)到达其最少需要0步”。这看上去是荒谬的，但可以简单而有效地避免马再次落入这些界外点。⑵该点在以前的扩展中没有到达过。如果曾经到达过，则根据广度优先搜索的原理，先前到达该点所需的步数一定小于当前步数，因此完全没有必要再扩展下去。由此得出，马的跳后位置（x,y）是否可以入队的约束条件是s[x][y]<0第十四页，共二十九页，2022年，8月28日海上葬礼有一片被大海包围的群岛，岛上居住着一个食人部族。很多年前部落里有一位巫师接受了神的召唤跳入海中，从此，那一片海域就被打上了神的烙印，被这片海域所包围的陆地也被赋予了神圣的意义（包围关系满足传递性，即海域A包围了岛B，岛B包围了海域C，而海域C中包含了岛D，则我们说海域A也包含了岛D）。从那以后，部落里的巫师死后都必须葬在这片神圣海域所包围的岛上，而且每一个岛都只能埋葬一位巫师（否则就会被视为对神的不敬，从而给部族带来灾难）。现在给你群岛的地图和最初那位巫师跳海的地方，请你计算一下最多可以埋葬多少巫师。第十五页，共二十九页，2022年，8月28日地图是一个n*m的字符矩阵，’#’代表陆地，’.’代表海洋。连通的一片陆地为一个岛，连通的一片海洋为一个海域。其中，陆地从上、下、左、右4个方向连通，海洋从上、下、左、右、左上、左下、右上、右下8个方向连通。如下图。图3中有4个岛，2片海域。如果在A处落水，则落水的海域包围了除右上、左下两个顶角外的3个岛屿；如果在B处落水，则只包含了中间的2个岛。数据范围是n,m<=500。第十六页，共二十九页，2022年，8月28日分析这道题目的思路比较简单。根据题意,可分三个步骤处理问题：做一遍floodfill,将最初的巫师落水的海域设立标记,假设为S再做一遍floodfill，将S区域所包围的所有区域（包括海洋和陆地）设立标记，假设为E。在E区域中做一遍floodfill，统计有多少块连通的陆地（即岛的个数）现在的问题就是，用什么样的算法实现floodfill。我们很容易想到深度优先遍历(DFS)的递归算法。由于要用递归，使用系统堆栈，因此对于500*500个结点的最坏情况下，会造成堆栈溢出，而且所需空间>1000kb，无法满足题设的空间限制。在这种情况下，我们考虑深度优先遍历的非递归过程。第十七页，共二十九页，2022年，8月28日分析首先给8个方向矢量定一个序号，用一个常量数组进行记录： CONSTd:array[1..8,1..2]ofshortint =((-1,-1),(0,-1),(-1,1),(0,1),(1,1),(0,1),(1,-1),(0,-1));建立一个顺序栈S，栈的每个元素代表深度优先遍历路径中的一个结点位置，记录该位置当前扩展到的方向矢量的序号，再用一对变量Current_x，Current_y记录栈顶元素所代表的具体位置，就可以以非递归的方式完成深度优先遍历了。第十八页，共二十九页，2022年，8月28日PROCDfs(startX,startY:integer);初始化栈Current_xstartXCurrent_ystartYtop1;s[top]0;{初始结点入栈}标记(Current_x,Current_y)为已扩展结点whiletop>0do【s[top]st[top]+1if（s[top]<=8）and（按s[top]方向扩展的结点属于海洋区域）and（之前没有扩展过）then【Current_xCurrent_x+d[s[top],1]Current_yCurrent_y+d[s[top],2]标记(Current_x,Current_y)为已扩展结点toptop+1;s[top]0{新结点入栈}】else【toptop-1{当前结点退栈}iftop>0then【Current_xCurrent_x–d[s[top],1]Current_yCurrent_y–d[s[top],2]】】】ENDP

第十九页，共二十九页，2022年，8月28日【培训试题】最大子序和问题描述输入一个长度为ｎ的整数序列（A1,A2,……,An），从中找出一段连续的长度不超过M的子序列，使得这个序列的和最大。第二十页，共二十九页，2022年，8月28日最大子序和例如：

序列1，-3，5，1，-2，3当M=2或3时S=5+1=6当M=4时S=5+1+(-2)+3=7数据范围:50%的数据N,M<=1000100%的数据N,M<=20000第二十一页，共二十九页，2022年，8月28日一个简化的问题[序列的最大连续和]输入一个长度为ｎ的整数序列（A1,A2,……,An），从中找出一段连续的子序列，使得这个序列的和最大。和原问题相比没有M这个序列长度的限制！第二十二页，共二十九页，2022年，8月28日分析：

设F(i)表示以第i个数结尾的最大连续和以第i个数结尾的最大连续和序列，可能存在两种选择：情形一：只包含Ai情形二：包含Ai和以Ai-1结尾的最大连续和序列动态规划：转移方程：F(i)=max{Ai,F(i-1)+Ai}边界：F(1)=A1要求的结果为max{F(i)|1<=i<=n}该算法的时间复杂度为O(n)一个简化的问题第二十三页，共二十九页，2022年，8月28日枚举算法设

F(i)为以Ai结尾长度不超过M的最大子序和对于每个F(i)，从1到m枚举k的值，完成Aj的累加和取最大值。该算法的时间复杂度为O(n2)问题初步分析第二十四页，共二十九页，2022年，8月28日简化方程第二十五页，共二十九页，2022年，8月28日队列优化在算法中，考虑用队列来维护