数据结构-清华大学-殷人昆-06

第6章查找清华大学计算机系殷人昆数据结构课件第六章查找世上万物，琳琅尽致快意搜索享尽人间无穷信息134-2查找的概念顺序查找折半查找静态查找树索引结构与B树散列法第6章查找134-3查找(Search)的概念所谓查找，就是在数据集合中寻找满足某种条件的数据元素。查找的结果通常有两种可能：查找成功，即找到满足条件的数据元素。这时，作为结果,可报告该元素在结构中的位置,还可给出该元素中的具体信息。查找不成功，或查找失败。作为结果,应报告一些信息，如失败标志、位置等。通常称用于查找的数据集合为查找结构，它是由同一数据类型的元素（或记录）组成。134-4在每个元素中有若干属性，其中有一个属性，其值可唯一地标识这个元素。称为关键字（key）。使用基于关键字的查找，查找结果应是唯一的。但在实际应用时，查找条件是多方面的，可以使用基于属性的查找方法，但查找结果可能不唯一。衡量一个查找算法的时间效率的标准是：在查找过程中关键字的平均比较次数，也称为平均查找长度ASL(AverageSearchLength)，通常它是查找结构中元素总数n的函数。静态查找常基于线性表，动态查找常基于树或字典。134-5静态查找表结构的定义#definemaxSize100//查找表最大尺寸typedefintElemType;//查找数据的类型typedefstruct{//查找表结点定义ElemTypekey;//关键字域other;//其他数据信息}ListNode;typedefstructdataList{//查找表结点定义ListNodedata[maxSize];//数据存储数组intn;//数组当前长度}134-6顺序查找(SequentialSearch)所谓顺序查找,又称线性查找,主要用于在线性结构中进行查找。设若表中有n个元素，则顺序查找从表的先端（或后端）开始，依次用各元素的关键字与给定值x进行比较，直到找到与其值相等的元素，则查找成功；给出该元素在表中的位置。若整个表都已检测完仍未找到关键字与x相等的元素,则查找失败。给出失败信息。134-7设置“监视哨”的顺序查找算法intLinearSearch(dataList&L,ElemTypex){//在数据表L.data[0]..L.data[n-1]中顺序查找关键字//值与给定值x相等的数据元素,L.data[n].key作为//控制搜索自动结束的“监视哨”使用L.data[L.n].key=x;inti=0;//将x送表尾的下一个位置设置监视哨while(L.data[i].key!=x)i++;//从前向后顺序查找returni;}134-8设查找第i个元素的概率为pi，查找到第i个元素所需比较次数为ci，则查找成功的平均查找长度为:在顺序查找并设置“监视哨”情形，ci=i+1,i=0,1,,n-1，因此-10-10succ)1(.ASLniiniiipcp1)(ASL-10succipnii算法分析134-9设查找概率相等，即pi=1/n,i=1,2,,n。则查找成功的平均查找长度为：而查找不成功时，一定把表中所有元素检测了一遍，一直到监视哨。所以查找不成功的平均查找长度为：ASLunsucc=n+1。顺序查找可以用递归方法实现。当查找表中第一个元素即为所求，查找成功；否则对除第一个元素外的后续表元素构成的查找表使用相同方法递归查找。当后续查找表为空，则查找失败。.-102121)(11)(1nisuccnnnninASL134-10顺序查找的递归算法intSeqSearch(dataList&L,ElemTypex,intloc){//在数据表L.data[0]..L.data[n-1]中查找其关键字值//与给定值x匹配的元素,函数返回其表中位置。//参数loc是在表中开始查找位置if(loc=L.n)return-1;//查找失败elseif(L.data[loc].key==x)returnloc;//查找成功elsereturnSeqSearch(L,x,loc+1);//递归查找}134-11基于有序顺序表的顺序查找有序顺序表限定表中的元素按照其关键字值从小到大或从大到小依次排列。在这类表中进行查找比表中元素任意存放，查找速度会有所提高。在有序顺序表中做顺序查找时，若查找不成功，不必检测到表尾才停止，只要发现有比它的关键字值大的即可停止查找。若设表中有n个元素，则查找成功的平均查找长度依旧，而查找不成功的平均查找长度为：21)(111)(11-10nnnninnASLniunsucc134-12基于有序顺序表的顺序查找算法intSeqSearch(dataList&L,ElemTypex){//在数据表L.data[0]..L.dada[n-1]中顺序查找关键字//值为x的数据元素for(inti=0;iL.n;i++)if(L.data[i].key==x)returni;//成功成功elseif(L.data[i].keyx)break;//查找失败return-1;//顺序查找失败,返回失败信息}134-13有序顺序表的顺序查找示例及分析其查找效率的判定树：(10,20,30,40,50,60)271)(6150isucciASL72761)(7150iunsucciASL1050======20304060134-14折半查找折半查找只适用于有序顺序表。做折半查找时,先求位于查找区间正中的元素的下标mid，用其关键字值与给定值x比较:A.data[mid].key==x,查找成功；A.data[mid].keyx,把查找区间缩小到表的前半部分，继续折半查找；A.data[mid].keyx，把查找区间缩小到表的后半部分，继续折半查找。如果查找区间已缩小到一个元素，仍未找到想要查找的元素，则查找失败。134-15查找成功的例子-101346810126012345678查找lowmidhigh66810125678lowmidhigh665lowmidhigh6134-16查找失败的例子-101346810125012345678查找lowmidhigh56810125678lowmidhigh655lowmidhigh5134-17折半查找的算法intBinSearch(dataList&L,ElemTypex){inthigh=L.n-1,low=0,mid;while(low=high){//lowhigh表明失败mid=(low+high)／2;if(L.data[mid].keyx)low=mid+1;//右缩查找区间elseif(L.data[mid].keyx)high=mid-1;//左缩查找区间elsereturnmid;//查找成功}return-1;//查找失败}134-18递归的折半查找算法intBinSearch(dataList&L,ElemTypex,intlow,inthigh){intmid=-1;if(low=high){mid=(low+high)／2;if(L.data[mid].keyx)mid=BinSearch(L,x,mid+1,high);elseif(L.data[mid].keyx)mid=BinSearch(L,x,low,mid-1);}returnmid;}//调用方式BinSearch(L,x,0,L.n-1);134-19有序顺序表的折半查找的判定树(10,20,30,40,50,60)50======30204060ASLunsucc=(2*1+3*6)/7=20/7ASLsucc=(1+2*2+3*3)/6=14/610134-20折半查找性能分析若设n=2h-1，则描述折半查找的判定树是高度为h的满二叉树。2h=n+1,h=log2(n+1)第1层结点有1个,查找第1层结点要比较1次;第2层结点有2个,查找第2层结点要比较2次;…,第i(1ih)层结点有2i-1个,查找第i层结点要比较i次，…。假定每个结点的查找概率相等，即pi=1/n，则查找成功的平均查找长度为134-21121)(221)(2322111221hhhhhh11)(log11)(log1)1)(1)log((11)21)((1222nnnnnnnnhnASLhsucc)2*2*1)(2*32*22*(1111221011-hhniiniiisucchhncncpASL可以用归纳法证明：这样134-22)211)((11))2(121)((1hhhsuccnhnnhhnASL-当表中关键字个数n2h-1时，它对应的判定树是一棵理想平衡树，其高度h=log2(n+1)；判定树第h层上面的h-1层是满的，有2h-1-1个结点，第h层有n-(2h-1-1)个结点。因此有1))2(*2*2(1n11))2*2*1)(2*32*22*(111012210hhhhsuccnhhnhhnASL-（134-23例如，右图是n=8的折半查找的判定树，查找成功的平均查找长度为使用上述计算式，h=log2(8+1)=4，查找成功的平均查找长度为8211)*44*32*21*(181ASLsucc821)219*(481211)(n*(hn1ASL4hsucc)-134-24静态查找树当有序顺序表各个结点的查找概率不等时，折半查找并非最优，可用静态查找树描述或构造其查找过程。设含有5个关键字的有序表(A,D,H,U,X)，其查找概率分别为比较相应于折半查找的判定树和用其他方法构成的查找树，其平均查找长度是不同的。ADHUXp1=0.1p2=0.1p3=0.2p4=0.4p5=0.2134-25折半查找在相等查找概率下其查找性能最好；在查找概率不相等的情况下，可以利用构造次优查找树的方法建立描述最佳查找过程的查找树。p1=0.1ADHUXp2=0.1p3=0.2p4=0.4p5=0.2ASLsucc=0.2*1+(0.1+0.4)*2+(0.1+0.2)*3=2.1DUXHAp1=0.1p2=0.1p3=0.2p4=0.4p5=0.2ASLsucc=0.4*1+(0.1+0.2)*2+(0.1+0.2)*3=1.9折半查找的判定树另一查找树134-26设有序顺序表中关键字为k1,k2,,kn,它们的查找概率分别为p1,p2,,pn,构成查找树后，它们在树中的层次为l1,l2,…,ln。基于该查找树的查找算法的平均查找长度为使得ASLsucc达到最小的静态查找树为静态最优二叉排序树。然而，求最优查找树的算法效率较低，达O(n3),可求次优查找树，其时间代价减低为O(nlog2n)。-10niiisucclpASL次优查找树的构造方法134-27次优查找树的构造设有一个按关键字值有序的子序列{kl,kl+1,,ki,,kh}l为下界，h为上界其权值分别为{wl,wl+1,,wi,,wh}轮流以各个关键字ki作根,计算其中，是从wl到wi-1的权值之和；1l1ikhikkkiwwPΔ1ilkkw134-28是从wi+1到wh的权值之和；是ki两边权值之差。Pi越小，ki两边权值之和越接近。选择使得Pi达到最小的ki作为整个序列的根，它将整个序列分为两个子序列:{kl,,ki-1}将是ki的左子树部分{ki+1,,kh}将是ki的右子树部分再对各子序列作同样的求根和划分子序列操作。hikkw