中国科大C+程序设计实习 数据结构课程中国科学技术大学网络学院中国科学技术大学网络学院中国科学技术大学网络学院中国科学技术大学网络学院数据结构第九章第九章查找查找本章内容9.1 查找的基本概念查找的基本概念9.2 静态查找表静态查找表9.3 动态查找表动态查找表9.4 哈希表哈希表9- 中国科大数据结构9.1 查找的基本概念pp查找表查找表查找表查找表(SearchTable)(SearchTable)查找表是由同一类型的数据元素查找表是由同一类型的数据元素查找表是由同一类型的数据元素查找表是由同一类型的数据元素( ( ( (或记录或记录或记录或记录) ) ) )构成的集合。对查找表的操构成的集合。对查找表的操构成的集合。对查找表的操构成的集合。对查找表的操作主要有：作主要有：作主要有：作主要有：1.1.1.1.查询某个查询某个查询某个查询某个“特定的特定的特定的特定的”数据元素是否在查找表中；数据元素是否在查找表中；数据元素是否在查找表中；数据元素是否在查找表中；2.2.2.2.检索某个检索某个检索某个检索某个“特定的特定的特定的特定的”数据元素的各种属性；数据元素的各种属性；数据元素的各种属性；数据元素的各种属性；3.3.3.3.在查找表中插入一个数据元素；在查找表中插入一个数据元素；在查找表中插入一个数据元素；在查找表中插入一个数据元素；4.4.4.4.从查找表中删去某个数据元素。从查找表中删去某个数据元素。从查找表中删去某个数据元素。从查找表中删去某个数据元素。pp查找表分类查找表分类查找表分类查找表分类n n静态查找表静态查找表静态查找表静态查找表仅作查询和检索操作的查找表。仅作查询和检索操作的查找表。仅作查询和检索操作的查找表。仅作查询和检索操作的查找表。n n动态查找表动态查找表动态查找表动态查找表在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素除已存在的某个数据元素除已存在的某个数据元素除已存在的某个数据元素9- 中国科大数据结构9.1 查找的基本概念pp关键字关键字关键字关键字(Key)(Key)关键字是数据元素（或记录）中某个数据项的值，用以标识关键字是数据元素（或记录）中某个数据项的值，用以标识关键字是数据元素（或记录）中某个数据项的值，用以标识关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。（识别）一个数据元素（或记录）。（识别）一个数据元素（或记录）。（识别）一个数据元素（或记录）。n n主关键字：可以识别唯一的一个记录的关键字主关键字：可以识别唯一的一个记录的关键字主关键字：可以识别唯一的一个记录的关键字主关键字：可以识别唯一的一个记录的关键字n n次关键字：能识别若干记录的关键字次关键字：能识别若干记录的关键字次关键字：能识别若干记录的关键字次关键字：能识别若干记录的关键字pp查找查找查找查找(Searching)(Searching)是根据给定的某个值，在查找表中确定一个其关键字等于给定是根据给定的某个值，在查找表中确定一个其关键字等于给定是根据给定的某个值，在查找表中确定一个其关键字等于给定是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。值的数据元素（或记录）。值的数据元素（或记录）。值的数据元素（或记录）。9- 中国科大数据结构9.1 查找的基本概念pp衡量查找算法的标准衡量查找算法的标准衡量查找算法的标准衡量查找算法的标准n n时间复杂度时间复杂度时间复杂度时间复杂度；n n空间复杂度空间复杂度空间复杂度空间复杂度；n n平均查找长度平均查找长度平均查找长度平均查找长度ASLASLASLASL：定义为确定记录在表中的位置所进行的和关定义为确定记录在表中的位置所进行的和关键字比较的次数的平均值键字比较的次数的平均值 n n n n ASL = ASL = ASL = ASL = P P P Pi i i iC C C Ci i i i i=1 i=1 i=1 i=1l ln n为查找表的长度，即表中所含元素的个数为查找表的长度，即表中所含元素的个数l lP Pi i为查找第为查找第i i个元素的概率个元素的概率(P(Pi i=1)=1)l lC Ci i是查找第是查找第i i个元素时同给定值个元素时同给定值K K比较的次数比较的次数9- 中国科大数据结构9.2 静态查找表9.2.19.2.1 顺序表的查找顺序表的查找顺序表的查找顺序表的查找顺序查找算法是顺序表（既无序表）的查找方法。在顺序查找算法顺序查找算法是顺序表（既无序表）的查找方法。在顺序查找算法顺序查找算法是顺序表（既无序表）的查找方法。在顺序查找算法顺序查找算法是顺序表（既无序表）的查找方法。在顺序查找算法中，以顺序表或线性链表表示静态查找表。中，以顺序表或线性链表表示静态查找表。中，以顺序表或线性链表表示静态查找表。中，以顺序表或线性链表表示静态查找表。pp面临的问题面临的问题面临的问题面临的问题下标越界的检查，需要相当的时间和空间代价。解决的办法是，将下标越界的检查，需要相当的时间和空间代价。解决的办法是，将下标越界的检查，需要相当的时间和空间代价。解决的办法是，将下标越界的检查，需要相当的时间和空间代价。解决的办法是，将ST.elem0.key ST.elem0.key ST.elem0.key ST.elem0.key 置为置为置为置为key,key,key,key,所有元素检查完还没有找到时，在所有元素检查完还没有找到时，在所有元素检查完还没有找到时，在所有元素检查完还没有找到时，在ST.elem0ST.elem0ST.elem0ST.elem0处一定找到。从而免去了检查下标越界的时间。处一定找到。从而免去了检查下标越界的时间。处一定找到。从而免去了检查下标越界的时间。处一定找到。从而免去了检查下标越界的时间。pp顺序查找算法顺序查找算法顺序查找算法顺序查找算法1.1.1.1.从表中从表中从表中从表中最后一个记录最后一个记录最后一个记录最后一个记录开始开始开始开始2.2.2.2.逐个进行记录的关键字和给定值的比较逐个进行记录的关键字和给定值的比较逐个进行记录的关键字和给定值的比较逐个进行记录的关键字和给定值的比较3.3.3.3.若某个记录比较相等，则查找成功若某个记录比较相等，则查找成功若某个记录比较相等，则查找成功若某个记录比较相等，则查找成功4.4.4.4.若直到第若直到第若直到第若直到第1 1 1 1个记录都比较不等，则查找不成功个记录都比较不等，则查找不成功个记录都比较不等，则查找不成功个记录都比较不等，则查找不成功9- 中国科大数据结构9.2 静态查找表pp顺序查找算法描述顺序查找算法描述顺序查找算法描述顺序查找算法描述uu设置设置设置设置“ “哨兵哨兵哨兵哨兵” ”的目的是省略对下标越界的检查，提高算法执行的目的是省略对下标越界的检查，提高算法执行的目的是省略对下标越界的检查，提高算法执行的目的是省略对下标越界的检查，提高算法执行速度。当然，哨兵也可以设置在高下标处。速度。当然，哨兵也可以设置在高下标处。速度。当然，哨兵也可以设置在高下标处。速度。当然，哨兵也可以设置在高下标处。intint Search_Seq(SSTableSearch_Seq(SSTableST,ST,KeyTypeKeyTypekey)key)/若查找成功，返回位置若查找成功，返回位置若查找成功，返回位置若查找成功，返回位置ST.elem0.key=key;ST.elem0.key=key;/“/“哨兵哨兵哨兵哨兵” ”，for(i=for(i=ST.lengthST.length; ;ST.elemi.keyST.elemi.key!=key;-i);!=key;-i);/从后往从后往从后往从后往前找前找前找前找returni;returni;/找不到时找不到时找不到时找不到时,i=0,i=0 9- 中国科大数据结构9.2 静态查找表pp顺序查找示举例顺序查找示举例顺序查找示举例顺序查找示举例在下列顺序表中寻找在下列顺序表中寻找在下列顺序表中寻找在下列顺序表中寻找62626262，如果找到，给出其所在位置的下标。，如果找到，给出其所在位置的下标。，如果找到，给出其所在位置的下标。，如果找到，给出其所在位置的下标。监视哨兵监视哨兵i=11i=7, ,找到找到i=8i=9i=10比较次数比较次数=5比较次数分析：比较次数分析：查找第查找第n n个元素：个元素： 1 1次次查找第查找第n-1n-1个元素：个元素： 2 2次次. .查找第查找第1 1个元素：个元素： n n次次查找第查找第i i个元素：个元素： n+1-in+1-i次次查找失败查找失败： n+1n+1次次 0 1 2 3 4 5 6 7 8 9 10 11625131921375662758088929- 中国科大数据结构9.2 静态查找表pp顺序查找性能分析顺序查找性能分析顺序查找性能分析顺序查找性能分析n n对顺序表而言，对顺序表而言，对顺序表而言，对顺序表而言，C Ci i=n-i+1=n-i+1n n在等概率查找的情况下，在等概率查找的情况下，在等概率查找的情况下，在等概率查找的情况下，P Pi i=1/n=1/n平均查找长度平均查找长度平均查找长度平均查找长度 ASLASLssss=n*P=n*P1 1 +(n-1)P +(n-1)P2 2 + 2P + 2Pn-1n-1+ + P Pn n = (n+1)/2 = (n+1)/2n n如果被查找的记录概率不等时，如果被查找的记录概率不等时，如果被查找的记录概率不等时，如果被查找的记录概率不等时， ASLASLASLASLssssssss在在在在 P P P Pn n n nPPPPn-1n-1n-1n-1 PPPP2 2 2 2PPPP1 1 1 1 时取时取时取时取极小值极小值极小值极小值n n若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。找之后，将刚刚查找到的记录直接移至表尾的位置上。找之后，将刚刚查找到的记录直接移至表尾的位置上。找之后，将刚刚查找到的记录直接移至表尾的位置上。pp顺序查找特点顺序查找特点顺序查找特点顺序查找特点n n优点：优点：1.1.简单简单2.2.适应面广适应面广( (对表的结构无任何要求对表的结构无任何要求) )n n缺点：缺点：1.1.平均查找长度较大平均查找长度较大2.2.特别是当特别是当n n很大时，查找效率很低很大时，查找效率很低9- 中国科大数据结构9.2 静态查找表9.2.29.2.2折半查找折半查找折半查找折半查找折半查找算法是折半查找算法是有序表有序表的查找方法。在折半查找算法中，静态查找的查找方法。在折半查找算法中，静态查找表按关键字大小的次序，有序地存放在顺序表中。表按关键字大小的次序，有序地存放在顺序表中。pp折半查找的原理折半查找的原理1.1.先确定待查记录所在的范围先确定待查记录所在的范围( (前部分或后部分前部分或后部分) )2.2.逐步缩小逐步缩小( (一半一半) )范围直到找范围直到找( (不不) )到该记录为止到该记录为止9- 中国科大数据结构9.2 静态查找表pp折半查找算法折半查找算法折半查找算法折半查找算法1.1.n n个对象从小到大存放在有序顺序表个对象从小到大存放在有序顺序表个对象从小到大存放在有序顺序表个对象从小到大存放在有序顺序表STST中中中中，k k为给定值为给定值为给定值为给定值2.2.2.2.设设设设lowlow、highhigh指向待查元素所在区间的下界、上界，即指向待查元素所在区间的下界、上界，即指向待查元素所在区间的下界、上界，即指向待查元素所在区间的下界、上界，即low=1,low=1,high=nhigh=n3.3.3.3.设设设设midmid指向待查区间的中点，即指向待查区间的中点，即指向待查区间的中点，即指向待查区间的中点，即 mid=(low+high)/2mid=(low+high)/2 4.4.4.4.让让让让k k k k与与与与midmid指向的记录比较指向的记录比较指向的记录比较指向的记录比较 若若若若 k=k=STmid.keySTmid.key，查找成功，查找成功，查找成功，查找成功 若若若若 kkkSTmid.keySTmid.key，则，则，则，则low=mid+1low=mid+1 下半区间下半区间下半区间下半区间 5.5.5.5.重复重复重复重复3,43,43,43,4操作，直至操作，直至操作，直至操作，直至lowhighlowhigh时，查找失败。时，查找失败。时，查找失败。时，查找失败。9- 中国科大数据结构9.2 静态查找表pp折半成功查找举例：在下列有序表中用折半查找法查找折半成功查找举例：在下列有序表中用折半查找法查找折半成功查找举例：在下列有序表中用折半查找法查找折半成功查找举例：在下列有序表中用折半查找法查找62626262所在位置。所在位置。所在位置。所在位置。Key = 62Key = 62Key = 62Key = 621 2 3 4 5 6 7 8 9 10 11513192137566275808892low=1mid=6high=11第一步：第一步：low=1,high=11,mid=6STmid=ST6=5662,则改变则改变high；第三步：第三步：high=mid-1=8,mid=7high=8mid=7STmid=ST7=62=62,找到！找到！629- 中国科大数据结构9.2 静态查找表pp折半查找失败举例：在上例有序表中找折半查找失败举例：在上例有序表中找折半查找失败举例：在上例有序表中找折半查找失败举例：在上例有序表中找6161。1 2 3 4 5 6 7 8 9 10 11513192137566275808892high=6low=7找找61u 当下界当下界lowlow大于上界大于上界highhigh时，说明有序时，说明有序 表中没有关键字等于表中没有关键字等于K K的元素，查找失败的元素，查找失败9- 中国科大数据结构9.2 静态查找表pp折半查找的性能分析折半查找的性能分析折半查找的性能分析折半查找的性能分析折半查找过程可以用二叉树（也叫判定树）来描述：折半查找过程可以用二叉树（也叫判定树）来描述：折半查找过程可以用二叉树（也叫判定树）来描述：折半查找过程可以用二叉树（也叫判定树）来描述：n判定树上每个结点需要的查找次数刚好为该结点所在的层数；判定树上每个结点需要的查找次数刚好为该结点所在的层数；n查找成功时查找次数不会超过判定树的深度查找成功时查找次数不会超过判定树的深度nn个结点的判定树的深度为个结点的判定树的深度为 log2n +1n比较次数最多不超过比较次数最多不超过 log2n +1n折半查找的算法复杂度为折半查找的算法复杂度为 log2n +13941756102118判定树判定树9- 中国科大数据结构9.2 静态查找表pp折半查找特点折半查找特点折半查找特点折半查找特点n n折半查找的效率比顺序查找高，特别是查找表的长度很长时；折半查找的效率比顺序查找高，特别是查找表的长度很长时；n n折半查找只能适用于等概率有序表，并且以顺序存储结构存储。折半查找只能适用于等概率有序表，并且以顺序存储结构存储。9- 中国科大数据结构9.2 静态查找表9.2.39.2.3分块查找分块查找分块查找分块查找uu分块查找是一种索引顺序表分块查找是一种索引顺序表( (分块有序表分块有序表) )查找方法，是折半查查找方法，是折半查找和顺序查找的简单结合；找和顺序查找的简单结合；uu索引顺序表索引顺序表( (分块有序表分块有序表) )将整个表分成几块，块内无序，块间将整个表分成几块，块内无序，块间有序有序uu所谓块间有序是指后一块表中所有记录的关键字均大于前一块所谓块间有序是指后一块表中所有记录的关键字均大于前一块表中的最大关键字表中的最大关键字9- 中国科大数据结构9.2 静态查找表pp基本概念基本概念基本概念基本概念n n主表：用数组存放待查记录主表：用数组存放待查记录主表：用数组存放待查记录主表：用数组存放待查记录, , , ,每个数据元素至少含有关键字域每个数据元素至少含有关键字域每个数据元素至少含有关键字域每个数据元素至少含有关键字域n n索引表：每个结点含有最大关键字域和指向本块第一个结点的索引表：每个结点含有最大关键字域和指向本块第一个结点的索引表：每个结点含有最大关键字域和指向本块第一个结点的索引表：每个结点含有最大关键字域和指向本块第一个结点的指针指针指针指针 1 2 3 4 5 6 7 8 9 10 11519132175566237888092211755929主表主表索引表索引表9- 中国科大数据结构9.2 静态查找表pp分块查找举例分块查找举例分块查找举例分块查找举例n n采用折半查找方法在索引表中找到块（第采用折半查找方法在索引表中找到块（第采用折半查找方法在索引表中找到块（第采用折半查找方法在索引表中找到块（第2 2 2 2块）块）块）块）n n用顺序查找方法在主表对应块中找到记录（第用顺序查找方法在主表对应块中找到记录（第用顺序查找方法在主表对应块中找到记录（第用顺序查找方法在主表对应块中找到记录（第3 3 3 3个记录）个记录）个记录）个记录）1 2 3 4 5 6 7 8 9 10 11519132175566237888092211755929主表主表索引表索引表找找629- 中国科大数据结构9.2 静态查找表pp分块查找性能分析分块查找性能分析分块查找性能分析分块查找性能分析n n若将长度为若将长度为n n的表分成的表分成b b块，每块含块，每块含s s个记录，并设表中每个记录个记录，并设表中每个记录查找概率相等查找概率相等n n用折半查找方法在索引表中查找索引块，用折半查找方法在索引表中查找索引块，ASLASL块间块间 loglog2 2(n/s+1)(n/s+1)n n用顺序查找方法在主表对应块中查找记录，用顺序查找方法在主表对应块中查找记录，ASLASL块内块内=s/2=s/2n nASLlog2(n/s+1) + s/2ASLlog2(n/s+1) + s/29- 中国科大数据结构9.3 动态查找表p动态查找表动态查找表如果应用问题涉及的数据量很大，而且数据经常发生变化，如如果应用问题涉及的数据量很大，而且数据经常发生变化，如图书馆经常购进图书，每购进新书，需将新书记录插入图书表，对图书馆经常购进图书，每购进新书，需将新书记录插入图书表，对这类表除了提供前面的介绍的查找外，还要提供动态查找功能：这类表除了提供前面的介绍的查找外，还要提供动态查找功能：1.查找某个查找某个“特定特定”元素是否在表中，若不在，将该元素插入；元素是否在表中，若不在，将该元素插入；2.查找某个查找某个“特定特定”元素是否在表中，若在，从表中删除；元素是否在表中，若在，从表中删除；p如何组织动态查找表？如何组织动态查找表？用静态查找方法不能满足要求了。本节介绍几种方法。用静态查找方法不能满足要求了。本节介绍几种方法。9- 中国科大数据结构9.3 动态查找表9.3.1 9.3.1 9.3.1 9.3.1 二叉排序树二叉排序树二叉排序树二叉排序树二叉排序树又称二叉查找树二叉排序树又称二叉查找树二叉排序树又称二叉查找树二叉排序树又称二叉查找树pp空树或者是具有如下特性的二叉树：空树或者是具有如下特性的二叉树：空树或者是具有如下特性的二叉树：空树或者是具有如下特性的二叉树：1.1.1.1.若左子树不空，则左子树上所有结点的值均小于根结点的值；若左子树不空，则左子树上所有结点的值均小于根结点的值；若左子树不空，则左子树上所有结点的值均小于根结点的值；若左子树不空，则左子树上所有结点的值均小于根结点的值；2.2.2.2.若右子树不空，则右子树上所有结点的值均大于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值；3.3.3.3.左、右子树也都分别是二叉排序树。左、右子树也都分别是二叉排序树。左、右子树也都分别是二叉排序树。左、右子树也都分别是二叉排序树。21二叉排序树二叉排序树非二叉排序树非二叉排序树566459237881980211375605664592378819802113759- 中国科大数据结构9.3 动态查找表pp二叉排序树查找算法二叉排序树查找算法二叉排序树查找算法二叉排序树查找算法 给定值与根结点比较：给定值与根结点比较：给定值与根结点比较：给定值与根结点比较：1.1.1.1.若相等，查找成功若相等，查找成功若相等，查找成功若相等，查找成功2.2.2.2.若小于，查找左子树若小于，查找左子树若小于，查找左子树若小于，查找左子树3.3.3.3.若大于，查找右子树若大于，查找右子树若大于，查找右子树若大于，查找右子树566459237881980211375例例1：在右图二叉排序树中查找关键字值等于：在右图二叉排序树中查找关键字值等于3737找到找到例例2：在右图二叉排序树中查找关键字值等于：在右图二叉排序树中查找关键字值等于88找到找到例例3：在右图二叉排序树中查找关键字值等于：在右图二叉排序树中查找关键字值等于94无此数无此数9- 中国科大数据结构9.3 动态查找表pp二叉排序树插入二叉排序树插入二叉排序树插入二叉排序树插入二叉排序树是一种动态树表。二叉排序树是一种动态树表。二叉排序树是一种动态树表。二叉排序树是一种动态树表。n n当树中不存在查找的结点时，作插入操作当树中不存在查找的结点时，作插入操作当树中不存在查找的结点时，作插入操作当树中不存在查找的结点时，作插入操作n n新插入的结点一定是叶子结点（只需改动一个结点的指针）新插入的结点一定是叶子结点（只需改动一个结点的指针）新插入的结点一定是叶子结点（只需改动一个结点的指针）新插入的结点一定是叶子结点（只需改动一个结点的指针）n n该叶子结点是查找不成功时路径上访问的最后一个结点左孩子该叶子结点是查找不成功时路径上访问的最后一个结点左孩子该叶子结点是查找不成功时路径上访问的最后一个结点左孩子该叶子结点是查找不成功时路径上访问的最后一个结点左孩子或右孩子或右孩子或右孩子或右孩子( ( ( (新结点值小于或大于该结点值新结点值小于或大于该结点值新结点值小于或大于该结点值新结点值小于或大于该结点值) ) ) )566459237881980211375例：在右图二叉树中插入结点例：在右图二叉树中插入结点例：在右图二叉树中插入结点例：在右图二叉树中插入结点9494。949- 中国科大数据结构9.3 动态查找表pp二叉排序树生成二叉排序树生成二叉排序树生成二叉排序树生成例：画出在初始为空的二叉排序树中依次插入例：画出在初始为空的二叉排序树中依次插入例：画出在初始为空的二叉排序树中依次插入例：画出在初始为空的二叉排序树中依次插入56,64,92,80,88,7556,64,92,80,88,7556,64,92,80,88,7556,64,92,80,88,75时该树的生长全过程时该树的生长全过程时该树的生长全过程时该树的生长全过程5664928880759- 中国科大数据结构9.3 动态查找表pp二叉排序树中序遍历二叉排序树中序遍历二叉排序树中序遍历二叉排序树中序遍历中序遍历二叉排序树，可得到一个关键字的有序序列中序遍历二叉排序树，可得到一个关键字的有序序列中序遍历二叉排序树，可得到一个关键字的有序序列中序遍历二叉排序树，可得到一个关键字的有序序列, , , ,如如如如5,13,19,21,37,56,64,92,75,80,885,13,19,21,37,56,64,92,75,80,885,13,19,21,37,56,64,92,75,80,885,13,19,21,37,56,64,92,75,80,885664592378819802113759- 中国科大数据结构9.3 动态查找表pp二叉排序树删除二叉排序树删除二叉排序树删除二叉排序树删除删除二叉排序树中的一个结点后，必须保持二叉排序树的特性：删除二叉排序树中的一个结点后，必须保持二叉排序树的特性：删除二叉排序树中的一个结点后，必须保持二叉排序树的特性：删除二叉排序树中的一个结点后，必须保持二叉排序树的特性：左子树的所有结点值小于根结点，右子树的所有结点值大于根结点。左子树的所有结点值小于根结点，右子树的所有结点值大于根结点。左子树的所有结点值小于根结点，右子树的所有结点值大于根结点。左子树的所有结点值小于根结点，右子树的所有结点值大于根结点。也即保持中序遍历后，输出为有序序列也即保持中序遍历后，输出为有序序列也即保持中序遍历后，输出为有序序列也即保持中序遍历后，输出为有序序列pp被删除结点具有以下三种情况被删除结点具有以下三种情况被删除结点具有以下三种情况被删除结点具有以下三种情况1.1.1.1.是叶子结点是叶子结点是叶子结点是叶子结点2.2.2.2.只有左子树或右子树只有左子树或右子树只有左子树或右子树只有左子树或右子树3.3.3.3.同时有左、右子树同时有左、右子树同时有左、右子树同时有左、右子树pp下面针对三种情况各举一例。下面针对三种情况各举一例。下面针对三种情况各举一例。下面针对三种情况各举一例。9- 中国科大数据结构9.3 动态查找表pp被删除结点是叶子结点：直接删除结点，并让其父结点指向该结点被删除结点是叶子结点：直接删除结点，并让其父结点指向该结点的指针变为空。的指针变为空。pp例：删除右二叉例：删除右二叉排序排序排序排序树中的树中的8888节点节点5664592378819802113759- 中国科大数据结构9.3 动态查找表pp被删除结点只有左子树或右子树被删除结点只有左子树或右子树被删除结点只有左子树或右子树被删除结点只有左子树或右子树删除结点删除结点删除结点删除结点, , , ,让其父结点指向该结点的指针指向其左子树让其父结点指向该结点的指针指向其左子树让其父结点指向该结点的指针指向其左子树让其父结点指向该结点的指针指向其左子树( ( ( (或右子树或右子树或右子树或右子树),),),),即用孩子结点替代被删除结点即可即用孩子结点替代被删除结点即可即用孩子结点替代被删除结点即可即用孩子结点替代被删除结点即可pp例：对于右边二叉例：对于右边二叉例：对于右边二叉例：对于右边二叉排序排序排序排序树中，先删除节点树中，先删除节点树中，先删除节点树中，先删除节点37373737，再删除节点，再删除节点，再删除节点，再删除节点64646464。5664537192113928880759- 中国科大数据结构9.3 动态查找表pp被删除结点被删除结点被删除结点被删除结点p p p p既有左子树，又有右子树既有左子树，又有右子树既有左子树，又有右子树既有左子树，又有右子树以中序遍历时的直接前驱以中序遍历时的直接前驱以中序遍历时的直接前驱以中序遍历时的直接前驱s s s s替代被删除结点替代被删除结点替代被删除结点替代被删除结点p p p p，然后再按照前面介绍，然后再按照前面介绍，然后再按照前面介绍，然后再按照前面介绍的发删除该直接前驱的发删除该直接前驱的发删除该直接前驱的发删除该直接前驱s s s s（只可能有左孩子）（只可能有左孩子）（只可能有左孩子）（只可能有左孩子）566459237888019211375例：在右边二叉排序树中例：在右边二叉排序树中例：在右边二叉排序树中例：在右边二叉排序树中, ,节点节点节点节点5656的中序遍历的直接前趋是节点的中序遍历的直接前趋是节点的中序遍历的直接前趋是节点的中序遍历的直接前趋是节点3737。9- 中国科大数据结构9.3 动态查找表pp二叉排序树性能分析二叉排序树性能分析二叉排序树性能分析二叉排序树性能分析n n在最好的情况下，二叉排序树在最好的情况下，二叉排序树在最好的情况下，二叉排序树在最好的情况下，二叉排序树为一近似完全二叉树时，其查为一近似完全二叉树时，其查为一近似完全二叉树时，其查为一近似完全二叉树时，其查找深度为找深度为找深度为找深度为loglogloglog2 2 2 2n n n n量级，即其时量级，即其时量级，即其时量级，即其时间复杂性为间复杂性为间复杂性为间复杂性为O(logO(logO(logO(log2 2 2 2n)n)n)n)n n在最坏的情况下，二叉排序树在最坏的情况下，二叉排序树在最坏的情况下，二叉排序树在最坏的情况下，二叉排序树为近似线性表时为近似线性表时为近似线性表时为近似线性表时( ( ( (如以升序或如以升序或如以升序或如以升序或降序输入结点时，见右图降序输入结点时，见右图降序输入结点时，见右图降序输入结点时，见右图) ) ) )，其查找深度为其查找深度为其查找深度为其查找深度为n n n n量级，即其时量级，即其时量级，即其时量级，即其时间复杂性为间复杂性为间复杂性为间复杂性为O(nO(nO(nO(n) ) ) )8088926475211913563759- 中国科大数据结构9.3 动态查找表pp二叉排序树特性二叉排序树特性二叉排序树特性二叉排序树特性n n一个无序序列可以通过构造一棵二叉排序一个无序序列可以通过构造一棵二叉排序一个无序序列可以通过构造一棵二叉排序一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列（通过中序遍历）树而变成一个有序序列（通过中序遍历）树而变成一个有序序列（通过中序遍历）树而变成一个有序序列（通过中序遍历）n n插入新记录时，只需改变一个结点的指针，插入新记录时，只需改变一个结点的指针，插入新记录时，只需改变一个结点的指针，插入新记录时，只需改变一个结点的指针，相当于在有序序列中插入一个记录而不需相当于在有序序列中插入一个记录而不需相当于在有序序列中插入一个记录而不需相当于在有序序列中插入一个记录而不需要移动其它记录要移动其它记录要移动其它记录要移动其它记录n n二叉排序树既拥有类似于折半查找的特性，二叉排序树既拥有类似于折半查找的特性，二叉排序树既拥有类似于折半查找的特性，二叉排序树既拥有类似于折半查找的特性，又采用了链表作存储结构又采用了链表作存储结构又采用了链表作存储结构又采用了链表作存储结构n n但当插入记录的次序不当时但当插入记录的次序不当时( (如升序或降如升序或降序序) )，则二叉排序树深度很深（见右图），则二叉排序树深度很深（见右图），增加了查找的时间增加了查找的时间8088926475211913563759- 中国科大数据结构9.3 动态查找表pp平衡二叉树平衡二叉树平衡二叉树平衡二叉树平衡二叉树平衡二叉树平衡二叉树平衡二叉树(BalancedBinaryTree,Height-BalancedTree(BalancedBinaryTree,Height-BalancedTree, , , ,又称又称又称又称AVLAVLAVLAVL树树树树, , , ,AdelsenAdelsen-VelskiiVelskiiandLandisandLandis，阿德尔森一维尔斯和兰阿德尔森一维尔斯和兰迪斯迪斯) ) ) )是二叉排序树的另一种形式。其特点为：树中每个结点的左、是二叉排序树的另一种形式。其特点为：树中每个结点的左、是二叉排序树的另一种形式。其特点为：树中每个结点的左、是二叉排序树的另一种形式。其特点为：树中每个结点的左、右子树深度之差的绝对值不大于右子树深度之差的绝对值不大于右子树深度之差的绝对值不大于右子树深度之差的绝对值不大于1 1 1 1，即，即，即，即|h|hL L-h-hR R|1|1。可以证明，它们。可以证明，它们。可以证明，它们。可以证明，它们的深度和的深度和的深度和的深度和lognlognlognlogn是同数量级的（其中是同数量级的（其中是同数量级的（其中是同数量级的（其中n n n n为节点个数）。为节点个数）。为节点个数）。为节点个数）。56645923788198021137560565641913753780928821AVLAVL树树非非AVLAVL树树9- 中国科大数据结构9.3 动态查找表pp平衡二叉树平衡因子平衡二叉树平衡因子平衡二叉树平衡因子平衡二叉树平衡因子n n每个结点附加一个数字每个结点附加一个数字每个结点附加一个数字每个结点附加一个数字, , , , 给出该结点左子树的高度减去右子树给出该结点左子树的高度减去右子树给出该结点左子树的高度减去右子树给出该结点左子树的高度减去右子树的高度所得的高度差的高度所得的高度差的高度所得的高度差的高度所得的高度差, , , ,这个数字即为结点的平衡因子这个数字即为结点的平衡因子这个数字即为结点的平衡因子这个数字即为结点的平衡因子(balance (balance (balance (balance factor)factor)factor)factor)n nAVLAVLAVLAVL树任一结点平衡因子只能取树任一结点平衡因子只能取树任一结点平衡因子只能取树任一结点平衡因子只能取 -1, 0, 1-1, 0, 1-1, 0, 1-1, 0, 1n n若某个结点的平衡因子的绝对值大于若某个结点的平衡因子的绝对值大于若某个结点的平衡因子的绝对值大于若某个结点的平衡因子的绝对值大于1 1 1 1，则这棵二叉搜索树就失，则这棵二叉搜索树就失，则这棵二叉搜索树就失，则这棵二叉搜索树就失去了平衡，不再是去了平衡，不再是去了平衡，不再是去了平衡，不再是AVLAVLAVLAVL树。树。树。树。56564191375378092882100-10-10001009- 中国科大数据结构9.3 动态查找表p非平衡二叉树的平衡处理非平衡二叉树的平衡处理若一棵二叉排序树是平衡二叉树，扦入某个结点后，可能会变若一棵二叉排序树是平衡二叉树，扦入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。成一棵平衡二叉树。处理的原则应该是处理与插入点最近的、而平衡因子又比处理的原则应该是处理与插入点最近的、而平衡因子又比1大大或比或比-1小的结点。下面将分四种情况讨论平衡处理。小的结点。下面将分四种情况讨论平衡处理。9- 中国科大数据结构9.3 动态查找表1.1.1.1.LLLLLLLL型型型型 的处理的处理的处理的处理( ( ( (左左型左左型左左型左左型) ) ) )n n如下图所示，若在如下图所示，若在如下图所示，若在如下图所示，若在C C C C的左孩子的左孩子的左孩子的左孩子B B B B上扦入一个左孩子结点上扦入一个左孩子结点上扦入一个左孩子结点上扦入一个左孩子结点A A A A，使，使，使，使C C C C的的的的平衡因子由平衡因子由平衡因子由平衡因子由1 1 1 1变成了变成了变成了变成了2 2 2 2，成为不平衡的二叉树序树。，成为不平衡的二叉树序树。，成为不平衡的二叉树序树。，成为不平衡的二叉树序树。n n平衡处理：将平衡处理：将平衡处理：将平衡处理：将C C C C顺时针旋转，成为顺时针旋转，成为顺时针旋转，成为顺时针旋转，成为B B B B的右子树，而原来的右子树，而原来的右子树，而原来的右子树，而原来B B B B的右子树的右子树的右子树的右子树则变成则变成则变成则变成C C C C的左子树，待扦入结点的左子树，待扦入结点的左子树，待扦入结点的左子树，待扦入结点A A A A作为作为作为作为B B B B的左子树。的左子树。的左子树。的左子树。CBA210CBA000结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该 结点的平衡因子结点的平衡因子结点的平衡因子结点的平衡因子9- 中国科大数据结构9.3 动态查找表2.LR型的处理型的处理(左右型左右型)n如下图所示，在如下图所示，在C的左孩子的左孩子A上扦入一个右孩子上扦入一个右孩子B，使的，使的C的平的平衡因子由衡因子由1变成了变成了2，成为不平衡的二叉排序树。，成为不平衡的二叉排序树。n平衡处理：将平衡处理：将B变到变到A与与C之间，使之成为之间，使之成为LL型，然后按第型，然后按第1种种情形情形LL型处理。型处理。CBA210CBA000CBA2-10结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该 结点的平衡因子结点的平衡因子结点的平衡因子结点的平衡因子9- 中国科大数据结构9.3 动态查找表3.RR型的处理型的处理(右右型右右型)n如下图所示，在如下图所示，在A的右孩子的右孩子B上扦入一个右孩子上扦入一个右孩子C，使，使A的平衡的平衡因子由因子由-1变成变成-2，成为不平衡的二叉排序树。，成为不平衡的二叉排序树。n平衡处理：将平衡处理：将A逆时针旋转，成为逆时针旋转，成为B的左子树，而原来的左子树，而原来B的左子的左子树则变成树则变成A的右子树，待扦入结点的右子树，待扦入结点C成为成为B的右子树。的右子树。CBA-2-10CBA000结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该 结点的平衡因子结点的平衡因子结点的平衡因子结点的平衡因子9- 中国科大数据结构9.3 动态查找表4.RL型的处理型的处理(右左型右左型)n如下图所示，在如下图所示，在A的右孩子的右孩子C上扦入一个左孩子上扦入一个左孩子B，使，使A的平衡的平衡因子由因子由-1变成变成-2，成为不平衡的二叉排序树。，成为不平衡的二叉排序树。n平衡处理：将平衡处理：将B变到变到A与与C之间，使之成为之间，使之成为RR型，然后按第型，然后按第(3)种情形种情形RR型处理。型处理。CBA-2-10CBA000结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该 结点的平衡因子结点的平衡因子结点的平衡因子结点的平衡因子ACB-2109- 中国科大数据结构9.3 动态查找表p例例1：给定一个关键字序列：给定一个关键字序列4,5,7,2,1,3,6，试生成一棵平衡二叉树。，试生成一棵平衡二叉树。p分析：平衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树分析：平衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，最的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。具体生成过程见下图。后就可以建成一棵平衡二叉树。具体生成过程见下图。40a)插入插入4，平衡，平衡4-1b) 插入插入5，平衡，平衡50c) 插入插入7，不平衡，要处理，不平衡，要处理4-25-170405070RR型处理型处理9- 中国科大数据结构9.3 动态查找表405170d) 插入插入7，平衡，平衡2141527022e) 插入插入1，不平衡，要处理，不平衡，要处理104050702010LL型处理型处理4052702-111f) 插入插入3，不平衡，要处理，不平衡，要处理30LR型处理型处理30405-12010709- 中国科大数据结构9.3 动态查找表304-15-2201071f) 插入插入6，不平衡，要处理，不平衡，要处理06RL型处理型处理304060201070509- 中国科大数据结构9.3 动态查找表p平衡二叉树的查找及性能分析平衡二叉树的查找及性能分析平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找树完全相同。但它的查找性能优于二叉排序树，不像二叉排序树一性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二叉排序树，它的时间复杂度与二叉排序树的最好时间复杂相同，都为的最好时间复杂相同，都为O(log2n)。9- 中国科大数据结构9.3 动态查找表p例例2，对例，对例1给定的关键字序列给定的关键字序列4,5,7,2,1,3,6，试用二叉排序树和平，试用二叉排序树和平衡二叉树两种方法查找，给出查找衡二叉树两种方法查找，给出查找6的次数及成功的平均查找长度。的次数及成功的平均查找长度。p分析：由于关键字序列的顺序己经确定，故得到的二叉排序树和平分析：由于关键字序列的顺序己经确定，故得到的二叉排序树和平衡二叉树都是唯一的。得到的平衡二叉树见下座图，得到的二叉排衡二叉树都是唯一的。得到的平衡二叉树见下座图，得到的二叉排序树见下右图。序树见下右图。3462175平衡二叉树平衡二叉树3452176二叉排序树二叉排序树从右图的二叉排序树可知，查找从右图的二叉排序树可知，查找6 6需需4 4次，平均查找长度次，平均查找长度ASL=(1+2+2+3+3+3+4)/7=18/72.57ASL=(1+2+2+3+3+3+4)/7=18/72.57从左图的平衡二叉树可知，查找从左图的平衡二叉树可知，查找6 6需需2 2次，平均查找长度次，平均查找长度ASL=(1+2+2+3+3+3+3)=17/72.43ASL=(1+2+2+3+3+3+3)=17/72.43从结果可知，从结果可知，平衡二叉树的查找性能优于二叉排序树平衡二叉树的查找性能优于二叉排序树。9- 中国科大数据结构9.4 哈希表9.4.19.4.1 哈希表哈希表哈希表哈希表哈希哈希哈希哈希(Hash)(Hash)表又称散列表表又称散列表表又称散列表表又称散列表, , , ,是一种直接计算记录存放地址的方是一种直接计算记录存放地址的方是一种直接计算记录存放地址的方是一种直接计算记录存放地址的方法，它在关键码与存储位置之间直接建立了映象。法，它在关键码与存储位置之间直接建立了映象。法，它在关键码与存储位置之间直接建立了映象。法，它在关键码与存储位置之间直接建立了映象。pp哈希哈希哈希哈希函数函数函数函数n n哈希函数是从关键字空间到存储地址空间的一种映象哈希函数是从关键字空间到存储地址空间的一种映象哈希函数是从关键字空间到存储地址空间的一种映象哈希函数是从关键字空间到存储地址空间的一种映象n n哈希函数在记录的关键字与记录的存储地址之间建立起一种对哈希函数在记录的关键字与记录的存储地址之间建立起一种对哈希函数在记录的关键字与记录的存储地址之间建立起一种对哈希函数在记录的关键字与记录的存储地址之间建立起一种对应关系。可写成：应关系。可写成：应关系。可写成：应关系。可写成：addr(aaddr(ai i)=)=H(keyH(keyi i) )n nH()H()为哈希函数为哈希函数为哈希函数为哈希函数n nkeykeyi i是表中元素是表中元素是表中元素是表中元素a ai i关键字关键字关键字关键字, , , ,addr(aaddr(ai i) )是存储地址是存储地址是存储地址是存储地址9- 中国科大数据结构9.4 哈希表pp哈希查找哈希查找哈希查找哈希查找n n哈希查找也叫散列查找，是利用哈希函数进行查找的过程哈希查找也叫散列查找，是利用哈希函数进行查找的过程哈希查找也叫散列查找，是利用哈希函数进行查找的过程哈希查找也叫散列查找，是利用哈希函数进行查找的过程n n首先利用哈希函数及记录的关键字计算出记录的存储地址首先利用哈希函数及记录的关键字计算出记录的存储地址首先利用哈希函数及记录的关键字计算出记录的存储地址首先利用哈希函数及记录的关键字计算出记录的存储地址n n然后直接到指定地址进行查找然后直接到指定地址进行查找然后直接到指定地址进行查找然后直接到指定地址进行查找n n不需要经过比较，一次存取就能得到所查元素不需要经过比较，一次存取就能得到所查元素不需要经过比较，一次存取就能得到所查元素不需要经过比较，一次存取就能得到所查元素pp哈希冲突哈希冲突哈希冲突哈希冲突n n不同的记录，其关键字通过哈希函数的计算，可能得到相同的不同的记录，其关键字通过哈希函数的计算，可能得到相同的不同的记录，其关键字通过哈希函数的计算，可能得到相同的不同的记录，其关键字通过哈希函数的计算，可能得到相同的地址地址地址地址n n把不同的记录映射到同一个散列地址上，这种现象称为冲突把不同的记录映射到同一个散列地址上，这种现象称为冲突把不同的记录映射到同一个散列地址上，这种现象称为冲突把不同的记录映射到同一个散列地址上，这种现象称为冲突9- 中国科大数据结构9.4 哈希表pp哈希表定义哈希表定义哈希表定义哈希表定义n n根据设定的哈希函数根据设定的哈希函数根据设定的哈希函数根据设定的哈希函数 H(keyH(keyH(keyH(key) ) ) ) 和所选中的处理冲突的方法和所选中的处理冲突的方法和所选中的处理冲突的方法和所选中的处理冲突的方法n n将一组关键字映象到一个有限的、地址连续的地址集上将一组关键字映象到一个有限的、地址连续的地址集上将一组关键字映象到一个有限的、地址连续的地址集上将一组关键字映象到一个有限的、地址连续的地址集上n n以关键字在地址集中的以关键字在地址集中的以关键字在地址集中的以关键字在地址集中的“象象象象”作为相应记录在表中的存储位置作为相应记录在表中的存储位置作为相应记录在表中的存储位置作为相应记录在表中的存储位置n n如此构造所得的查找表称之为如此构造所得的查找表称之为如此构造所得的查找表称之为如此构造所得的查找表称之为“哈希表哈希表哈希表哈希表”。pp哈希函数均匀性哈希函数均匀性哈希函数均匀性哈希函数均匀性n n哈希函数实现的一般是从一个大的集合（部分元素，空间位置哈希函数实现的一般是从一个大的集合（部分元素，空间位置哈希函数实现的一般是从一个大的集合（部分元素，空间位置哈希函数实现的一般是从一个大的集合（部分元素，空间位置上一般不连续）到一个小的集合（空间连续）的映射上一般不连续）到一个小的集合（空间连续）的映射上一般不连续）到一个小的集合（空间连续）的映射上一般不连续）到一个小的集合（空间连续）的映射n n一个好的哈希函数，对于记录中的任何关键字，将其映射到地一个好的哈希函数，对于记录中的任何关键字，将其映射到地一个好的哈希函数，对于记录中的任何关键字，将其映射到地一个好的哈希函数，对于记录中的任何关键字，将其映射到地址集合中任何一个地址的概率应该是相等的址集合中任何一个地址的概率应该是相等的址集合中任何一个地址的概率应该是相等的址集合中任何一个地址的概率应该是相等的n n即关键字经过哈希函数得到一个即关键字经过哈希函数得到一个即关键字经过哈希函数得到一个即关键字经过哈希函数得到一个“随机的地址随机的地址随机的地址随机的地址”9- 中国科大数据结构9.4 哈希表9.4.29.4.2哈希函数哈希函数哈希函数哈希函数pp要求要求要求要求n n哈希函数应是简单的，能在较短的时间内计算出结果哈希函数应是简单的，能在较短的时间内计算出结果哈希函数应是简单的，能在较短的时间内计算出结果哈希函数应是简单的，能在较短的时间内计算出结果n n哈希函数的定义域必须包括需要存储的全部关键字，如果散列哈希函数的定义域必须包括需要存储的全部关键字，如果散列哈希函数的定义域必须包括需要存储的全部关键字，如果散列哈希函数的定义域必须包括需要存储的全部关键字，如果散列表允许有表允许有表允许有表允许有 m m m m 个地址时，其值域必须在个地址时，其值域必须在个地址时，其值域必须在个地址时，其值域必须在 0 0 0 0 到到到到 m-1 m-1 m-1 m-1 之间之间之间之间 n n散列函数计算出来的地址应能均匀分布在整个地址空间中散列函数计算出来的地址应能均匀分布在整个地址空间中散列函数计算出来的地址应能均匀分布在整个地址空间中散列函数计算出来的地址应能均匀分布在整个地址空间中9- 中国科大数据结构9.4 哈希表pp哈希函数哈希函数哈希函数哈希函数( ( ( (直接定址法直接定址法直接定址法直接定址法) ) ) )n n直接定址法中，哈希函数取关键字的线性函数直接定址法中，哈希函数取关键字的线性函数直接定址法中，哈希函数取关键字的线性函数直接定址法中，哈希函数取关键字的线性函数 H(keyH(key)=akey+b)=akey+b其中其中其中其中a a a a和和和和b b b b为常数为常数为常数为常数pp直接定址法举例直接定址法举例直接定址法举例直接定址法举例H(keyH(key)=key-2005131000)=key-200513100000300320051310032005131003朱嘉成朱嘉成朱嘉成朱嘉成男男男男网络学院网络学院网络学院网络学院00500520051310052005131005陈乾陈乾陈乾陈乾男男男男网络学院网络学院网络学院网络学院00600620051310062005131006桂许升桂许升桂许升桂许升男男男男网络学院网络学院网络学院网络学院00700720051310072005131007罗杨洋罗杨洋罗杨洋罗杨洋男男男男网络学院网络学院网络学院网络学院00800820051310082005131008叶建行叶建行叶建行叶建行男男男男网络学院网络学院网络学院网络学院00900920051310092005131009曹亚仑曹亚仑曹亚仑曹亚仑男男男男网络学院网络学院网络学院网络学院01201220051310122005131012欧东欧东欧东欧东男男男男网络学院网络学院网络学院网络学院9- 中国科大数据结构9.4 哈希表pp直接定址法特性直接定址法特性直接定址法特性直接定址法特性n n直接定址法仅适合于地址集合的大小与关键字集合的大小相等直接定址法仅适合于地址集合的大小与关键字集合的大小相等直接定址法仅适合于地址集合的大小与关键字集合的大小相等直接定址法仅适合于地址集合的大小与关键字集合的大小相等的情况的情况的情况的情况n n当当当当a=1a=1a=1a=1时，时，时，时，H(keyH(keyH(keyH(key)=key)=key)=key)=key，即用关键字作地址，即用关键字作地址，即用关键字作地址，即用关键字作地址n n在实际应用中能使用这种哈希函数的情况很少在实际应用中能使用这种哈希函数的情况很少在实际应用中能使用这种哈希函数的情况很少在实际应用中能使用这种哈希函数的情况很少9- 中国科大数据结构9.4 哈希表pp哈希函数哈希函数哈希函数哈希函数( ( ( (数字分析法数字分析法数字分析法数字分析法) ) ) )n n假设关键字集合中的每个关键字都是由假设关键字集合中的每个关键字都是由假设关键字集合中的每个关键字都是由假设关键字集合中的每个关键字都是由 s s s s 位数字组成位数字组成位数字组成位数字组成 (u(u1 1,u,u2 2, ,u,us s) )n n分析关键字集中的全体分析关键字集中的全体分析关键字集中的全体分析关键字集中的全体n n从中提取从中提取从中提取从中提取分布均匀分布均匀分布均匀分布均匀的若干位或它们的组合作为地址。的若干位或它们的组合作为地址。的若干位或它们的组合作为地址。的若干位或它们的组合作为地址。9- 中国科大数据结构9.4 哈希表pp数字分析法举例数字分析法举例数字分析法举例数字分析法举例有有有有80808080个记录，关键字为个记录，关键字为个记录，关键字为个记录，关键字为8 8 8 8位十进制数，哈希地址为位十进制数，哈希地址为位十进制数，哈希地址为位十进制数，哈希地址为2 2 2 2位十进制数位十进制数位十进制数位十进制数8 1 3 4 6 5 3 28 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 3 6 8 5 3 78 1 4 1 9 3 5 58 1 4 1 9 3 5 5 分析：分析：只取只取8 8 只取只取1 1 只取只取3 3、4 4 只取只取2 2、7 7、5 5 数字分布近乎随机数字分布近乎随机所以：取所以：取任意两位或两位与任意两位或两位与另两位的叠加作哈希地址另两位的叠加作哈希地址9- 中国科大数据结构9.4 哈希表pp数字分析法特性数字分析法特性数字分析法特性数字分析法特性n n数字分析法仅适用于事先明确知道表中所有关键码每一位数值数字分析法仅适用于事先明确知道表中所有关键码每一位数值数字分析法仅适用于事先明确知道表中所有关键码每一位数值数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况的分布情况的分布情况的分布情况n n数字分析法完全依赖于关键码集合。数字分析法完全依赖于关键码集合。数字分析法完全依赖于关键码集合。数字分析法完全依赖于关键码集合。n n如果换一个关键码集合，选择哪几位要重新决定。如果换一个关键码集合，选择哪几位要重新决定。如果换一个关键码集合，选择哪几位要重新决定。如果换一个关键码集合，选择哪几位要重新决定。9- 中国科大数据结构9.4 哈希表pp哈希函数哈希函数哈希函数哈希函数( ( ( (平方取中法平方取中法平方取中法平方取中法) ) ) )以关键字的平方值的中间几位作为存储地址。以关键字的平方值的中间几位作为存储地址。以关键字的平方值的中间几位作为存储地址。以关键字的平方值的中间几位作为存储地址。n n求求求求“关键字的平方值关键字的平方值关键字的平方值关键字的平方值” 的目的是的目的是的目的是的目的是“扩大差别扩大差别扩大差别扩大差别” n n同时平方值的中间各位又能受到整个关键字中各位的影响。同时平方值的中间各位又能受到整个关键字中各位的影响。同时平方值的中间各位又能受到整个关键字中各位的影响。同时平方值的中间各位又能受到整个关键字中各位的影响。9- 中国科大数据结构9.4 哈希表pp平方取中法举例平方取中法举例平方取中法举例平方取中法举例此方法在词典处理中使用十分广泛。它先计算构成关键码的标此方法在词典处理中使用十分广泛。它先计算构成关键码的标此方法在词典处理中使用十分广泛。它先计算构成关键码的标此方法在词典处理中使用十分广泛。它先计算构成关键码的标识符的内码的平方识符的内码的平方识符的内码的平方识符的内码的平方, , , , 然后按照散列表的大小取中间的若干位作为散然后按照散列表的大小取中间的若干位作为散然后按照散列表的大小取中间的若干位作为散然后按照散列表的大小取中间的若干位作为散列地址。列地址。列地址。列地址。pp标识符的八进制内码表示及其平方值标识符的八进制内码表示及其平方值标识符的八进制内码表示及其平方值标识符的八进制内码表示及其平方值标识符标识符标识符标识符内码内码内码内码 内码的平方内码的平方内码的平方内码的平方 散列地址散列地址散列地址散列地址A A0101 0101001001A A1 1013401342 20420420 0042042B B02024 4004004DMAXDMAX04150130041501302152621526443443617100617100443443DMAXDMAX1104150130340415013034 52644752644735235221514202151420352352AMAX AMAX 0115013001150130135413542362361710017100236236AMAXAMAX1101150130340115013034 345424345424652652215142021514206526529- 中国科大数据结构9.4 哈希表pp平方取中法特性平方取中法特性平方取中法特性平方取中法特性n n平方取中法是较常用的构造哈希函数的方法平方取中法是较常用的构造哈希函数的方法平方取中法是较常用的构造哈希函数的方法平方取中法是较常用的构造哈希函数的方法n n适合于关键字中的每一位都有某些数字重复出现且频度很高的适合于关键字中的每一位都有某些数字重复出现且频度很高的适合于关键字中的每一位都有某些数字重复出现且频度很高的适合于关键字中的每一位都有某些数字重复出现且频度很高的情况情况情况情况n n中间所取的位数，由哈希表长决定中间所取的位数，由哈希表长决定中间所取的位数，由哈希表长决定中间所取的位数，由哈希表长决定9- 中国科大数据结构9.4 哈希表pp哈希函数哈希函数哈希函数哈希函数( ( ( (折叠法折叠法折叠法折叠法) ) ) )将关键字分割成位数相同的若干部分将关键字分割成位数相同的若干部分将关键字分割成位数相同的若干部分将关键字分割成位数相同的若干部分( ( ( (最后部分的位数可以不最后部分的位数可以不最后部分的位数可以不最后部分的位数可以不同同同同) ) ) )，然后取它们的叠加和，然后取它们的叠加和，然后取它们的叠加和，然后取它们的叠加和( ( ( (舍去进位舍去进位舍去进位舍去进位) ) ) )为哈希地址。为哈希地址。为哈希地址。为哈希地址。n n移位叠加移位叠加移位叠加移位叠加: : : :将分割后的几部分低位对齐相加将分割后的几部分低位对齐相加将分割后的几部分低位对齐相加将分割后的几部分低位对齐相加n n间界叠加间界叠加间界叠加间界叠加: : : :从一端沿分割界来回折送，然后对齐相加从一端沿分割界来回折送，然后对齐相加从一端沿分割界来回折送，然后对齐相加从一端沿分割界来回折送，然后对齐相加9- 中国科大数据结构9.4 哈希表pp折叠法举例：关键字为：折叠法举例：关键字为：折叠法举例：关键字为：折叠法举例：关键字为：0442205864044220586404422058640442205864，哈希地址位数为，哈希地址位数为，哈希地址位数为，哈希地址位数为4 4 4 4pp折叠法特性折叠法特性折叠法特性折叠法特性折叠法适合于关键字的数字位数特别多，而且每一位上数字分折叠法适合于关键字的数字位数特别多，而且每一位上数字分折叠法适合于关键字的数字位数特别多，而且每一位上数字分折叠法适合于关键字的数字位数特别多，而且每一位上数字分布大致均匀的情况布大致均匀的情况布大致均匀的情况布大致均匀的情况5 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加间界叠加9- 中国科大数据结构9.4 哈希表pp哈希函数哈希函数哈希函数哈希函数( ( ( (除留余数法除留余数法除留余数法除留余数法) ) ) )取关键字被某个不大于哈希表长取关键字被某个不大于哈希表长取关键字被某个不大于哈希表长取关键字被某个不大于哈希表长m m m m的数的数的数的数p p p p除后所得余数为哈希地址除后所得余数为哈希地址除后所得余数为哈希地址除后所得余数为哈希地址H(keyH(keyH(keyH(key) = key MOD p ( ) = key MOD p ( ) = key MOD p ( ) = key MOD p ( pmpmpmpm ) ) ) )n nm m m m为表长为表长为表长为表长 n np p p p为不大于为不大于为不大于为不大于m m m m的素数或是不含的素数或是不含的素数或是不含的素数或是不含20202020以下的质因子以下的质因子以下的质因子以下的质因子pp哈希函数哈希函数哈希函数哈希函数( ( ( (除留余数法除留余数法除留余数法除留余数法p p p p值值值值) ) ) )给定一组关键字为给定一组关键字为给定一组关键字为给定一组关键字为: 12,39,18,24,33,21: 12,39,18,24,33,21: 12,39,18,24,33,21: 12,39,18,24,33,21，若取，若取，若取，若取 p=9, p=9, p=9, p=9, 则他们对应的则他们对应的则他们对应的则他们对应的哈希函数值将为哈希函数值将为哈希函数值将为哈希函数值将为: : : : 3, 3, 0, 6, 6, 33, 3, 0, 6, 6, 33, 3, 0, 6, 6, 33, 3, 0, 6, 6, 3可见，若可见，若可见，若可见，若p p p p中含质因子中含质因子中含质因子中含质因子3, 3, 3, 3, 则所有含质因子则所有含质因子则所有含质因子则所有含质因子3 3 3 3的关键字均映射到的关键字均映射到的关键字均映射到的关键字均映射到“3 3 3 3 的的的的倍数倍数倍数倍数”的地址上，从而增加了的地址上，从而增加了的地址上，从而增加了的地址上，从而增加了“冲突冲突冲突冲突”的可能的可能的可能的可能pp除留余数法特性除留余数法特性除留余数法特性除留余数法特性n n除留余数法是一种最简单、最常用的构造哈希函数的方法除留余数法是一种最简单、最常用的构造哈希函数的方法除留余数法是一种最简单、最常用的构造哈希函数的方法除留余数法是一种最简单、最常用的构造哈希函数的方法n n可以对关键字直接取模可以对关键字直接取模可以对关键字直接取模可以对关键字直接取模(MOD)(MOD)(MOD)(MOD)，也可在折叠、平方取中等运算之后取模。，也可在折叠、平方取中等运算之后取模。，也可在折叠、平方取中等运算之后取模。，也可在折叠、平方取中等运算之后取模。9- 中国科大数据结构9.4 哈希表9.4.39.4.3处理冲突法处理冲突法处理冲突法处理冲突法“处理冲突处理冲突处理冲突处理冲突” 的实际含义是：为产生冲突的地址寻找下一个的实际含义是：为产生冲突的地址寻找下一个的实际含义是：为产生冲突的地址寻找下一个的实际含义是：为产生冲突的地址寻找下一个哈希地址。处理冲突的方法主要有三种：哈希地址。处理冲突的方法主要有三种：哈希地址。处理冲突的方法主要有三种：哈希地址。处理冲突的方法主要有三种：1.1.1.1.开放定址法开放定址法开放定址法开放定址法2.2.2.2.再哈希法再哈希法再哈希法再哈希法3.3.3.3.链地址法链地址法链地址法链地址法9- 中国科大数据结构9.4 哈希表pp处理冲突的方法处理冲突的方法处理冲突的方法处理冲突的方法( (开放定址法开放定址法开放定址法开放定址法) )为产生冲突的地址为产生冲突的地址为产生冲突的地址为产生冲突的地址 H(keyH(keyH(keyH(key) ) ) ) 求得一个空的地址序列求得一个空的地址序列求得一个空的地址序列求得一个空的地址序列：H H0 0,H,H1 1, ,H H2 2,H,Hs s，1sm-11sm-1H Hi i=H(key)+dH(key)+di iMODm(i=1,2,s)MODm(i=1,2,s)n nH(keyH(key) )为哈希函数为哈希函数为哈希函数为哈希函数n nm m m m为哈希表长为哈希表长为哈希表长为哈希表长n n当当当当d d d di i i i取取取取1,2,3,1,2,3,1,2,3,1,2,3,m-1,m-1,m-1,m-1时，称这种开放定址法为时，称这种开放定址法为时，称这种开放定址法为时，称这种开放定址法为线性探测再散列。线性探测再散列。线性探测再散列。线性探测再散列。9- 中国科大数据结构pp举例：在长度为举例：在长度为举例：在长度为举例：在长度为11111111的哈希表中已填有关键字分别为的哈希表中已填有关键字分别为的哈希表中已填有关键字分别为的哈希表中已填有关键字分别为17171717，60606060和和和和29292929的记的记的记的记录（哈希函数录（哈希函数录（哈希函数录（哈希函数H(keyH(keyH(keyH(key) ) ) ) key MOD 11key MOD 11key MOD 11key MOD 11），现有第四个记录，其关键），现有第四个记录，其关键），现有第四个记录，其关键），现有第四个记录，其关键字为字为字为字为38383838，由哈希函数得到的哈希地址为，由哈希函数得到的哈希地址为，由哈希函数得到的哈希地址为，由哈希函数得到的哈希地址为5 5 5 5，产生冲突。，产生冲突。，产生冲突。，产生冲突。n n线性探测再散列：得到下一个地址线性探测再散列：得到下一个地址线性探测再散列：得到下一个地址线性探测再散列：得到下一个地址6 6 6 6，仍冲突；再求下一个地址，仍冲突；再求下一个地址，仍冲突；再求下一个地址，仍冲突；再求下一个地址7 7 7 7，仍冲突；直到哈希地址为，仍冲突；直到哈希地址为，仍冲突；直到哈希地址为，仍冲突；直到哈希地址为8 8 8 8的位置（的位置（的位置（的位置（“空空空空”）时止。）时止。）时止。）时止。n n二次探测再散列：应填入序号为二次探测再散列：应填入序号为二次探测再散列：应填入序号为二次探测再散列：应填入序号为4 4 4 4的位置。的位置。的位置。的位置。n n伪随机探测再散列：伪随机数列伪随机探测再散列：伪随机数列伪随机探测再散列：伪随机数列伪随机探测再散列：伪随机数列9, 9, 9, 9, 应填入序号为应填入序号为应填入序号为应填入序号为2 2 2 2的位置。的位置。的位置。的位置。 9.4 哈希表9- 中国科大数据结构9.4 哈希表0 1 2 3 4 5 6 7 8 9 60 17 29 (a)插入前插入前 60 17 29 38(b) 线性探测再散列线性探测再散列 38 60 17 29 (c) 二次探测再散列二次探测再散列60 17 29 38 (d) 伪随机探测再散列伪随机探测再散列 用开放定址处理冲突时，关键字为用开放定址处理冲突时，关键字为3838的记录插入前后的哈希表的记录插入前后的哈希表 9- 中国科大数据结构9.4 哈希表pp处理冲突的方法处理冲突的方法处理冲突的方法处理冲突的方法( ( ( (再哈希法再哈希法再哈希法再哈希法) ) ) )H H H Hi i i i = = = = RHRHRHRHi i i i (key) (key) (key) (key) ( i = 1, 2, ( i = 1, 2, ( i = 1, 2, ( i = 1, 2, , k ) , k ) , k ) , k )n n其中，其中，其中，其中，R R R R、H H H Hi i i i均是不同的哈希函数，即在同义词产生地址冲突时计算另均是不同的哈希函数，即在同义词产生地址冲突时计算另均是不同的哈希函数，即在同义词产生地址冲突时计算另均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。一个哈希函数地址，直到冲突不再发生。一个哈希函数地址，直到冲突不再发生。一个哈希函数地址，直到冲突不再发生。n n再哈希法特点：不易产生聚集，但增加计算时间再哈希法特点：不易产生聚集，但增加计算时间再哈希法特点：不易产生聚集，但增加计算时间再哈希法特点：不易产生聚集，但增加计算时间pp处理冲突的方法处理冲突的方法处理冲突的方法处理冲突的方法( ( ( (链地址法链地址法链地址法链地址法) ) ) )将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址区间数产生的哈希地址区间数产生的哈希地址区间数产生的哈希地址区间0, m0, m0, m0, m1111上，则设立一个指针型向量：上，则设立一个指针型向量：上，则设立一个指针型向量：上，则设立一个指针型向量：Chain Chain Chain Chain ChainChainChainChain HashmHashmHashmHashm;其每个分裂的初始状态都是空指针。凡哈希地址为其每个分裂的初始状态都是空指针。凡哈希地址为其每个分裂的初始状态都是空指针。凡哈希地址为其每个分裂的初始状态都是空指针。凡哈希地址为i i i i的记录都插入到头指针的记录都插入到头指针的记录都插入到头指针的记录都插入到头指针为为为为Chain Chain Chain Chain HashmHashmHashmHashm 的链表中。在链表中的插入位置可以在表头或表尾，也可的链表中。在链表中的插入位置可以在表头或表尾，也可的链表中。在链表中的插入位置可以在表头或表尾，也可的链表中。在链表中的插入位置可以在表头或表尾，也可以在中间，以保持同义词在同一线性链表中按关键字有序。以在中间，以保持同义词在同一线性链表中按关键字有序。以在中间，以保持同义词在同一线性链表中按关键字有序。以在中间，以保持同义词在同一线性链表中按关键字有序。9- 中国科大数据结构9.4 哈希表pp举例：给定关键字集合举例：给定关键字集合举例：给定关键字集合举例：给定关键字集合19,01,23,14,55,68, 19,01,23,14,55,68, 19,01,23,14,55,68, 19,01,23,14,55,68, 11,82,3611,82,3611,82,3611,82,36，设定哈希函，设定哈希函，设定哈希函，设定哈希函数数数数H(keyH(keyH(keyH(key)=key MOD 11 )=key MOD 11 )=key MOD 11 )=key MOD 11 ( ( ( (表长表长表长表长=11)=11)=11)=11)表后插入表后插入表后插入表后插入 pp查找不成功，再插入新结查找不成功，再插入新结查找不成功，再插入新结查找不成功，再插入新结点时，用表后插入方法较点时，用表后插入方法较点时，用表后插入方法较点时，用表后插入方法较好好好好 0123456789101901145568118236239- 中国科大数据结构9.4 哈希表pp举例：给定关键字集合举例：给定关键字集合举例：给定关键字集合举例：给定关键字集合19,01,23,14,55,68, 19,01,23,14,55,68, 11,82,3611,82,36，设定哈希函设定哈希函设定哈希函设定哈希函数数数数H(keyH(key)=key MOD 11 )=key MOD 11 ( ( ( (表长表长表长表长=11)=11)=11)=11)表头插入表头插入表头插入表头插入 pp给定关键字集合，逐步生给定关键字集合，逐步生给定关键字集合，逐步生给定关键字集合，逐步生成哈希表时，用表头插入成哈希表时，用表头插入成哈希表时，用表头插入成哈希表时，用表头插入方法较好方法较好方法较好方法较好 0123456789101923361168558214019- 中国科大数据结构9.4 哈希表9.4.49.4.4哈希表的实现哈希表的实现哈希表的实现哈希表的实现假设哈希函数为关键字求模运算，哈希表用拉链法解决冲突，假设哈希函数为关键字求模运算，哈希表用拉链法解决冲突，假设哈希函数为关键字求模运算，哈希表用拉链法解决冲突，假设哈希函数为关键字求模运算，哈希表用拉链法解决冲突，其结构可以定义如下：其结构可以定义如下：其结构可以定义如下：其结构可以定义如下：#defineLEN31/表长表长LEN最好为质数最好为质数typedefstructnodeintdata;structnode*next;node;structnodeHashTabLEN;9- 中国科大数据结构9.4 哈希表pp哈希表的实现哈希函数哈希表的实现哈希函数哈希表的实现哈希函数哈希表的实现哈希函数hash()hash()hash()hash()返回值为哈希表地址返回值为哈希表地址返回值为哈希表地址返回值为哈希表地址: : : :pp查找过程查找过程查找过程查找过程n n对于给定值对于给定值对于给定值对于给定值keykeykeykey，计算哈希地址，计算哈希地址，计算哈希地址，计算哈希地址 p=p=hash(Keyhash(Key) )n n若若若若HashTabp.nextHashTabp.next=NULL=NULL，则，则，则，则查找不成功查找不成功查找不成功查找不成功n n若若若若HashTabp.next.dataHashTabp.next.data=key=key，则查找成功，则查找成功，则查找成功，则查找成功n n否则否则否则否则 “求下一地址求下一地址求下一地址求下一地址”，再进行，再进行，再进行，再进行比较比较比较比较inthash(intkey)retAddr=keyMODLEN;return(retAddr);给定给定k值值计算计算hash(key)此地址为空此地址为空关键字关键字=key查找失败返回查找失败返回或插入新结点或插入新结点查找成功查找成功按处理冲突方法按处理冲突方法计算下一地址计算下一地址YNYN9- 中国科大数据结构9.4 哈希表pp查找函数查找函数查找函数查找函数search()search()search()search()若找到若找到若找到若找到keykeykeykey，返回其结点指针；否则将其插入表中再返回其结，返回其结点指针；否则将其插入表中再返回其结，返回其结点指针；否则将其插入表中再返回其结，返回其结点指针；否则将其插入表中再返回其结点指针点指针点指针点指针 链地址法解决冲突，表头插入链地址法解决冲突，表头插入链地址法解决冲突，表头插入链地址法解决冲突，表头插入 node*search(intkey)i=hash(key);p=HashTabi.next;while(p!=NULL)if(p.data=key)return(p);p=p.next;q=malloc(sizeof(node);/表头插入表头插入q.data=key;q.next=HashTabi.next;HashTabi.next=q;return(q);9- 中国科大数据结构9.4 哈希表9.4.59.4.5 哈希哈希哈希哈希查找的性能分析查找的性能分析查找的性能分析查找的性能分析哈希查找按理论分析，它的时间复杂度应为哈希查找按理论分析，它的时间复杂度应为哈希查找按理论分析，它的时间复杂度应为哈希查找按理论分析，它的时间复杂度应为O(1)O(1)，它的平均查，它的平均查，它的平均查，它的平均查找长度应为找长度应为找长度应为找长度应为ASL=1ASL=1，但实际上由于冲突的存在，它的平均查找长度，但实际上由于冲突的存在，它的平均查找长度，但实际上由于冲突的存在，它的平均查找长度，但实际上由于冲突的存在，它的平均查找长度将会比将会比将会比将会比1 1大。下面将分析几种方法的平均查找长度。大。下面将分析几种方法的平均查找长度。大。下面将分析几种方法的平均查找长度。大。下面将分析几种方法的平均查找长度。pp线性探查法的性能分析线性探查法的性能分析线性探查法的性能分析线性探查法的性能分析由于线性探查法解决冲突是线性地查找空闲位置的，平均查找由于线性探查法解决冲突是线性地查找空闲位置的，平均查找由于线性探查法解决冲突是线性地查找空闲位置的，平均查找由于线性探查法解决冲突是线性地查找空闲位置的，平均查找长度与表的大小长度与表的大小长度与表的大小长度与表的大小mm无关，只与所选取的散列函数无关，只与所选取的散列函数无关，只与所选取的散列函数无关，只与所选取的散列函数H H及装填因子及装填因子及装填因子及装填因子 的值的值的值的值和该处理方法有关，这时的成功的平均查找长度为和该处理方法有关，这时的成功的平均查找长度为和该处理方法有关，这时的成功的平均查找长度为和该处理方法有关，这时的成功的平均查找长度为ASL=1/2ASL=1/2(1+1/(1-)(1+1/(1-)。pp链地址法的性能分析链地址法的性能分析链地址法的性能分析链地址法的性能分析由于拉链法查找就是在单链表上查找，查找单链表中第一个结由于拉链法查找就是在单链表上查找，查找单链表中第一个结由于拉链法查找就是在单链表上查找，查找单链表中第一个结由于拉链法查找就是在单链表上查找，查找单链表中第一个结点的次数为点的次数为点的次数为点的次数为1 1，第二个结点次数为，第二个结点次数为，第二个结点次数为，第二个结点次数为2 2，其余依次类推。它的平均查找，其余依次类推。它的平均查找，其余依次类推。它的平均查找，其余依次类推。它的平均查找长度长度长度长度ASL=1+/2ASL=1+/2。9- 中国科大数据结构9.4 哈希表pp哈希查找的性能分析哈希查找的性能分析哈希查找的性能分析哈希查找的性能分析( ( ( (平均查找长度平均查找长度平均查找长度平均查找长度ASL)ASL)ASL)ASL)n n线性探测再散列的哈希表查找成功时：线性探测再散列的哈希表查找成功时：线性探测再散列的哈希表查找成功时：线性探测再散列的哈希表查找成功时：ASL()(1+1/(1-)ASL()(1+1/(1-)n n二次探测再散列的哈希表查找成功时：二次探测再散列的哈希表查找成功时：二次探测再散列的哈希表查找成功时：二次探测再散列的哈希表查找成功时：ASL-(1/)ln(1-)ASL-(1/)ln(1-)n n链地址法处理冲突的哈希表查找成功时：链地址法处理冲突的哈希表查找成功时：链地址法处理冲突的哈希表查找成功时：链地址法处理冲突的哈希表查找成功时：ASL(1+/2)ASL(1+/2)9- 中国科大数据结构习题pp本章习题参见教师网页：本章习题参见教师网页：本章习题参见教师网页：本章习题参见教师网页：http:/http:/staff.ustc.edu.cn/leeyistaff.ustc.edu.cn/leeyi9-