《九章查找Search》由会员分享，可在线阅读，更多相关《九章查找Search（98页珍藏版）》请在金锄头文库上搜索。
1、第九章第九章 查找查找(Search)9.1 9.1 基本概念基本概念9.2 9.2 静态查找表静态查找表9.3 9.3 动态查找表动态查找表9.4 Hash9.4 Hash表表虹虹脑脑母母希希憋憋抠抠敝敝滓滓危危妮妮尘尘当当名名遭遭豢豢邹邹乏乏赠赠喜喜孜孜冕冕当当呕呕翼翼痘痘戊戊晃晃鳃鳃壤壤苍苍建建弯弯九九章章查查找找Search九九章章查查找找Search若表中存在特定元素，称查找成功；若表中存在特定元素，称查找成功；否则，称查找不成功（应输出失败标志或失败位置）否则，称查找不成功（应输出失败标志或失败位置）;查找表查找表查查 找找查找成功查找成功查找不成功查找不成功静态查找静态查找动态查
2、找动态查找关键字关键字主关键字主关键字次关键字次关键字由同一类型的数据元素（或记录）构成的集合。由同一类型的数据元素（或记录）构成的集合。查询查询(Searching)特定元素特定元素是否在表中。是否在表中。只查找，不改变集合内的数据元素。只查找，不改变集合内的数据元素。既查找，又改变（增减）集合内的数据元素。既查找，又改变（增减）集合内的数据元素。记录中某个数据项的值，可用来识别一个记录记录中某个数据项的值，可用来识别一个记录 可以可以唯一唯一标识一个记录的关键字标识一个记录的关键字例如例如“学号学号”例如例如“女女”识别若干记录的关键字识别若干记录的关键字9.1 9.1 基本概念基本概念厌
3、厌例例圣圣现现炳炳镀镀饵饵纱纱椽椽拧拧瞥瞥楞楞聋聋绞绞凳凳非非秩秩金金因因氮氮牟牟渭渭降降宪宪笋笋炼炼佩佩盾盾讳讳柒柒汤汤邻邻九九章章查查找找Search九九章章查查找找Searchv对查找表常用的操作有对查找表常用的操作有哪些？哪些？ v查询某个查询某个“特定的特定的”数据元素是否在表中；数据元素是否在表中；v查询某个查询某个“特定的特定的”数据元素的各种属性；数据元素的各种属性；v在查找表中插入一元素；在查找表中插入一元素；v从查找表中删除一元素。从查找表中删除一元素。 v查找的过程是怎样的？查找的过程是怎样的？ 给定一个值给定一个值K K，在含有，在含有n n个记录的文件中进行搜索，寻找
4、个记录的文件中进行搜索，寻找一个关键字值等于一个关键字值等于K K的记录，如找到则输出该记录，否则输出的记录，如找到则输出该记录，否则输出查找不成功的信息。查找不成功的信息。9.1 9.1 基本概念基本概念墟墟络络呻呻椒椒质质呐呐莲莲镜镜枫枫喂喂苞苞业业恒恒飘飘际际堪堪彤彤秘秘危危磅磅某某猾猾歌歌繁繁嚼嚼摹摹潜潜闰闰叶叶明明赋赋匝匝九九章章查查找找Search九九章章查查找找Searchv如何评估查找方法的优劣？如何评估查找方法的优劣？ 查找的过程就是将给定的值与文件中各记录的关查找的过程就是将给定的值与文件中各记录的关键字逐项进行比较的过程。所以用比较次数的平均值键字逐项进行比较的过程。所以
5、用比较次数的平均值来评估算法的优劣，称为来评估算法的优劣，称为平均查找长度平均查找长度（ASLASL：average search lengthaverage search length）。）。其中：其中：n n是文件记录个数；是文件记录个数；P Pi i是查找第是查找第i i个记录的查找概率；个记录的查找概率；C Ci i是找到第是找到第i i个记录时所经历的比较次数。个记录时所经历的比较次数。显然，显然，ASLASL值越小，时间效率越高。值越小，时间效率越高。 9.1 9.1 基本概念基本概念崩崩山山申申怜怜甜甜晚晚疏疏淄淄呐呐宵宵漳漳钦钦炮炮逃逃浓浓司司鸿鸿掺掺呆呆耪耪勇勇兼兼岭岭帆帆裹
6、裹里里砾砾沁沁惟惟危危馋馋熔熔九九章章查查找找Search九九章章查查找找Search静态查找表抽象数据类型静态查找表抽象数据类型ADT StaticSearchTable Data: SET Operations:Create(&ST, n): 创建具有创建具有n个元素的查找表。个元素的查找表。Destroy( &ST): 销毁查找表。销毁查找表。Search(ST,key): 查找具有关键字查找具有关键字key 的元素。的元素。Traverse( ST,visit(): 遍历查找表。遍历查找表。ADT StaticSearchTable9.2 9.2 静态查找（搜索）表静态查找（搜索）表渡
7、渡碰碰太太扣扣逊逊持持仇仇电电蕾蕾贾贾孙孙钥钥放放担担狄狄谬谬袜袜啤啤杭杭垃垃顷顷鞍鞍摇摇泅泅筑筑韧韧趣趣绽绽牡牡途途琢琢镁镁九九章章查查找找Search九九章章查查找找Search一、顺序查找（线性查找）一、顺序查找（线性查找）二、折半查找（二分或对分查找）二、折半查找（二分或对分查找）三、分块查找（索引顺序查找）三、分块查找（索引顺序查找）9.1 9.1 静态查找（搜索）表静态查找（搜索）表n静态查找表可用静态查找表可用顺序表或单链表存储，顺序表或单链表存储， 本章只讨论顺序表。本章只讨论顺序表。为为哑哑滑滑默默凡凡遵遵宴宴卤卤系系伯伯寓寓裤裤投投盲盲篇篇档档会会黎黎凡凡蕊蕊孟孟蝗蝗播播描
8、描驮驮蔫蔫涣涣梨梨同同圣圣赏赏譬譬九九章章查查找找Search九九章章查查找找Search所谓顺序查找，又称线性查找，主要用于在所谓顺序查找，又称线性查找，主要用于在线性结构线性结构中中进行查找。进行查找。设若表中有设若表中有 n n 个记录，则顺序查找从表的先端开始，个记录，则顺序查找从表的先端开始，顺序用各记录的关键码与给定值顺序用各记录的关键码与给定值x x进行比较，直到找到与进行比较，直到找到与其值相等的记录，则称查找成功，给出该记录在表中的其值相等的记录，则称查找成功，给出该记录在表中的位置。位置。n若若整整个个表表都都已已检检测测完完仍仍未未找找到到关关键键码码与与x x相相等等的
9、的记记录录，则查找失败，给出失败信息。则查找失败，给出失败信息。一、顺序查找（一、顺序查找（Linear search,又称线性查找）线性查找）辫辫犬犬姐姐鬃鬃嵌嵌汕汕旺旺梳梳湾湾虎虎桥桥赠赠秽秽宝宝闹闹福福粘粘考考亮亮沥沥砌砌定定塔塔伴伴慢慢荐荐吩吩倪倪堰堰疫疫所所常常九九章章查查找找Search九九章章查查找找Search一、顺序查找1).1).顺序表的机内存储结构：顺序表的机内存储结构：typedef struct ElemType *elem; /表基址，表基址，0 0号单元留空。表容量为全部元素号单元留空。表容量为全部元素 int length; /表长，即表中数据元素个数表长，即表
10、中数据元素个数SSTable;佰佰糜糜敲敲号号几几锣锣桂桂辜辜使使怯怯航航雅雅虽虽凌凌描描聚聚协协钵钵耐耐藩藩跳跳萨萨筹筹窿窿乐乐灼灼皆皆箱箱熄熄羊羊韵韵杂杂九九章章查查找找Search九九章章查查找找Search2).算法的实现：算法的实现：编程技巧：编程技巧：把待查关键字把待查关键字keykey存入表头或表尾（俗存入表头或表尾（俗称称“哨兵哨兵”），这样可以加快执行速度（避免每一次），这样可以加快执行速度（避免每一次查找都检测整个表是否查找完毕）。查找都检测整个表是否查找完毕）。例：例：若将待查找的特定值若将待查找的特定值keykey存入存入顺序表的顺序表的首部首部（如（如0 0号单元），
11、则顺序查找的算法思想为：号单元），则顺序查找的算法思想为：从后向前从后向前逐个比较！逐个比较！一、顺序查找一、顺序查找语语要要媳媳喜喜参参锌锌琐琐捡捡惶惶谨谨硒硒汉汉纠纠簧簧煽煽范范抱抱备备掷掷犯犯享享掘掘退退绑绑淆淆撬撬洱洱嘻嘻谱谱退退恿恿奇奇九九章章查查找找Search九九章章查查找找Searchint Search_Seq( SSTable ST , KeyType key ) /在顺序表在顺序表STST中，查找关键字与中，查找关键字与keykey相同的元素；若成功，相同的元素；若成功，返回其位置信息，否则返回返回其位置信息，否则返回0 0。 ST.elem0.key =key; for
12、( i=ST.length; ST.elem i .key!=key; - - i ); /不要用不要用for(i=n; i0; - -i) 或或 for(i=1; i x x，把把查查找找区区间间缩缩小小到到表表的的前前半半部部分分，再继续进行对分查找；再继续进行对分查找； L L midmid.KeyKey x x x x，r=mid-1;r=mid-1;r=mid-1;r=mid-1;uu L L L L midmidmidmid.Key Key Key Key x x x x，l=mid+1;l=mid+1;l=mid+1;l=mid+1;4 4 4 4 若若若若l=r l=r l=r
13、 l=r 转转转转2 2 2 2，否则查找失败，返回，否则查找失败，返回，否则查找失败，返回，否则查找失败，返回 0 0 0 0；考虑对考虑对单链表结构单链表结构如何折半查找？如何折半查找？ 无法实现！无法实现！寿寿咸咸榜榜侩侩幽幽猩猩眯眯积积蛙蛙谍谍练练隅隅岭岭阑阑岛岛叫叫稍稍骤骤精精钦钦归归擦擦孩孩扼扼纬纬畅畅歇歇慈慈踏踏暗暗联联售售九九章章查查找找Search九九章章查查找找Searchint Search_Bin ( SSTable ST, KeyType key ) / 在有序表在有序表ST中折半查找其关键字等于中折半查找其关键字等于key的数据元素。的数据元素。/ 若找到，则函数值
14、为该元素在表中的位置，否则为若找到，则函数值为该元素在表中的位置，否则为0。low = 1; high = ST.length; / 置区间初值置区间初值while (low = high) mid = (low + high) / 2;if (key = ST.elemmid.key) return mid; / 找到待查元素找到待查元素else if ( key data = T-data = RiRi; / ; / 生成结点生成结点构造次优二叉树的算法构造次优二叉树的算法优优猫猫严严隙隙渍渍迈迈狭狭僵僵施施荐荐泉泉绘绘铝铝淡淡腑腑耻耻田田憨憨兽兽趣趣继继证证默默搐搐鼎鼎椅椅弹弹躁躁寸寸上
15、上巨巨别别九九章章查查找找Search九九章章查查找找Searchif (i=low) T-lchild = NULL; / 左子树空左子树空else SecondOptimal(T-lchild, R, sw, low, i-1); / 构造左子树构造左子树 if (i=high) T-rchild = NULL; / 右子树空右子树空 else SecondOptimal(T-rchild, R, sw, i+1, high); / 构造右子树构造右子树 return OK; / SecondOptimal蔑蔑符符掣掣立立潞潞犬犬蹈蹈估估公公之之嘿嘿弥弥瘴瘴尊尊爆爆宿宿连连培培债债主主瑞瑞
16、膀膀盆盆蜀蜀募募焊焊梭梭囚囚节节辟辟涸涸卓卓九九章章查查找找Search九九章章查查找找Search次优查找树采用二叉链表的存储结构次优查找树采用二叉链表的存储结构Status CreateSOSTre(Status CreateSOSTre(SOSTree &TSOSTree &T, SSTable ST) , SSTable ST) / / 由有序表由有序表 ST ST 构造一棵次优查找树构造一棵次优查找树 T T。 / ST / ST 的数据元素含有权域的数据元素含有权域 weight weight if (ST.length = 0) T = NULL; if (ST.length =
17、 0) T = NULL; else else FindSW(sw, ST); FindSW(sw, ST); / / 按照有序表按照有序表 ST ST 中各数据元素中各数据元素 / / 的的 weight weight 值求累计权值表值求累计权值表 SecondOpiamal(T, ST.elem, sw, 1, ST.length);SecondOpiamal(T, ST.elem, sw, 1, ST.length); return OK; return OK; / CreatSOSTree / CreatSOSTree曲曲獭獭苏苏咯咯顶顶湃湃擒擒卑卑协协炬炬疑疑终终呸呸娇娇绰绰失失裔裔
18、贺贺厕厕饵饵影影齿齿蒋蒋笺笺邱邱犀犀斗斗掳掳桩桩楼楼抚抚阻阻九九章章查查找找Search九九章章查查找找Search三、索引顺序表的查找三、索引顺序表的查找(分块查找分块查找)索引顺序表的查找索引顺序表的查找是鉴于是鉴于顺序查找顺序查找和和折半查找折半查找的一种查找。的一种查找。索引顺序表索引顺序表是由是由索引表索引表和和顺序表顺序表两部分组成。两部分组成。索引顺序表的特点索引顺序表的特点是把若干个数据元素分成若干块，每一块是把若干个数据元素分成若干块，每一块称为一个称为一个顺序表，顺序表，要求块与块之间要有序，即第要求块与块之间要有序，即第i+1块的所有块的所有元素的关键字要大于第元素的关键
19、字要大于第i块的所有元素的关键字。块的所有元素的关键字。为了查找方便，为每一块建立一个为了查找方便，为每一块建立一个索引项：索引项：索引项索引项：(key,addr), key 域标记该块中最大记录的关键字，域标记该块中最大记录的关键字， addr域指向该块的起始地址。域指向该块的起始地址。索引表索引表是由若干是由若干索引项索引项组成的有序表。组成的有序表。刻刻契契臼臼窗窗制制砚砚娇娇概概杰杰凸凸圃圃咱咱斧斧泅泅斧斧晤晤芳芳后后惹惹疆疆乌乌甸甸块块燕燕咋咋特特戒戒癸癸气气烁烁殉殉烛烛九九章章查查找找Search九九章章查查找找Search例：例：22 15 13 8 17 20 35 24 3
20、3 40 36 29 50 48 60 49 54 6122 40 611 7 13最大关键字最大关键字(key)(key)起始地址起始地址(addr)(addr)第一块第一块索引表索引表第三块第三块第二块第二块盛盛磨磨怖怖哮哮回回柠柠凯凯故故击击之之腊腊猛猛采采监监酮酮辉辉驶驶茨茨宏宏荣荣宏宏兼兼负负辽辽朔朔著著鬼鬼挛挛扭扭棕棕矮矮凡凡九九章章查查找找Search九九章章查查找找Search有必要时可以在索引表上再建立索引表有必要时可以在索引表上再建立索引表稠密索引稠密索引: 为每条记录设一个索引项。为每条记录设一个索引项。稀疏索引：稀疏索引：一组记录设一个索引项。一组记录设一个索引项。三、
21、索引顺序表的查找三、索引顺序表的查找(分块查找分块查找)机机极极梆梆废废寄寄役役溢溢弘弘罪罪滋滋得得斤斤雄雄业业玄玄钳钳乾乾凉凉挚挚礼礼餐餐神神诊诊乳乳喜喜拳拳点点兵兵赏赏慌慌作作私私九九章章查查找找Search九九章章查查找找Search三、索引顺序表的查找三、索引顺序表的查找(分块查找分块查找)分块查找的数据结构：分块查找的数据结构：D=d1,d2,.,dn1. 将将n个数据元素分为个数据元素分为s个块个块 B1,B2, , Bs ；2. 块之间有序：块之间有序：Bi+1中的任一元素小于中的任一元素小于Bi中的任一元中的任一元 素素(i=1,2,n-1)；3. 为每个为每个Bi块设一索引项
22、块设一索引项(keyi, addri)；4. s个索引项构成索引表；个索引项构成索引表；5. 块内可有序也可无序块内可有序也可无序;箱箱辨辨件件堰堰卢卢吝吝屯屯育育皑皑鳞鳞臼臼绑绑惭惭上上雹雹舀舀峡峡捕捕畜畜码码晋晋盛盛耗耗矾矾平平况况脓脓章章贪贪赎赎玖玖忍忍九九章章查查找找Search九九章章查查找找Search三、索引顺序表的查找三、索引顺序表的查找(分块查找分块查找)在索引顺序表中查找的基本思想在索引顺序表中查找的基本思想:1.首先在索引表中查找，确定该首先在索引表中查找，确定该查找的元素查找的元素在哪个块在哪个块中中(可以是折半查找，也可以是顺序查找可以是折半查找，也可以是顺序查找)。
23、2. 然后在块中查找然后在块中查找(只能是顺序查找只能是顺序查找)。郝郝尤尤肋肋番番溶溶喝喝稀稀柔柔轿轿早早甥甥陪陪库库妮妮糕糕痢痢酱酱析析瞄瞄亡亡春春减减涎涎氢氢讫讫硫硫馏馏呀呀胁胁板板翟翟憎憎九九章章查查找找Search九九章章查查找找Search算法分析：算法分析：设在索引表中和块内都是顺序查找。设在索引表中和块内都是顺序查找。索引表中查找：索引表中查找：ALSindex=(s+1)/2块中查找：块中查找： ALSlock=(n/s+1)/2所以：所以： ALSbsbs= (s+1)/2 + (n/s+1)/2=(n/s+s)/2+1显然它与显然它与s 的取值有关。当的取值有关。当 时，
24、时，ASLbs有有最小值最小值 三、索引顺序表的查找三、索引顺序表的查找(分块查找分块查找)负负持持光光氛氛微微陕陕受受泽泽搭搭扯扯怪怪扑扑舅舅尘尘汀汀沃沃九九桃桃立立硫硫萧萧慈慈雇雇刹刹寒寒染染箩箩受受僳僳冯冯囚囚需需九九章章查查找找Search九九章章查查找找Search 例例 n=10000; s=100;则则顺序查找顺序查找： ASL=(n+1)/2 5000次次 索引顺序表索引顺序表退化成顺序表退化成顺序表, 即可进行即可进行顺序查找顺序查找折半查找折半查找: ASL14 次次当当s=n时时,索引顺序表索引顺序表退化成有序表退化成有序表, 即可进行即可进行折半查找折半查找当当s=1时
25、时, 100次次分块查找分块查找: ASLbs= (n/s+s)/2+1 100次次分块查找分块查找: Min(ASLbs)=( ) 害害坠坠漳漳联联康康谅谅炉炉铬铬婿婿辟辟渴渴脆脆抬抬鸯鸯修修乎乎猜猜恫恫媚媚乎乎萄萄辗辗咕咕队队兰兰邹邹业业卷卷挚挚岂岂跑跑讳讳九九章章查查找找Search九九章章查查找找Search9.2 9.2 动态查找（搜索）表动态查找（搜索）表 动态查找的特点是，表结构本身是在查找动态查找的特点是，表结构本身是在查找过程中动态生成的，即对给定关键字值过程中动态生成的，即对给定关键字值key ，表中有具有此值的记录，则查找成功返回，否表中有具有此值的记录，则查找成功返回，
26、否则插入此关键字的新记录。则插入此关键字的新记录。衷衷华华祝祝朗朗虱虱芋芋尿尿疗疗越越垦垦俗俗别别桌桌汞汞衅衅晶晶傅傅烩烩抱抱拍拍佑佑变变枷枷绩绩影影址址归归泵泵氖氖窜窜瞎瞎裙裙九九章章查查找找Search九九章章查查找找SearchADT DynamicSearchTable 数据对象数据对象D D：具有相同特性的数据元素的集合。每个数具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素据元素含有类型相同的关键字，可唯一标识数据元素。数据关系数据关系R：数据元素同属一个集合。数据元素同属一个集合。 基本操作基本操作:InitDSTable(&DT); /构造一个
27、空的动态查找表构造一个空的动态查找表DTDTDestroyDStable( &DT); / 销毁查找表销毁查找表DTDT。SearchDSTable(DT,key); /查找具有关键字查找具有关键字key key 的元素。的元素。InsertDSTable(&DT,e); /插入新记录。插入新记录。DeleteDSTable(&DT,key );/删除记录。删除记录。TraverseDSTable(DT,visit(); /遍历查找表。遍历查找表。 ADT DynamicSearchTable 动态查找表的抽象数据类型动态查找表的抽象数据类型巷巷驶驶擎擎撅撅微微森森瓶瓶南南帛帛恨恨莲莲兴兴扶扶
28、坟坟睁睁勤勤蚤蚤障障癣癣茂茂鞋鞋枚枚钓钓胁胁咱咱寝寝作作朽朽俺俺脆脆盆盆语语九九章章查查找找Search九九章章查查找找Search一、二叉排序树一、二叉排序树二、平衡二叉树二、平衡二叉树9.2 9.2 动态查找（搜索）表动态查找（搜索）表粒粒戈戈浚浚剩剩诗诗丫丫荣荣己己尝尝丝丝进进鳃鳃展展密密灶灶趣趣罐罐汐汐摔摔象象衷衷罪罪囱囱睬睬语语且且痴痴南南篮篮循循牛牛达达九九章章查查找找Search九九章章查查找找Searchq1.1.二叉排序树的定义二叉排序树的定义 二叉排序树或者是一棵空树，或者是具有下列性质二叉排序树或者是一棵空树，或者是具有下列性质二叉排序树或者是一棵空树，或者是具有下列性质
29、二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：的二叉树：的二叉树：的二叉树： 若它的左子树不空若它的左子树不空若它的左子树不空若它的左子树不空, , , ,则左子树上所有结点的关键字都则左子树上所有结点的关键字都则左子树上所有结点的关键字都则左子树上所有结点的关键字都 小于根结点的关键字。小于根结点的关键字。小于根结点的关键字。小于根结点的关键字。 若它的右子树不空若它的右子树不空若它的右子树不空若它的右子树不空, , , ,则右子树上所有结点的关键字都则右子树上所有结点的关键字都则右子树上所有结点的关键字都则右子树上所有结点的关键字都 大于根结点的关键字。大于根结点的关键字。大于根结
30、点的关键字。大于根结点的关键字。 左子树和右子树分别是二叉排序树。左子树和右子树分别是二叉排序树。左子树和右子树分别是二叉排序树。左子树和右子树分别是二叉排序树。一、二叉排序树一、二叉排序树捻捻阐阐洗洗铅铅胳胳娟娟真真焉焉辅辅围围龚龚轴轴督督倘倘高高靳靳涟涟烤烤联联冗冗阂阂蓟蓟蜂蜂七七疗疗仗仗亥亥侨侨遗遗行行寞寞艺艺九九章章查查找找Search九九章章查查找找Search二叉排序树的例子二叉排序树的例子不是二叉排序树不是二叉排序树50308020901085403525238866律律疥疥狙狙砖砖漏漏袖袖梧梧蒙蒙庭庭阻阻万万逝逝弃弃楼楼猾猾东东绥绥需需娟娟圾圾李李氨氨贵贵时时幽幽翁翁顶顶沿沿嘻
31、嘻盖盖产产新新九九章章查查找找Search九九章章查查找找Search 如果对一棵二叉排序树进行中序遍历，可以如果对一棵二叉排序树进行中序遍历，可以如果对一棵二叉排序树进行中序遍历，可以如果对一棵二叉排序树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，按从小到大的顺序，将各结点关键码排列起来，按从小到大的顺序，将各结点关键码排列起来，按从小到大的顺序，将各结点关键码排列起来，q2.二叉排序树的存储结构（二叉链表）二叉排序树的存储结构（二叉链表）typedef struct BiTNode / 结点结构结点结构 struct BiTNode *lchild, *rchild; El
32、emType data; BiTNode, *BiTree;q二叉排序树的定义二叉排序树的定义这这雹雹义义阐阐桅桅旷旷蚁蚁垛垛己己恩恩解解折折盏盏叭叭企企宜宜拜拜阂阂衍衍及及检检太太慎慎凸凸涎涎搓搓萧萧岸岸吻吻耻耻洼洼矿矿九九章章查查找找Search九九章章查查找找Search 算法思想：算法思想：(1) p指向根；指向根；(2) p的关键字与的关键字与key比较，有三种情况：比较，有三种情况： p-data.key=key; 查找成功，返回查找成功，返回p, 结束；结束； p-data.keykey; 到左子树中找，到左子树中找，p指向它左子女；指向它左子女；p-data.keydata.k
33、ey) return p; /查找成功，返回查找成功，返回p else if (kdata.key) p=p-lchild; /到左子树中找到左子树中找 else p=p-rchild; /到右子树中找到右子树中找 return p; /查找失败，返回空查找失败，返回空 / search该算法可设计为递归算法，请大家自己设计。该算法可设计为递归算法，请大家自己设计。q二叉排序树的查找二叉排序树的查找闽闽筋筋示示恩恩橱橱轴轴鲍鲍疽疽机机巩巩浊浊低低颜颜刻刻寡寡傣傣忍忍蹬蹬吱吱泥泥姜姜夏夏娠娠鸭鸭至至撑撑砾砾惜惜向向专专这这俗俗九九章章查查找找Search九九章章查查找找Search 629741
34、83的插入位置在在在在插插插插入入入入之之之之前前前前，先先先先使使使使用用用用查查查查找找找找算算算算法法法法在在在在树树树树中中中中检检检检查查查查要要要要插插插插入入入入元元元元素素素素有还是没有。有还是没有。有还是没有。有还是没有。uu 查找成功查找成功查找成功查找成功: : : : 树中已有这个元素，不再插入。树中已有这个元素，不再插入。树中已有这个元素，不再插入。树中已有这个元素，不再插入。uu 查查查查找找找找不不不不成成成成功功功功: : : : 树树树树中中中中原原原原来来来来没没没没有有有有关关关关键键键键码码码码等等等等于于于于给给给给定定定定值值值值的结点，把新元素加到
35、查找操作停止的地方。的结点，把新元素加到查找操作停止的地方。的结点，把新元素加到查找操作停止的地方。的结点，把新元素加到查找操作停止的地方。q4.4.二叉排序树的插入二叉排序树的插入啸啸痴痴贮贮拼拼琳琳恤恤设设选选台台孽孽龄龄霓霓狮狮醛醛瓷瓷蛙蛙赖赖谱谱突突烬烬向向逐逐钓钓溃溃包包攫攫逢逢旦旦派派郁郁就就逮逮九九章章查查找找Search九九章章查查找找Search为找到插入位置的双亲，查找算法做如下改动：为找到插入位置的双亲，查找算法做如下改动：BiTree search(KeyType k，BiTree &pre, BiTree T) pre=NULL; p=T; while (p) if
36、(k=p-data.key) return p; /查找成功，返回查找成功，返回p else pre=p; if (kdata.key) p=p.lchild; /到左子树中找到左子树中找 else p=p-rchild; /到右子树中找到右子树中找 return p; /查找失败，返回空查找失败，返回空 / searchq二叉排序树的插入二叉排序树的插入斜斜氯氯饭饭菏菏我我凑凑芜芜盆盆守守箔箔蝉蝉淋淋餐餐笨笨渴渴染染嘻嘻柄柄窿窿宴宴眺眺尺尺守守津津袁袁归归魁魁征征惋惋惧惧根根簿簿九九章章查查找找Search九九章章查查找找Searchvoid insert(ElemType e, BiTre
37、e &T) p=search(e.key, &pre,T); if (!p) /树中无树中无e，插入。，插入。 q=(BiTree)malloc(sizeof( BiTNode); q-data=e; q-lchild=q-rchild=NULL; if (!pre) T=q; else if (e.keydata.key) pre-lchild=q; /插到左子女插到左子女 else pre-rchild=q; /插到右子女插到右子女 / insertq二叉排序树的插入二叉排序树的插入造造想想芍芍竭竭慰慰廉廉详详治治当当拦拦葛葛躁躁鲍鲍纲纲瑟瑟盆盆谊谊务务显显箍箍现现哀哀齐齐贷贷因因扦扦烹烹
38、厂厂英英我我惧惧稗稗九九章章查查找找Search九九章章查查找找Search 二叉查找树的查找二叉查找树的查找 插入新结点插入新结点88 每次结点的插入，都要从根结点出发查找插入位每次结点的插入，都要从根结点出发查找插入位置，然后把新结点作为叶结点插入。置，然后把新结点作为叶结点插入。q二叉排序树的插入二叉排序树的插入线线孩孩矮矮俗俗诈诈罗罗佯佯狗狗追追烷烷南南龚龚酸酸珠珠香香支支坡坡霍霍莫莫真真贰贰词词际际攻攻弦弦弄弄锥锥祷祷脸脸嚼嚼恩恩隙隙九九章章查查找找Search九九章章查查找找Search建立二叉排序树建立二叉排序树输入数据序列输入数据序列 53,78,65,17,87,09,81,
39、45,23 53,78,65,17,87,09,81,45,23雌雌惩惩爬爬挑挑肌肌切切侩侩畏畏瘤瘤赘赘夫夫尘尘浮浮驴驴钨钨枪枪阁阁槛槛介介乃乃休休淆淆奢奢榆榆联联臃臃沼沼卜卜茧茧涸涸遗遗村村九九章章查查找找Search九九章章查查找找Search输入顺序不同，建立起来的二叉排序树的形态也不同。输入顺序不同，建立起来的二叉排序树的形态也不同。这直接影响到二叉排序树的查找性能。这直接影响到二叉排序树的查找性能。 如果输入序列选得不好，会建立起一棵单支树，使得二叉查如果输入序列选得不好，会建立起一棵单支树，使得二叉查找树的高度达到最大，这样必然会降低查找性能。找树的高度达到最大，这样必然会降低查找
40、性能。例：例：3 3 个数据个数据 1, 2, 3 1, 2, 3 ，1231111322233231, 2, 31, 2, 31, 3, 21, 3, 22, 1, 3 2, 1, 3 2, 3, 12, 3, 13, 1, 23, 1, 23, 2, 13, 2, 1 输入数据，建立二叉排序树输入数据，建立二叉排序树览览灰灰嘛嘛余余酪酪乱乱倡倡收收达达舆舆塘塘监监楔楔日日柠柠侨侨钮钮平平久久敦敦傅傅讶讶骋骋党党淬淬沥沥盟盟唉唉摆摆似似估估妒妒九九章章查查找找Search九九章章查查找找Search 和插入相反，删除是在和插入相反，删除是在查找成功时查找成功时进行的，并且进行的，并且要求在删
41、除二叉排序树上某个结点之后，要求在删除二叉排序树上某个结点之后，仍然保持二仍然保持二叉排序树的特性。叉排序树的特性。q5.5.二叉排序树的删除二叉排序树的删除（1 1）被删除的结点）被删除的结点是叶子是叶子；（2 2）被删除的结点）被删除的结点只有左子树只有左子树或者或者只有右子树只有右子树；（3 3）被删除的结点）被删除的结点既有左子树，也有右子树既有左子树，也有右子树。三种情况三种情况讨论：讨论：眨眨哎哎怕怕哥哥私私挛挛孽孽墙墙杖杖岭岭庞庞乍乍毙毙绘绘疏疏掘掘迸迸氓氓莫莫设设泥泥静静籽籽片片逼逼蚂蚂幽幽云云带带挨挨蔡蔡出出九九章章查查找找Search九九章章查查找找Searchq二叉排序树
42、的删除二叉排序树的删除（1 1）被删除的结点是）被删除的结点是叶子结点叶子结点其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”50308020908540358832例如例如: :被删关键字被删关键字 = 2088召召莲莲烙烙项项梧梧获获锋锋澄澄织织毯毯徽徽粥粥猫猫仲仲弛弛衰衰撬撬古古词词涛涛溶溶倍倍肠肠嘎嘎岩岩出出挽挽饶饶设设闪闪潜潜桶桶九九章章查查找找Search九九章章查查找找Searchq二叉排序树的删除二叉排序树的删除（2 2）被删除的结点）被删除的结点只有左子树只有左子树或者或者只有右子树只有右子树其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为 “
43、指向被删除结点指向被删除结点的左子树或右子树的左子树或右子树”。50308020908540358832删除删除40，80锥锥哄哄免免垦垦露露蛇蛇沛沛巧巧邑邑握握砰砰浑浑羊羊瘟瘟忻忻允允则则桂桂舷舷耶耶吨吨卵卵耳耳阳阳洞洞摸摸帘帘傻傻胀胀盂盂眨眨台台九九章章查查找找Search九九章章查查找找Search （3 3）被删结点的左、右子树都存在）被删结点的左、右子树都存在 找到被删结点在中序下的前驱找到被删结点在中序下的前驱, ,设为设为B B1)1)将被删结点的左孩子代替被删结点将被删结点的左孩子代替被删结点, ,被删结点的被删结点的右子树改为右子树改为B B的右子树的右子树; ; 2)2)将
44、将B B代替被删结点代替被删结点, ,被删结点的右子树改为被删结点的右子树改为B B的右的右子树子树,B,B的左子树成为的左子树成为B B的双亲的右子树的双亲的右子树. . q二叉排序树的删除二叉排序树的删除即即无无溺溺陕陕唾唾利利缄缄审审绑绑焚焚遇遇板板梗梗涌涌确确腑腑夷夷氟氟凡凡可可骗骗侯侯梧梧园园癣癣铅铅勋勋盖盖筏筏牢牢揖揖挝挝九九章章查查找找Search九九章章查查找找Search503080209085403588324040删除删除50q二叉排序树的删除二叉排序树的删除炕炕带带青青孙孙溺溺辩辩沙沙终终村村秘秘砂砂绘绘逢逢伟伟熙熙枪枪块块料料泣泣前前借借譬譬乘乘牺牺柴柴粳粳寻寻讯讯桌
45、桌坞坞匝匝糙糙九九章章查查找找Search九九章章查查找找SearchVoid delete(BiTree T,KeyType k) if (T) / 树不空树不空 p=search(k,&pre,T); /查找到被删除结点查找到被删除结点p及其双亲及其双亲pre； if (p) / 查找成功查找成功 if (!p-lchild) / p无左子女无左子女 if (!pre) T=p - rchild; else if (pre - lchild=p) pre - lchild=p - rchild; else pre - rchild=p - rchild; else if (!p - rch
46、ild) / p无右子女无右子女 if (!pre) T=p - lchild; else if (pre - lchild=p) pre - lchild=p - lchild; else pre - rchild=p - lchild; q二叉排序树的删除算法二叉排序树的删除算法烽烽掘掘瓮瓮桩桩稻稻后后炔炔输输拌拌出出潘潘来来粘粘玫玫鸽鸽鬼鬼铁铁跃跃初初官官业业紫紫渣渣软软踏踏席席怜怜充充景景罩罩祖祖樟樟九九章章查查找找Search九九章章查查找找Search else / p左右子女都不空左右子女都不空 rr=p; r=p-lchild; /在在 p 的左子树中找出最大结点的左子树中找出
47、最大结点 while (r-rchild) rr=r; r=r-rchild; rr-rchild=r-lchild; p-data=r-data; /将将r中元素复制到中元素复制到 p中中 free(r); / if (p) / if (root)q二叉排序树的删除算法二叉排序树的删除算法彩彩忿忿豪豪涩涩盼盼本本迈迈见见轻轻牟牟癌癌吭吭页页主主诌诌嫂嫂卉卉撂撂消消琶琶窟窟腮腮磋磋菏菏引引缀缀烘烘烬烬槽槽熄熄句句厄厄九九章章查查找找Search九九章章查查找找Search查找、插入和删除算法的查找、插入和删除算法的T(n) 均与二叉排序树的高均与二叉排序树的高度成正比。度成正比。6297418
48、6297418q6. 6. 插入删除算法分析插入删除算法分析寅寅憋憋嘛嘛囤囤诞诞下下律律莲莲昭昭颤颤死死性性继继堪堪诽诽纵纵苗苗朝朝腿腿注注心心惮惮铸铸能能粪粪雕雕什什费费滴滴拧拧痢痢玲玲九九章章查查找找Search九九章章查查找找Search若树退化成单分支若树退化成单分支,设树的深度为设树的深度为n, 则则ASL=(n+1)/2在最坏情况下：在最坏情况下： 在平均情况下在平均情况下,二叉排序树的的平均查找长度和二叉排序树的的平均查找长度和logn是同数量级的是同数量级的.但但忆忆郊郊垦垦钮钮都都封封强强砧砧孜孜疆疆苯苯谱谱案案育育庆庆痔痔逐逐挫挫霍霍悔悔稼稼滨滨忌忌哟哟侧侧镑镑尽尽吃吃堕堕
49、涵涵仍仍九九章章查查找找Search九九章章查查找找Search二、平衡二叉树二、平衡二叉树(Balanced Binary Tree)当确定搜索树的高度总是当确定搜索树的高度总是O(logn)O(logn)时，能够保证每个搜索时，能够保证每个搜索树操作所占用的时间为树操作所占用的时间为O(logn)O(logn)。高度为。高度为O(logn)O(logn)的树称的树称为平衡树为平衡树(balanced tree)(balanced tree)19621962年，俄国数学家提出了一种非常流行的平衡树年，俄国数学家提出了一种非常流行的平衡树AVLAVL树树(AVL tree(AVL tree）。
50、）。侣侣芥芥顽顽府府漏漏搞搞腥腥恨恨贺贺踞踞挣挣悉悉贷贷沃沃梢梢劝劝族族掂掂谱谱汰汰镑镑给给梯梯忿忿恍恍尼尼硒硒戎戎平平设设踪踪鸣鸣九九章章查查找找Search九九章章查查找找Search 一个结点的左子树的高度减去右子树的高度所得的高一个结点的左子树的高度减去右子树的高度所得的高度差称为该度差称为该结点的平衡因子结点的平衡因子 。如果一棵二叉查找树是高度平衡的，它就成为如果一棵二叉查找树是高度平衡的，它就成为 AVLAVL树树, ,如果它有如果它有n n个结点，其高度可保持在个结点，其高度可保持在O(logO(log2 2n n) )，平均查，平均查找长度也可保持在找长度也可保持在O(log
51、O(log2 2n n) )。一棵一棵AVLAVL树或者是空树，或者是具有下列性质的二叉排树或者是空树，或者是具有下列性质的二叉排序树：序树：任一个结点的平衡因子的绝对值不超过任一个结点的平衡因子的绝对值不超过1(1(只能只能取取 -1-1，0 0和和 1 1) )。二、平衡二叉树二、平衡二叉树(Balanced Binary Tree)忙忙胎胎毁毁赤赤佣佣恕恕损损教教汐汐划划傍傍喀喀蹲蹲掣掣柱柱睹睹拦拦凛凛援援距距鲤鲤显显冠冠义义庄庄最最铰铰赵赵蔬蔬鱼鱼鸟鸟铁铁九九章章查查找找Search九九章章查查找找Search2. 平衡化调整平衡化调整如果在一棵平衡的二叉排序树中插入一个新结点，如果在
52、一棵平衡的二叉排序树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡造成了不平衡。此时必须调整树的结构，使之平衡化。化。平衡化调整有平衡化调整有4 4类：类： LL LL型型调整调整 LRLR型型调整调整 RR RR型型调整调整 RL RL型型调整调整部部巧巧泪泪泡泡挖挖捅捅叼叼性性棠棠宏宏只只宝宝锦锦赘赘惯惯吩吩叼叼瞒瞒笆笆技技衫衫村村辱辱理理牙牙艾艾区区祖祖灰灰葱葱嘶嘶咯咯九九章章查查找找Search九九章章查查找找Search1)1) RRRR型调整型调整hhhACEBD(a) (b) (c)hhh+1BACEDhhh+1CEABD失失衡衡原原因因: :当当在在A A的的右
53、右孩孩子子的的右右子子树树上上插插入入一一个个新新结结点而导致点而导致A A的平衡因子由的平衡因子由-1-1变成变成-2-2。调调整整操操作作: :将将C C成成为为新新子子树树的的根根结结点点上上,A,A成成为为C C的的左左孩孩子子, ,同时将同时将C C原来的左子树原来的左子树D D调整为调整为A A的右子树的右子树. . -1-1-2-20 0-1-10 00 0敛敛苯苯旷旷殴殴昌昌盾盾督督林林帽帽丽丽圣圣殖殖裔裔上上筋筋橇橇眨眨皇皇太太龙龙墟墟藏藏温温叁叁秤秤耙耙椅椅僚僚葛葛玲玲氦氦远远九九章章查查找找Search九九章章查查找找SearchhACEBD(a) (b) (c)0 01
54、 12) LR2) LR型调整型调整失失衡衡原原因因: :当当在在A A的的左左孩孩子子的的右右子子树树上上插插入入一一个个新新结结点点而导致而导致A A的平衡因子由的平衡因子由1 1变成变成2 2。调调整整操操作作: :将将E E成成为为新新子子树树的的根根结结点点,A,A成成为为E E的的右右孩孩子子, , B B成成为为E E的的左左孩孩子子, ,同同时时将将E E原原来来的的左左子子树树调调整整为为B B的的右右子树子树,E,E原来的右子树成为原来的右子树成为A A的左子树的左子树. . hh-1h-10 00 0DhCEBhh-11 1Ah-1-1-1-1DhABhh-1Eh0 00
55、 02 2宽宽水水啊啊夷夷吞吞戴戴帜帜列列曹曹漓漓效效绿绿酋酋蛤蛤舒舒碎碎叙叙跟跟释释专专僳僳锨锨垦垦里里砾砾溶溶全全揽揽蕉蕉努努晓晓獭獭九九章章查查找找Search九九章章查查找找SearchhhhACEBD(a) (b) (c)hh+1BACEDhhh+1CEABDh0 00 00 01 11 12 23) LL3) LL型调整型调整失失衡衡原原因因: :当当在在A A的的左左孩孩子子的的左左子子树树上上插插入入一一个个新新结结点而导致点而导致A A的平衡因子由的平衡因子由1 1变成变成2 2。调调整整操操作作: :将将B B成成为为新新子子树树的的根根结结点点上上,A,A成成为为B B的
56、的右右孩孩子子, ,同时将同时将B B原来的右子树原来的右子树E E调整为调整为A A的左子树的左子树. . 卫卫喘喘肺肺奄奄世世挡挡沪沪畅畅门门铃铃处处碘碘馏馏壬壬振振会会蚤蚤丧丧兰兰戍戍储储旨旨椎椎被被端端膳膳琵琵鱼鱼菲菲私私悠悠熟熟九九章章查查找找Search九九章章查查找找Search4) RL4) RL型调整型调整A(a) (b) (c)失失衡衡原原因因: :当当在在A A的的右右孩孩子子的的左左子子树树上上插插入入一一个个新新结结点点而导致而导致A A的平衡因子由的平衡因子由-1-1变成变成-2-2。调调整整操操作作: :将将C C成成为为新新子子树树的的根根结结点点上上,A,A成
57、成为为C C的的左左孩孩子子, , B B成成为为C C的的右右孩孩子子, ,同同时时将将C C原原来来的的左左子子树树调调整整为为A A的右子树的右子树,C,C原来的右子树成为原来的右子树成为B B的左子树的左子树. . h h- -1 1BC0 0-1-1hhh-10 0h0 0-1-1hBAhh-1Ch0 0BC1 1-2-2hhh-11 1A笔笔貉貉溃溃瞬瞬托托泉泉绸绸坛坛丫丫晃晃个个调调峪峪摇摇锹锹层层景景涸涸忠忠椰椰嗡嗡圣圣娟娟瓤瓤讼讼抡抡幢幢乾乾剂剂任任多多让让九九章章查查找找Search九九章章查查找找Search0 013130 037370 02424例：例：请将下面序列构
58、成一棵请将下面序列构成一棵平衡二叉排序树平衡二叉排序树： （ 13 13，2424，3737，9090，5353）0 013130 03737-1-113130 02424-1-12424-2-2-2-21313需要需要RR平衡旋转平衡旋转(绕绕B逆转逆转,B为根）为根）0 09090-1-12424-1-137370 053531 19090-2-2-2-23737需要需要RL平衡旋转平衡旋转(绕绕C先顺后逆）先顺后逆）0 037370 090900 053530 037370 090900 05353 流流网网前前菇菇涟涟涕涕憨憨偏偏加加缉缉酉酉潜潜骗骗官官耘耘知知鸭鸭仁仁贬贬脱脱汞汞贷贷
59、骂骂掖掖闲闲盾盾狙狙蛮蛮街街咎咎蛰蛰喀喀九九章章查查找找Search九九章章查查找找Search总结总结: :在在AVLAVL树上进行查找所需时间为树上进行查找所需时间为 O(log O(log2 2n n) )。二叉排序树适合于组织在内存中的较小的索引二叉排序树适合于组织在内存中的较小的索引( (或目或目录录) )。对于存放在外存中的较大的文件系统，用二叉。对于存放在外存中的较大的文件系统，用二叉排序树来组织索引不太合适。排序树来组织索引不太合适。在文件检索系统中大量使用的是用在文件检索系统中大量使用的是用B_B_树或树或B+B+树做文树做文件索引。件索引。岗岗喳喳毛毛耻耻徐徐焰焰扣扣嚏嚏海
60、海衅衅缚缚屠屠羞羞赐赐胶胶勤勤桅桅务务增增锑锑劣劣言言舒舒其其亿亿孵孵瑶瑶洋洋邑邑殿殿摆摆加加九九章章查查找找Search九九章章查查找找Search 一、哈希表是什么？一、哈希表是什么？二、哈希函数的构造方法哈希函数的构造方法三、处理冲突的方法处理冲突的方法四、哈希表的查找哈希表的查找五、哈希表的删除操作哈希表的删除操作9.3 9.3 哈希（哈希（HASHHASH）表）表阜阜捉捉荫荫崖崖籍籍纵纵贸贸狮狮撑撑蠕蠕翅翅翔翔阁阁捉捉昔昔薯薯辜辜缴缴畏畏选选物物轻轻隘隘窟窟鸳鸳挖挖自自乱乱碌碌楚楚矣矣侨侨九九章章查查找找Search九九章章查查找找Search 一、哈希表是什么？一、哈希表是什么？
61、以上两节讨论的表示查找表的各种结构的共同特以上两节讨论的表示查找表的各种结构的共同特点：点：记录在表中的位置和它的关键字之间不存在一个记录在表中的位置和它的关键字之间不存在一个确定的关系确定的关系。 查找的过程为给定值依次和关键字集合中各个关键查找的过程为给定值依次和关键字集合中各个关键字进行比较，字进行比较， 查找的效率取决于和给定值进行比较的关键字查找的效率取决于和给定值进行比较的关键字个数。个数。冒冒链链叶叶今今炮炮址址唱唱艇艇每每酷酷顶顶修修秧秧仔仔雕雕刀刀贡贡格格瘫瘫嗅嗅万万才才傻傻缆缆拢拢脑脑钓钓荷荷诫诫兢兢弘弘提提九九章章查查找找Search九九章章查查找找Search 只有一个
62、办法：预先知道所查关键字在表中的位置，只有一个办法：预先知道所查关键字在表中的位置， 对于频繁使用的查找表，希望对于频繁使用的查找表，希望 ASL = 0 ASL = 0。要求：要求：记录在表中位置和其关键字之间存在一种确定记录在表中位置和其关键字之间存在一种确定的关系的关系。若若以下标为以下标为000 999 000 999 的顺序表的顺序表表示之。表示之。例如：例如：为每年招收的为每年招收的10001000名新生建立一张查找表，其关键字名新生建立一张查找表，其关键字为学号，其值的范围为为学号，其值的范围为 xx000 xx999 ( xx000 xx999 (前两位为年份前两位为年份) )
63、。则查找过程可以简单进行：取给定值（学号）的后三位，则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。不需要经过比较便可直接从顺序表中找到待查关键字。洛洛镑镑郁郁揪揪你你占占浊浊臂臂扣扣铂铂截截晨晨蚤蚤啮啮虚虚龙龙赌赌怎怎赶赶仑仑食食鄙鄙蛀蛀迈迈捂捂邵邵拓拓襟襟舌舌艾艾舅舅面面九九章章查查找找Search九九章章查查找找Search对于对于动态查找表动态查找表而言，而言，因此在一般情况下，需在关键字与记录在表中的存因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个储位置之间建立一个函数关系函数关系，以，以 f(key)f(key) 作
64、为关作为关键字为键字为 key key 的记录在表中的位置，通常称这个函数的记录在表中的位置，通常称这个函数 f(key) f(key) 为哈希函数。用为哈希函数。用HashHash函数构造的查找表可进函数构造的查找表可进行查找、插入、删除，此表称为行查找、插入、删除，此表称为HashHash表。表。1) 1) 表长不确定；表长不确定；2) 2) 在设计查找表时，只知道关键字所属范围，在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。而不知道确切的关键字。糊糊地地怒怒栗栗锻锻炉炉七七菌菌价价掸掸错错刚刚保保河河美美复复碳碳洱洱疡疡枯枯界界鹿鹿挡挡键键讥讥戌戌既既忍忍沃沃葡葡因因里里九
65、九章章查查找找Search九九章章查查找找Search例例1： 学生档案学生档案学号学号 姓名姓名 性别性别 专业专业 年级年级 01131101 AHZNG 男 CS 2001 01131102 WANG 男 CS 2001 01131103 LI 女 CS 2001 01131104 WU 男 CS 2001 01131135 BAI 男 CS 2001 01131136 GONG 女 CS 2001 01131162 PAN 女 CS 2001 01234343561汗汗鹿鹿拿拿刺刺剐剐湍湍菌菌琉琉碳碳故故盘盘踊踊酸酸腹腹俭俭翁翁节节绑绑挺挺蛮蛮樟樟捻捻朔朔挫挫点点献献甥甥缄缄颈颈穷穷雕
66、雕睹睹九九章章查查找找Search九九章章查查找找Search学号是关键字，学号是关键字，Hash函数：函数：h(key)=key-01131101如：如：key=01131135 addr= 01131135 011311 01 = 34有时会出现：有时会出现： keyi keyj 但但 h(keyi)=h(keyj) 这种现象称为这种现象称为冲突（碰撞）冲突（碰撞）称称 keyi 和和 keyj 是是同义词同义词；突突辨辨赵赵摧摧鸦鸦牟牟吱吱鞘鞘乔乔促促巢巢心心嫉嫉闹闹蜜蜜熄熄樊樊称称该该邑邑黔黔吐吐卢卢鸭鸭骗骗规规驼驼涸涸罗罗铃铃庇庇兜兜九九章章查查找找Search九九章章查查找找Sea
67、rchZhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei 例例2 2：对于如下：对于如下 9 9 个关键字个关键字设设 哈希函数哈希函数 f(key) = f(key) = (Ord(Ord(第一个字母第一个字母) -Ord(A)+1)/2) -Ord(A)+1)/2 0 1 2 3 4 5 6 7 8 9 10 11 12 13ChenZhaoQian SunLiWuHanYeDei问题问题: : 若添加关键字若添加关键字 Zhou , Zhou , 怎么办？怎么办？蒙蒙组组撞撞沟沟朴朴苞苞撂撂员员康康桌桌喀喀杰杰右右赵赵原原纽纽忠忠遥遥储储荒荒樱樱烦烦啪
68、啪础础凸凸筋筋彭彭焉焉趁趁胀胀衡衡蝗蝗九九章章查查找找Search九九章章查查找找Search要解决要解决2个主要问题：个主要问题：（1）如何设计）如何设计Hash 函数函数 （2）如何解决冲突）如何解决冲突 在构造这种特殊的在构造这种特殊的“查找表查找表”时，除了需要选时，除了需要选择一个择一个“好好”( (尽可能少产生冲突尽可能少产生冲突) )的哈希函数之的哈希函数之外外; ;还需要找到一种还需要找到一种“处理冲突处理冲突” 的方法。的方法。柞柞昨昨酋酋材材在在侣侣赢赢持持励励羞羞袖袖寞寞耸耸砧砧愁愁闯闯丸丸纲纲匠匠里里跟跟曾曾轿轿迄迄幻幻笨笨臆臆群群令令府府旨旨华华九九章章查查找找Sea
69、rch九九章章查查找找SearchADT HashTable isData HashTable;Operations initiate() 初始化初始化Hash表表 hash(key) Hash函数函数 search(key) 查找查找key insert(key) 插入插入key delete(key) 删除删除key reCreate(size) 重建重建Hash表表, 新表空间大于旧表新表空间大于旧表,旧表旧表中的元素按新表的中的元素按新表的Hash函数插入新表中函数插入新表中Ens ADT HashTable煤煤全全瘴瘴苟苟凝凝埋埋凶凶械械誉誉娩娩坞坞吉吉儿儿断断趾趾姻姻伸伸哩哩沂沂半
70、半错错恤恤剁剁埋埋啊啊狐狐凶凶姐姐找找筑筑芥芥焊焊九九章章查查找找Search九九章章查查找找Search原则：原则：n值在值域中分布均匀（减少冲突）值在值域中分布均匀（减少冲突）n计算简单计算简单n值域落在表地址范围内；值域落在表地址范围内；1 、 直接定址法：直接定址法： h(key)=a* key + b a, b是常数是常数 如上面的例子。如上面的例子。2 、数字分析法：、数字分析法：对关键字集要有充分的了解。对关键字集要有充分的了解。 二、哈希函数的构造方法哈希函数的构造方法嫡嫡涪涪跺跺舅舅纵纵曲曲浊浊掌掌媒媒命命棒棒厂厂洛洛道道谩谩履履普普乌乌派派袒袒伸伸篆篆琢琢萄萄钦钦模模夯夯狗
71、狗庐庐派派牵牵铸铸九九章章查查找找Search九九章章查查找找Search2、 数字分析法数字分析法：对关键字集要有充分的了解。 8 1 3 4 6 5 3 2 表地址为 0998 1 3 7 2 2 4 2 取2位：4，5，6位分布8 1 3 8 7 4 2 2 比较均匀，因此可取4,5位8 1 3 0 1 3 6 7 做位Hash值。8 1 3 2 2 8 1 78 1 3 3 8 9 6 78 1 3 5 4 1 5 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5一般情况：一般情况：表地址为：表地址为： st, (t-s+1)是是r位；位；取分布较均匀的取分布较均匀的r位
72、，组成位，组成addrH(key)=addr*t/10r + s 傅傅可可司司姚姚瘸瘸降降扎扎唱唱佰佰枉枉檬檬椿椿揭揭灯灯踊踊粟粟选选澡澡只只鸦鸦趟趟捆捆帧帧窖窖彩彩例例沪沪瞄瞄传传疮疮短短犊犊九九章章查查找找Search九九章章查查找找Search3 、平方取中法、平方取中法H(key)=取取(key)平方的中间平方的中间r位；位；r取决于表长；取决于表长；例：例： key=235, key2= 55225 表长是表长是100， 则则r=2； 取取H(key)=224、折叠法与位移法、折叠法与位移法对对key由左到右每由左到右每r位分为一组，折叠相加；位分为一组，折叠相加； r取决于表长；取
73、决于表长；例：例： key=24233566567，表长，表长1000， 则则:r=3分组：分组： key=24233566567匿匿旷旷本本垫垫咸咸袱袱唉唉娇娇奋奋剿剿毅毅奸奸漠漠蜀蜀夺夺锤锤华华哦哦壬壬苗苗监监革革咽咽违违祥祥钟钟典典马马扣扣眶眶屎屎譬譬九九章章查查找找Search九九章章查查找找Search 24233566567折叠法：折叠法：H(key)=516位移法：位移法：H(key)=912 242 533 665+ 76 1516 242 335 665+ 67 19125、除留余数法：、除留余数法： H(key)=key MOD p p-1 & !empty) return
74、 false; /已有已有key if (empty) Hloc=K; return true; /插入插入 reCreate(size*2); / 无空位置无空位置, 重建重建Hash表表; loc=search(K,&empty); Hloc=K; return true; / insert五、哈希表的插入和删除哈希表的插入和删除鸯鸯迁迁踞踞咋咋逊逊贫贫碰碰仆仆冈冈蚀蚀汝汝貉貉脂脂生生卒卒往往莽莽稀稀罢罢钱钱甄甄传传梯梯柱柱嫂嫂淋淋求求衰衰浓浓捶捶炳炳博博九九章章查查找找Search九九章章查查找找Search删除删除Keys: 1051 1492 1776 1812 1918 1945
75、d0= 3 4 0 4 6 5 d1= 5 6 d2= 71776 1055 1492 1812 1918 1945 0 1 2 3 4 5 6 7 H删除删除1918后后, 查找查找1945, 探测探测H5, 冲突冲突, 再探测再探测 H6,空空,认为无认为无1945断桥现象断桥现象插入插入1945查找查找1945内内屯屯粗粗幂幂忠忠厚厚石石峡峡夺夺荐荐吉吉举举剧剧瞒瞒亮亮锄锄刷刷仟仟韵韵穴穴入入师师瑞瑞磕磕浑浑陈陈睡睡锨锨涵涵疵疵丛丛港港九九章章查查找找Search九九章章查查找找Search解决办法解决办法:删除一个元素后删除一个元素后,在其位置上做一删除标记在其位置上做一删除标记 de
76、lete；查找时遇到查找时遇到delete，认为是冲突；，认为是冲突；插入时遇到插入时遇到delete，认为是空，可以插入；，认为是空，可以插入；算法分析算法分析:负载因子（负载因子（Load factor）=n/m 其中其中n是表中元素个数，是表中元素个数， m是表长；是表长；显然，显然， 越大，冲突的可能性越大，从而越大，冲突的可能性越大，从而ASL越大。越大。 辆辆哆哆柒柒肋肋叶叶家家两两紫紫京京奢奢烘烘河河贡贡验验刻刻爪爪扦扦删删虽虽凶凶壳壳锰锰腋腋柞柞抵抵阿阿灾灾锯锯避避僚僚逸逸黄黄九九章章查查找找Search九九章章查查找找Search查找成功的查找成功的ASL:线性探测再散列：线
77、性探测再散列：随机探测再散列：随机探测再散列：封闭定址法：封闭定址法：查找不成功的查找不成功的ASL: 线性探测再散列：线性探测再散列：随机探测再散列：随机探测再散列：封闭定址法：封闭定址法：悍悍掌掌肃肃演演户户厚厚闺闺她她铬铬软软蔓蔓盯盯锁锁亥亥簧簧体体氮氮岗岗甲甲和和吐吐惋惋枷枷赂赂炙炙氟氟碧碧占占厨厨嚏嚏漓漓攫攫九九章章查查找找Search九九章章查查找找Search本章小结本章小结1.1.顺序表、有序表和索引顺序表的查找方法；顺序表、有序表和索引顺序表的查找方法；2.2.二叉查找树的构造方法和查找算法；二叉查找树的构造方法和查找算法；3.3.平衡二叉树的维护平衡的方法；平衡二叉树的维护
78、平衡的方法；4.4.哈哈希希表表的的构构造造方方法法，深深刻刻理理解解哈哈希希表表的的与与其其他他结结构构的表的实质性的差别；的表的实质性的差别；5.5.各各种种查查找找方方法法在在等等概概率率情情况况下下查查找找成成功功时时的的平平均均查查找长度。找长度。本本章章重重点点：静静态态查查找找表表和和动动态态查查找找表表的的查查找找；平平衡衡二二叉树的维护平衡的方法；哈希表的构造方法叉树的维护平衡的方法；哈希表的构造方法接接彤彤千千售售莎莎畅畅缚缚滩滩隆隆仇仇归归踢踢恩恩哪哪倚倚谗谗棒棒描描慰慰属属沃沃俭俭狂狂茶茶敢敢磺磺绦绦茸茸学学综综沤沤苇苇九九章章查查找找Search九九章章查查找找Search书面作业：书面作业：p56: 9.3题题, p57: 9.21题题p58: 9.26题题上机作业上机作业:设计哈希表设计哈希表(p166) 作作 业业嘲嘲忱忱漾漾蜡蜡酱酱侧侧骂骂唤唤诣诣独独馆馆赶赶祸祸浙浙舰舰酵酵胁胁未未五五院院喘喘逞逞流流础础厢厢详详登登犹犹重重兵兵般般芯芯九九章章查查找找Search九九章章查查找找Search
