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

数据结构队列及其应用第1页，共29页，编辑于2022年，星期六队列队列 所谓队列所谓队列所谓队列所谓队列,就是允许在一端进行插入就是允许在一端进行插入就是允许在一端进行插入就是允许在一端进行插入,在另一端进行删除的线在另一端进行删除的线在另一端进行删除的线在另一端进行删除的线性表。允许插入的一端称为队尾。性表。允许插入的一端称为队尾。性表。允许插入的一端称为队尾。性表。允许插入的一端称为队尾。队列是一种先进先出队列是一种先进先出队列是一种先进先出队列是一种先进先出(FIFO)(FIFO)的线性表的线性表的线性表的线性表 队列的顺序存储结构和链式存储结构队列的顺序存储结构和链式存储结构队列的顺序存储结构和链式存储结构队列的顺序存储结构和链式存储结构 队列必须构造成循环队列的形式队列必须构造成循环队列的形式队列必须构造成循环队列的形式队列必须构造成循环队列的形式,否则会出现否则会出现否则会出现否则会出现“假溢出假溢出假溢出假溢出”#definemaxsize#definemaxsize队列最大容量；队列最大容量；队列最大容量；队列最大容量；structlinestructlineintamaxsize-1;intamaxsize-1;intrear,front;/frontintrear,front;/front队头队头队头队头;rear;rear队尾队尾队尾队尾第2页，共29页，编辑于2022年，星期六队列操作队列操作 举例举例举例举例食堂排队食堂排队食堂排队食堂排队排队买票排队买票排队买票排队买票吸管里的饮料吸管里的饮料吸管里的饮料吸管里的饮料作用：维持顺序作用：维持顺序作用：维持顺序作用：维持顺序数组实现：元素数组实现：元素数组实现：元素数组实现：元素a0.maxn-1a0.maxn-1，队首，队首，队首，队首frontfront，队尾，队尾，队尾，队尾rearrear 入队：入队：入队：入队：rear+;arear=x;rear+;arear=x;出队：出队：出队：出队：ele=afront;front+;ele=afront;front+;队空条件：队空条件：队空条件：队空条件：frontrearfrontrear 问题：出队的元素还在数组里，不是很浪费吗？问题：出队的元素还在数组里，不是很浪费吗？问题：出队的元素还在数组里，不是很浪费吗？问题：出队的元素还在数组里，不是很浪费吗？循环队列循环队列循环队列循环队列 把队列看成环行的，则把队列看成环行的，则把队列看成环行的，则把队列看成环行的，则 入队：入队：入队：入队：rear=(rear+1)%maxn;rear=(rear+1)%maxn;不定义为不定义为不定义为不定义为a1.maxna1.maxn的原因的原因的原因的原因 出队：出队：出队：出队：front=(front+1)%maxn;front=(front+1)%maxn;可能存在队满的情况：条件也是可能存在队满的情况：条件也是可能存在队满的情况：条件也是可能存在队满的情况：条件也是front rearfront rear第3页，共29页，编辑于2022年，星期六用队列实现图的宽度优先搜索算法用队列实现图的宽度优先搜索算法我们要对图进行分层次遍历我们要对图进行分层次遍历,遍历的序列为遍历的序列为1，2，7，宽度优先搜索算法遍历序列图宽度优先搜索算法遍历序列图第4页，共29页，编辑于2022年，星期六分析分析 要对图进行按层次遍历，我们可采用逐层标号法进行。要对图进行按层次遍历，我们可采用逐层标号法进行。方法如下：方法如下：第一步：将初始点放入队列，并将该点设置为已标号的点。第一步：将初始点放入队列，并将该点设置为已标号的点。第一步：将初始点放入队列，并将该点设置为已标号的点。第一步：将初始点放入队列，并将该点设置为已标号的点。第二步：从队列中取出已标号而未检查的点，访问该点的所第二步：从队列中取出已标号而未检查的点，访问该点的所第二步：从队列中取出已标号而未检查的点，访问该点的所第二步：从队列中取出已标号而未检查的点，访问该点的所有邻接顶点，放入队列，并进行标号，该顶点为已检查的点。有邻接顶点，放入队列，并进行标号，该顶点为已检查的点。有邻接顶点，放入队列，并进行标号，该顶点为已检查的点。有邻接顶点，放入队列，并进行标号，该顶点为已检查的点。第三步：检查队列中是否还有未标号的点，若有，转第二第三步：检查队列中是否还有未标号的点，若有，转第二第三步：检查队列中是否还有未标号的点，若有，转第二第三步：检查队列中是否还有未标号的点，若有，转第二步，否则，图便历完毕，算法终止。步，否则，图便历完毕，算法终止。步，否则，图便历完毕，算法终止。步，否则，图便历完毕，算法终止。第5页，共29页，编辑于2022年，星期六void bfs(v);/void bfs(v);/从从从从v v开始宽度有先遍历图开始宽度有先遍历图开始宽度有先遍历图开始宽度有先遍历图 inicycque(q);/inicycque(q);/初始化队列初始化队列初始化队列初始化队列q qq.encycque(v);vistedv:=true;/q.encycque(v);vistedv:=true;/初始点初始点初始点初始点v v放入队列放入队列放入队列放入队列,并标号并标号并标号并标号while(!q.empty)/while(!q.empty)/直到队列不为空直到队列不为空直到队列不为空直到队列不为空while(vwhile(v的邻接顶点存在的邻接顶点存在的邻接顶点存在的邻接顶点存在)q.encycque(vq.encycque(v的邻接顶点的邻接顶点的邻接顶点的邻接顶点););vistedvvistedv的邻接顶点的邻接顶点的邻接顶点的邻接顶点:=true;:=true;q.dlcycque(v);q.dlcycque(v);第6页，共29页，编辑于2022年，星期六 已知队列已知队列已知队列已知队列(13,2,11,34,41,77,5,7,18,26,15),(13,2,11,34,41,77,5,7,18,26,15),第一个进入队第一个进入队第一个进入队第一个进入队列的元素是列的元素是列的元素是列的元素是13,13,则第五个出队列的元素是则第五个出队列的元素是则第五个出队列的元素是则第五个出队列的元素是()()。(NOIP9)(NOIP9)A)5B)41C)77D)13E)18A)5B)41C)77D)13E)18 设栈设栈设栈设栈S S和队列和队列和队列和队列QQ的初始状态为空的初始状态为空的初始状态为空的初始状态为空,元素元素元素元素e1,e2,e3,e4,e5e1,e2,e3,e4,e5,e6,e6依次通过栈依次通过栈依次通过栈依次通过栈S,S,一个元素出栈后即进入队列一个元素出栈后即进入队列一个元素出栈后即进入队列一个元素出栈后即进入队列Q,Q,若出队的顺序若出队的顺序若出队的顺序若出队的顺序为为为为e2,e4,e3,e6,e5,e1,e2,e4,e3,e6,e5,e1,则栈则栈则栈则栈S S的容量至少应该为的容量至少应该为的容量至少应该为的容量至少应该为()()。(NOIP8)(NOIP8)A)2B)3C)4D)5A)2B)3C)4D)5队列练习试题队列练习试题第7页，共29页，编辑于2022年，星期六【培训试题】细胞统计【培训试题】细胞统计1611DescriptionDescription：一矩形阵列由数字：一矩形阵列由数字：一矩形阵列由数字：一矩形阵列由数字0 0到到到到9 9组成组成组成组成,数字数字数字数字1 1到到到到9 9代表细胞代表细胞代表细胞代表细胞,细胞的细胞的细胞的细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞定义为沿细胞数字上下左右还是细胞数字则为同一细胞定义为沿细胞数字上下左右还是细胞数字则为同一细胞定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列求给定矩形阵列求给定矩形阵列求给定矩形阵列的细胞个数。的细胞个数。的细胞个数。的细胞个数。InputInput：第一行为整数：第一行为整数：第一行为整数：第一行为整数m,n(m=100,n=100m,n(m=100,n=100分别表示分别表示分别表示分别表示mm行和行和行和行和n n列列列列)，以下为一个以下为一个以下为一个以下为一个mxnmxn的矩阵的矩阵的矩阵的矩阵 OutputOutput：细胞的个数：细胞的个数：细胞的个数：细胞的个数0 02345234500000067671 10 0345634560 05 500002 20 0456456000067167100000000000000008989第8页，共29页，编辑于2022年，星期六算法步骤：算法步骤：u u1 1 1 1、读入、读入、读入、读入m*nm*nm*nm*n矩阵矩阵矩阵矩阵,将其转换为将其转换为将其转换为将其转换为0 0 0 0、1 1 1 1矩阵存入矩阵存入矩阵存入矩阵存入picpicpicpic数组中；数组中；数组中；数组中；u u2 2 2 2、沿、沿、沿、沿picpicpicpic数组矩阵从上到下数组矩阵从上到下数组矩阵从上到下数组矩阵从上到下,从左到右从左到右从左到右从左到右,找到遇到的第一个细胞；将细找到遇到的第一个细胞；将细找到遇到的第一个细胞；将细找到遇到的第一个细胞；将细胞的位置入队胞的位置入队胞的位置入队胞的位置入队h,h,h,h,并沿其上、下、左、右四个方向搜索并沿其上、下、左、右四个方向搜索并沿其上、下、左、右四个方向搜索并沿其上、下、左、右四个方向搜索,如果遇到细胞如果遇到细胞如果遇到细胞如果遇到细胞(picij=1)(picij=1)(picij=1)(picij=1)则将其位置入队则将其位置入队则将其位置入队则将其位置入队,入队后的位置入队后的位置入队后的位置入队后的位置picijpicijpicijpicij数组置为数组置为数组置为数组置为0 0 0 0；u u3 3 3 3、将、将、将、将h h h h队的队头出队队的队头出队队的队头出队队的队头出队,沿其上、下、左、右四个方向上搜索沿其上、下、左、右四个方向上搜索沿其上、下、左、右四个方向上搜索沿其上、下、左、右四个方向上搜索,如如如如果遇到细胞则将其位置入队果遇到细胞则将其位置入队果遇到细胞则将其位置入队果遇到细胞则将其位置入队,入队后的位置入队后的位置入队后的位置入队后的位置picpicpicpic数组置为数组置为数组置为数组置为0 0 0 0；u u4 4 4 4、重复、重复、重复、重复3,3,3,3,直至直至直至直至h h h h队空为止队空为止队空为止队空为止,则此时找出了一个细胞；则此时找出了一个细胞；则此时找出了一个细胞；则此时找出了一个细胞；u u5 5 5 5、重复、重复、重复、重复2,2,2,2,直至矩阵找不到细胞；直至矩阵找不到细胞；直至矩阵找不到细胞；直至矩阵找不到细胞；u u6 6 6 6、输出找到的细胞数。、输出找到的细胞数。、输出找到的细胞数。、输出找到的细胞数。第9页，共29页，编辑于2022年，星期六void work(int x,int y)void work(int x,int y)int first,last,i,h,ll;int first,last,i,h,ll;first=1;last=1;total+;hang1=x;lie1=y;first=1;last=1;total+;hang1=x;lie1=y;while(firstlast)while(firstlast)for(i=0;i4;i+)for(i=0;i0&h0&ll0&h0&ll=n&ahll)last+;last+;hanglast=h;lielast=ll;/hanglast=h;lielast=ll;/入队入队入队入队 ahll=false;ahll=false;first+;/first+;/出队出队出队出队 int main()int main()init();init();for(i=1;i=m;i+)for(i=1;i=m;i+)for(j=1;j=n;j+)if(aij)work(i,j);for(j=1;j=n;j+)if(aij)work(i,j);couttotalendl;couttotal1(m,n1且且且且m,n15)m,n15)。OutputOutput输出所有可能路路径条数，如果没有一条可行的路则输出。输出所有可能路路径条数，如果没有一条可行的路则输出。输出所有可能路路径条数，如果没有一条可行的路则输出。输出所有可能路路径条数，如果没有一条可行的路则输出。SampleInputSampleInput5656 100101100101 111111111111 001110001110 111110111110 111011111011 1111 5656SampleOutputSampleOutput：1212 第11页，共29页，编辑于2022年，星期六【模拟试题】最少步数【模拟试题】最少步数1800【问问问问题题题题描描描描述述述述】：在在在在各各各各种种种种棋棋棋棋中中中中，棋棋棋棋子子子子的的的的走走走走法法法法总总总总是是是是一一一一定定定定的的的的，如如如如中中中中国国国国象象象象棋棋棋棋中中中中马马马马走走走走“日日日日”。有有有有一一一一位位位位小小小小学学学学生生生生就就就就想想想想如如如如果果果果马马马马能能能能有有有有两两两两种种种种走走走走法法法法将将将将增增增增加加加加其其其其趣趣趣趣味味味味性性性性，因因因因此此此此，他他他他规规规规定定定定马马马马既既既既能能能能按按按按“日日日日”走走走走，也也也也能能能能如如如如象象象象一一一一样样样样走走走走“田田田田”字字字字。他他他他的的的的同同同同桌桌桌桌平平平平时时时时喜喜喜喜欢欢欢欢下下下下围围围围棋棋棋棋，知知知知道道道道这这这这件件件件事事事事后后后后觉觉觉觉得得得得很很很很有有有有趣趣趣趣，就就就就想想想想试试试试一一一一试试试试，在在在在一一一一个个个个（100*100100*100）的的的的围围围围棋棋棋棋盘盘盘盘上上上上任任任任选选选选两两两两点点点点A A、B B，A A点点点点放放放放上上上上黑黑黑黑子子子子，B B点点点点放放放放上上上上白白白白子子子子，代代代代表表表表两两两两匹匹匹匹马马马马。棋棋棋棋子子子子可可可可以以以以按按按按“日日日日”字字字字走走走走，也也也也可可可可以以以以按按按按“田田田田”字字字字走走走走，俩俩俩俩人人人人一一一一个个个个走走走走黑黑黑黑马马马马，一一一一个个个个走走走走白白白白马马马马。谁谁谁谁用用用用最最最最少少少少的的的的步步步步数数数数走走走走到到到到左左左左上上上上角角角角坐坐坐坐标标标标为为为为(1,1)(1,1)的的的的点点点点时时时时，谁谁谁谁获获获获胜胜胜胜。现现现现在在在在他他他他请请请请你你你你帮帮帮帮忙忙忙忙，给给给给你你你你A A、B B两两两两点的坐标，想知道两个位置到（点的坐标，想知道两个位置到（点的坐标，想知道两个位置到（点的坐标，想知道两个位置到（1,11,1）点的可能最少步数。）点的可能最少步数。）点的可能最少步数。）点的可能最少步数。输入：输入：输入：输入：12 16 12 16 18 10 18 10输出：输出：输出：输出：8 8 9 9第12页，共29页，编辑于2022年，星期六1 1、确定出发点、确定出发点、确定出发点、确定出发点 从（从（从（从（x,yx,y）出发通过一次广度优先搜索，可以找到从）出发通过一次广度优先搜索，可以找到从）出发通过一次广度优先搜索，可以找到从）出发通过一次广度优先搜索，可以找到从(x,y)(x,y)至棋盘上所有可至棋盘上所有可至棋盘上所有可至棋盘上所有可达点的最少步数。而问题中要求的是黑马所在的（达点的最少步数。而问题中要求的是黑马所在的（达点的最少步数。而问题中要求的是黑马所在的（达点的最少步数。而问题中要求的是黑马所在的（x1x1，y1y1）和白马所在（）和白马所在（）和白马所在（）和白马所在（x2x2，y2y2）到达）到达）到达）到达(1,1)(1,1)目标点的最少步数。虽然两条路径的起点不一样，但是它目标点的最少步数。虽然两条路径的起点不一样，但是它目标点的最少步数。虽然两条路径的起点不一样，但是它目标点的最少步数。虽然两条路径的起点不一样，但是它们的终点却是一样的。如果我们将终点们的终点却是一样的。如果我们将终点们的终点却是一样的。如果我们将终点们的终点却是一样的。如果我们将终点(1,1)(1,1)作为起点，这样只需要一次广度作为起点，这样只需要一次广度作为起点，这样只需要一次广度作为起点，这样只需要一次广度优先搜索便可以得到（优先搜索便可以得到（优先搜索便可以得到（优先搜索便可以得到（x1x1，y1y1）和（）和（）和（）和（x2x2，y2y2）到达）到达）到达）到达(1,1)(1,1)的最少步数。的最少步数。的最少步数。的最少步数。2 2、数据结构、数据结构、数据结构、数据结构 设设设设queuequeue队列，存储从队列，存储从队列，存储从队列，存储从(1,1)(1,1)可达的点（可达的点（可达的点（可达的点（queuek1.2queuek1.2）以及到达该点）以及到达该点）以及到达该点）以及到达该点所需要的最少步数（所需要的最少步数（所需要的最少步数（所需要的最少步数（queuek3queuek3）（）（）（）（0k192+10k192+1）。队列的首指针为）。队列的首指针为）。队列的首指针为）。队列的首指针为openopen，尾指针为尾指针为尾指针为尾指针为closedclosed。初始时，。初始时，。初始时，。初始时，queuequeue中只有一个元素为中只有一个元素为中只有一个元素为中只有一个元素为(1,1)(1,1)，最少步数为，最少步数为，最少步数为，最少步数为0 0。S S记录记录记录记录(1,1)(1,1)到每点所需要的最少步数。显然，问题的答案是到每点所需要的最少步数。显然，问题的答案是到每点所需要的最少步数。显然，问题的答案是到每点所需要的最少步数。显然，问题的答案是sx1y2sx1y2和和和和sx2y2sx2y2。初始时，。初始时，。初始时，。初始时，s11s11为为为为0 0，除此之外的所有元素值设为，除此之外的所有元素值设为，除此之外的所有元素值设为，除此之外的所有元素值设为-1-1。第13页，共29页，编辑于2022年，星期六 dx dx、dydy移动后的位置增量数组。马有移动后的位置增量数组。马有移动后的位置增量数组。马有移动后的位置增量数组。马有1212种不同的扩展方向：种不同的扩展方向：种不同的扩展方向：种不同的扩展方向：马走马走马走马走“日日日日”：(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-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)(x-2,y-2)(x-2,y+2)(x+2,y-2)(x+2,y+2)我们将我们将我们将我们将i i方向上的位置增量存入常量数组方向上的位置增量存入常量数组方向上的位置增量存入常量数组方向上的位置增量存入常量数组dxidxi、dyidyi中（中（中（中（1i121i12）int dx12=-2,-2,-1,1,2,2,2,2,1,-1,-2,-2,int dx12=-2,-2,-1,1,2,2,2,2,1,-1,-2,-2,dy12=-1,-2,-2,-2,-2,-1,1,2,2,2,2,1;dy12=-1,-2,-2,-2,-2,-1,1,2,2,2,2,1;3 3、约束条件、约束条件、约束条件、约束条件 不能越出界外。由于马的所有可能的落脚点不能越出界外。由于马的所有可能的落脚点不能越出界外。由于马的所有可能的落脚点不能越出界外。由于马的所有可能的落脚点s s均在均在均在均在s s的范围内，因此一旦的范围内，因此一旦的范围内，因此一旦的范围内，因此一旦马越出界外，就将其马越出界外，就将其马越出界外，就将其马越出界外，就将其s s值赋为值赋为值赋为值赋为0 0，表示，表示，表示，表示“已经扩展过，且已经扩展过，且已经扩展过，且已经扩展过，且(1,1)(1,1)到达其最少需要到达其最少需要到达其最少需要到达其最少需要0 0步步步步”。这看上去是荒谬的，但可以简单而有效地避免马再次落入这些界外点。这看上去是荒谬的，但可以简单而有效地避免马再次落入这些界外点。这看上去是荒谬的，但可以简单而有效地避免马再次落入这些界外点。这看上去是荒谬的，但可以简单而有效地避免马再次落入这些界外点。该点在以前的扩展中没有到达过。如果曾经到达过，则根据广度优先搜索该点在以前的扩展中没有到达过。如果曾经到达过，则根据广度优先搜索该点在以前的扩展中没有到达过。如果曾经到达过，则根据广度优先搜索该点在以前的扩展中没有到达过。如果曾经到达过，则根据广度优先搜索的原理，先前到达该点所需的步数一定小于当前步数，因此完全没有必要再扩展的原理，先前到达该点所需的步数一定小于当前步数，因此完全没有必要再扩展的原理，先前到达该点所需的步数一定小于当前步数，因此完全没有必要再扩展的原理，先前到达该点所需的步数一定小于当前步数，因此完全没有必要再扩展下去。下去。下去。下去。由此得出，马的跳后位置（由此得出，马的跳后位置（由此得出，马的跳后位置（由此得出，马的跳后位置（x,yx,y）是否可以入队的约束条件是）是否可以入队的约束条件是）是否可以入队的约束条件是）是否可以入队的约束条件是sxy0sxy0第14页，共29页，编辑于2022年，星期六海上葬礼海上葬礼 有一片被大海包围的群岛，岛上居住着一个食人部族。很多年前有一片被大海包围的群岛，岛上居住着一个食人部族。很多年前部落里有一位巫师接受了神的召唤跳入海中，从此，那一片海域部落里有一位巫师接受了神的召唤跳入海中，从此，那一片海域就被打上了神的烙印，被这片海域所包围的陆地也被赋予了神圣就被打上了神的烙印，被这片海域所包围的陆地也被赋予了神圣的意义（包围关系满足传递性，即海域的意义（包围关系满足传递性，即海域A包围了岛包围了岛B，岛，岛B包围了包围了海域海域C，而海域，而海域C中包含了岛中包含了岛D，则我们说海域，则我们说海域A也包含了岛也包含了岛D）。）。从那以后，部落里的巫师死后都必须葬在这片神圣海域所包围的从那以后，部落里的巫师死后都必须葬在这片神圣海域所包围的岛上，而且每一个岛都只能埋葬一位巫师（否则就会被视为对神岛上，而且每一个岛都只能埋葬一位巫师（否则就会被视为对神的不敬，从而给部族带来灾难）。现在给你群岛的地图和最初那的不敬，从而给部族带来灾难）。现在给你群岛的地图和最初那位巫师跳海的地方，请你计算一下最多可以埋葬多少巫师。位巫师跳海的地方，请你计算一下最多可以埋葬多少巫师。第15页，共29页，编辑于2022年，星期六 地图是一个地图是一个地图是一个地图是一个n*mn*m的字符矩阵，的字符矩阵，的字符矩阵，的字符矩阵，#代表陆地，代表陆地，代表陆地，代表陆地，.代表海洋。代表海洋。代表海洋。代表海洋。连通的一片陆地为一个岛，连通的一片海洋为一个海域。其中，连通的一片陆地为一个岛，连通的一片海洋为一个海域。其中，连通的一片陆地为一个岛，连通的一片海洋为一个海域。其中，连通的一片陆地为一个岛，连通的一片海洋为一个海域。其中，陆地从上、下、左、右陆地从上、下、左、右陆地从上、下、左、右陆地从上、下、左、右4 4个方向连通，海洋从上、下、左、右、个方向连通，海洋从上、下、左、右、个方向连通，海洋从上、下、左、右、个方向连通，海洋从上、下、左、右、左上、左下、右上、右下左上、左下、右上、右下左上、左下、右上、右下左上、左下、右上、右下8 8个方向连通。如下图。个方向连通。如下图。个方向连通。如下图。个方向连通。如下图。图图图图3 3中有中有中有中有4 4个岛，个岛，个岛，个岛，2 2片海域。如果在片海域。如果在片海域。如果在片海域。如果在A A处落水，则落水的海域包围了处落水，则落水的海域包围了处落水，则落水的海域包围了处落水，则落水的海域包围了除右上、左下两个顶角外的除右上、左下两个顶角外的除右上、左下两个顶角外的除右上、左下两个顶角外的3 3个岛屿；如果在个岛屿；如果在个岛屿；如果在个岛屿；如果在B B处落水，则只包含处落水，则只包含处落水，则只包含处落水，则只包含了中间的了中间的了中间的了中间的2 2个岛。个岛。个岛。个岛。数据范围是数据范围是数据范围是数据范围是n,m=500n,m1000kb，无法满足题设的空间，无法满足题设的空间限制。在这种情况下，我们考虑深度优先遍历的非递归过程。限制。在这种情况下，我们考虑深度优先遍历的非递归过程。第17页，共29页，编辑于2022年，星期六分析首先给首先给8个方向矢量定一个序号，用一个常量数组进行记个方向矢量定一个序号，用一个常量数组进行记录：录：CONSTd:array1.8,1.2ofshortint=(-1,-1),(0,-1),(-1,1),(0,1),(1,1),(0,1),(1,-1),(0,-1);建立一个顺序栈建立一个顺序栈S，栈的每个元素代表深度优先遍历路径中，栈的每个元素代表深度优先遍历路径中的一个结点位置，记录该位置当前扩展到的方向矢量的序号，的一个结点位置，记录该位置当前扩展到的方向矢量的序号，再用一对变量再用一对变量Current_x，Current_y记录栈顶元素所代表记录栈顶元素所代表的具体位置，就可以以非递归的方式完成深度优先遍历了。的具体位置，就可以以非递归的方式完成深度优先遍历了。第18页，共29页，编辑于2022年，星期六PROCDfs(startX,startY:integer);初始化栈初始化栈Current_xstartXCurrent_ystartYtop1;stop0;初始结点入栈初始结点入栈标记标记(Current_x,Current_y)为已扩展结点为已扩展结点whiletop0do【stopsttop+1if（stop0then【Current_xCurrent_xdstop,1Current_yCurrent_ydstop,2】ENDP 第19页，共29页，编辑于2022年，星期六【培训试题】最大子序和【培训试题】最大子序和问题描述 输入一个长度为的整数序列（A1,A2,An），从中找出一段连续的长度不超过M的子序列，使得这个序列的和最大。第20页，共29页，编辑于2022年，星期六最大子序和例如：序列 1，-3，5，1，-2，3当M=2或3时S=5+1=6当M=4时S=5+1+(-2)+3=7数据范围:50%的数据N,M=1000 100%的数据N,M=20000第21页，共29页，编辑于2022年，星期六一个简化的问题序列的最大连续和 输入一个长度为的整数序列（A1,A2,An），从中找出一段连续的子序列，使得这个序列的和最大。和原问题相比没有M这个序列长度的限制！第22页，共29页，编辑于2022年，星期六分析：分析：设 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)一个简化的问题第23页，共29页，编辑于2022年，星期六枚举算法设 F(i)为以Ai结尾长度不超过M的最大子序和 对于每个F(i)，从1到m枚举k的值，完成Aj的累加和取最大值。该算法的时间复杂度为O(n2)问题初步分析第24页，共29页，编辑于2022年，星期六简化方程第25页，共29页，编辑于2022年，星期六队列优化 在算法中，考虑用队列来维护决策值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)这个决策永远不会在以后用到，可以将S(k)从队尾删除掉（此时队列的尾部形成了一个类似栈的结构）第26页，共29页，编辑于2022年，星期六队列优化 同理，若队列中两个元素S(i)和S(j)，若i=S(j)，则我们可以删掉S(i)（因为S(i)永远不会被用到）。此时的队列中的元素构成了一个单调递增的序列，即：S1S2S3Sk第27页，共29页，编辑于2022年，星期六 我们来整理在求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)取出队列中的最小值，即队首元素。第28页，共29页，编辑于2022年，星期六 由于对于求每个F(i)的时候，进队和出队的元素不止一个。但是我们可以通过分摊分析得知，每一个元素S(i)只进队一次、出队一次，所以队列维护的时间复杂度是O(n)。而每次求F(i)的时候取最小值操作的复杂度是O(1)，所以这一步的总复杂度也是O(n)。综上所述，该算法的总复杂度是O(n)第29页，共29页，编辑于2022年，星期六