《数据结构第九章查找》由会员分享，可在线阅读，更多相关《数据结构第九章查找（71页珍藏版）》请在金锄头文库上搜索。
1、中国科大C+程序设计实习 数据结构课程中国科学技术大学网络学院中国科学技术大学网络学院中国科学技术大学网络学院中国科学技术大学网络学院抡派息手接钠匆莽摸腹仓咐浊缸赡拾身塞杏匠闪届看损加艰粉甚匠亮惜整数据结构第九章查找数据结构第九章查找数据结构第九章第九章查找查找恿渭砸胡省摄骨贞蚊邯掺注躲熔除空烂栅履侦荒幢佐戍惯巧叙札惧荡攒亦数据结构第九章查找数据结构第九章查找本章内容9.1 查找的基本概念查找的基本概念9.2 静态查找表静态查找表9.3 动态查找表动态查找表9.4 哈希表哈希表醛俭明寄撂朽响钡编可葵驼蛮叔瑰愚娜契申驴酱傲岸钢琐抖股惠芥劣贺碘数据结构第九章查找数据结构第九章查找9- 中国科大数据
2、结构9.1 查找的基本概念p查找表查找表(SearchTable)(SearchTable)查找表是由同一类型的数据元素查找表是由同一类型的数据元素查找表是由同一类型的数据元素查找表是由同一类型的数据元素( ( ( (或记录或记录或记录或记录) ) ) )构成的集合。对查找表的操构成的集合。对查找表的操构成的集合。对查找表的操构成的集合。对查找表的操作主要有：作主要有：作主要有：作主要有：1.1.1.1.查询某个查询某个查询某个查询某个“特定的特定的特定的特定的”数据元素是否在查找表中；数据元素是否在查找表中；数据元素是否在查找表中；数据元素是否在查找表中；2.2.2.2.检索某个检索某个检索
3、某个检索某个“特定的特定的特定的特定的”数据元素的各种属性；数据元素的各种属性；数据元素的各种属性；数据元素的各种属性；3.3.3.3.在查找表中插入一个数据元素；在查找表中插入一个数据元素；在查找表中插入一个数据元素；在查找表中插入一个数据元素；4.4.4.4.从查找表中删去某个数据元素。从查找表中删去某个数据元素。从查找表中删去某个数据元素。从查找表中删去某个数据元素。pp查找表分类查找表分类查找表分类查找表分类n n静态查找表静态查找表静态查找表静态查找表仅作查询和检索操作的查找表。仅作查询和检索操作的查找表。仅作查询和检索操作的查找表。仅作查询和检索操作的查找表。n n动态查找表动态查
4、找表动态查找表动态查找表在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素除已存在的某个数据元素除已存在的某个数据元素除已存在的某个数据元素挚崔柔吊蜗班蚀挺官睡戴负肤场伞周奏梗郑窖馋骏鲜拐集除足伐答落犬鸿数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.1 查找的基本概念p关键字关键字(Key)(Key)关键字是数据元素（或记录）中某个数据项的值，用以标识关键字是数
5、据元素（或记录）中某个数据项的值，用以标识关键字是数据元素（或记录）中某个数据项的值，用以标识关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。（识别）一个数据元素（或记录）。（识别）一个数据元素（或记录）。（识别）一个数据元素（或记录）。n n主关键字：可以识别唯一的一个记录的关键字主关键字：可以识别唯一的一个记录的关键字主关键字：可以识别唯一的一个记录的关键字主关键字：可以识别唯一的一个记录的关键字n n次关键字：能识别若干记录的关键字次关键字：能识别若干记录的关键字次关键字：能识别若干记录的关键字次关键字：能识别若干记录的关键字pp查找查找查找查找(Se
6、arching)(Searching)是根据给定的某个值，在查找表中确定一个其关键字等于给定是根据给定的某个值，在查找表中确定一个其关键字等于给定是根据给定的某个值，在查找表中确定一个其关键字等于给定是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。值的数据元素（或记录）。值的数据元素（或记录）。值的数据元素（或记录）。拍所奏炒翰炒虐面梢颂拯筛疟垣欺增邵那谓琴豺晚牲涅惧厂蚂颜蜕漓宵受数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.1 查找的基本概念p衡量查找算法的标准衡量查找算法的标准n n时间复杂度时间复杂度时间复杂度时间复杂度；n n空间复杂度空间
7、复杂度空间复杂度空间复杂度；n n平均查找长度平均查找长度平均查找长度平均查找长度ASLASLASLASL：定义为确定记录在表中的位置所进行的和关定义为确定记录在表中的位置所进行的和关键字比较的次数的平均值键字比较的次数的平均值 n n n n ASL = P ASL = P ASL = P ASL = 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个元
8、素时同给定值个元素时同给定值K K比较的次数比较的次数翰器骚掷乍捆诡日她晤棚溜消世躁些俯潘雷患捂雌篱槛酗挫割成湾掂寇涟数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.2 静态查找表9.2.1 顺序表的查找顺序表的查找顺序查找算法是顺序表（既无序表）的查找方法。在顺序查找算法顺序查找算法是顺序表（既无序表）的查找方法。在顺序查找算法中，以顺序表或线性链表表示静态查找表。中，以顺序表或线性链表表示静态查找表。p面临的问题面临的问题下标越界的检查，需要相当的时间和空间代价。解决的办法是，将下标越界的检查，需要相当的时间和空间代价。解决的办法是，将ST.elem0.key ST.elem
9、0.key 置为置为key,key,所有元素检查完还没有找到时，在所有元素检查完还没有找到时，在ST.elem0ST.elem0处一定找到。从而免去了检查下标越界的时间。处一定找到。从而免去了检查下标越界的时间。pp顺序查找算法顺序查找算法顺序查找算法顺序查找算法1.1.1.1.从表中从表中从表中从表中最后一个记录最后一个记录最后一个记录最后一个记录开始开始开始开始2.2.2.2.逐个进行记录的关键字和给定值的比较逐个进行记录的关键字和给定值的比较逐个进行记录的关键字和给定值的比较逐个进行记录的关键字和给定值的比较3.3.3.3.若某个记录比较相等，则查找成功若某个记录比较相等，则查找成功若某
10、个记录比较相等，则查找成功若某个记录比较相等，则查找成功4.4.4.4.若直到第若直到第若直到第若直到第1 1 1 1个记录都比较不等，则查找不成功个记录都比较不等，则查找不成功个记录都比较不等，则查找不成功个记录都比较不等，则查找不成功壕询化丢颂察胎立疏摩省遗矮锑邻蝇贱旦债蛇耍磋位蹄滑拜疵墓潦栋廖狮数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.2 静态查找表p顺序查找算法描述顺序查找算法描述uu设置设置设置设置“ “哨兵哨兵哨兵哨兵” ”的目的是省略对下标越界的检查，提高算法执行的目的是省略对下标越界的检查，提高算法执行的目的是省略对下标越界的检查，提高算法执行的目的是省略对
11、下标越界的检查，提高算法执行速度。当然，哨兵也可以设置在高下标处。速度。当然，哨兵也可以设置在高下标处。速度。当然，哨兵也可以设置在高下标处。速度。当然，哨兵也可以设置在高下标处。intSearch_Seq(SSTableST,KeyTypekey)intSearch_Seq(SSTableST,KeyTypekey)/若查找成功，返回位置若查找成功，返回位置若查找成功，返回位置若查找成功，返回位置ST.elem0.key=key;ST.elem0.key=key;/“/“哨兵哨兵哨兵哨兵” ”，for(i=ST.length;ST.elemi.key!=key;-i);for(i=ST.le
12、ngth;ST.elemi.key!=key;-i);/从后往前找从后往前找从后往前找从后往前找returni;returni;/找不到时找不到时找不到时找不到时,i=0,i=0 迄描粤逞瘩寇营射俊烤歉傍馏上资赋荆奉消销毙母罪玖惺鲜蠢每灾激特泡数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.2 静态查找表p顺序查找示举例顺序查找示举例在下列顺序表中寻找在下列顺序表中寻找6262，如果找到，给出其所在位置的下标。，如果找到，给出其所在位置的下标。监视哨兵监视哨兵i=11i=7, ,找到找到i=8i=9i=10比较次数比较次数=5比较次数分析：比较次数分析：查找第查找第n n个元素：
13、个元素： 1 1次次查找第查找第n-1n-1个元素：个元素： 2 2次次. .查找第查找第1 1个元素：个元素： n n次次查找第查找第i i个元素：个元素： n+1-i n+1-i次次查找失败：查找失败： n+1 n+1次次 0 1 2 3 4 5 6 7 8 9 10 1162513192137566275808892杀候造丈干憨惕照慕试碎常膨缘设固煮软刃立穆灌才前设那札烛扯讥凿鲜数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.2 静态查找表p顺序查找性能分析顺序查找性能分析n n对顺序表而言，对顺序表而言，对顺序表而言，对顺序表而言，C Ci i=n-i+1=n-i+1n
14、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如果被查找的记录概率不等时，如果被查找的记录概率不等时，如果被查找的记录概率不等时，如果被查找的记录概率不等时， ASL ASL ASL ASLssssssss在在在在 P P P Pn n n nPPPPn-1n-1n-1n-1 PPPP2 2 2 2P
15、PPP1 1 1 1 时取时取时取时取极小值极小值极小值极小值n n若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。找之后，将刚刚查找到的记录直接移至表尾的位置上。找之后，将刚刚查找到的记录直接移至表尾的位置上。找之后，将刚刚查找到的记录直接移至表尾的位置上。pp顺序查找特点顺序查找特点顺序查找特点顺序查找特点n n优点：优点：1.1.简单简单2.2.适应面
16、广适应面广( (对表的结构无任何要求对表的结构无任何要求) )n n缺点：缺点：1.1.平均查找长度较大平均查找长度较大2.2.特别是当特别是当n n很大时，查找效率很低很大时，查找效率很低讽答冬铡肄绷湃织烘囚诡毗枣团纺措齐霉虹跋蜒殴遮竭喊习呆该含郧坑严数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.2 静态查找表9.2.2折半查找折半查找折半查找算法是折半查找算法是有序表有序表的查找方法。在折半查找算法中，静态查找的查找方法。在折半查找算法中，静态查找表按关键字大小的次序，有序地存放在顺序表中。表按关键字大小的次序，有序地存放在顺序表中。pp折半查找的原理折半查找的原理1.1.
17、先确定待查记录所在的范围先确定待查记录所在的范围( (前部分或后部分前部分或后部分) )2.2.逐步缩小逐步缩小( (一半一半) )范围直到找范围直到找( (不不) )到该记录为止到该记录为止鸥捂浙右桐插患簿咖耽腮枢乾篆奄椿摔题奄陶桓粒盐颤糙袄理淤譬殿嚏谁数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.2 静态查找表p折半查找算法折半查找算法1.1.n n个对象从小到大存放在有序顺序表个对象从小到大存放在有序顺序表个对象从小到大存放在有序顺序表个对象从小到大存放在有序顺序表STST中中中中，k k为给定值为给定值为给定值为给定值2.2.2.2.设设设设lowlow、highhig
18、h指向待查元素所在区间的下界、上界，即指向待查元素所在区间的下界、上界，即指向待查元素所在区间的下界、上界，即指向待查元素所在区间的下界、上界，即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=STmid.keyk=STmid.key，查找成功，查找成功，查找成功，查找成功 若
19、若若若 kSTmid.keykSTmid.keykSTmid.key，则，则，则，则low=mid+1low=mid+1 下半区间下半区间下半区间下半区间 5.5.5.5.重复重复重复重复3,43,43,43,4操作，直至操作，直至操作，直至操作，直至lowhighlowhigh时，查找失败。时，查找失败。时，查找失败。时，查找失败。族惫敲码街土霓勋玻驳情因但寸迈延凭宝另裤档嘴吃橱工吾饰哦员赐逛绞数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.2 静态查找表p折半成功查找举例：在下列有序表中用折半查找法查找折半成功查找举例：在下列有序表中用折半查找法查找6262所在位置。所在位置
20、。Key = 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,找到！找到！62檀铣汝史擅裁希腺按娜蛋咬戊逗索氯釉凋析惶疽苯辣馏垦陇个颊戒理汕配数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.2 静态查找表p折半查找失败举例：在上例有序表中找折半查找失败举例：在上例有序表中找61。
21、1 2 3 4 5 6 7 8 9 10 11513192137566275808892high=6low=7找找61u 当下界当下界lowlow大于上界大于上界highhigh时，说明有序时，说明有序 表中没有关键字等于表中没有关键字等于K K的元素，查找失败的元素，查找失败赞枚喻血豫操凑守净硬律更棺模梦漾拙黎说咨事弹雁岭诧铝穆和列捉理热数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.2 静态查找表p折半查找的性能分析折半查找的性能分析折半查找过程可以用二叉树（也叫判定树）来描述：折半查找过程可以用二叉树（也叫判定树）来描述：折半查找过程可以用二叉树（也叫判定树）来描述：折半查
22、找过程可以用二叉树（也叫判定树）来描述：n判定树上每个结点需要的查找次数刚好为该结点所在的层数；判定树上每个结点需要的查找次数刚好为该结点所在的层数；n查找成功时查找次数不会超过判定树的深度查找成功时查找次数不会超过判定树的深度nn个结点的判定树的深度为个结点的判定树的深度为 log2n +1n比较次数最多不超过比较次数最多不超过 log2n +1n折半查找的算法复杂度为折半查找的算法复杂度为 log2n +13941756102118判定树判定树斧汝饿迎皇莫沪匆垫宗拔淋缠疾惯拆弯真崔僧挚报寻赌刻愤妖厘庶痰氢攒数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.2 静态查找表p折半查
23、找特点折半查找特点n n折半查找的效率比顺序查找高，特别是查找表的长度很长时；折半查找的效率比顺序查找高，特别是查找表的长度很长时；n n折半查找只能适用于等概率有序表，并且以顺序存储结构存储。折半查找只能适用于等概率有序表，并且以顺序存储结构存储。窟咀茨廖达酸撩硝矽需媚扮即超涨聘廊吮胸骸扁啤讳唤奉罗盈怠授忽冀漆数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.2 静态查找表9.2.3分块查找分块查找uu分块查找是一种索引顺序表分块查找是一种索引顺序表( (分块有序表分块有序表) )查找方法，是折半查查找方法，是折半查找和顺序查找的简单结合；找和顺序查找的简单结合；uu索引顺序表索
24、引顺序表( (分块有序表分块有序表) )将整个表分成几块，块内无序，块间将整个表分成几块，块内无序，块间有序有序uu所谓块间有序是指后一块表中所有记录的关键字均大于前一块所谓块间有序是指后一块表中所有记录的关键字均大于前一块表中的最大关键字表中的最大关键字皇孩售嘲遂屉小仑蚤摘挣竞横牟悸隋刁甜梁芍徒蜘谅忿夺仔咎团场妄傣芽数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.2 静态查找表p基本概念基本概念n n主表：用数组存放待查记录主表：用数组存放待查记录主表：用数组存放待查记录主表：用数组存放待查记录, , , ,每个数据元素至少含有关键字域每个数据元素至少含有关键字域每个数据元素至
25、少含有关键字域每个数据元素至少含有关键字域n n索引表：每个结点含有最大关键字域和指向本块第一个结点的索引表：每个结点含有最大关键字域和指向本块第一个结点的索引表：每个结点含有最大关键字域和指向本块第一个结点的索引表：每个结点含有最大关键字域和指向本块第一个结点的指针指针指针指针 1 2 3 4 5 6 7 8 9 10 11519132175566237888092211755929主表主表索引表索引表逮戍悔递得据蘸仰民避景距道问妮骂罗浊谈居帕俊畅马讹酶拥争牲喧砚葱数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.2 静态查找表p分块查找举例分块查找举例n n采用折半查找方法在索
26、引表中找到块（第采用折半查找方法在索引表中找到块（第采用折半查找方法在索引表中找到块（第采用折半查找方法在索引表中找到块（第2 2 2 2块）块）块）块）n n用顺序查找方法在主表对应块中找到记录（第用顺序查找方法在主表对应块中找到记录（第用顺序查找方法在主表对应块中找到记录（第用顺序查找方法在主表对应块中找到记录（第3 3 3 3个记录）个记录）个记录）个记录）1 2 3 4 5 6 7 8 9 10 11519132175566237888092211755929主表主表索引表索引表找找62栽泛磺父孟常蚊扦寅会兜辗胎绣燎孙隔秤硬喷煞文戴豆胯初郎结塞品峭楔数据结构第九章查找数据结构第九章查找
27、9- 中国科大数据结构9.2 静态查找表p分块查找性能分析分块查找性能分析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/2泄恤亥滇酪宾轮措釉洁诫离徘
28、狰燃动吝乞椿卓绕卖渴袱殃睛惮微癣今创箔数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p动态查找表动态查找表如果应用问题涉及的数据量很大，而且数据经常发生变化，如如果应用问题涉及的数据量很大，而且数据经常发生变化，如图书馆经常购进图书，每购进新书，需将新书记录插入图书表，对图书馆经常购进图书，每购进新书，需将新书记录插入图书表，对这类表除了提供前面的介绍的查找外，还要提供动态查找功能：这类表除了提供前面的介绍的查找外，还要提供动态查找功能：1.查找某个查找某个“特定特定”元素是否在表中，若不在，将该元素插入；元素是否在表中，若不在，将该元素插入；2.查找某个查找某个
29、“特定特定”元素是否在表中，若在，从表中删除；元素是否在表中，若在，从表中删除；p如何组织动态查找表？如何组织动态查找表？用静态查找方法不能满足要求了。本节介绍几种方法。用静态查找方法不能满足要求了。本节介绍几种方法。爵蚂追寿拧缠家廓孵筹摘熬哉蔼债骨祭南秩必磋沫差司雀实炊负野邮怪是数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表9.3.1 9.3.1 二叉排序树二叉排序树二叉排序树又称二叉查找树二叉排序树又称二叉查找树pp空树或者是具有如下特性的二叉树：空树或者是具有如下特性的二叉树：空树或者是具有如下特性的二叉树：空树或者是具有如下特性的二叉树：1.1.1.1.若
30、左子树不空，则左子树上所有结点的值均小于根结点的值；若左子树不空，则左子树上所有结点的值均小于根结点的值；若左子树不空，则左子树上所有结点的值均小于根结点的值；若左子树不空，则左子树上所有结点的值均小于根结点的值；2.2.2.2.若右子树不空，则右子树上所有结点的值均大于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值；3.3.3.3.左、右子树也都分别是二叉排序树。左、右子树也都分别是二叉排序树。左、右子树也都分别是二叉排序树。左、右子树也都分别是二叉排序树。21二叉排
31、序树二叉排序树非二叉排序树非二叉排序树56645923788198021137560566459237881980211375无三蚌甸严桶囚憨忆冕隆哗捣伸炮居唱厩搞烩歹拒膜她噪茄除砧狙验焕狗数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p二叉排序树查找算法二叉排序树查找算法 给定值与根结点比较：给定值与根结点比较：给定值与根结点比较：给定值与根结点比较：1.1.1.1.若相等，查找成功若相等，查找成功若相等，查找成功若相等，查找成功2.2.2.2.若小于，查找左子树若小于，查找左子树若小于，查找左子树若小于，查找左子树3.3.3.3.若大于，查找右子树若大于，查找
32、右子树若大于，查找右子树若大于，查找右子树566459237881980211375例例1：在右图二叉排序树中查找关键字值等于：在右图二叉排序树中查找关键字值等于3737找到找到例例2：在右图二叉排序树中查找关键字值等于：在右图二叉排序树中查找关键字值等于88找到找到例例3：在右图二叉排序树中查找关键字值等于：在右图二叉排序树中查找关键字值等于94无此数无此数党参硼赢漓浦赊仟戚渔瘪芦敦贬矣篱尸媒执搂陨澈烂淬甄篙列富望鉴铣惑数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p二叉排序树插入二叉排序树插入二叉排序树是一种动态树表。二叉排序树是一种动态树表。二叉排序树是一种
33、动态树表。二叉排序树是一种动态树表。n n当树中不存在查找的结点时，作插入操作当树中不存在查找的结点时，作插入操作当树中不存在查找的结点时，作插入操作当树中不存在查找的结点时，作插入操作n n新插入的结点一定是叶子结点（只需改动一个结点的指针）新插入的结点一定是叶子结点（只需改动一个结点的指针）新插入的结点一定是叶子结点（只需改动一个结点的指针）新插入的结点一定是叶子结点（只需改动一个结点的指针）n n该叶子结点是查找不成功时路径上访问的最后一个结点左孩子该叶子结点是查找不成功时路径上访问的最后一个结点左孩子该叶子结点是查找不成功时路径上访问的最后一个结点左孩子该叶子结点是查找不成功时路径上访
34、问的最后一个结点左孩子或右孩子或右孩子或右孩子或右孩子( ( ( (新结点值小于或大于该结点值新结点值小于或大于该结点值新结点值小于或大于该结点值新结点值小于或大于该结点值) ) ) )566459237881980211375例：在右图二叉树中插入结点例：在右图二叉树中插入结点例：在右图二叉树中插入结点例：在右图二叉树中插入结点9494。94快匝痘盗奉胸尾穗吕潍艰集缘啤友轰档于沦妻闰鳞僳脑貉绿帘栖苗腮态锣数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p二叉排序树生成二叉排序树生成例：画出在初始为空的二叉排序树中依次插入例：画出在初始为空的二叉排序树中依次插入56
35、,64,92,80,88,7556,64,92,80,88,75时该树的生长全过程时该树的生长全过程566492888075篇劣缉襟溪锰尖没耍湍察稽史典鬃瘴篱沧洱拱纷死霜缄豪灌卡如形缨舟影数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p二叉排序树中序遍历二叉排序树中序遍历中序遍历二叉排序树，可得到一个关键字的有序序列中序遍历二叉排序树，可得到一个关键字的有序序列, ,如如5,13,19,21,37,56,64,92,75,80,885,13,19,21,37,56,64,92,75,80,88566459237881980211375盯苍甚翠献吠碟徽樟赁亢蠢犊吴窗
36、刚诵愤遍赌敢屿迎润房第范萧凿拷等溶数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p二叉排序树删除二叉排序树删除删除二叉排序树中的一个结点后，必须保持二叉排序树的特性：删除二叉排序树中的一个结点后，必须保持二叉排序树的特性：左子树的所有结点值小于根结点，右子树的所有结点值大于根结点。左子树的所有结点值小于根结点，右子树的所有结点值大于根结点。也即保持中序遍历后，输出为有序序列也即保持中序遍历后，输出为有序序列pp被删除结点具有以下三种情况被删除结点具有以下三种情况被删除结点具有以下三种情况被删除结点具有以下三种情况1.1.1.1.是叶子结点是叶子结点是叶子结点是叶子
37、结点2.2.2.2.只有左子树或右子树只有左子树或右子树只有左子树或右子树只有左子树或右子树3.3.3.3.同时有左、右子树同时有左、右子树同时有左、右子树同时有左、右子树pp下面针对三种情况各举一例。下面针对三种情况各举一例。下面针对三种情况各举一例。下面针对三种情况各举一例。拒羡诬寞阀榴烤垄腆拈百刻碳卫狂轨怨练峻凑玄阔嚣馁好枪燥乳壕晕冶瘟数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表pp被删除结点是叶子结点：直接删除结点，并让其父结点指向该结点被删除结点是叶子结点：直接删除结点，并让其父结点指向该结点的指针变为空。的指针变为空。pp例：删除右二叉例：删除右二叉
38、排序排序排序排序树中的树中的8888节点节点566459237881980211375衍宅拥输销郑泛书习并狐缨赊驻驰溯辅喊茁胎腆名幼驱涩算寸瞅腕枚观劝数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p被删除结点只有左子树或右子树被删除结点只有左子树或右子树删除结点删除结点, ,让其父结点指向该结点的指针指向其左子树让其父结点指向该结点的指针指向其左子树( (或右子树或右子树),),即用孩子结点替代被删除结点即可即用孩子结点替代被删除结点即可p例：对于右边二叉例：对于右边二叉排序排序树中，先删除节点树中，先删除节点3737，再删除节点，再删除节点6464。566453
39、719211392888075壕歇孜锨粒寂螟乏病葵渣磐着连游楔壕酥舷篆郊骇菱快巳兜罐辜卫簇侈柠数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p被删除结点被删除结点p p既有左子树，又有右子树既有左子树，又有右子树以中序遍历时的直接前驱以中序遍历时的直接前驱s s替代被删除结点替代被删除结点p p，然后再按照前面介绍，然后再按照前面介绍的发删除该直接前驱的发删除该直接前驱s s（只可能有左孩子）（只可能有左孩子）566459237888019211375例：在右边二叉排序树中例：在右边二叉排序树中例：在右边二叉排序树中例：在右边二叉排序树中, ,节点节点节点节点56
40、56的中序遍历的直接前趋是节点的中序遍历的直接前趋是节点的中序遍历的直接前趋是节点的中序遍历的直接前趋是节点3737。阜当冠徽案熔掏苯臂镣假屹财兴颗册辖页瞥屁第伏臂羌混扑福哨坑达酗钝数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p二叉排序树性能分析二叉排序树性能分析n在最好的情况下，二叉排序树在最好的情况下，二叉排序树为一近似完全二叉树时，其查为一近似完全二叉树时，其查找深度为找深度为loglog2 2n n量级，即其时量级，即其时间复杂性为间复杂性为O(logO(log2 2n)n)n在最坏的情况下，二叉排序树在最坏的情况下，二叉排序树为近似线性表时为近似线性表
41、时( (如以升序或如以升序或降序输入结点时，见右图降序输入结点时，见右图) )，其查找深度为其查找深度为n n量级，即其时量级，即其时间复杂性为间复杂性为O(n)O(n)808892647521191356375辐哑蕊惋猜解矿剖行地奄络矢校冲航轮汐喜颂插莉塌感总本俗县篓兔般涂数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p二叉排序树特性二叉排序树特性n n一个无序序列可以通过构造一棵二叉排序一个无序序列可以通过构造一棵二叉排序一个无序序列可以通过构造一棵二叉排序一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列（通过中序遍历）树而变成一个有序序列（通过中序遍
42、历）树而变成一个有序序列（通过中序遍历）树而变成一个有序序列（通过中序遍历）n n插入新记录时，只需改变一个结点的指针，插入新记录时，只需改变一个结点的指针，插入新记录时，只需改变一个结点的指针，插入新记录时，只需改变一个结点的指针，相当于在有序序列中插入一个记录而不需相当于在有序序列中插入一个记录而不需相当于在有序序列中插入一个记录而不需相当于在有序序列中插入一个记录而不需要移动其它记录要移动其它记录要移动其它记录要移动其它记录n n二叉排序树既拥有类似于折半查找的特性，二叉排序树既拥有类似于折半查找的特性，二叉排序树既拥有类似于折半查找的特性，二叉排序树既拥有类似于折半查找的特性，又采用了
43、链表作存储结构又采用了链表作存储结构又采用了链表作存储结构又采用了链表作存储结构n n但当插入记录的次序不当时但当插入记录的次序不当时( (如升序或降如升序或降序序) )，则二叉排序树深度很深（见右图），则二叉排序树深度很深（见右图），增加了查找的时间增加了查找的时间808892647521191356375长诡此售嗅墨纲测本采塌闰喜殊辆撩拽芜膛酪扒摸册狂哎姐删僧滥宾消缎数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p平衡二叉树平衡二叉树平衡二叉树平衡二叉树(BalancedBinaryTree,Height-BalancedTree, ,又称又称AVLAVL树树
44、, ,Adelsen-VelskiiandLandis，阿德尔森一维尔斯和兰阿德尔森一维尔斯和兰迪斯迪斯) )是二叉排序树的另一种形式。其特点为：树中每个结点的左、是二叉排序树的另一种形式。其特点为：树中每个结点的左、右子树深度之差的绝对值不大于右子树深度之差的绝对值不大于1 1，即，即|hL-hR|1。可以证明，它们。可以证明，它们的深度和的深度和lognlogn是同数量级的（其中是同数量级的（其中n n为节点个数）。为节点个数）。56645923788198021137560565641913753780928821AVLAVL树树非非AVLAVL树树巩喘哑踪砸粱论些须似昼踢鳞豪较亭过西聘
45、佰测犀恿岁汽础婚畔捞舜掇磺数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p平衡二叉树平衡因子平衡二叉树平衡因子n n每个结点附加一个数字每个结点附加一个数字每个结点附加一个数字每个结点附加一个数字, , , , 给出该结点左子树的高度减去右子树给出该结点左子树的高度减去右子树给出该结点左子树的高度减去右子树给出该结点左子树的高度减去右子树的高度所得的高度差的高度所得的高度差的高度所得的高度差的高度所得的高度差, , , ,这个数字即为结点的平衡因子这个数字即为结点的平衡因子这个数字即为结点的平衡因子这个数字即为结点的平衡因子(balance (balance (b
46、alance (balance factor)factor)factor)factor)n nAVLAVLAVLAVL树任一结点平衡因子只能取树任一结点平衡因子只能取树任一结点平衡因子只能取树任一结点平衡因子只能取 -1, 0, 1 -1, 0, 1 -1, 0, 1 -1, 0, 1n n若某个结点的平衡因子的绝对值大于若某个结点的平衡因子的绝对值大于若某个结点的平衡因子的绝对值大于若某个结点的平衡因子的绝对值大于1 1 1 1，则这棵二叉搜索树就失，则这棵二叉搜索树就失，则这棵二叉搜索树就失，则这棵二叉搜索树就失去了平衡，不再是去了平衡，不再是去了平衡，不再是去了平衡，不再是AVLAVLA
47、VLAVL树。树。树。树。56564191375378092882100-10-1000100吓蔽殷旁桅胶召惟胀文垮翁梁莫祈缕滥夹怀葬琳苟凉蓬速亨喻抱韶辟可柞数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p非平衡二叉树的平衡处理非平衡二叉树的平衡处理若一棵二叉排序树是平衡二叉树，扦入某个结点后，可能会变若一棵二叉排序树是平衡二叉树，扦入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。成一棵平衡二叉树。处理的原则应该是处理与插入点最近的、而平衡因子又比处理的原则
48、应该是处理与插入点最近的、而平衡因子又比1大大或比或比-1小的结点。下面将分四种情况讨论平衡处理。小的结点。下面将分四种情况讨论平衡处理。蛆抑缓乡屁诸靡辈袜利脐奈竟毅毒肌坪晌奎湃醒挫执偏硼毅埃宽僚涪扩欠数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表1.1.1.1.LLLLLLLL型型型型 的处理的处理的处理的处理( ( ( (左左型左左型左左型左左型) ) ) )n n如下图所示，若在如下图所示，若在如下图所示，若在如下图所示，若在C C C C的左孩子的左孩子的左孩子的左孩子B B B B上扦入一个左孩子结点上扦入一个左孩子结点上扦入一个左孩子结点上扦入一个左孩
49、子结点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的左子树，待扦入结点的左子树，待扦入结点的左子树，待
50、扦入结点的左子树，待扦入结点A A A A作为作为作为作为B B B B的左子树。的左子树。的左子树。的左子树。CBA210CBA000结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该 结点的平衡因子结点的平衡因子结点的平衡因子结点的平衡因子兹搓搜妨虐豢丙室世掂访线仇备艾枚蝶鄙姑甭育宠姿怠鳖辣司磊仕孙馒饺数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表2.LR型的处理型的处理(左右型左右型)n如下图所示，在如下图所示，在C的左孩子的左孩子A上扦入一个右孩子上扦入一个右孩子B，使的，使的C的平的平衡因子由衡因子由1变成了变成了2，成为不
51、平衡的二叉排序树。，成为不平衡的二叉排序树。n平衡处理：将平衡处理：将B变到变到A与与C之间，使之成为之间，使之成为LL型，然后按第型，然后按第1种种情形情形LL型处理。型处理。CBA210CBA000CBA2-10结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该 结点的平衡因子结点的平衡因子结点的平衡因子结点的平衡因子销沟哉戌叠顶抒漠髓犊临籽禹猖我般阵啊至羹爆脾衣典舀捷展媳帚建捻鬃数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表3.RR型的处理型的处理(右右型右右型)n如下图所示，在如下图所示，在A的右孩子的右孩子B上扦入一个右孩子
52、上扦入一个右孩子C，使，使A的平衡的平衡因子由因子由-1变成变成-2，成为不平衡的二叉排序树。，成为不平衡的二叉排序树。n平衡处理：将平衡处理：将A逆时针旋转，成为逆时针旋转，成为B的左子树，而原来的左子树，而原来B的左子的左子树则变成树则变成A的右子树，待扦入结点的右子树，待扦入结点C成为成为B的右子树。的右子树。CBA-2-10CBA000结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该 结点的平衡因子结点的平衡因子结点的平衡因子结点的平衡因子衰阀崭唤婚洗海速踏副叹澎派侮食狱舌厨户畴奴遇懦杰惟瞪贪堂呐南眯瑟数据结构第九章查找数据结构第九章查找9- 中国科大数
53、据结构9.3 动态查找表4.RL型的处理型的处理(右左型右左型)n如下图所示，在如下图所示，在A的右孩子的右孩子C上扦入一个左孩子上扦入一个左孩子B，使，使A的平衡的平衡因子由因子由-1变成变成-2，成为不平衡的二叉排序树。，成为不平衡的二叉排序树。n平衡处理：将平衡处理：将B变到变到A与与C之间，使之成为之间，使之成为RR型，然后按第型，然后按第(3)种情形种情形RR型处理。型处理。CBA-2-10CBA000结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该结点旁边的数字表示该 结点的平衡因子结点的平衡因子结点的平衡因子结点的平衡因子ACB-210禹瀑骤价稚少淋郝抄白菜何帚留谱迹
54、瞄变慑恕窝潞墨镇窗苛氓采譬筛缴材数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p例例1：给定一个关键字序列：给定一个关键字序列4,5,7,2,1,3,6，试生成一棵平衡二叉树。，试生成一棵平衡二叉树。p分析：平衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树分析：平衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，最的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。具体生成过程见下图。后就可以建成一棵平衡二叉树。具体生成过程见下图。40a)插入插入
55、4，平衡，平衡4-1b) 插入插入5，平衡，平衡50c) 插入插入7，不平衡，要处理，不平衡，要处理4-25-170405070RR型处理型处理篡催日堂立杏坐逐握夏符攀藤队呈死俩吊昂赫粒油剐琳奠瞄殊钒侧政坎虎数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表405170d) 插入插入7，平衡，平衡2141527022e) 插入插入1，不平衡，要处理，不平衡，要处理104050702010LL型处理型处理4052702-111f) 插入插入3，不平衡，要处理，不平衡，要处理30LR型处理型处理30405-1201070酵歹学严坏寨波复顿阑嘱绥育牙胶豆昔电烙苔铸蒙韦逮洛殃
56、稀踩下榜剐盯数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表304-15-2201071f) 插入插入6，不平衡，要处理，不平衡，要处理06RL型处理型处理30406020107050贬辣账雄恿箭粮嘴语屹疗络唁芝膨刑刑咖慎并源邮帅籽景智芍寝皋降苗尝数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p平衡二叉树的查找及性能分析平衡二叉树的查找及性能分析平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找树完全相同。但它的查找性能优于二叉排序树，不像二叉排序树一性能优
57、于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二叉排序树，它的时间复杂度与二叉排序树的最好时间复杂相同，都为的最好时间复杂相同，都为O(log2n)。酿尔吟耕勿硕盲茶倘嗣郧懈渔引丘虐呆责预怂铡伸勇侗亲莽蹭传摈超卜亏数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.3 动态查找表p例例2，对例，对例1给定的关键字序列给定的关键字序列4,5,7,2,1,3,6，试用二叉排序树和平，试用二叉排序树和平衡二叉树两种方法查找，给出查找衡二叉树两种方法查找，给出查找6的次数及成功的平均查找长度。的次数及成功的平均查找长度。p分析：由
58、于关键字序列的顺序己经确定，故得到的二叉排序树和平分析：由于关键字序列的顺序己经确定，故得到的二叉排序树和平衡二叉树都是唯一的。得到的平衡二叉树见下座图，得到的二叉排衡二叉树都是唯一的。得到的平衡二叉树见下座图，得到的二叉排序树见下右图。序树见下右图。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从左图的平衡二叉树可知，查找从左图的平衡二叉树可知，查找
59、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.1 哈希表哈希表哈希哈希(Hash)表又称散列表表又称散列表, ,是一种直接计算记录存放地址的方是一种直接计算记录存放地址的方法，它在关键码与存储位置之间直接建立了映象。法，它在关键码与存储位置之间直接
60、建立了映象。pp哈希哈希哈希哈希函数函数函数函数n n哈希函数是从关键字空间到存储地址空间的一种映象哈希函数是从关键字空间到存储地址空间的一种映象哈希函数是从关键字空间到存储地址空间的一种映象哈希函数是从关键字空间到存储地址空间的一种映象n n哈希函数在记录的关键字与记录的存储地址之间建立起一种对哈希函数在记录的关键字与记录的存储地址之间建立起一种对哈希函数在记录的关键字与记录的存储地址之间建立起一种对哈希函数在记录的关键字与记录的存储地址之间建立起一种对应关系。可写成：应关系。可写成：应关系。可写成：应关系。可写成：addr(aaddr(ai i)=H(key)=H(keyi i) )n n
61、H()H()为哈希函数为哈希函数为哈希函数为哈希函数n nkeykeyi i是表中元素是表中元素是表中元素是表中元素a ai i关键字关键字关键字关键字, , , ,addr(aaddr(ai i) )是存储地址是存储地址是存储地址是存储地址唁亥劈亥升涸春痴马榔挨腋钝衷随榜朝自旨仑晃舔储铜群阎驴鹅尧喻板觉数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表p哈希查找哈希查找n哈希查找也叫散列查找，是利用哈希函数进行查找的过程哈希查找也叫散列查找，是利用哈希函数进行查找的过程n首先利用哈希函数及记录的关键字计算出记录的存储地址首先利用哈希函数及记录的关键字计算出记录的存储地址
62、n然后直接到指定地址进行查找然后直接到指定地址进行查找n不需要经过比较，一次存取就能得到所查元素不需要经过比较，一次存取就能得到所查元素pp哈希冲突哈希冲突哈希冲突哈希冲突n n不同的记录，其关键字通过哈希函数的计算，可能得到相同的不同的记录，其关键字通过哈希函数的计算，可能得到相同的不同的记录，其关键字通过哈希函数的计算，可能得到相同的不同的记录，其关键字通过哈希函数的计算，可能得到相同的地址地址地址地址n n把不同的记录映射到同一个散列地址上，这种现象称为冲突把不同的记录映射到同一个散列地址上，这种现象称为冲突把不同的记录映射到同一个散列地址上，这种现象称为冲突把不同的记录映射到同一个散列
63、地址上，这种现象称为冲突灼曼谎缺绢匆件诞语杖邮胯妆往涝窃殿逾崎药枢杠奋抿渔卑哮霸般砖线雾数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表p哈希表定义哈希表定义n根据设定的哈希函数根据设定的哈希函数 H(key) H(key) 和所选中的处理冲突的方法和所选中的处理冲突的方法n将一组关键字映象到一个有限的、地址连续的地址集上将一组关键字映象到一个有限的、地址连续的地址集上n以关键字在地址集中的以关键字在地址集中的“象象”作为相应记录在表中的存储位置作为相应记录在表中的存储位置n如此构造所得的查找表称之为如此构造所得的查找表称之为“哈希表哈希表”。pp哈希函数均匀性哈希函数
64、均匀性哈希函数均匀性哈希函数均匀性n n哈希函数实现的一般是从一个大的集合（部分元素，空间位置哈希函数实现的一般是从一个大的集合（部分元素，空间位置哈希函数实现的一般是从一个大的集合（部分元素，空间位置哈希函数实现的一般是从一个大的集合（部分元素，空间位置上一般不连续）到一个小的集合（空间连续）的映射上一般不连续）到一个小的集合（空间连续）的映射上一般不连续）到一个小的集合（空间连续）的映射上一般不连续）到一个小的集合（空间连续）的映射n n一个好的哈希函数，对于记录中的任何关键字，将其映射到地一个好的哈希函数，对于记录中的任何关键字，将其映射到地一个好的哈希函数，对于记录中的任何关键字，将其
65、映射到地一个好的哈希函数，对于记录中的任何关键字，将其映射到地址集合中任何一个地址的概率应该是相等的址集合中任何一个地址的概率应该是相等的址集合中任何一个地址的概率应该是相等的址集合中任何一个地址的概率应该是相等的n n即关键字经过哈希函数得到一个即关键字经过哈希函数得到一个即关键字经过哈希函数得到一个即关键字经过哈希函数得到一个“随机的地址随机的地址随机的地址随机的地址”怪肯瓷谦纂蔚歌屏笋侧娜未欣署午肌云寇哈问调氟蛾己递励权柬胁书午椒数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表9.4.2哈希函数哈希函数pp要求要求要求要求n n哈希函数应是简单的，能在较短的时间内
66、计算出结果哈希函数应是简单的，能在较短的时间内计算出结果哈希函数应是简单的，能在较短的时间内计算出结果哈希函数应是简单的，能在较短的时间内计算出结果n n哈希函数的定义域必须包括需要存储的全部关键字，如果散列哈希函数的定义域必须包括需要存储的全部关键字，如果散列哈希函数的定义域必须包括需要存储的全部关键字，如果散列哈希函数的定义域必须包括需要存储的全部关键字，如果散列表允许有表允许有表允许有表允许有 m m m m 个地址时，其值域必须在个地址时，其值域必须在个地址时，其值域必须在个地址时，其值域必须在 0 0 0 0 到到到到 m-1 m-1 m-1 m-1 之间之间之间之间 n n散列函数
67、计算出来的地址应能均匀分布在整个地址空间中散列函数计算出来的地址应能均匀分布在整个地址空间中散列函数计算出来的地址应能均匀分布在整个地址空间中散列函数计算出来的地址应能均匀分布在整个地址空间中喷活绝淬蹿咆鬼堡扒谁灸筐匙啸箭伺蛆廊眯缘裴选配掐盾温泊影舅剃处楷数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表p哈希函数哈希函数( (直接定址法直接定址法) )n n直接定址法中，哈希函数取关键字的线性函数直接定址法中，哈希函数取关键字的线性函数直接定址法中，哈希函数取关键字的线性函数直接定址法中，哈希函数取关键字的线性函数 H(key)=akey+bH(key)=akey+b其
68、中其中其中其中a a a a和和和和b b b b为常数为常数为常数为常数pp直接定址法举例直接定址法举例直接定址法举例直接定址法举例H(key)=key-2005131000H(key)=key-20051310000032005131003朱嘉成朱嘉成男男网络学院网络学院0052005131005陈乾陈乾男男网络学院网络学院0062005131006桂许升桂许升男男网络学院网络学院0072005131007罗杨洋罗杨洋男男网络学院网络学院0082005131008叶建行叶建行男男网络学院网络学院0092005131009曹亚仑曹亚仑男男网络学院网络学院0122005131012欧东欧东男男
69、网络学院网络学院寨熬口菩耐沁排寄邦俞缚济哺玻犀次汇材坦仍补邑啥赛盗渭垛再衍寒埔湍数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表p直接定址法特性直接定址法特性n直接定址法仅适合于地址集合的大小与关键字集合的大小相等直接定址法仅适合于地址集合的大小与关键字集合的大小相等的情况的情况n当当a=1a=1时，时，H(key)=keyH(key)=key，即用关键字作地址，即用关键字作地址n在实际应用中能使用这种哈希函数的情况很少在实际应用中能使用这种哈希函数的情况很少惊攫鉴疏噶鳃骆皖扫由绢假型浓咨籽盼敢议蚀恕岔锄穿由耐杉坝翔憋控舞数据结构第九章查找数据结构第九章查找9- 中国科
70、大数据结构9.4 哈希表p哈希函数哈希函数( (数字分析法数字分析法) )n n假设关键字集合中的每个关键字都是由假设关键字集合中的每个关键字都是由假设关键字集合中的每个关键字都是由假设关键字集合中的每个关键字都是由 s s s s 位数字组成位数字组成位数字组成位数字组成 (u(u1 1,u,u2 2, ,u,us s) )n n分析关键字集中的全体分析关键字集中的全体分析关键字集中的全体分析关键字集中的全体n n从中提取从中提取从中提取从中提取分布均匀分布均匀分布均匀分布均匀的若干位或它们的组合作为地址。的若干位或它们的组合作为地址。的若干位或它们的组合作为地址。的若干位或它们的组合作为地
71、址。惶玄央涸含拴想眨坟阳械慎珐胀梨豺生容是裤聊腆颖赴钓哗垫绩阳戌央狄数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表p数字分析法举例数字分析法举例有有8080个记录，关键字为个记录，关键字为8 8位十进制数，哈希地址为位十进制数，哈希地址为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
72、 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 哈希表p数字分析法特性数字分析法特性n数字分析法仅适用于事先明确知道表
73、中所有关键码每一位数值数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况的分布情况n数字分析法完全依赖于关键码集合。数字分析法完全依赖于关键码集合。n如果换一个关键码集合，选择哪几位要重新决定。如果换一个关键码集合，选择哪几位要重新决定。鲸俐牡烛泪吐涡鸟舅氛中臃箩酮皖歇咕痢怒青密阐呸虾共鸣莱旭凡棚埋蒂数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表p哈希函数哈希函数( (平方取中法平方取中法) )以关键字的平方值的中间几位作为存储地址。以关键字的平方值的中间几位作为存储地址。n n求求求求“关键字的平方值关键字的平方值关键字的平方值关键字的平方值” 的目的
74、是的目的是的目的是的目的是“扩大差别扩大差别扩大差别扩大差别” n n同时平方值的中间各位又能受到整个关键字中各位的影响。同时平方值的中间各位又能受到整个关键字中各位的影响。同时平方值的中间各位又能受到整个关键字中各位的影响。同时平方值的中间各位又能受到整个关键字中各位的影响。差吗坊鹃翻潦苗保雨叫曼汪梢嘘绒逸钩效搪竹菩浴简签谊咬萝博匙膏米队数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表p平方取中法举例平方取中法举例此方法在词典处理中使用十分广泛。它先计算构成关键码的标此方法在词典处理中使用十分广泛。它先计算构成关键码的标识符的内码的平方识符的内码的平方, , 然后按照
75、散列表的大小取中间的若干位作为散然后按照散列表的大小取中间的若干位作为散列地址。列地址。p标识符的八进制内码表示及其平方值标识符的八进制内码表示及其平方值标识符标识符标识符标识符内码内码内码内码 内码的平方内码的平方内码的平方内码的平方 散列地址散列地址散列地址散列地址A A0101 0101001001A A1 1013401342 20420420 0042042B B02024 4004004DMAXDMAX04150130041501302152621526443443617100617100443443DMAXDMAX1104150130340415013034 5264475264
76、4735235221514202151420352352AMAX AMAX 0115013001150130135413542362361710017100236236AMAXAMAX1101150130340115013034 34542434542465265221514202151420652652弘方渣加型助蹭情珍灶想汾存汁都魁矫脱驶遏戮糊爽澳浊丸柿臀蓉凡氨垦数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表p平方取中法特性平方取中法特性n平方取中法是较常用的构造哈希函数的方法平方取中法是较常用的构造哈希函数的方法n适合于关键字中的每一位都有某些数字重复出现且频度
77、很高的适合于关键字中的每一位都有某些数字重复出现且频度很高的情况情况n中间所取的位数，由哈希表长决定中间所取的位数，由哈希表长决定滁肉拽崔扭疚懦铡特典期浸筛冤除咏枣鱼目亏建港追涨时虑边瘴哨插盯普数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表p哈希函数哈希函数( (折叠法折叠法) )将关键字分割成位数相同的若干部分将关键字分割成位数相同的若干部分将关键字分割成位数相同的若干部分将关键字分割成位数相同的若干部分( ( ( (最后部分的位数可以不最后部分的位数可以不最后部分的位数可以不最后部分的位数可以不同同同同) ) ) )，然后取它们的叠加和，然后取它们的叠加和，然后取
78、它们的叠加和，然后取它们的叠加和( ( ( (舍去进位舍去进位舍去进位舍去进位) ) ) )为哈希地址。为哈希地址。为哈希地址。为哈希地址。n n移位叠加移位叠加移位叠加移位叠加: : : :将分割后的几部分低位对齐相加将分割后的几部分低位对齐相加将分割后的几部分低位对齐相加将分割后的几部分低位对齐相加n n间界叠加间界叠加间界叠加间界叠加: : : :从一端沿分割界来回折送，然后对齐相加从一端沿分割界来回折送，然后对齐相加从一端沿分割界来回折送，然后对齐相加从一端沿分割界来回折送，然后对齐相加郸齐级门付课裤澳枷流耐汗锨掺哼途倪馒睡瓷拴鸽禾躇揉类禽编辖尊囤从数据结构第九章查找数据结构第九章查找
79、9- 中国科大数据结构9.4 哈希表p折叠法举例：关键字为：折叠法举例：关键字为：04422058640442205864，哈希地址位数为，哈希地址位数为4 4p折叠法特性折叠法特性折叠法适合于关键字的数字位数特别多，而且每一位上数字分折叠法适合于关键字的数字位数特别多，而且每一位上数字分布大致均匀的情况布大致均匀的情况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间界叠加间界叠加猫咒龚睡俊股和拙棘回恭腕伸蹬洞骇诌汲媚桃赘蛔口烤歼钎揭蝗姜成站装数据结构第九章查找数据结构第九章查找
80、9- 中国科大数据结构9.4 哈希表p哈希函数哈希函数( (除留余数法除留余数法) )取关键字被某个不大于哈希表长取关键字被某个不大于哈希表长取关键字被某个不大于哈希表长取关键字被某个不大于哈希表长m m m m的数的数的数的数p p p p除后所得余数为哈希地址除后所得余数为哈希地址除后所得余数为哈希地址除后所得余数为哈希地址H(key) = key MOD p ( pm )H(key) = key MOD p ( pm )H(key) = key MOD p ( pm )H(key) = key MOD p ( pm )n nm m m m为表长为表长为表长为表长 n np p p p为不
81、大于为不大于为不大于为不大于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, 则他们对应的则他们对应的则他们
82、对应的则他们对应的哈希函数值将为哈希函数值将为哈希函数值将为哈希函数值将为: : : : 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 的的的的倍数倍数倍数倍数”的地址上，从而增加了的地址上，从而增加了的地址上，从而增加了的地址上，从而增加了“冲突冲突冲突
83、冲突”的可能的可能的可能的可能pp除留余数法特性除留余数法特性除留余数法特性除留余数法特性n n除留余数法是一种最简单、最常用的构造哈希函数的方法除留余数法是一种最简单、最常用的构造哈希函数的方法除留余数法是一种最简单、最常用的构造哈希函数的方法除留余数法是一种最简单、最常用的构造哈希函数的方法n n可以对关键字直接取模可以对关键字直接取模可以对关键字直接取模可以对关键字直接取模(MOD)(MOD)(MOD)(MOD)，也可在折叠、平方取中等运算之后取模。，也可在折叠、平方取中等运算之后取模。，也可在折叠、平方取中等运算之后取模。，也可在折叠、平方取中等运算之后取模。捅沦峨样犁三委茫里残傻褪觉
84、雅缓青含训惦狄休勺跃沙圈豹瓜叛立构仗虱数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表9.4.3处理冲突法处理冲突法“处理冲突处理冲突” 的实际含义是：为产生冲突的地址寻找下一个的实际含义是：为产生冲突的地址寻找下一个哈希地址。处理冲突的方法主要有三种：哈希地址。处理冲突的方法主要有三种：1.1.1.1.开放定址法开放定址法开放定址法开放定址法2.2.2.2.再哈希法再哈希法再哈希法再哈希法3.3.3.3.链地址法链地址法链地址法链地址法跌梯脊于艘她钳摩罐蔚剐陵强犀启橇淄笼取勇啡冷姓占帽凹松虞镍昌描膘数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希
85、表p处理冲突的方法处理冲突的方法(开放定址法开放定址法)为产生冲突的地址为产生冲突的地址为产生冲突的地址为产生冲突的地址 H(key) H(key) H(key) H(key) 求得一个空的地址序列求得一个空的地址序列求得一个空的地址序列求得一个空的地址序列：H H0 0,H,H1 1, ,H H2 2,H,Hs s，1sm-11sm-1H Hi i=H(key)+d=H(key)+di iMODm(i=1,2,s)MODm(i=1,2,s)n nH(key)H(key)为哈希函数为哈希函数为哈希函数为哈希函数n nm m m m为哈希表长为哈希表长为哈希表长为哈希表长n n当当当当d d d
86、 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- 中国科大数据结构p举例：在长度为举例：在长度为1111的哈希表中已填有关键字分别为的哈希表中已填有关键字分别为1717，6060和和2929的记的记录（哈希函数录（哈希函数H(key)H(key) key MOD 11 key MOD 1
87、1），现有第四个记录，其关键），现有第四个记录，其关键字为字为3838，由哈希函数得到的哈希地址为，由哈希函数得到的哈希地址为5 5，产生冲突。，产生冲突。n线性探测再散列：得到下一个地址线性探测再散列：得到下一个地址6 6，仍冲突；再求下一个地址，仍冲突；再求下一个地址7 7，仍冲突；直到哈希地址为，仍冲突；直到哈希地址为8 8的位置（的位置（“空空”）时止。）时止。n二次探测再散列：应填入序号为二次探测再散列：应填入序号为4 4的位置。的位置。n伪随机探测再散列：伪随机数列伪随机探测再散列：伪随机数列9, 9, 应填入序号为应填入序号为2 2的位置。的位置。 9.4 哈希表瓢堵巩枪弗吵峙诺
88、酮崩七扩调契诀宠步像拆皆锦俺僵塌复携澎歹围妇轻蛹数据结构第九章查找数据结构第九章查找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
89、- 中国科大数据结构9.4 哈希表p处理冲突的方法处理冲突的方法( (再哈希法再哈希法) )H H H Hi i i i = RH = RH = RH = RHi 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均是不同的哈希函数，即在同义词产生地址冲突时计算另均是不同的哈希函数，即在同义词产生地址冲突时计算另均是不同的哈希函数，即在同义词产生地址冲突时计算另均是不同的
90、哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。一个哈希函数地址，直到冲突不再发生。一个哈希函数地址，直到冲突不再发生。一个哈希函数地址，直到冲突不再发生。n n再哈希法特点：不易产生聚集，但增加计算时间再哈希法特点：不易产生聚集，但增加计算时间再哈希法特点：不易产生聚集，但增加计算时间再哈希法特点：不易产生聚集，但增加计算时间pp处理冲突的方法处理冲突的方法处理冲突的方法处理冲突的方法( ( ( (链地址法链地址法链地址法链地址法) ) ) )将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函将
91、所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址区间数产生的哈希地址区间数产生的哈希地址区间数产生的哈希地址区间0, m0, m0, m0, m1111上，则设立一个指针型向量：上，则设立一个指针型向量：上，则设立一个指针型向量：上，则设立一个指针型向量：Chain Chain Hashm;Chain Chain Hashm;Chain Chain Hashm;Chain Chain Hashm;其每个分裂的初始状态都是空指针。凡哈希地址为其每个分裂的初始状态都是空指针。凡哈希地址为其每个分裂的初始状态都是空
92、指针。凡哈希地址为其每个分裂的初始状态都是空指针。凡哈希地址为i i i i的记录都插入到头指针的记录都插入到头指针的记录都插入到头指针的记录都插入到头指针为为为为Chain HashmChain HashmChain HashmChain Hashm的链表中。在链表中的插入位置可以在表头或表尾，也可的链表中。在链表中的插入位置可以在表头或表尾，也可的链表中。在链表中的插入位置可以在表头或表尾，也可的链表中。在链表中的插入位置可以在表头或表尾，也可以在中间，以保持同义词在同一线性链表中按关键字有序。以在中间，以保持同义词在同一线性链表中按关键字有序。以在中间，以保持同义词在同一线性链表中按关键
93、字有序。以在中间，以保持同义词在同一线性链表中按关键字有序。豌拳扰汁一级许田和蚁罩元铂琉唬毯侦徒规唆罩蔫猜醒产聘萝奖涎参宅杨数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表p举例：给定关键字集合举例：给定关键字集合19,01,23,14,55,68, 19,01,23,14,55,68, 11,82,3611,82,36，设定哈希函，设定哈希函数数H(key)=key MOD 11 H(key)=key MOD 11 ( (表长表长=11)=11)表后插入表后插入 p查找不成功，再插入新结查找不成功，再插入新结点时，用表后插入方法较点时，用表后插入方法较好好012345
94、678910190114556811823623匹虎称妊宵颇舶变鉴狭峦薪抡匿舜疹锑发搽赁渐挛雏篡昧贰较京裹蒲郁炎数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表p举例：给定关键字集合举例：给定关键字集合19,01,23,14,55,68, 19,01,23,14,55,68, 11,82,3611,82,36，设定哈希函设定哈希函设定哈希函设定哈希函数数数数H(key)=key MOD 11 H(key)=key MOD 11 ( ( ( (表长表长表长表长=11)=11)=11)=11)表头插入表头插入表头插入表头插入 pp给定关键字集合，逐步生给定关键字集合，逐步生
95、给定关键字集合，逐步生给定关键字集合，逐步生成哈希表时，用表头插入成哈希表时，用表头插入成哈希表时，用表头插入成哈希表时，用表头插入方法较好方法较好方法较好方法较好012345678910192336116855821401卞膳郑裳铆叭袄感留箍冰枚吉为锅嗡阁旅煎仕踢某鸣出桅猖裳譬谷搀乖徽数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表9.4.4哈希表的实现哈希表的实现假设哈希函数为关键字求模运算，哈希表用拉链法解决冲突，假设哈希函数为关键字求模运算，哈希表用拉链法解决冲突，假设哈希函数为关键字求模运算，哈希表用拉链法解决冲突，假设哈希函数为关键字求模运算，哈希表用拉链法
96、解决冲突，其结构可以定义如下：其结构可以定义如下：其结构可以定义如下：其结构可以定义如下：#defineLEN31/表长表长LEN最好为质数最好为质数typedefstructnodeintdata;structnode*next;node;structnodeHashTabLEN;驹腑玉蜂龟让兰团膀奖议锈铰掉赎赴葵漾铁磅衣悟硬束肃夷釜特脱涎碳彼数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表p哈希表的实现哈希函数哈希表的实现哈希函数hash()hash()返回值为哈希表地址返回值为哈希表地址: :pp查找过程查找过程查找过程查找过程n n对于给定值对于给定值对于给定值
97、对于给定值keykeykeykey，计算哈希地址，计算哈希地址，计算哈希地址，计算哈希地址 p=hash(Key)p=hash(Key)n n若若若若HashTabp.next=NULLHashTabp.next=NULL，则，则，则，则查找不成功查找不成功查找不成功查找不成功n n若若若若HashTabp.next.data=keyHashTabp.next.data=key，则查找成功，则查找成功，则查找成功，则查找成功n n否则否则否则否则 “求下一地址求下一地址求下一地址求下一地址”，再进行，再进行，再进行，再进行比较比较比较比较inthash(intkey)retAddr=keyMO
98、DLEN;return(retAddr);给定给定k值值计算计算hash(key)此地址为空此地址为空关键字关键字=key查找失败返回查找失败返回或插入新结点或插入新结点查找成功查找成功按处理冲突方法按处理冲突方法计算下一地址计算下一地址YNYN翘咨玛失咽夹谤挟舜庚疹只焊复敌吨伎簧傅迈瓣盆洗请剔岩肠溺免复扑粤数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表p查找函数查找函数search()search()若找到若找到keykey，返回其结点指针；否则将其插入表中再返回其结，返回其结点指针；否则将其插入表中再返回其结点指针点指针 链地址法解决冲突，表头插入链地址法解决冲突
99、，表头插入 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.5 哈希哈希查找的性能分析查找的性能分析查找的性能分析查找的性能分析哈希查找按
100、理论分析，它的时间复杂度应为哈希查找按理论分析，它的时间复杂度应为哈希查找按理论分析，它的时间复杂度应为哈希查找按理论分析，它的时间复杂度应为O(1)O(1)，它的平均查，它的平均查，它的平均查，它的平均查找长度应为找长度应为找长度应为找长度应为ASL=1ASL=1，但实际上由于冲突的存在，它的平均查找长度，但实际上由于冲突的存在，它的平均查找长度，但实际上由于冲突的存在，它的平均查找长度，但实际上由于冲突的存在，它的平均查找长度将会比将会比将会比将会比1 1大。下面将分析几种方法的平均查找长度。大。下面将分析几种方法的平均查找长度。大。下面将分析几种方法的平均查找长度。大。下面将分析几种方法
101、的平均查找长度。pp线性探查法的性能分析线性探查法的性能分析线性探查法的性能分析线性探查法的性能分析由于线性探查法解决冲突是线性地查找空闲位置的，平均查找由于线性探查法解决冲突是线性地查找空闲位置的，平均查找由于线性探查法解决冲突是线性地查找空闲位置的，平均查找由于线性探查法解决冲突是线性地查找空闲位置的，平均查找长度与表的大小长度与表的大小长度与表的大小长度与表的大小mm无关，只与所选取的散列函数无关，只与所选取的散列函数无关，只与所选取的散列函数无关，只与所选取的散列函数H H及装填因子及装填因子及装填因子及装填因子 的值的值的值的值和该处理方法有关，这时的成功的平均查找长度为和该处理方法
102、有关，这时的成功的平均查找长度为和该处理方法有关，这时的成功的平均查找长度为和该处理方法有关，这时的成功的平均查找长度为ASL=1/2ASL=1/2(1+1/(1-)(1+1/(1-)。pp链地址法的性能分析链地址法的性能分析链地址法的性能分析链地址法的性能分析由于拉链法查找就是在单链表上查找，查找单链表中第一个结由于拉链法查找就是在单链表上查找，查找单链表中第一个结由于拉链法查找就是在单链表上查找，查找单链表中第一个结由于拉链法查找就是在单链表上查找，查找单链表中第一个结点的次数为点的次数为点的次数为点的次数为1 1，第二个结点次数为，第二个结点次数为，第二个结点次数为，第二个结点次数为2
103、2，其余依次类推。它的平均查找，其余依次类推。它的平均查找，其余依次类推。它的平均查找，其余依次类推。它的平均查找长度长度长度长度ASL=1+/2ASL=1+/2。着憨趟遍籍暇毅度曹拣滩鞘朋夕啊曰涌厢茨擎搓杨陕握咸察篡坞酗祁她谓数据结构第九章查找数据结构第九章查找9- 中国科大数据结构9.4 哈希表p哈希查找的性能分析哈希查找的性能分析( (平均查找长度平均查找长度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- 中国科大数据结构习题p本章习题参见教师网页：本章习题参见教师网页：http:/
