数据结构2队列及其应用

1、数据结构2队列及其应用我们要对图进行分层次遍历我们要对图进行分层次遍历,遍历的序列为遍历的序列为1，2，7， 宽度优先搜索算法遍历序列图宽度优先搜索算法遍历序列图有一片被大海包围的群岛，岛上居住着一个食人部族。很多年前有一片被大海包围的群岛，岛上居住着一个食人部族。很多年前部落里有一位巫师接受了神的召唤跳入海中，从此，那一片海域部落里有一位巫师接受了神的召唤跳入海中，从此，那一片海域就被打上了神的烙印，被这片海域所包围的陆地也被赋予了神圣就被打上了神的烙印，被这片海域所包围的陆地也被赋予了神圣的意义（包围关系满足传递性，即海域的意义（包围关系满足传递性，即海域A包围了岛包围了岛B，岛，岛B包围

2、了包围了海域海域C，而海域，而海域C中包含了岛中包含了岛D，则我们说海域，则我们说海域A也包含了岛也包含了岛D）。从）。从那以后，部落里的巫师死后都必须葬在这片神圣海域所包围的岛上，而那以后，部落里的巫师死后都必须葬在这片神圣海域所包围的岛上，而且每一个岛都只能埋葬一位巫师（否则就会被视为对神的不敬，从而给且每一个岛都只能埋葬一位巫师（否则就会被视为对神的不敬，从而给部族带来灾难）。现在给你群岛的地图和最初那位巫师跳海的地方，请部族带来灾难）。现在给你群岛的地图和最初那位巫师跳海的地方，请你计算一下最多可以埋葬多少巫师。你计算一下最多可以埋葬多少巫师。 这道题目的思路比较简单。根据题意这道题目

3、的思路比较简单。根据题意,可分三个步骤处理问题：可分三个步骤处理问题：做一遍做一遍floodfill,将最初的巫师落水的海域设立标记将最初的巫师落水的海域设立标记,假设为假设为S再做一遍再做一遍floodfill，将，将S区域所包围的所有区域（包括海洋和陆地）设立标记，区域所包围的所有区域（包括海洋和陆地）设立标记，假设为假设为E。在在E区域中做一遍区域中做一遍floodfill，统计有多少块连通的陆地（即岛的个数），统计有多少块连通的陆地（即岛的个数）1.现在的问题就是，用什么样的算法实现现在的问题就是，用什么样的算法实现floodfill。我们很容易想到深度。我们很容易想到深度优先遍历优先

4、遍历(DFS)的递归算法。由于要用递归，使用系统堆栈，因此对于的递归算法。由于要用递归，使用系统堆栈，因此对于500*500个结点的最坏情况下，会造成堆栈溢出，而且所需空间个结点的最坏情况下，会造成堆栈溢出，而且所需空间1000kb，无法满足题设的空间限制。在这种情况下，我们考虑深度优先遍历的非递归无法满足题设的空间限制。在这种情况下，我们考虑深度优先遍历的非递归过程。过程。分析首先给首先给8个方向矢量定一个序号，用一个常量数组进行记个方向矢量定一个序号，用一个常量数组进行记录：录：CONST d :array1.8, 1.2of shortint=(-1, -1), (0, -1), (-1

5、, 1), (0, 1), (1, 1), (0, 1), (1, -1), (0, -1);建立一个顺序栈建立一个顺序栈S，栈的每个元素代表深度优先遍历路径，栈的每个元素代表深度优先遍历路径中的一个结点位置，记录该位置当前扩展到的方向矢量中的一个结点位置，记录该位置当前扩展到的方向矢量的序号，再用一对变量的序号，再用一对变量Current_x，Current_y记录栈记录栈顶元素所代表的具体位置，就可以以非递归的方式完顶元素所代表的具体位置，就可以以非递归的方式完成深度优先遍历了。成深度优先遍历了。 PROC Dfs(startX, startY : integer); 初始化栈初始化栈 C

6、urrent_xstartX Current_ystartY top1; stop0; 初始结点入栈初始结点入栈 标记标记(Current_x, Current_y)为已扩展结点为已扩展结点 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

7、或3时S=5+1=6当M=4时S=5+1+(-2)+3=7数据范围: 50%的数据N,M=1000 100%的数据N,M=202X0一个简化的问题序列的最大连续和 输入一个长度为的整数序列（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

8、该算法的时间复杂度为O(n)一个简化的问题枚举算法设 F(i)为以Ai结尾长度不超过M的最大子序和ikijjmkAiF1.1|max)( 对于每个F(i)，从1到m枚举k的值，完成Aj的累加和取最大值。该算法的时间复杂度为O(n2)问题初步分析简化方程ikijjmkAiF1.1|max)(i1jjA) i (S令.1| )(min)(.1| )()(maxmkkiSiSmkkiSiS队列优化 在算法中，考虑用队列来维护决策值S(i-k)。每次只需要在队首删掉S(i-m-1)，在队尾添加S(i-1) 。但是取最小值操作还是需要O(n)时间复杂度的扫描。 考察在添加S(i-1)的时候，设现在队尾的

9、元素是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)永远不会被用到）。此时的队列中的元素构成了一个单调递增的序列，即：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) 取出队列中的最小值，即队首元素。 由于