数据结构 第七章教学课件 .ppt

数据结构 第七章教学课件 第七章第七章 查找查找数据结构数据结构目目录录4 41 12 23 3 查找查找静态查找表静态查找表动态查找表动态查找表哈希表哈希表5 5小结小结第七章第七章第七章第七章查找查找查找查找总总体要求体要求掌握顺序查找、折半查找的实现方法；掌握顺序查找、折半查找的实现方法；掌握动态查找表（包括：二叉排序树、二叉平衡树、掌握动态查找表（包括：二叉排序树、二叉平衡树、B-树）的构造和查找方法；树）的构造和查找方法；掌握哈希表、哈希函数冲突的基本概念和解决冲突掌握哈希表、哈希函数冲突的基本概念和解决冲突的方法。的方法。7.1基本概念基本概念1 1、数据项、数据项、数据项、数据项数据项是具有独立含义的标识单位，是数据不可分数据项是具有独立含义的标识单位，是数据不可分数据项是具有独立含义的标识单位，是数据不可分数据项是具有独立含义的标识单位，是数据不可分割的割的割的割的最小单位最小单位最小单位最小单位。2 2、数据元素、数据元素、数据元素、数据元素数据元素是由若干数据项构成的数据单位，是在某数据元素是由若干数据项构成的数据单位，是在某数据元素是由若干数据项构成的数据单位，是在某数据元素是由若干数据项构成的数据单位，是在某一问题中作为整体进行考虑和处理的一问题中作为整体进行考虑和处理的一问题中作为整体进行考虑和处理的一问题中作为整体进行考虑和处理的基本单位基本单位基本单位基本单位。数据元素数据元素数据项数据项(值值)数据项数据项(名名)3 3、关键字、关键字、关键字、关键字关键字是数据元素中某数据项的值，用该值可以标关键字是数据元素中某数据项的值，用该值可以标关键字是数据元素中某数据项的值，用该值可以标关键字是数据元素中某数据项的值，用该值可以标识一个数据元素。识一个数据元素。识一个数据元素。识一个数据元素。4 4、查找、查找、查找、查找根据给定的某个值，在查找表中寻找一个其关键字根据给定的某个值，在查找表中寻找一个其关键字根据给定的某个值，在查找表中寻找一个其关键字根据给定的某个值，在查找表中寻找一个其关键字等于给定值的数据元素。（成功或失败）等于给定值的数据元素。（成功或失败）等于给定值的数据元素。（成功或失败）等于给定值的数据元素。（成功或失败）主关键字主关键字次关键字次关键字5 5、查找表（、查找表（、查找表（、查找表（searchtablesearchtable）由同一类型的数据元素构成的集合。查找表有如下由同一类型的数据元素构成的集合。查找表有如下由同一类型的数据元素构成的集合。查找表有如下由同一类型的数据元素构成的集合。查找表有如下四种基本操作：四种基本操作：四种基本操作：四种基本操作：(1)(1)判定数据元素是否存在判定数据元素是否存在判定数据元素是否存在判定数据元素是否存在(2)(2)查找数据元素各属性值查找数据元素各属性值查找数据元素各属性值查找数据元素各属性值(3)(3)插入一个元素（在插入元素前表中不能存在有相插入一个元素（在插入元素前表中不能存在有相插入一个元素（在插入元素前表中不能存在有相插入一个元素（在插入元素前表中不能存在有相同主关键字的记录）同主关键字的记录）同主关键字的记录）同主关键字的记录）(4)(4)删除一个元素（在删除元素前表中必须存在该记删除一个元素（在删除元素前表中必须存在该记删除一个元素（在删除元素前表中必须存在该记删除一个元素（在删除元素前表中必须存在该记录）录）录）录）静态查找表静态查找表动态查找表动态查找表7.2静态查找表静态查找表静态查找表一般以线性表表示。静态查找表一般以线性表表示。静态查找表一般以线性表表示。静态查找表一般以线性表表示。线性表结构可以是线性表结构可以是线性表结构可以是线性表结构可以是顺序表结构，也可以是单链表结构。顺序表结构，也可以是单链表结构。顺序表结构，也可以是单链表结构。顺序表结构，也可以是单链表结构。u7.2.1顺序查找顺序查找从静态查找表的一端开始，将给定记录的关键字与从静态查找表的一端开始，将给定记录的关键字与从静态查找表的一端开始，将给定记录的关键字与从静态查找表的一端开始，将给定记录的关键字与表中各记录的关键字逐一比较。表中各记录的关键字逐一比较。表中各记录的关键字逐一比较。表中各记录的关键字逐一比较。找64publicclassElemTypeTextendsComparableTkey;/关键字域关键字域/.其它域其它域publicElemType()key=null;publicElemType(Tdata)key=data;顺序查找的线性表数据元素定义如下：顺序查找的线性表数据元素定义如下：publicclassSeqTableTextendsComparableprotectedArrayListElemTypeelem;/数据元素存储空间基址数据元素存储空间基址protectedintlength;/表长度表长度public SeqTable(Tdata,intn)/用数组用数组data中的前中的前n个元素初始化顺序表个元素初始化顺序表publicintSearch_Seq(Tkey)/顺序查找顺序查找顺序查找的线性表结构定义如下：顺序查找的线性表结构定义如下：【算法算法7-1】初始化顺序表初始化顺序表public SeqTable(Tdata,intn)elem=newArrayListElemType();ElemTypee;for(inti=0;in;i+)e=newElemType(datai);elem.add(i,e);length=n;【算法算法7-2】顺序查找顺序查找publicintSearch_Seq(Tkey)/顺序查找顺序查找inti;ElemTypee=newElemType(key);elem.add(length,e);/“哨兵哨兵”for(i=0;elem.get(i)pareTo(key)!=0;+i);if(ilength)returni;elsereturn-1;找找60监视哨监视哨找到第找到第i个记录个记录需比较的次数。需比较的次数。对含有对含有n个记录的表，查找个记录的表，查找成功成功成功成功时：时：第第i个记录被个记录被查找的概率。查找的概率。1234567891011顺序查找的平均查找长度：顺序查找的平均查找长度：ASL=P1+2P2+(n-1)Pn-1+nPn 假设每个记录的查找概率相等：假设每个记录的查找概率相等：Pi=1/n 则：则：ASL=1/n*(1+2+3.+n)=(n+1)/2时间复杂度：时间复杂度：O(n）顺序查找优点：顺序查找优点：算法简单，适应面广。算法简单，适应面广。顺序查找缺点：顺序查找缺点：平均查找长度大。平均查找长度大。平均查找长度大。平均查找长度大。u7.2.2折半查找（二分查找）折半查找（二分查找）有序、顺序存储有序、顺序存储折半查找折半查找查找过程：查找过程：012345678910513192137566475808892找找21lowmidhigh012345678910513192137566475808892找找63lowhighmidhighlow【算法算法7-3】折半查找折半查找publicintSearch_Bin(Tkey)intlow,high,mid;low=0;high=length-1;/置区间初值置区间初值while(low=high)mid=(low+high)/2;if(pareTo(elem.get(mid).key)=0)returnmid;/找到待查元素找到待查元素elseif(pareTo(elem.get(mid).key)0)high=mid-1;elselow=mid+1;return-1;性能分析：性能分析：01234567891051319213756647580889212233334444Cii5 2 8 0 3 6 91 4 710 判定树判定树查找查找37比较次数比较次数=路径上的结点数路径上的结点数比较次数比较次数=结点结点4的层数的层数比较次数比较次数树的深度树的深度 log2n+1查找成功：查找成功：查找成功：查找成功：查找不成功：查找不成功：查找不成功：查找不成功：比较次数比较次数=路径上的内部结点数路径上的内部结点数比较次数比较次数 log2n+1平均查找长度平均查找长度ASL（成功时）：（成功时）：第第j 层的每个结点要比较的次数层的每个结点要比较的次数第第 j 层层结点数结点数第第j 层要比较的总次数层要比较的总次数折半查找折半查找优点优点优点优点：效率比顺序查找高。：效率比顺序查找高。折半查找折半查找缺点缺点缺点缺点：只适用于：只适用于有序表有序表有序表有序表，限于，限于顺序存储结构顺序存储结构顺序存储结构顺序存储结构1)1(log1)1(log1211221111-+-+=-=nnnnjncncpASLhjjniiniiibs7.3动态动态查找表查找表u7.3.1二叉排序树二叉排序树二叉排序树上查找某关键字等于给定值的结点过二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。程，其实就是走了一条从根到该结点的路径。3080209085403588325035比较的关键字次数比较的关键字次数此结点所在层次数此结点所在层次数最多的比较次数最多的比较次数树的深度树的深度=查找关键字：查找关键字：35二叉排序树的平均查找长度：二叉排序树的平均查找长度：452412375393(45,24,53,12,37,93)二叉排序树二叉排序树插入的插入的n个元素从一开始就有序，个元素从一开始就有序，变成单支树的形态！变成单支树的形态！此时树的深度为此时树的深度为n;ASL=(n+1)/2查找效率与顺序查找情况相同。查找效率与顺序查找情况相同。含有含有n个结点的二叉排序树的平均查找长度和树的形态有关个结点的二叉排序树的平均查找长度和树的形态有关形态比较均衡形态比较均衡树的深度为：树的深度为：log2n+1;452412375393452412375393最最坏坏情情况况最最好好情情况况有有n 个关键字的二叉排序树的平均查找长度个关键字的二叉排序树的平均查找长度设每种树态出现概率相同，查找每个关键字也是等概率的，设每种树态出现概率相同，查找每个关键字也是等概率的，则二叉排序树的则二叉排序树的 由此可见，在由此可见，在随机随机的情况下，二叉排序树的的情况下，二叉排序树的ASL和和log2n是是等数量级等数量级的。的。问题：问题：问题：问题：如何提高形态不均衡的二叉排序树的查找效率？如何提高形态不均衡的二叉排序树的查找效率？平衡二叉树平衡二叉树解决办法：解决办法：解决办法：解决办法：做做“平衡化平衡化”处理，即尽量让二叉树的形状均衡！处理，即尽量让二叉树的形状均衡！u7.3.2平衡二叉树平衡二叉树平衡二叉树平衡二叉树（BalancedBinaryTreeBalancedBinaryTree），它或者是一），它或者是一），它或者是一），它或者是一棵空树，或者是具有如下特性的二叉排序树：棵空树，或者是具有如下特性的二叉排序树：棵空树，或者是具有如下特性的二叉排序树：棵空树，或者是具有如下特性的二叉排序树：(1)(1)左子树和右子树的深度之差的绝对值不超过左子树和右子树的深度之差的绝对值不超过左子树和右子树的深度之差的绝对值不超过左子树和右子树的深度之差的绝对值不超过1 1；(2)(2)它的左、右子树也分别是平衡二叉树。它的左、右子树也分别是平衡二叉树。它的左、右子树也分别是平衡二叉树。它的左、右子树也分别是平衡二叉树。平衡因子平衡因子平衡因子平衡因子=该结点左子树与右子树的深度差该结点左子树与右子树的深度差。任一。任一结点的平衡因子只能取：结点的平衡因子只能取：-1、0或或1；希望二叉排序树的形态均匀希望二叉排序树的形态均匀!图图7.4平衡与非平衡二叉树平衡与非平衡二叉树平衡二叉树上任何结点的左、右子树的深度之差都平衡二叉树上任何结点的左、右子树的深度之差都不超过不超过1，它的平均查找长度是和，它的平均查找长度是和 log2n+1同数同数量级的。量级的。非平衡非平衡二二叉树叉树例：判断下列二叉树是否例：判断下列二叉树是否AVL树？树？1-100-110平平衡衡二二叉叉树树0012-10假设在一棵假设在一棵二叉排序树上插入一个新结点后造成二叉排序树上插入一个新结点后造成失衡，则必须失衡，则必须重新调整树的结构重新调整树的结构重新调整树的结构重新调整树的结构，使之恢复平衡。，使之恢复平衡。我们称此调整平衡的过程为我们称此调整平衡的过程为平衡旋转平衡旋转平衡旋转平衡旋转。平衡旋转的类别平衡旋转的类别单右平衡旋转单右平衡旋转单左平衡旋转单左平衡旋转先左后右平衡旋转先左后右平衡旋转先右后左平衡旋转先右后左平衡旋转若在若在C的的左子树的左子树上插入左子树的左子树上插入结点，使结点，使C的平衡因子从的平衡因子从1增加增加至至2，需要进行一次需要进行一次顺时针旋转顺时针旋转。(以以B为旋转轴）为旋转轴）A若在若在A的的右子树的右子树上插入右子树的右子树上插入结点，使结点，使A的平衡因子从的平衡因子从-1改变改变为为-2，需要进行一次，需要进行一次逆时针旋转逆时针旋转。(以以B为旋转轴）为旋转轴）2)单左平衡旋转：单左平衡旋转：C1)单右平衡旋转：单右平衡旋转：CBCABA若在若在C的的左子树的右子树上插入左子树的右子树上插入结点，使结点，使C的平的平衡因子从衡因子从1增加增加至至2，需要需要先进行逆时针旋转，先进行逆时针旋转，再顺时针旋转。再顺时针旋转。(以插入的结点以插入的结点B为旋转轴）为旋转轴）B3)先左旋转，后右旋转先左旋转，后右旋转平衡旋转：平衡旋转：CAABCCAB若在若在A的的右子树的左子树上插入右子树的左子树上插入结点，使结点，使A的平的平衡因子从衡因子从-1改变为改变为-2，需要，需要先进行顺时针旋转，先进行顺时针旋转，再逆时针旋转。再逆时针旋转。(以插入的结点以插入的结点B为旋转轴）为旋转轴）4)先右旋转，后左旋转先右旋转，后左旋转平衡旋转：平衡旋转：B 调整必须保证二叉排序树的特性不变调整必须保证二叉排序树的特性不变 ACBACCBA013037024例：例：请将下面序列构成一棵平衡二叉排序树：请将下面序列构成一棵平衡二叉排序树：(13,24,37,90,53)013037-113024-124-213090-124-137053190-237需要需要单左平衡单左平衡旋转旋转(绕绕24逆转，逆转，24为根为根)需要需要RL平衡平衡旋转（绕旋转（绕53先顺后逆）先顺后逆）-224037090053053037090-124u7.3.3B-树树一种平衡的一种平衡的多路查找树多路查找树一棵一棵m阶的阶的B-树的定义如下：树的定义如下：(1)树中每个结点最多有树中每个结点最多有m棵子树；棵子树；(2)若根结点不是叶子结点，则至少有两棵子树；若根结点不是叶子结点，则至少有两棵子树；(3)除根之外的所有非终端结点至少有除根之外的所有非终端结点至少有 m/2 棵子树棵子树(4)所有的非终端结点中包含下列信息数据所有的非终端结点中包含下列信息数据(n,p0,k1,p1,k2,p2.pn,kn),ki是关键字是关键字,kiki+1且且，pi为为指向子树根结点的指针，且指向子树根结点的指针，且pi所指子树中所有结点所指子树中所有结点的关键字均小于的关键字均小于ki+1且大于且大于ki，n为关键字的个数。为关键字的个数。一棵一棵m阶的阶的B-树的定义如下：树的定义如下：(5)所有的叶子结点都出现在同一层次上，并且不带所有的叶子结点都出现在同一层次上，并且不带信息。信息。一棵深度为一棵深度为4的的4阶阶B-树树2、B-树的查找树的查找查找关键字：查找关键字：47B-B-树的查找是从根结点出发，沿指针搜索结树的查找是从根结点出发，沿指针搜索结点（纵向查找）和在结点内进行顺序（或折半）点（纵向查找）和在结点内进行顺序（或折半）查找（横向查找）两个过程交叉进行。查找（横向查找）两个过程交叉进行。3、B-树的插入树的插入(a)3阶阶B-树树(b)插入结点插入结点60(c)插入结点插入结点90(d)插入结点插入结点304、B-树的删除树的删除3阶阶B-树删除结点树删除结点613阶阶B-树删除结点树删除结点50B-树插入、删除时易于平衡，外部查找效率高，适树插入、删除时易于平衡，外部查找效率高，适合于组织磁盘文件的动态索引结构。在文件系统中合于组织磁盘文件的动态索引结构。在文件系统中很有用。很有用。7.4哈希表哈希表查找操作要完成什么任务？查找操作要完成什么任务？待查值待查值k确定确定k在存储结构中的位置在存储结构中的位置学过哪些查找技术？这些查找技术的共性？学过哪些查找技术？这些查找技术的共性？顺序查找、折半查找、二叉排序树查找等。顺序查找、折半查找、二叉排序树查找等。由于记录的存储位置与关键字之间不存在确定的由于记录的存储位置与关键字之间不存在确定的关系，故查找时要进行一系列对关键字的查找比关系，故查找时要进行一系列对关键字的查找比较，查找效率由比较一次缩小的查找范围决定。较，查找效率由比较一次缩小的查找范围决定。u7.4.1哈希表的概念哈希表的概念在记录的存储位置和它的关键字之间建立一个确定的在记录的存储位置和它的关键字之间建立一个确定的对应关系对应关系，以，以作为关键字为作为关键字为的记录在表中的位置。的记录在表中的位置。设哈希函数：设哈希函数：则构建的哈希表如下所示：则构建的哈希表如下所示：表示字符的次序，表示字符的次序，AA的次序为的次序为1 1如果要查找给定关键字为如果要查找给定关键字为“Qian”的记录，的记录，H(Qian）=8，即可从地址为，即可从地址为8的表中取得该记录。的表中取得该记录。u7.4.2哈希表函数的构建哈希表函数的构建1 1、直接定址法、直接定址法、直接定址法、直接定址法哈希函数为关键字的线性函数，即：哈希函数为关键字的线性函数，即：哈希函数为关键字的线性函数，即：哈希函数为关键字的线性函数，即：H(key)=akey+bH(key)=akey+b（a a，b b为常数）为常数）为常数）为常数）2 2、数字分析法、数字分析法、数字分析法、数字分析法对各个关键字的各个码位进行分析，取关键字中某对各个关键字的各个码位进行分析，取关键字中某对各个关键字的各个码位进行分析，取关键字中某对各个关键字的各个码位进行分析，取关键字中某些取值较分散的数字位作为哈希地址的方法。些取值较分散的数字位作为哈希地址的方法。些取值较分散的数字位作为哈希地址的方法。些取值较分散的数字位作为哈希地址的方法。3、平方取中法、平方取中法以关键字的平方值的中间几位作为存储地址。以关键字的平方值的中间几位作为存储地址。4、折叠法、折叠法将关键字分割成位数相同的几部分将关键字分割成位数相同的几部分(最后一部分的位最后一部分的位数可以不同数可以不同)，然后取它们的叠加和，然后取它们的叠加和(舍去进位舍去进位)为哈为哈希地址。希地址。5、除留余数法、除留余数法除留余数法是用模（除留余数法是用模（%）运算得到的方法，其哈希）运算得到的方法，其哈希函数函数H(key)=key%p，pm,其中其中m为存储单元数。为存储单元数。4、折叠法、折叠法将关键字分割成位数相同的几部分将关键字分割成位数相同的几部分(最后一部分的位最后一部分的位数可以不同数可以不同)，然后取它们的叠加和，然后取它们的叠加和(舍去进位舍去进位)为哈为哈希地址。希地址。14147 7141414147 70 01414散列地址散列地址散列地址散列地址5656494942423535282821211414 关键字关键字关键字关键字例：例：p21p=8散列地址散列地址6543210u7.4.3处理冲突处理冲突开放定址法（开放定址法（OpenAddressing）定义：就是一旦产生了冲突，即该地址已经存放定义：就是一旦产生了冲突，即该地址已经存放了其它数据元素，就去寻找另一个空的散列地址。了其它数据元素，就去寻找另一个空的散列地址。!若发生了第若发生了第i次冲突，试探的下一个地址将增加次冲突，试探的下一个地址将增加di!hi(key)=(h(key)+di)modTableSize(1iTableSize)线性探测、线性探测、二次探测、二次探测、双散列双散列di=idi=i2di=i*h2(key)1.线性探测法（线性探测法（LinearProbing）例例设关键词序列为设关键词序列为47,7,29,11,9,84,54,20,30散列表表长散列表表长TableSize=11，散列函数为：散列函数为：H(key)=keymod11。用用线性探测法线性探测法处理冲突，列出依次插入后的散列表，处理冲突，列出依次插入后的散列表，并估算查找性能。并估算查找性能。ASLs=（4*1+2+3+4+5+8）/9=26/92.89“一次聚集（一次聚集（PrimaryClustering）”现象：需要经过现象：需要经过很多次冲突才找到空位置。很多次冲突才找到空位置。关键词关键词(key)4772911984542030散列地址散列地址h(key)3770971098冲突次数冲突次数001003247例：设关键字序列为例：设关键字序列为47,7,29,11,16,92,22,8,3;散列散列函数取为：函数取为：H(key)=key%11。2.链接法链接法因查找成功的ASL s=（6+3*2）/9 1.3u7.4.4哈希表的查找及其分析哈希表的查找及其分析 平均查找长度（平均查找长度（ASL）用来度量散列表查找效率。）用来度量散列表查找效率。另一方面另一方面，关键词的比较次数，取决于产生冲突，关键词的比较次数，取决于产生冲突的多少。的多少。影响产生冲突多少有以下三个因素影响产生冲突多少有以下三个因素：（1）散列函数是否均匀；）散列函数是否均匀；（2）处理冲突的方法；）处理冲突的方法；（3）散列表的装填因子）散列表的装填因子。主要分析后两者对主要分析后两者对查找效率的影响。查找效率的影响。可以证明，线性探查法的期望平均查找长度满足可以证明，线性探查法的期望平均查找长度满足下列公式：下列公式：1.线性探查法的查找性能线性探查法的查找性能所有地址链表的平均长度定义成装填因子所有地址链表的平均长度定义成装填因子，有有可能超过可能超过1。平均查找次数为：。平均查找次数为：2.链接法的查找性能链接法的查找性能装填因子是指散列表中已有的元素个数装填因子是指散列表中已有的元素个数n与散列表空与散列表空间大小间大小m的比值，即的比值，即=n/m。本章小结本章小结 3、折半查找折半查找又称为二分查找，它是一种效率较高的查又称为二分查找，它是一种效率较高的查找方法，时间复杂度为找方法，时间复杂度为O(log2n)但要求线性表必须采用但要求线性表必须采用顺序存储结构，且表中元素必须按关键字有序（升序或顺序存储结构，且表中元素必须按关键字有序（升序或降序均可）。降序均可）。1、查找表按照实施的操作可以分为：、查找表按照实施的操作可以分为：静态查找表和动静态查找表和动态查找表态查找表。2、顺序查找顺序查找方法既适用于线性表的顺序存储结构，也方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构，但是查找效率较低，时适用于线性表的链式存储结构，但是查找效率较低，时间复杂度为间复杂度为O(n)。4、二叉排序树二叉排序树查找最好情况下的查找时间与折半查找查找最好情况下的查找时间与折半查找是同数量级的，即是同数量级的，即O(log2n)。6、B-树树是一种平衡的多路查找树，插入、删除时易于是一种平衡的多路查找树，插入、删除时易于平衡，外部查找效率高。平衡，外部查找效率高。5、二叉排序树的查找效率与二叉排序树的形态有关，、二叉排序树的查找效率与二叉排序树的形态有关，故希望二叉排序树的形态均匀，引入了故希望二叉排序树的形态均匀，引入了平衡二叉树平衡二叉树。7、通过哈希函数可以确定记录在表中位置和其关键字、通过哈希函数可以确定记录在表中位置和其关键字之间的关系之间的关系-哈希表哈希表。