广度优先搜索.pptx

还是以迷宫作为引入。可怜的小老鼠被困在了迷宫里还是以迷宫作为引入。可怜的小老鼠被困在了迷宫里面想要逃出去，但是它不知道到底该怎么走，无论如何还面想要逃出去，但是它不知道到底该怎么走，无论如何还是先选定一个方向走一下再说。是先选定一个方向走一下再说。我们对各个方向设定一个优先级，比如我们设定先向我们对各个方向设定一个优先级，比如我们设定先向上走，再向右走，然后是向下，向左。这个顺序是顺时针上走，再向右走，然后是向下，向左。这个顺序是顺时针排的。不难想象，通过设定一个优先级，我们可以保证在排的。不难想象，通过设定一个优先级，我们可以保证在行进过程不会因为随机选择而出现重复情况。行进过程不会因为随机选择而出现重复情况。深度优先搜索的思路是找到一条可能的路就一直那么深度优先搜索的思路是找到一条可能的路就一直那么走下去直到走不通为止。这个走不通可能的情况很多，也走下去直到走不通为止。这个走不通可能的情况很多，也许是遇到了自然的障碍物，也许是到了死胡同走不下去了，许是遇到了自然的障碍物，也许是到了死胡同走不下去了，这个时侯只有倒退回去。这个时侯只有倒退回去。但是现实总是充满了陷阱，或许就存在这么一种路，但是现实总是充满了陷阱，或许就存在这么一种路，当你辛辛苦苦走了几十步甚至上百步之后才发现那是一个当你辛辛苦苦走了几十步甚至上百步之后才发现那是一个没有未来的选择。我们可以在迷宫中给老鼠设定，上帝也没有未来的选择。我们可以在迷宫中给老鼠设定，上帝也可以在人生里为我们设定。可以在人生里为我们设定。第1页/共161页我们发现固执的小老鼠就是那样子走下去了没有我们发现固执的小老鼠就是那样子走下去了没有回头。该怎么办才能防止这种情况的发生呢？回头。该怎么办才能防止这种情况的发生呢？对，我们可以叫住他！对，我们可以叫住他！“喂，那条路不能走了，喂，那条路不能走了，快回来！快回来！”实现起来其实很简单，就是在程序里实现起来其实很简单，就是在程序里面加一个深度判断，如果深度达到了一个上界，面加一个深度判断，如果深度达到了一个上界，我们就不继续往下走了，也就是跳出返回。其实我们就不继续往下走了，也就是跳出返回。其实这里面要涉及的还有很多，比如迭代加深搜索，这里面要涉及的还有很多，比如迭代加深搜索，A*等。等。其实我们可以让那只老鼠变得聪明一点的。假如其实我们可以让那只老鼠变得聪明一点的。假如我们的主角不是一只小老鼠，而是一大群，如果我们的主角不是一只小老鼠，而是一大群，如果你是老鼠王，你会怎么安排让你的子民们尽快逃你是老鼠王，你会怎么安排让你的子民们尽快逃生？生？Thinking。第2页/共161页很简单，让老鼠们分头行动。我们给每一只老鼠很简单，让老鼠们分头行动。我们给每一只老鼠都配一个对讲机。从出发点开始分成四个小队，都配一个对讲机。从出发点开始分成四个小队，四个小队分别分别负责四个方向，一起出发。每四个小队分别分别负责四个方向，一起出发。每次只能选择没有去过的地方走，没有去过既包括次只能选择没有去过的地方走，没有去过既包括自己没有去过也要包括别的老鼠没有去过，这个自己没有去过也要包括别的老鼠没有去过，这个我们可以用一个布尔数组在去过的地方标记一下，我们可以用一个布尔数组在去过的地方标记一下，对于小老鼠来说标记的方式可能会比较特殊。每对于小老鼠来说标记的方式可能会比较特殊。每次到一个位置都可能会有几种不同的走法，那好，次到一个位置都可能会有几种不同的走法，那好，我们把当前的这个小队再次划分，每个能走的方我们把当前的这个小队再次划分，每个能走的方向都派一个小小队去。如果没有路可走了，就呆向都派一个小小队去。如果没有路可走了，就呆在那儿了。当有一队老鼠或者是一只找到了出口，在那儿了。当有一队老鼠或者是一只找到了出口，这位英雄就在对讲机里大吼一声，这位英雄就在对讲机里大吼一声，“哈哈，我找哈哈，我找到出口啦，大家到这里来到出口啦，大家到这里来”。第3页/共161页相信大家听问题的时候都注意到了关键词相信大家听问题的时候都注意到了关键词“尽快尽快”。毋庸置疑，老鼠们的做法是肯定能在最快时。毋庸置疑，老鼠们的做法是肯定能在最快时间内找到出口。接下来我们分析一下其中原因。间内找到出口。接下来我们分析一下其中原因。我们给老鼠能到的每个方块一个距离。初始位置我们给老鼠能到的每个方块一个距离。初始位置的距离为的距离为0，由这个位置出发能到的距离为，由这个位置出发能到的距离为1，再，再有这些点能到的不重复的点的距离为有这些点能到的不重复的点的距离为2。如。如此下去，我们就可以给每一个可以到达的位置一此下去，我们就可以给每一个可以到达的位置一个距离值。我们每次所做的都是把一个位置能够个距离值。我们每次所做的都是把一个位置能够拓展的所有位置都拓展出来了，而且也没有走重拓展的所有位置都拓展出来了，而且也没有走重复的路。可以保证在到达某一个位置的时候我们复的路。可以保证在到达某一个位置的时候我们所走的距离肯定是最短的。所走的距离肯定是最短的。这就是宽度优先搜索。这就是宽度优先搜索。恭喜老鼠们成功获救！可是现在的问题我们如何恭喜老鼠们成功获救！可是现在的问题我们如何在程序里面实现？在程序里面实现？第4页/共161页BFS的关键：队列我们要模拟出小老鼠找路的过程就必须把每一个时刻每一我们要模拟出小老鼠找路的过程就必须把每一个时刻每一队小老鼠所到的位置记录下来。对于我们来说，只有在知队小老鼠所到的位置记录下来。对于我们来说，只有在知道当前老鼠的位置的前提下，我们才能产生下一时间的决道当前老鼠的位置的前提下，我们才能产生下一时间的决策。而为了达到上面所说的拓展最短，我们就必须根据各策。而为了达到上面所说的拓展最短，我们就必须根据各个位置被到达的先后顺序来拓展。这就要用到队列。个位置被到达的先后顺序来拓展。这就要用到队列。第5页/共161页队列第6页/共161页队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。故队列又称为先进先出（FIFOfirst in first out）线性表。第7页/共161页队列可以用数组queue1maxn来存储，数组的上界maxn即是队列所容许的最大容量。在队列的运算中需设两个指针：head，队头指针，指向实际队头元素；tail，队尾指针，指向实际队尾元素的下一个位置。第8页/共161页123Push入队入队Procedure push(x:integer);Begin Queuetail:=x;tail:=tail+1;End;headtail567840第9页/共161页123Pop出队出队Procedure pop;Begin write(Queuehead);head:=head+1;End;headtail45678队列为空的标志是队列为空的标志是head追上追上tail，即即head=tail第10页/共161页队列应用例例0：解密：解密QQ。新学期开始了，小哈是小哼的新同桌（小哈是个小美女哦），小哼向小哈询问 QQ号，小哈当然不会直接告诉小哼啦，原因嘛你懂的。所以小哈给了小哼一串加密过的数字，同时小哈也告诉了小哼解密规则。规则是这样的：首先将第 1个数删除，紧接着将第 2个数放到这串数的末尾，再将第 3个数删除并将第 4个数放到这串数的末尾，再将第 5个数删除直到剩下最后一个数，将最后一个数也删除。按照刚才删除的顺序，把这些删除的数连在一起就是小哈的 QQ啦。现在你来帮帮小哼吧。小哈给小哼加密过的一串数是“6 3 1 7 5 8 9 2 4”。输入：96 3 1 7 5 8 9 2 4输出6 1 5 9 4 7 2 8 3第11页/共161页分析：分析：1.首先需要一个数组queue来存储这一串数，并初始化这个数组即(6,3,1,7,5,8,9,2,4)；2.解密的第一步是将第一个数删除。如何在数组中删除一个数呢？最简单的方法是将所有后面的数都往前面挪动一位，将前面的数覆盖。但是这样的做法很耗费时间。第12页/共161页3.在这里引入两个整型变量 head和 tail。head用来记录队列的队首（即第一位），tail 用来记录队列的队尾（即最后一位）的下一个位置。你可能会问：为什么 tail 不直接记录队尾，却要记录队尾的下一个位置呢？这是因为当队列中只剩下一个元素时，队首和队尾重合会带来一些麻烦。我们这里规定队首和队尾重合时，队列为空。第13页/共161页4.现在有 9个数，9个数全部放入队列之后 head=1;tail=10;此时 head和 tail之间的数就是目前队列中“有效”的数。如果要删除一个数的话，将 head后移一位就 OK了，这样仍然可以保持 head和 tail之间的数为目前队列中“有效”的数。这样做虽然浪费了一个空间，却节省了大量的时间，这是非常划算的。第14页/共161页5.新增加一个数也很简单，把需要增加的数放到队尾即 qtail之后再 tail后移一位就 OK啦。第15页/共161页1.const maxn=100;2.var queue:array1.maxn of integer;3.n,i:integer;4.head,tail:integer;5.begin6.readln(n);7.for i:=1 to n do8.read(queuei);9.head:=1;10.tail:=n+1;/tail指向队尾的后一个位置指向队尾的后一个位置11.11.while head tail do /当队列不为空的时候执行循环当队列不为空的时候执行循环12.12.begin13./打印队首并将队首出队打印队首并将队首出队14.14.write(queuehead,);15.inc(head);16./先将新队首的数添加到队尾先将新队首的数添加到队尾17.17.queuetail:=queuehead;18.inc(tail);19./再将队首出队再将队首出队20.20.inc(head);21.end;22.end.第16页/共161页例1：迷宫问题描述：解救小哈。有一天，小哈一个人去玩迷宫，但是方向感不好的小白就快就迷了路。小哼得知后便立即去解救无助的小哈。小哼当然是有备而来，已经弄清楚了迷宫的地图，现在小哼要去解救小哈。问题就此开始了第17页/共161页任务：帮助小哼找到从迷宫起点通往小哈所在位置的的最少步数，并打印出一条最短路径。输入样例：5 40 0 1 00 0 0 00 0 1 00 1 0 00 0 0 11 1 4 3输出样例：7(1,1)-(2,1)-(3,1)-(4,1)-(5,1)-(5,2)-(5,3)-(4,3)第18页/共161页算法分析：最开始小哼在入口（1,1）处，一步之内可以到达的点有（1,2）和（2,1）1 12 23 34 41 12 23 3 4 4 5 5 1234第19页/共161页算法分析：最开始小哼在入口（1,1）处，一步之内可以到达的点有（1,2）和（2,1）1 12 23 34 41 12 23 3 4 4 5 5 第20页/共161页算法分析：但是小哈并不在这两个点上，那小哼只能通过（1,2）和（2,1）这两个点继续往下走。比如现在小哼走到了（1,2）这个点，之后他又能到达哪些新的点呢？1 12 23 34 41 12 23 3 4 4 5 5 第21页/共161页算法分析：但是小哈并不在这两个点上，那小哼只能通过（1,2）和（2,1）这两个点继续往下走。比如现在小哼走到了（1,2）这个点，之后他又能到达哪些新的点呢？1 12 23 34 41 12 2 3 3 4 4 5 5 第22页/共161页算法分析：再看看通过（2,1）又可以到达哪些点呢？1 12 23 34 41 1 2 2 3 3 4 4 5 5 第23页/共161页算法分析：再看看通过（2,1）又可以到达哪些点呢？1 12 23 34 41 1 2 2 3 3 4 4 5 5 第24页/共161页算法分析：此时，你会发现（2,2）这个点既可以从（1,2）到达，也可以从（2,1）到达，并且都只使用了2步。为避免一个点多次被走到，这里需要一个数组来记录一个点是否已走过。1 12 23 34 41 1 2 2 3 3 4 4 5 5 第25页/共161页算法分析：此时，小哼2步可以走到的点已全部走过，有（2,2)和（3,1），可小哈并不在这两个点上，还得继续往下尝试，看通过（2，2）和（3,1）这两个点还能到达哪些新的没有走过的点。1 12 23 34 41 1 2 2 3 3 4 4 5 5 第26页/共161页算法分析：通过（2,2）我们可以到达（2,3）和（3,2）通过（3,1）我们可以到达（4,1）1 12 23 34 41 12 2 3 3 4 4 5 5 第27页/共161页算法分析：搜索继续1 12 23 34 41 12 2 3 3 4 4 5 5 第28页/共161页算法分析：搜索继续1 12 23 34 41 1 2 2 3 3 4 4 5 5 第29页/共161页算法分析：搜索继续1 12 23 34 41 1 2 2 3 3 4 4 5 5 第30页/共161页算法分析：当进行到第7步时，终于 “抱得美人归”。1 12 23 34 41 1 2 2 3 3 4 4 5 5 第31页/共161页回顾一下刚才的算法，可以用一个队列来模拟整个回顾一下刚才的算法，可以用一个队列来模拟整个过程。过程。123456789xyprestep每个队列元素至少包含下列信息：x:横坐标 y:纵坐标 pre:由哪一个节点扩展而来（父节点）step:第几步扩展到该节点第32页/共161页算法分析：操作：队列指针初始化；将起点信息入队操作：队列指针初始化；将起点信息入队 1 12 23 34 41 12 23 3 4 4 5 5 0123456789xyprestep1234head tail第33页/共161页算法分析：操作：队列指针初始化；将起点信息入队操作：队列指针初始化；将起点信息入队 1 12 23 34 41 12 23 3 4 4 5 5 0123456789x1y1pre0step01234head tail第34页/共161页算法分析：操作：检测到队列不为空（操作：检测到队列不为空（headtail），则），则inc(head)1 12 23 34 41 12 23 3 4 4 5 5 0123456789x1y1pre0step0head tail第35页/共161页算法分析：操作：准备扩展高亮显示的节点操作：准备扩展高亮显示的节点 1 12 23 34 41 12 23 3 4 4 5 5 0123456789x1y1pre0step0headtail1234第36页/共161页算法分析：操作：按顺时针方向搜索可到达的格子，例如（操作：按顺时针方向搜索可到达的格子，例如（1,2）1 12 23 34 41 1 2 23 3 4 4 5 5 0123456789x1y1pre0step0headtail1234第37页/共161页算法分析：操作：操作：inc(tail)；将队首节点可到达节点（；将队首节点可到达节点（1,2）入队）入队 1 12 23 34 41 1 2 23 3 4 4 5 5 0123456789x1y1pre0step0headtail1234第38页/共161页 1 12 23 34 41 1 2 23 3 4 4 5 5 0123456789x11y12pre01step01head1234tail第39页/共161页算法分析：操作：继续搜索可到达的格子，例如（操作：继续搜索可到达的格子，例如（2,1）1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x11y12pre01step01headtail1234第40页/共161页算法分析：操作：操作：inc(tail)；将队首节点可到达节点（；将队首节点可到达节点（2,1）入队）入队 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x11y12pre01step01headtail1234第41页/共161页 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112y121pre011step011headtail1234第42页/共161页算法分析：操作：队首节点扩展完毕操作：队首节点扩展完毕 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112y121pre011step011headtail1234第43页/共161页算法分析：操作：操作：inc(head);准备扩展队首节点准备扩展队首节点 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112y121pre011step011headtail1234第44页/共161页 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112y121pre011step011headtail1234第45页/共161页算法分析：操作：搜索队首节点可到达的格子操作：搜索队首节点可到达的格子 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112y121pre011step011head tail1234第46页/共161页算法分析：操作：搜索队首节点可到达的格子操作：搜索队首节点可到达的格子 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112y121pre011step011head tail1234第47页/共161页算法分析：操作：搜索队首节点可到达的格子（操作：搜索队首节点可到达的格子（2,2）1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112y121pre011step011head tail1234第48页/共161页算法分析：操作：操作：inc(tail)；将队首可到达的节点入队；将队首可到达的节点入队 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112y121pre011step011head tail第49页/共161页算法分析：操作：操作：inc(tail)；将队首可到达的节点入队；将队首可到达的节点入队 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112y121pre011step011headtail第50页/共161页算法分析：操作：操作：inc(tail)；将队首可到达的节点（；将队首可到达的节点（2,2）入队）入队 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x1122y1212pre0112step0112headtail第51页/共161页算法分析：操作：队首节点扩展完毕操作：队首节点扩展完毕 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x1122y1212pre0112step0112headtail第52页/共161页算法分析：操作：操作：inc(head)，准备扩展队首节点，准备扩展队首节点 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x1122y1212pre0112step0112headtail第53页/共161页算法分析：操作：搜索队首可到达的格子，例如（操作：搜索队首可到达的格子，例如（2,2）（）（3,1），其中（），其中（2,2）已访问）已访问 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x1122y1212pre0112step0112head tail第54页/共161页算法分析：操作：操作：inc(tail)1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x1122y1212pre0112step0112head tail第55页/共161页算法分析：操作：（操作：（3,1）入队）入队 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x11223y12121pre01123step01122headtail第56页/共161页算法分析：操作：队首扩展完毕操作：队首扩展完毕 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x11223y12121pre01123step01122headtail第57页/共161页算法分析：操作：操作：inc(head)1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x11223y12121pre01123step01122headtail第58页/共161页算法分析：操作：搜索可到达的格子，例如（操作：搜索可到达的格子，例如（2,3）1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x11223y12121pre01123step01122head tail第59页/共161页算法分析：操作：操作：inc(tail);1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x11223y12121pre01123step01122head tail第60页/共161页算法分析：操作：入队操作：入队 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112232y121213pre011234step011223headtail第61页/共161页算法分析：操作：继续搜索可到达的格子操作：继续搜索可到达的格子 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112232y121213pre011234step011223headtail第62页/共161页算法分析：操作：继续搜索可到达的格子（操作：继续搜索可到达的格子（3,2）1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112232y121213pre011234step011223headtail第63页/共161页算法分析：操作：操作：inc(tail)1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112232y121213pre011234step011223headtail第64页/共161页算法分析：操作：入队操作：入队 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x1122323y1212132pre0112344step0112233headtail第65页/共161页算法分析：操作：队首节点扩展完毕操作：队首节点扩展完毕 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x1122323y1212132pre0112344step0112233headtail第66页/共161页算法分析：操作：操作：inc(head)1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x1122323y1212132pre0112344step0112233headtail第67页/共161页算法分析：操作：搜索可到达的格子操作：搜索可到达的格子 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x1122323y1212132pre0112344step0112233headtail第68页/共161页算法分析：操作：搜索可到达的格子操作：搜索可到达的格子 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x1122323y1212132pre0112344step0112233headtail第69页/共161页算法分析：操作：操作：inc(tail)1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x1122323y1212132pre0112344step0112233headtail第70页/共161页算法分析：操作：入队操作：入队 1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x11223234y12121321pre01123443step01122333headtail第71页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x11223234y12121321pre01123443step01122333headtail第72页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x11223234y12121321pre01123443step01122333headtail第73页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x11223234y12121321pre01123443step01122333headtail第74页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112232342y121213214pre011234436step011223334headtail第75页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112232342y121213214pre011234436step011223334headtail第76页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112232342y121213214pre011234436step011223334headtail第77页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112232342y121213214pre011234436step011223334headtail第78页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112232342y121213214pre011234436step011223334head tail第79页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789x112232342y121213214pre011234436step011223334head tail第80页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 01234567891011x1122323425y1212132141pre0112344368step0112233344headtail第81页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 01234567891011x1122323425y1212132141pre0112344368step0112233344head tail第82页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 01234567891011x1122323425y1212132141pre0112344368step0112233344head tail第83页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 01234567891011x11223234253y12121321414pre01123443689step01122333445headtail第84页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 01234567891011x11223234253y12121321414pre01123443689step01122333445headtail第85页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 01234567891011x11223234253y12121321414pre01123443689step01122333445headtail第86页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112x112232342531y121213214144pre011234436899step011223334455headtail第87页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112x112232342531y121213214144pre011234436899step011223334455headtail第88页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112x112232342531y121213214144pre011234436899step011223334455headtail第89页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 012345678910111213x112232342531y121213214144pre011234436899step011223334455headtail第90页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112131415x1122323425315y1212132141442pre01123443689910step0112233344555headtail第91页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112131415x1122323425315y1212132141442pre01123443689910step0112233344555headtail第92页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112131415x1122323425315y1212132141442pre01123443689910step0112233344555headtail第93页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112131415x1122323425315y1212132141442pre01123443689910step0112233344555headtail第94页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112131415x1122323425315y1212132141442pre01123443689910step0112233344555headtail第95页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112131415x11223234253154y12121321414424pre0112344368991011step01122333445556headtail第96页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112131415x11223234253154y12121321414424pre0112344368991011step01122333445556headtail第97页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112131415x11223234253154y12121321414424pre0112344368991011step01122333445556headtail第98页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112131415x11223234253154y12121321414424pre0112344368991011step01122333445556head tail第99页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112131415x11223234253154y12121321414424pre0112344368991011step01122333445556head tail第100页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112131415x112232342531545y121213214144243pre011234436899101113step011223334455566headtail第101页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112131415x112232342531545y121213214144243pre011234436899101113step011223334455566headtail第102页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112131415x112232342531545y121213214144243pre011234436899101113step011223334455566headtail第103页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112131415x112232342531545y121213214144243pre011234436899101113step011223334455566headtail第104页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 0123456789101112131415x112232342531545y121213214144243pre011234436899101113step011223334455566headtail第105页/共161页算法分析：操作：操作：1 12 23 34 41 1 2 2 3 3 4 4 5 5 01234