书签 分享 收藏 举报 版权申诉 / 29
上传文档赚钱

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

  • 上传人(卖家):晟晟文业
  • 文档编号:4614287
  • 上传时间:2022-12-25
  • 格式:PPT
  • 页数:29
  • 大小:104.50KB
  • 【下载声明】
    1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
    2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
    3. 本页资料《数据结构2—队列及其应用课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
    4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
    5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
    配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    数据结构 队列 及其 应用 课件
    资源描述:

    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)

    展开阅读全文
    提示  163文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:数据结构2—队列及其应用课件.ppt
    链接地址:https://www.163wenku.com/p-4614287.html

    Copyright@ 2017-2037 Www.163WenKu.Com  网站版权所有  |  资源地图   
    IPC备案号:蜀ICP备2021032737号  | 川公网安备 51099002000191号


    侵权投诉QQ:3464097650  资料上传QQ:3464097650
       


    【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。

    163文库