数据结构课件25讲第九章查找

第九章查找本章内容与要点本章内容讨论基于比较的各种查找的实现方法：顺序表查找、有序表查找、树表查找、哈希表查找以及相应的衡量查找效率的平均查找长度的分析。本章要点熟练掌握顺序表和有序表的查找方法，并能灵活应用；熟练掌握二叉排序树的构造和查找方法；掌握哈希表的构造方法。各种查找方法的查找效率分析；基本概念查找:就是在一组数据集合中找到满足某种条件的数据。查找表由同一类型的数据元素构成的集合；静态查找表对查找表的查找仅是以查询为目的，不改动查找表中的数据。动态查找表在查找的过程中同时插入不存在的记录，或删除某个已存在的记录。关键字数据元素（或记录）的某个数据项，能用来标识一个数据元素。若能唯一的标识一个数据元素，则称为主关键字（primarykey），反之则为次关键字（secondarykey）。基本概念（续）查找成功查找表中存在满足查找条件的记录。查找不成功查找表中不存在满足查找条件的记录。内查找整个查找过程都在内存中进行。外查找在查找过程中需要访问外存。平均查找长度ASL——查找方法时效的度量为确定记录在查找表中的位置，需将关键字和给定值比较次数的期望值。查找成功时的ASL计算方法：n：记录的个数pi：查找第i个记录的概率，(不特别声明时认为等概率pi=1/n)ci：找到第i个记录所需的比较次数9.1静态查找表顺序表的查找通常查找表中的各元素（或记录）的关键字的值是无序的。实际查找时，通常将给定值放在第0个记录处，然后从后向前查找，直到找到所查记录为止，找不到则返回结果0。因为记录0像哨兵一样看守着查找表下界，所以不会越界。typedefintKeytype; /*定义关键字类型为整型*/typedefstruct{Keytypekey; /*关键字*/ /*此处为其它数据项*/}Rcdtype; /*记录类型*/顺序表算法及性能分析intsequelsearch(Rcdtypes[],Keytypekey,intn){/*在s[1]~s[n]中顺序查找关键字为key的记录*/ for(i=n;i>0&&s[i].key!=key;i--); returni;}性能分析查找成功时ASLs(n)==(1+2+...+n)/n=(n+1)/2查找失败时ASLf=n+1s[0]=key;for(i=n;s[i].key!=key;i--); returni;静态查找表有序表的查找有序表查找表中的各元素（或记录）的关键字的值是有序的。仍可用顺序查找，但在找不到时不需比较到表尾，只需比较到比给定值大的记录就可终止。在等概率情况下，顺序查找有序表的平均查找长度为：ASL成功

=（n+1)/2ASL不成功

=（n+2)/2。有序表的查找比较好的方法是折半查找。二分法查找－－－折半查找将给定值与中间的记录进行比较；若找到则查找成功；否则若给定值比中间记录小，则对前一半子表进行折半查找，反之则对后一半子表进行折半查找。若在查找过程中，遇到查找子表的上界小于下界，则表示查找失败。

设顺序表中有11个记录，它们的关键字依次为{7,15,19,21,38,40,66,78,83,102,110}，用二分查找法在该顺序表中查找关键字为21和63的记录。7 15 19213840667883102110lowhighmid7 15 19213840667883102110lowmidhigh查找关键字21查找关键字63折半查找算法的非递归算法intbinarysearch(Rcdtypes[],Keytypekey,intn){low=1;high=n;while(low<=high) { mid=(low+high)/2; if(key==s[mid].key)returnmid; elseif(key<s[mid].key)high=mid-1; elselow=mid+1; } return0;}折半查找算法的递归算法intbinarysearch2(Rcdtypes[],Keytypekey,intlow,inthigh){ if(low>high)return0; else { mid=(low+high)/2; if(s[mid].key==key)returnmid; elseif(s[mid].key>key) returnbinarysearch2(s,key,low,mid-1); else returnbinarysearch2(s,key,mid+1,high); }}折半查找的性能分析折半查找每次只查表的一半，其所有记录的查找路径构成一棵二叉树，称为折半查找树（或判定树），每次查找只走了该树的一条分支，故平均查找长度不超过log2n+1折半查找举例有一组记录的关键字为{1，2，3，4，5，6，7，8}，求其在等概率情况下查找成功的平均查找长度：42516378其查找树如左图所示：ASL成功

==21/8。1*1+2*2+3*4+4*189.1.3分块查找－－索引顺序表的查找索引顺序表带索引表的顺序表索引部分一定是有序的，这部分可用折半查找等方法；顺序表本身不一定有序，要根据顺序表是否有序而选用相应的查找方法。分块查找（blockingsearch）将索引部分和表体部分分开查找的方法。索引表的平均查找长度为两部分查找之和。35689311013最大关键字起始地址索引表231611356283125194157689375886913245678910111213141516顺序表9.2树表的动态查找二叉排序树9.2.1二叉排序树空或有一个根；根的左子树若非空，则左子树上的所有结点的关键字值均小于根结点的值；根的右子树若非空，则右子树上的所有结点的关键字值均大于根结点的值；根结点的左、右子树也分别为二叉排序树；12225030011020099LNPEMCY105230216二叉排序树查找算法思路：btreebssearch(btreebt,Keytypekey)/*在二叉排序树查找关键字之值为key的结点，找到返回该结

点的地址，否则返回空。bt为二叉排序树的根结点的地址。*/{if((!bt)||key==bt->key))return(bt);elseif(key<bt->key) return(bssearch(bt->lchild,key));elsereturn(bssearch(bt->rchild,key));}若根结点的关键字值等于查找的关键字,成功;否则，若小于根结点的关键字值，查其左子树;若大于根结点的关键字值，查其右子树;在左右子树上的操作类似。122250300110200991052302161222503001102009910523021628030011099eg：将数的序列：122、99、250、110、300、280作为二叉排序树的结点的关键字值，生成二叉排序树。二叉排序树的插入首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右孩子。将被插结点作为叶子结点插入。若二叉树为空,则首先单独生成根结点。注意：新插入的结点总是叶子结点。122250二叉排序树的插入算法12225030011099f:bt的父亲结点p:指向最后一个结点，TRUE找到；FALSE叶子的父亲结点。如：插入280的过程。280voidinsert(btree*bt,Keytypex){ p=*bt; while(p) { if(x==p->key)return; f=p; p=(x<p->key)?p->lchild:p->rchild;} p=(btree)malloc(sizeof(bsnodetype)); p->key=x;p->lchild=p->rchild=NULL; if(*bt==NULL)*bt=p; else if(x<f->key)f->lchild=p; elsef->rchild=p;}}pbtf二叉排序树的查找分析

平均情况分析（在成功查找两种的情况下）e.g:下述两种情况下的成功的平均查找长度ASL156070302050ASL=(1+2+2+3+3+3)/6=14/6156070302050ASL=(1+2+3+4+5+6)/6=21/6二叉排序树的删除叶子结点：直接删除，更改它的父亲结点的相应指针域为空。如：删除数据域为15、70的结点。15607030205060302050删除子树的根结点：通常的做法：选取“替身”取代被删结点。有资格充当该替身的是谁哪？左子树中最大的结点或右子树中最小的结点。要点：维持二叉排序树的特性不变。在中序遍历中紧靠着被删结点的结点才有资格作为“替身”。二叉排序树的删除（续）12225030020099110105230216400450500子树的根结点：若被删结点的左孩子为空或者右孩子为空。如下图所示，删除结点的数据域为99的结点。被删结点122250300200230216400450500110105删除99二叉排序树的删除（续）12225030011099105200230216400450500被删结点子树的根结点：若被删结点的左孩子为空或者右孩子为空。如下图所示，删除结点的数据域为200的结点。删除20012225030023021640045050011099105二叉排序树的删除（续）

12225030099110105200230216400450500被删结点子树的根结点：若被删结点的左孩子为空或者右孩子为空。如下图所示，删除结点的数据域为99、200的结点。结论:

将被删结点的另一孩子作为它的父亲结点的孩子，究竟是作为左孩子还是右孩子依被删结点和其父亲结点的关系而定。释放被删结点的空间。被删结点

子树的根结点：若被删结点的左、右子树皆不空，则：通常的做法：选取“替身”取代被删结点。有资格充当该替身的是谁哪？左子树中最大的结点(被删结点的左子树中的最右的结点，其右孩子指针域为空)或右子树中最小的结点(被删结点的右子树中的最左的结点，其左孩子指针域为空)，参看下图。要点：维持二叉排序树的特性不变。在中序遍历中紧靠着被删结点的结点才有资格作为“替身”。12225030011020099105230216400450500被删结点替身替身11025030010520099230216400450500做法：将替身的数据域复制到被删结点的数据域。将结点的左孩子作为的父结点的右孩子。11011099注意：结点右孩子必为空结点的父结点为11011099

12225030011020099105230216400450500被删结点替身替身20025030011099105230216400450500做法：将替身的数据域复制到被删结点的数据域。将结点的右孩子作为的父结点的左孩子。注意：结点左孩子必为空结点的父结点为200200200200250子树的根结点：若被删结点的左、右子树皆不空，则：通常的做法：选取“替身”取代被删结点。有资格充当该替身的是谁哪？左子树中最大的结点(被删结点的左子树中的最右的结点，其右孩子指针域为空)或右子树中最小的结点(被删结点的右子树中的最左的结点，其左孩子指针域为空)，参看下图。要点：维持二叉排序树的特性不变。在中序遍历中紧靠着被删结点的结点才有资格作为“替身”。二叉排序树的操作二叉排序树的查找若当前结点指针为空或当前结点为所找结点则返回当前指针；若当前结点关键字值比给定值大则继续查找当前结点的左子树；否则就继续查找当前结点的右子树。二叉排序树的插入先用给定值查找二叉排序树，查找成功则返回所找结点指针；否则在找不到时的叶结点的左