数据结构2—队列及其应用课件.ppt

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

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

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

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

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

6、rtY 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或3时S=5+1=6当M=4时S=5+1+(-2)+3=7数据范围:50%的数据N,M=1

7、000 100%的数据N,M=20000一个简化的问题序列的最大连续和 输入一个长度为的整数序列（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的最大子序和ik

8、ijjmkAiF1.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)的时候，设现在队尾的元素是S(k)，由于ki-1，所以S(k)必然比S(i-1)先出队。若此时S(i-1)=S(k)，则S(k)这个决策

9、永远不会在以后用到，可以将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)取出队列中的最小值，即队首元素。由于对于求每个F(i)的时候，进队和出队的元素不止一个。但是我们可以通过分摊分析得知，每一个元素S(i)只进队一次、出队一次，所以队列维护的时间复杂度是O(n)。而每次求F(i)的时候取最小值操作的复杂度是O(1)，所以这一步的总复杂度也是O(n)。综上所述，该算法的总复杂度是O(n)