数据结构队列及其应用.ppt

队列及其应用 队列 所谓队列,就是允许在一端进行插入,在另一端进行删除的线性表。允许插入的一端称为队尾。 队列是一种先进先出(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 【培训试题】走迷宫 2349 【模拟试题】最少步数1800 海上葬礼 有一片被大海包围的群岛，岛上居住着一个食人部族。很多年前部落里有一位巫师接受了神的召唤跳入海中，从此，那一片海域就被打上了神的烙印，被这片海域所包围的陆地也被赋予了神圣的意义（包围关系满足传递性，即海域A包围了岛B，岛B包围了海域C，而海域C中包含了岛D，则我们说海域A也包含了岛D）。从那以后，部落里的巫师死后都必须葬在这片神圣海域所包围的岛上，而且每一个岛都只能埋葬一位巫师（否则就会被视为对神的不敬，从而给部族带来灾难）。现在给你群岛的地图和最初那位巫师跳海的地方，请你计算一下最多可以埋葬多少巫师。 地图是一个n*m的字符矩阵，’#’代表陆地，’.’代表海洋。连通的一片陆地为一个岛，连通的一片海洋为一个海域。其中，陆地从上、下、左、右4个方向连通，海洋从上、下、左、右、左上、左下、右上、右下8个方向连通。如下图。 图3中有4个岛，2片海域。如果在A处落水，则落水的海域包围了除右上、左下两个顶角外的3个岛屿；如果在B处落水，则只包含了中间的2个岛。 数据范围是n,m=500。 分 析 这道题目的思路比较简单。根据题意,可分三个步骤处理问题： 做一遍floodfill,将最初的巫师落水的海域设立标记,假设为S 再做一遍floodfill，将S区域所包围的所有区域（包括海洋和陆地）设立标记，假设为E。 在E区域中做一遍floodfill，统计有多少块连通的陆地（即岛的个数） 现在的问题就是，用什么样的算法实现floodfill。我们很容易想到深度优先遍历(DFS)的递归算法。由于要用递归，使用系统堆栈，因此对于500*500个结点的最坏情况下，会造成堆栈溢出，而且所需空间1000kb，无法满足题设的空间限制。在这种