数据结构耿国华高教版 第8章

第八章查找8.1查找的基本概念8.2基于线性表的查找法8.3基于树的查找法8.4计算式查找法－哈希法8.5总结与提高第八章查找8.1查找的基本概念列表：由同一类型的数据元素（或记录）构成的集合，可利用任意数据结构实现。关键字：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。主关键字：如果一个关键字可以唯一标识列表中的一个数据元素，则称其为主关键字，否则为次关键字。当数据元素仅有一个数据项时，数据元素的值就是关键字。查找：根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。在查找算法中要用到三类参量，即：①查找对象K（找什么）②查找范围L（在哪找）③查找的结果（K在L中的位置）其中①、②为输入参量，在函数中不可缺少。③为输出参量，可用函数返回值表示。平均查找长度：为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。对于长度为n的列表，查找成功时的平均查找长度为：ASL=P1C1+P2C2+…+PnCn=i=1nPiCi其中Pi为查找列表中第i个数据元素的概率，Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。查找的基本方法：比较式查找法计算式查找法－HASH（哈希）查找法基于线性表的查找法基于树的查找法8.2基于线性表的查找法具有顺序查找法、折半查找法和分块查找法三种8.2.1顺序查找法顺序查找法的特点是：用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。存储结构：顺序结构链式结构顺序结构有关数据类型的定义：#defineLIST_SIZE20typedefstruct{KeyTypekey;OtherTypeother_data;}RecordType;typedefstruct{RecordTyper[LIST_SIZE+1];/*r[0]为工作单元*/intlength;}RecordList;设置监视哨的顺序查找算法intSeqSearch（RecordListl,KeyTypek）/*在顺序表l中顺序查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否则为0*/{l.r[0].key=k;i=l.length;while(l.r[i].key!=k)i--;return（i）;}其中l.r[0]为监视哨，可以起到防止越界的作用。不设置监视哨的顺序查找算法intSeqSearch（RecordListl,KeyTypek）/*不用监视哨法，在顺序表中查找关键字等于k的元素*/{l.r[0].key=k;i=l.length;while(i=1&&l.r[i].key!=k)i--;if(i=1)return（i）elsereturn(0);}循环条件i=1判断查找是否越界。用平均查找长度分析顺序查找算法的性能。假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较，即Ci=n-i+1。又假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为：ASL=i=1nPiCi＝n1i=1nCi＝n1i=1n(n-i+1)=21(n+1)8.2.2折半查找法（二分法查找法）条件：要求待查找的列表必须是按关键字大小有序排列的顺序表。基本过程：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。例如用折半查找法查找10、50的具体过程，其中mid=(low+high)/2，当highlow时，表示不存在这样的子表空间，查找失败。6058463528252218151261234567891011low=1mid=6high=116058463528252218151261234567891011low=1mid=3high=5用折半查找法查找12的过程为：6058463528252218151261234567891011low=1mid=1high=26058463528252218151261234567891011low=2mid=2high=2用折半查找法查找50的过程：6058463528252218151261234567891011low=1mid=6high=116058463528252218151261234567891011low=7mid=9high=116058463528252218151261234567891011low=10mid=10high=116058463528252218151261234567891011low=10high=9折半查找的算法如下：intBinSrch（SqListl,KeyTypek）/*在有序表l中折半查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置*/{low=1;high=l.length;/*置区间初值*/while(low=high){mid=(low+high)/2;if(k==l.r[mid].key)return（mid）;/*找到待查元素*/elseif(kl.r[mid].key)high=mid-1;/*未找到，则继续在前半区间进行查找*/elselow=mid+1;/*继续在后半区间进行查找*/}return(0);}用平均查找长度分析折半查找算法的性能折半查找成功时的平均查找长度为：ASLbs＝i=1nPiCi＝n1j=1nj×2j-1＝nn+1log2(n+1)-1优点：比较次数少，查找速度快，平均性能好。缺点：要求待查的表为有序表，且插入、删除困难。8.2.3分块查找法分块查找法要求将列表组织成以下索引顺序结构：★首先将列表分成若干个块（子表）。一般情况下，块的长度均匀，最后一块可以不满。每块中元素任意排列，即块内无序，但块与块之间有序。★构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置，和每块中的最大关键字（或最小关键字）。索引表按关键字有序排列。下图为一个索引顺序表2558888871605836453228825121418索引表各块内的最大关键字各块的起始地址列表0123456789101112此表包括三个块，第一个块的起始地址为0，块内最大关键字为25;第二个块的起始地址为5，块内最大关键字为58;第三个块的起始地址为10，块内最大关键字为88。分块查找的基本过程为：（1）首先，将待查关键字K与索引表中的关键字进行比较，以确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。（2）进一步用顺序查找法，在相应块内查找关键字为K的元素。例如查找上图索引表中36。分块查找的平均查找长度由两部分组成：即查找索引表时的平均查找长度为LB，以及在相应块内进行顺序查找的平均查找长度LW。ASLbs=LB+LW假定将长度为n的表分成b块，且每块含s个元素，则b=n/s。又假定表中每个元素的查找概率相等，则每个索引项的查找概率为1/b，块中每个元素的查找概率为1/s。若用顺序查找法确定待查元素所在的块，则有：LB＝b1∑j＝j=1bb＋12Lw＝s1∑j＝i=1ss＋12ASLbs=LB+LW＝2b+s+1将b=n/s代入，得ASLbs＝21+1sn+s)(8.3基于树的查找法基于树的查找法（树表查找法），是将待查表组织成特定树的形式并在树结构上实现查找的方法。基于树的查找法二叉排序树平衡二叉排序树B树8.3.1二叉排序树二叉排序树（二叉查找树），它是一种特殊结构的二叉树，其定义为：二叉树排序树或者是一棵空树，或者是具有如下性质的二叉树：（1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；（3）它的左右子树也分别为二叉排序树。由定义可以得出二叉排序树的一个重要性质：中序遍历一个二叉排序树时可以得到一个递增有序序列。521436879二叉排序树示例1CAOZHAODINGCHENWANG二叉排序树示例2使用二叉链表作为存储结构，其结点结构说明如下：typedefstructnode{KeyTypekey;/*关键字的值*/structnode*lchild,*rchild;/*左右指针*/}bstnode,*BSTree;1.二叉树的插入和生成①若二叉排序树是空树，则Key成为二叉排序树的根；②若二叉树排序树非空，则将key与二叉树排序树的根进行比较，如果key的值等于根结点的值，则停止插入，如果key的值小于根结点的值，则将key插入左子树，如果key的值大于根结点的值，则将key插入右子树。已知一个关键字值为Key的结点s，插入的方法：二叉排序树的插入算法：voidInsertBST(BSTree*bst,KeyTypekey)/*若在二叉排序树中不存在关键字等于key的元素，插入该元素*/{BiTrees;if(*bst==NULL)/*递归结束条件*/{s=(BSTree)malloc(sizeof(BSTNode));/*申请新的结点s*/s-key=key;s-lchild=NULL;s-rchild=NULL;*bst=s;}elseif(key(*bst)-key)InsertBST(&((*bst)-lchild),key);/*将s插入左子树*/elseif(key(*bst)-key)InsertBST(&((*bst)-rchild),key);/*将s插入右子树*/}二叉排序树的生成方法：假若给定一个元素序列，可以利用上述算法创建一棵二叉排序树。将二叉排序树初始化为一棵空树，然后逐个读入元素，每读入一个元素，就建立一个新的结点插入到当前已生成的二叉排序树中，即调用上述二叉排序树的插入算法将新结点插入。生成二叉排序树的算法：voidCreateBST(BSTree*bst)/*从键盘输入元素的值，创建相应的二叉排序树*/{KeyTypekey;*bst=NULL;scanf(%d,&key);while(key!=ENDKEY)/*ENDKEY为自定义常数*/{InsertBST(bst,key);scanf(%d,&key);}}设关键字的输入顺序为：45，24，53，12，28，90，按上述算法生成的二叉排序树的过程：空树45插入454524插入24452453插入5345245312插入124524531228插入28452453122890插入90对同样一些元素值，如果输入的顺序不同，则所建的二叉树形态也不同。如果将上述例子中的关键字顺序变为：24，53,90,12,28,45,则生成的二叉排序树为：2412285390452.二叉排序树的删除删除操作：首先确定被删除的结点是否在二叉排序树中。若不在，则不做任何操作；否则，假设要删除的结点为p，结点p的双亲结点为f，并假设结点p是结点f的左孩子（右孩子的情况类似）。从二叉排序树中删除一个结点，必须保证删除后所得的二叉树仍然满足二叉排序树的性质不变。下面分三种情况讨论：（2）若p结点只有左子树，或只有右子树，则可将p的左子树或右子树直接改为其双亲结点f的左子树。即：f-lchild=p-lchild（或f-lchild=p-rchild）；free(p)；（1）若p为叶结点，则可直接将其删除：f-lchild=NULL；free(p)；（3）若p既有左子树，又有右子树，如下图(a)，则处理的方法有两种：FPPLPRfp(a)P的左右子树均不空方法一：首先找到p结点在中序序列中的直接前驱s结点，如图(b)所示，然后将p的左子树改为f的左子树，而将p的右子树改为s的右子树：f-lchild=p-lchild；s-rchild=p-rchild；free(p)；结果如图(