数据结构-第五部分

数据结构-第五部分朗读前明确读的要求：读准字音，读出节奏；朗读后同学间评价朗读情况。三、学生自学，二读课文１、一边默读课文，一边运用书下注释解释重点词，并练习翻译，看谁做得最好。２、学生自学，教师巡视，了解学情。３、检查自学效果：（请一位学生回答，其他同学认真听，如有错，请帮忙纠正）。（学生依次回答，如有错，请学生更正，学生不会，教师更正。）⑶学生快速对照相关译文，自我检查。四、字词小结。随堂练习（投影出示练习）数据结构-第五部分数据结构-第五部分朗读前明确读的要求：读准字音，读出节奏；朗读后同学间评价朗读情况。三、学生自学，二读课文１、一边默读课文，一边运用书下注释解释重点词，并练习翻译，看谁做得最好。２、学生自学，教师巡视，了解学情。３、检查自学效果：（请一位学生回答，其他同学认真听，如有错，请帮忙纠正）。（学生依次回答，如有错，请学生更正，学生不会，教师更正。）⑶学生快速对照相关译文，自我检查。四、字词小结。随堂练习（投影出示练习）枚举法枚举法适合于解的候选者是有限、可枚举的场合。枚举法就是对可能是解的众多候选者按某种顺序进行逐一枚举和检验，从中找出符合要求的候选解作为问题的解。基于枚举法的算法一般都比较直观，容易理解。但由于要检查所有的候选解，因此时间性能较差2数据结构-第五部分全文共83页，当前为第1页。数据结构-第五部分全文共83页，当前为第2页。3枚举法实例用50元钱买了三种水果：西瓜、苹果和桔子。各种水果加起来一共100个。假如，西瓜5元一个，苹果1元一个，桔子1元3个，设计一算法输出每种水果各买了几个。数据结构-第五部分全文共83页，当前为第3页。4约束条件三种水果一共100个；买三种水果一共花了50元。如果西瓜有mellon个，苹果有apple个，桔子有orange个，那么：

mellon+apple+orange等于1005*mellon+1*apple+orange/3等于50。数据结构-第五部分全文共83页，当前为第4页。5直观的枚举For(mellon=1,mellon<99;++mellon)For(apple=1,apple<99;++apple)For(orange=1;orange<99;orange)If（mellon+apple+orange等于100并且5*mellon+1*apple+orange/3等于50）输出此方案；列出所有的情况，检查是否满足两个约束条件数据结构-第五部分全文共83页，当前为第5页。6改进的方案intmain(){intmellon,apple,orange;for(mellon=1;mellon<10;++mellon)for(apple=1;apple<50-5*mellon;++apple){ orange=3*(50-5*mellon-apple);if(mellon+apple+orange==100){cout<<"mellon:"<<mellon<<''; cout<<"apple:"<<apple<<''; cout<<"orange:"<<orange<<endl; }}return0;}按一个约束条件列出所有可行的情况，然后对每个可能解检查它是否满足第二个约束条件。数据结构-第五部分全文共83页，当前为第6页。7执行结果Mellon：1apple：18orange：81Mellon：2apple：11orange：87Mellon：3apple：4orange：93数据结构-第五部分全文共83页，当前为第7页。8第15章算法设计技术枚举法贪婪法分而治之法动态规划回溯法随机算法介绍通用的算法设计模式数据结构-第五部分全文共83页，当前为第8页。9贪婪法贪婪法适合于分阶段完成的工作。在每一阶段都选择当前最好的答案，而不管将来如何。Dijkstra算法，prim算法和Kruskal算法都是贪婪算法贪婪法不一定能得到最优解，但是一个可行的、较好的解。数据结构-第五部分全文共83页，当前为第9页。10最少背包问题假设有许多盒子，每个盒子能保存的总重量为1.0。有N个项i1,i2,…,iN，它们的重量分别是w1,w2,…,wN。目的是用尽可能少的盒子放入所有的项，任何盒子的重量不能超过他的容量。例如，如果项的重量为0.4,0.4,0.6和0.6，最佳的方案是用两个盒子。但要得到最佳方案，必须尝试所有种组合情况。当n很大时，这是不可能的。一种解决方案使用贪婪法数据结构-第五部分全文共83页，当前为第10页。11解决策略按给定的次序扫描每一个项，把每一个项放入能够容纳他而不至于溢出的最满的盒子。如果项的重量为0.4,0.4,0.6和0.6，贪婪法的方案是用三个盒子。其装载的重量分别为0.8,0.6,0.6数据结构-第五部分全文共83页，当前为第11页。12第15章算法设计技术枚举法贪婪法分而治之法动态规划回溯法随机算法介绍通用的算法设计模式数据结构-第五部分全文共83页，当前为第12页。13分而治之法分而治之法的思想分：递归解决若干个较小的问题治：从子问题的答案中形成原始问题的解分治法的的算法至少有两个递归调用已见过的分治法算法：快速排序，树的遍历数据结构-第五部分全文共83页，当前为第13页。14分治法实例最长连续子序列问题最近点问题数学计算问题数据结构-第五部分全文共83页，当前为第14页。15最长连续子序列问题假设输入是{4，－3，5，－2，－1，2，6，－2}。我们把这个输入划分成两部分，前四个和后四个。这样最大连续子序列的和可能出现在下面三种情况中。情况1：整个位于前半部，可递归计算。情况2：整个位于后半部，可递归计算。情况3：从前半部开始但在后半部结束。数据结构-第五部分全文共83页，当前为第15页。16情况3的解决方法从两半部分的边界开始，通过从右到左的扫描来找到左半段的最长序列。类似地，从左到右的扫描找到右半段的最长序列。把这两个子序列组合起来，形成跨越分割边界的最大连续子序列。在这个实例中，结果序列是从第一部分的第一个元素到第二部分的其余元素。总和是两个子序列的和，即4+7=11.数据结构-第五部分全文共83页，当前为第16页。17算法总结递归地计算整个位于前半部的最大连续子序列。递归地计算整个位于后半部的最大连续子序列。通过两个连续循环，计算从前半部开始但在后半部结束的最大连续子序列的和。选择三个和中的最大值。数据结构-第五部分全文共83页，当前为第17页。18IntmaxSum(inta[],intleft,intright){intmaxLeft,maxRight,center;intleftSum=0,rightSum=0;intmaxLeftTmp=NEGMAX,maxRightTmp=NEGMAX;center=(left+right)/2;if(left==right)returna[left]>0?a[left]:0;maxLeft=maxSum(a,left,center);maxRight=maxSum(a,center+1,right);数据结构-第五部分全文共83页，当前为第18页。19for(inti=center;i>=left;--i){leftSum+=a[i];if(leftSum>maxLeftTmp)maxLeftTmp=leftSum;}for(inti=center+1;i<=right;++i){rightSum+=a[i];if(rightSum>maxRightTmp)maxRightTmp=rightSum;}returnmax3(maxLeft,maxRight,maxLeftTmp+maxRightTmp);}数据结构-第五部分全文共83页，当前为第19页。20分治法实例最长连续子序列问题最近点问题数学计算问题数据结构-第五部分全文共83页，当前为第20页。21最近点问题在二维平面上有N个点，试找出距离最短的两个点。蛮力算法：计算两两之间的距离，从中找出最小的一个。N个点有N（N-1）/2对距离，因此时间复杂度为O(N2)数据结构-第五部分全文共83页，当前为第21页。22分治法解法将所有的点按x值排序。取一个合适的x值，把所有点分成两半PL和PR。距离最近的两个点可能出现在PL中(dL)，也可能出现在PR(dR)中，也可能一个点在PL，一个点在PR(dC)dL和dR可用递归得到dC的计算：设δ=min(dL,dR)如果dC比δ大，则没必要计算。因此用于计算dC的点必须落在分界线±δ的范围内，计算此范围中点对的距离中的最小值数据结构-第五部分全文共83页，当前为第22页。23dLdRdCδδ数据结构-第五部分全文共83页，当前为第23页。24优化在最坏的情况下，所有的点都落在分界线δ以内。但此时不一定要计算所有点对的距离。只要两点的y坐标大于δ，这两点之间的距离也不用算了。假设该区间中的点按y坐标排序，则可得下列算法数据结构-第五部分全文共83页，当前为第24页。25for(i=0;i<n;++i)if(pj+1的y-pj的y>=δ)break;elseif(dist(pj,pj+1)<δ)δ=dist(pj,pj+1);数据结构-第五部分全文共83页，当前为第25页。26分治法实例最长连续子序列问题最近点问题数学计算问题数据结构-第五部分全文共83页，当前为第26页。27数学计算问题设X和Y是两个N位的整数，假如一位乘法花费一个单位时间，那么计算X*Y的时间复杂性为O(N2)分治法计算将X和Y均分成两半，分别称为XL，XR，YL，YR。则X=XL10N/2+XR，Y=YL10N/2+YR。那么，XY=XLYL10N+(XLYR+XRYL)10N/2+XRYR时间复杂度：T(N)=4T(N/2)+O(N)=O(N2)数据结构-第五部分全文共83页，当前为第27页。28进一步改进上述算法的问题是需要太多次（4次）的递归调用。如果能减少递归调用，则能提高时间性能注意：XLYR+XRYL=(XL–XR)(YR–YL)+XLYL+XRYR

代入前式，XY=XLYL10N+(XLYR+XRYL)10N/2+XRYR=XLYL10N+((XL–XR)(YR–YL)+XLYL+XRYR)10N/2+XRYR

可见只需3次递归调用时间复杂性：数据结构-第五部分全文共83页，当前为第28页。29第15章算法设计技术枚举法贪婪法分而治之法动态规划回溯法随机算法介绍通用的算法设计模式数据结构-第五部分全文共83页，当前为第29页。30动态规划用表代替递归例：斐波那契函数f(n)=f(n-1)+f(n-2)。计算f(n)需要计算f(n-1)和f(n-2)。当计算f(n-1)时要计算f(n-2)和f(n-3)。因此在计算f(n)中f(n-2)被计算了两次。为了减少重复的递归调用，我们可以反过来计算。先计算f(2)，有了f(2)再计算f(3)，以此类推，计算到f(n)。在此过程中不需要任何递归数据结构-第五部分全文共83页，当前为第30页。31动态规划硬币找零问题最优二叉查找树数据结构-第五部分全文共83页，当前为第31页。32找零问题对于一种货币，有面值为C1,C2,…,CN(分)的硬币，最少需要多少个硬币来找出K分钱的零钱。数据结构-第五部分全文共83页，当前为第32页。33贪婪法解法我们不断使用可能的最大面值的硬币如：美元的硬币有1、5、10和25分的面值(忽略流通频率很低的50分硬币)。我们可以通过使用2个25分、一个10分的硬币以及三个1分来找出63分钱，一共是6个硬币。如果美元中包含一个21分硬币时，贪心算法仍然给出一个用六个硬币的解，但是最佳的解是用三个硬币(三个都是21分的硬币。)数据结构-第五部分全文共83页，当前为第33页。34解法1－－分治法如果我们可以用一个硬币找零，这就是最小的。否则，对于每个可能的值i，我们可以独立计算找i分钱零钱和K-i分钱需要的最小硬币数。然后选择这个和最小的i。

数据结构-第五部分全文共83页，当前为第34页。35怎样找出63分钱零钱找出1分钱零钱和62分钱零钱分别需要的硬币数是1和4。因此，63分钱需要使用五个硬币。找出2分钱和61分钱分别需要2和4个硬币，一共是六个硬币。我们继续尝试所有的可能性。我们看到一个21分和42分的分解，它可以分别用一个和两个硬币来找开，因此，这个找零问题就可以用三个硬币解决。我们需要尝试的最后一种分解是31分和32分。我们可以用两个硬币找出31分零钱，用三个硬币找出32分零钱，一共是五个硬币。因此最小值是三个硬币。数据结构-第五部分全文共83页，当前为第35页。36intcoin(intk){inti,tmp,intcoinNum=k;

if（能用一个硬币找零）return1;for(i=1;i<k;++i)if((tmp=coin(i)+coin(k-i))<coinNum)

coinNum=tmp;returncoinNum;}数据结构-第五部分全文共83页，当前为第36页。37上述解法分析此算法的效率很低事实上63分钱找零的问题是不会在一个合理的时间内解决的。就如Finbonacci函数一样数据结构-第五部分全文共83页，当前为第37页。38解法2通过指定其中的一个硬币来递归地简化问题。例如，对于63分钱，我们可以给出以下找零的办法。一个1分的硬币加上递归地分派62分钱一个5分的硬币加上递归地分派58分钱一个10分的硬币加上递归地分派53分钱一个21分的硬币加上递归地分派42分钱一个25分的硬币加上递归地分派38分钱该算法的问题仍然是效率问题数据结构-第五部分全文共83页，当前为第38页。39动态规划解效率低下主要是由于重复计算造成的。因此，可把已有子问题的答案存放起来，当再次遇到此子问题时就不用重复计算了。在本例中，我们用coinsUsed[i]代表了找i分零钱所需的最小硬币数。数据结构-第五部分全文共83页，当前为第39页。40算法思想先找出一分钱的找零方法，把最小硬币数存入coinUsed[1]依次找出2分钱、3分钱…的找零方法，知道到达要找零的钱为止：对每个要找的零钱i，可以把i分解成某个coins[j]和i-coins[j]，所需硬币数为coinUsed[i-coins[j]]+1。对所有的j，取最小的coinUsed[i-coins[j]]+1作为i元钱找零的的答案。数据结构-第五部分全文共83页，当前为第40页。41函数原型Voidmakechange(intcoins[],intdifferentCoins,intmaxChange,intcoinUsed[])Coins存放所有不同的硬币值，不同的硬币个数为differentCoins。maxChange为要找的零钱数数据结构-第五部分全文共83页，当前为第41页。42voidmakechange(intcoins[],intdifferentCoins,intmaxChange,intcoinUsed[]){coinUsed[0]=0;for(intcents=1;cents<=maxChange;cents++){intminCoins=cents;for(intj=1;j<differentCoins;j++){if(coins[j]>cents)continue;if(coinUsed[cents-coins[j]]+1<minCoins)minCoins=coinUsed[cents-coins[j]]+1;}coinUsed[cents]=minCoins;}}

数据结构-第五部分全文共83页，当前为第42页。43动态规划硬币找零问题最优二叉查找树数据结构-第五部分全文共83页，当前为第43页。44最优二叉查找树有一组词w1,w2,…,wN，他们的出现概率分别为p1,p2,…pN。构建一棵二叉排序树使得访问时间的期望值最小。即如果wi所在的层次是di，那么该问题类似于哈夫曼树，概率大的靠近根，概率小的远离根。但它比哈夫曼树更复杂。因为它还要满足二叉排序树的特性数据结构-第五部分全文共83页，当前为第44页。45贪婪法的解法选择出现概率最大的词作为树根，把剩余的词分成两组：小于根的和大于根的。递归构建左子树和右子树。A0.22Am0.18And0.20Egg0.05If0.25The0.02two0.08iftwotheaandamegg显然不是最优的，代价为：2.43数据结构-第五部分全文共83页，当前为第45页。46最优解法假如要对wleft到wright构建一棵最优二叉排序树，那么这棵树的形式一定是根为wi，左子树的节点为left到i-1，右子树的节点为i+1到right，左子树和右子树也是最优的设Cleft，right是树的代价，那么数据结构-第五部分全文共83页，当前为第46页。47最优解法对a,am.and,egg,if,the,two对所有的可能的情况计算它的代价，从中找出最小的：根为a，左子树为空，右子树为am，…，two。根为am，左子树为a，右子树为and,…，two。根为and，左子树为a，am,右子树为egg,…，two。根为egg，左子树为a,am,and,右子树为if,…，two。…在上述每一种情况中，我们需要继续递归。如：在尝试根为egg，左子树为a,am,and,右子树为if,…，two的情况时，要找出最优的左子树，我们又要尝试根节点为a，左子树为空，右子树为am和and根节点为am，左子树为a，右子树为and根节点为and，左子树为a和am，右子树为空。数据结构-第五部分全文共83页，当前为第47页。48动态规划解法从上述分析可以看出，在找出由a到two组成的最优树时，由a组成的树，由a和am组成的树，由am和and组成的树，…，会分别被计算很多次。解决方法：从小到大计算由n个节点组成的最优树，并把它保存在一个表中。当所有的节点形成了一棵树时，任务就完成了。每棵树的保存用两个信息：根和代价。数据结构-第五部分全文共83页，当前为第48页。49生成过程先生成由一个节点组成的树。树的代价就是节点的权值。保存这些树和相应的代价。生成所有由两个节点组成的树：将第一个节点作为根，第二个节点作为右子树。计算代价。将第二个节点作为根，第一个节点作为右子树。计算代价。取代价小的树作为最终的树保存下来。生成由三个节点组成的树，四个节点组成的树…数据结构-第五部分全文共83页，当前为第49页。50two0.08the0.02if0.25egg0.05and0.20am0.18a0.22Two..twoThe..theIf..ifEgg..eggAnd..andAm..ama..aLeft=7Left=6Left=5Left=4Left=3Left=2Left=1a0.58a..amand0.56Am..andand0.30And..eggif0.35Egg..ifif0.29If..thetwo0.12The..twoand0.66Am..eggand0.80And..ifif0.39Egg..theif0.47If..twoAm1.02a..andand1.21Am..ifif0.84And..theif0.57Egg..twoAm1.17a..eggand1.27Am..theif1.02And..twoAnd1.83a..ifand1.53Am..twoAnd1.89a..theAnd2.15a..twoi=1i=2i=3i=4i=5i=6i=7andaamifeggtwothe数据结构-第五部分全文共83页，当前为第50页。51第15章算法设计技术枚举法贪婪法分而治之法动态规划回溯法随机算法介绍通用的算法设计模式数据结构-第五部分全文共83页，当前为第51页。52第15章算法设计技术枚举法贪婪法分而治之法动态规划回溯法随机算法介绍通用的算法设计模式数据结构-第五部分全文共83页，当前为第52页。53回溯法八皇后问题分书问题首先暂时放弃问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现候选解不可能是解时，就选择下一候选解。如果当前候选解除了不满足规模要求外，满足其他所有要求时，继续扩大当前候选解的规模，并继续试探。如果当前的候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。数据结构-第五部分全文共83页，当前为第53页。54八皇后问题在一个8*8的棋盘上放8个皇后，使8个皇后中没有两个以上的皇后会在同一行、同一列或同一对角线上数据结构-第五部分全文共83页，当前为第54页。55八皇后问题的求解过程求解过程从空配置开始，在第一列到第m列为合理配置的基础上再配置m+1列，直到第n列的配置也时合理时，就找到了一个解。另外在一列上也有n种配置。开始时配置在第一行，以后改变时，顺序选择第二行、第三行、。。、第n行。当配置到第n行时还找不到一个合理的配置时，就要回朔，去改变前一列的配置。数据结构-第五部分全文共83页，当前为第55页。56算法{m=0;/*从空配置开始*/good=true;/*配置中的皇后不冲突*/do{if(good)if(m==8){输出解；重新寻找下一可行的解；

}else向前试探，扩展至下一列；

else回朔，形成下一候选解；

good=检查当前候选解的合理性；

}while(m!=0);}数据结构-第五部分全文共83页，当前为第56页。57棋盘的数据结构的设计比较直观的方法是采用一个二维数组，但仔细考察，就会发现，这种表示方法给调整候选解及检查其合理性会带来困难。对于本题来说，我们关心的并不是皇后的具体位置，而是“一个皇后是否已经在某行和某条斜线合理地安置好了”。因为在每一列上恰好放一个皇后，所以引入一个一维数组(设为col（9）)，值col[j]表示在棋盘第j列上的皇后位置。如col[3]的值为4，就表示第三列的皇后在第四行。另外，为了使程序在找完了全部解后回溯到最初位置，设定col[0]的初值为0。当回溯到第0列时，说明程序已求得全部解(或无解)，结束程序执行。数据结构-第五部分全文共83页，当前为第57页。58候选解的合理性检查引入以下三个工作数组数组a[9]，a[A]=true表示第A行上还没有皇后；数组b[16]，b[A]=true表示第A条右高左低斜线上没有皇后；从左上角依次编到右下角(1-15)。数组c[16]，c[A]=true表示第A条左高右低斜线上没有皇后。从左下角依次编到右上角(1-15)。数据结构-第五部分全文共83页，当前为第58页。59

voidqueen_a11(intk)//在8x8棋盘的第k列上找合理的配置{inti,j;charawn;for(i=1;i<=9;i++)//依次在l至8行上配置k列的皇后if(a[i]&&b[k+i-1]&&c[8+k-i])//可行位置{col[k]=i;a[i]=b[k+i-1]=c[8+k-i]=false;//置对应位置有皇后if(k==8)//找到一个可行解{for(j=1;j<=8;j++)cout<<j<<col[j]<<'\t'; cout<<endl;cin>>awn;if(awn=='Q'||awn=='q')exit(0);}elsequeen_a11(k+1);//递归至第k十1列a[i]=b[k+i-1]=c[8+k-i]=true;//恢复对应位置无皇后

}}

数据结构-第五部分全文共83页，当前为第59页。60主程序intcol[9];boola[9],b[17],c[17];intmain(){intj;for(j=0;j<=8;j++)a[j]=true;for(j=0;j<=16;j++)b[j]=c[j]=true;queen_a11(1);return0;}数据结构-第五部分全文共83页，当前为第60页。61回溯法八皇后问题分书问题首先暂时放弃问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现候选解不可能是解时，就选择下一候选解。如果当前候选解除了不满足规模要求外，满足其他所有要求时，继续扩大当前候选解的规模，并继续试探。如果当前的候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。数据结构-第五部分全文共83页，当前为第61页。62分书问题有编号为0，1，2，3，4的5本书，准备分给5个人A，B，C，D，E，每个人的阅读兴趣用一个二维数组描述：

Like[i][j]=truei喜欢书jLike[i][j]=falsei不喜欢书j

写一个程序，输出所有皆大欢喜的分书方案0011011001011010001001001数据结构-第五部分全文共83页，当前为第62页。63存储设计用一个二维数组like存储用户的兴趣用一个一维的整型数组take表示某本书分给了某人。Take[j]=i表示第j本书给了第i个人。数据结构-第五部分全文共83页，当前为第63页。64解题思路依次尝试把书j分给人i。如果第i个人不喜欢第j本书，则尝试下一本书，如果喜欢，并且第j本书尚未分配，则把书j分配给i。如果i是最后一个人，则方案数加1，输出该方案。否则调用try（i+1)为第i+1个人分书。回溯。让第i个人退回书j，尝试下一个j，即寻找下一个可行的方案由于在每次try中都要用到like，take以及目前找到的方案数n，因此可将它们作为全局变量，以免每次函数调用时都要带一大串参数。设计一个函数try(i)给第i个人分书。数据结构-第五部分全文共83页，当前为第64页。65voidtrynext(inti){intj,k;for(j=0;j<5;++j){if(like[i][j]&&take[j]==-1){ take[j]=i;if(i==4){ n++;cout<<"\n第"<<n<<"种方案:"<<endl; cout<<"书\t人"<<endl;for(k=0;k<5;k++)cout<<k<<'\t'<<char(take[k]+'A')<<endl;}elsetrynext(i+1);take[j]=-1; }}}数据结构-第五部分全文共83页，当前为第65页。66当like矩阵的值为调用trynext(0);的结果为：第1种方案：书人0B1C2A3D4E第2种方案：书人0B1E2A3D4C数据结构-第五部分全文共83页，当前为第66页。67第14章算法设计技术枚举法贪婪法分而治之法动态规划回溯法随机算法介绍通用的算法设计模式数据结构-第五部分全文共83页，当前为第67页。68随机算法在算法中，至少有一个地方使用随机数作决策。随机算法的时间复杂度取决于选择的随机数随机算法的时间复杂度用期望的运行时间来表示。一般假设随机数的选择是均匀分布的例如，在快速排序中将中间点用随机数来选择，则快速排序成为一个随机算法。可以证明，期望的时间复杂度为O(NlogN)数据结构-第五部分全文共83页，当前为第68页。69随机算法实例跳表素数检测数据结构-第五部分全文共83页，当前为第69页。70跳表以O(logN)的期望的时间复杂性支持插入和删除的数据结构跳表的概念：支持动态查找必须用链表，但链表查找的时间为N。可以用增加链的方式提高查找效率增加一条链，让头节点指向第二个节点，第二个节点指向第四个节点，第四个节点指向第六个节点，…。查找时间为再增加一条链，让头节点指向第四个节点，第四个节点指向第八个节点，第八个节点指向第十二个节点，…。查找时间为推而广之，对于2i<N≤2i+1个节点，设置i条链，第j条链指向其后的第2j个节点数据结构-第五部分全文共83页，当前为第70页。71821011131920222325821013192023251122821013192023251122数据结构-第五部分全文共83页，当前为第71页。72查找过程（节点x）首先查找第i条链，如下一节点比x大，则查找第i-1条链，否则继续查找第i条链。依次执行，直到找到或找不到x最坏情况下的时间性能：数据结构-第五部分全文共83页，当前为第72页。73插入过程当插入一节点时，所有的节点都要变化。为了避免这个变化，插入采用随机算法定义：有k条链的节点称为level-k节点在跳表中，level-i的节点有N/2i个，即level-i的节点出现的概率为1/2i。插入过程：查找到插入点生成一个新节点按概率生成节点的level插入该节点因此跳表并不一定是严格的隔2i个节点有一条第i层的链，而只是从概率上讲符合此分布数据结构-第五部分全文共83页，当前为第73页。74随机算法实例跳表素数检测数据结构-第五部分全文共83页，当前为第74页。75素数检测方法一：依次检测1到N能否被N整除，如果能被整除的数的个数等于2，则N是素数。时间复杂度为O（N）方法二：依次检测2、3、5、7到sqrt(N)，只要有一个能整除N，则N为非素数。最坏情况的时间复杂度O(N1/2)上述两方法对小素数适合，大素数不适合方法三：随机算法。该算