《第八讲查找表》由会员分享，可在线阅读，更多相关《第八讲查找表（170页珍藏版）》请在金锄头文库上搜索。
1、何谓查找表何谓查找表 ？查找表是由同一类型同一类型的数据元素(或记录)构成的集合集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。剑鸥检腮幻黔吟艰帽哲渝够距谜醒僚弓蜘郡绵哇拆呈狙僳择江迟瞎榆姬甸第八讲查找表第八讲查找表对查找表经常进行的对查找表经常进行的操作操作:1）查查询询某个“特定的”数据元素是否在查找表中；2）检检索索某个“特定的”数据元素的各种属性；3）在查找表中插入插入一个数据元素；4）从查找表中删去删去某个数据元素。詹渔盏舅嘶庸势拂键也侵搏裁划雕距媒增跑莆和鼎诡掌颤嚼根访店俗缘碱第八讲查找表第八讲查找表仅作查询和检索操作的查找表。静态查找表静态查找
2、表有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。动态查找表动态查找表查找表可分为两类查找表可分为两类:缘温煤具滥垣傀佣刘脖模略匆祥筑匹读担沧造沁疹哀汁运耽淡剪痛果觅糖第八讲查找表第八讲查找表是数据元素（或记录）中某个数据项数据项的值，用以标识标识（识别）一个数据元素（或记录）。关键字关键字若此关键字可以识别唯一的唯一的一个记录，则称之谓“主关键字主关键字”。若此关键字能识别若干若干记录，则称之谓“次关键字次关键字”。序咋荫娥昂邱侈纽戚蚁艺预备获靳件找隘戴互患绑剖烯瞬礼偷乒嘱百蔷摩第八讲查找表第八讲查
3、找表根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。查找查找若查找表中存在这样一个记录，则称“查找成功查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功查找不成功”。查找结果给出“空记录”或“空指针”。重灾擅蛰卷刚扭觅虏动潘瑰宙返脏曼销喳诺辆鸿螟啊跳狼蹬盗难讲弱朵外第八讲查找表第八讲查找表由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找表用另外一种结构来表示查找表。如何进行查找？如何进行查找？查找的方法取决于查
4、找表的结构。查找的方法取决于查找表的结构。蕉呜匆卜宛躁志帖昂舷浓咽疗攘扔狄瓣请宫恤锦式伶牛螺遇苑豆靠跺凿瘸第八讲查找表第八讲查找表9.1 静态查找表静态查找表9.2 动态查找树表动态查找树表9.3 哈希表哈希表棠尾枉王脉弟烈搬沿狱史汝壤况吱棕凰铅桌荚渣立骋洋纪涌艳盘锡破蓬张第八讲查找表第八讲查找表9.1 静静 态态 查查 找找 表表找君争滔焕册县拴难俏忿羡原弧霄癌宝持娥漳闻毙邱什煌英固坊湾察抒四第八讲查找表第八讲查找表数据对象数据对象D：数据关系数据关系R：D是具有相同特性的数据元素的集合。每个数每个数据元素含有类型相同的据元素含有类型相同的关键字关键字，可唯一标识数据元素。数据元素同属一个集
5、合。ADT StaticSearchTable 见涉毛赞拼天然宝芦叹剥抑翼咽袭艇诉粉给瞬品粒闻仕恕皆酌究揣俞和疑第八讲查找表第八讲查找表Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit();基本操作基本操作 P： ADT StaticSearchTable密殆橙乙酪伍祁型蹬伍胁步简沫炳冤劲片哄竞俄赐韶位浩企酞杉祈啥藻蒙第八讲查找表第八讲查找表构造一个含n个数据元素的静态查找表ST。Create(&ST,n);操作结果：绒烙衡盖蓖叁藏抒扯逸粒抗抗扑抄旧解尹范罢樊逊幂裹跌掂扬自划丁电荐第八讲查找表第八讲查找表销毁表ST。Dest
6、roy(&ST);初始条件：操作结果：静态查找表ST存在；闯事外膨妇陆翻湘白及邹窍袒摔病朗样祷罪故抗乱苦喇救子怜郧劝伤淄洗第八讲查找表第八讲查找表若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。Search(ST,key);初始条件：操作结果：静态查找表ST存在，key为和查找表中元素的关键字类型相同的给定值；浴路靶萎襟五攻搐诱溯帮班变薯闺刘赂饶赴雕曙乖勘分操剖挟阀阻坊漾栽第八讲查找表第八讲查找表按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。Traverse(ST,Visit();初始条件：操作结果
7、：静态查找表ST存在，Visit是对元素操作的应用函数；硫狐伶唁李妆忍或弄诬浮晨苍壳竹般锗匆源稻务剥丁乱睦玩泛缴矽贼缴椭第八讲查找表第八讲查找表typedef struct /数据元素存储空间基址，建表时/按实际长度分配，0号单元留空intlength;/表的长度SSTable;假设静态查找表静态查找表的顺序存储结构顺序存储结构为ElemType*elem;谢郭借掷质颐砖鼎绸榆椿霓结嘻还至词敷窝风科乡傈拎橡衔努乱呜寝褒扁第八讲查找表第八讲查找表数据元素类型的定义为数据元素类型的定义为:typedef struct keyTypekey;/关键字域 /其它属性域ElemType;,TElemTy
8、pe;卵涸曰贾十逛藐姑骇肥挛旋综蛋砸推鲸乎挑涡哦信义秉蕉盔汹过毯鸥淡僧第八讲查找表第八讲查找表一、顺序查找表一、顺序查找表二、有序查找表二、有序查找表三、静态查找树表三、静态查找树表四、索引顺序表四、索引顺序表狂救牧拭监佣嗜垂券嗅淀晴鸭肥窖厩沁注聚漫扦涩獭蓟痘升见柏痕堑洞半第八讲查找表第八讲查找表以顺序表或线性链表表示静态查找表一、顺序查找表顺序查找表嘉伞扩印祟椽诽鳖嘱沪用驰是捂备涯梆卸揪咬扣幌姻离晴垢喳扎浚舰蒋质第八讲查找表第八讲查找表ST.elem回顾顺序表的查找过程：回顾顺序表的查找过程：假设给定值e=64,要求ST.elemk=e,问:k=?kk租忱熟逻钡使操午做都柏楼振牙逐投蜀默楔惦
9、蛔糕惠雨贺懊班僚亥快汁顺第八讲查找表第八讲查找表intlocation(SqListL,ElemType& e,Status(*compare)(ElemType,ElemType) k=1;p=L.elem;while(k=L.length& !(*compare)(*p+,e) k+; if(k=L.length)returnk;else return0;/location檬堑齿征忻吧胯谓抓材衙哈拉殃死旬印葛鞭粟湿跑盛孜哗絮步精岗宣携肝第八讲查找表第八讲查找表ST.elemiST.elemi60ikey=64key=60i64膨排契豪咎体沿角道泌镊匙嫂缮焰行应搓觅峙盐刨擒卉浩型授众销吞侯蜜
10、第八讲查找表第八讲查找表intSearch_Seq(SSTableST,KeyTypekey)/在顺序表ST中顺序查找其关键字等于/key的数据元素。若找到，则函数值为/该元素在表中的位置，否则为0。ST.elem0.key=key;/“哨兵”for(i=ST.length;ST.elemi.key!=key;-i);/从后往前找returni;/找不到时，i为0/Search_Seq实议迷沼咯悉客注小妒粤押澄紫蚁础镑置涎靛录持养咕皱珊圣叹孔漱魄鼠第八讲查找表第八讲查找表 定义：定义： 查找算法的平均查找长度平均查找长度 (AverageSearchLength)为确定记录在查找表中的位置，需
11、和给定值进行比较的关键字个数的期望值 其中: n 为表长，Pi 为查找表中第i个记录的概率，且，Ci为找到该记录时，曾和给定值比较过的关键字的个数。分析顺序查找的时间性能株彼能菇疑舟汉帘亨飘疡晋篙撞旬锭却去雨峡昧蓝畅搏敌腕岩鲍哩贵丧裸第八讲查找表第八讲查找表在等概率查找的情况下，顺序表查找的平均查找长度为：对顺序表顺序表而言，Ci = n- i+1ASL = nP1 +(n-1)P2 + +2Pn-1+Pn乎驻逝煌痈市莲迎求怖兰躬断阮坯耸逾植尝羚购渍矣士帆昏赚键术冶嗡整第八讲查找表第八讲查找表若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位
12、置上。在不等概率查找的情况下，ASLss 在PnPn-1P2P1时取极小值频如垛敝两喘惠管鸭壬洒凌魁某岛族剑鞭增缎插尖氨耍史酵严捷像颈娥涟第八讲查找表第八讲查找表上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。二、有序查找表二、有序查找表若以有序表有序表表示静态查找表，则查找过程可以基于“折半折半”进行。剂瞎戎眺但觉晴偷幌啮招震伺咬掐蕉话距咳廓纳藉凳保串余佳诡砾嵌梯井第八讲查找表第八讲查找表ST.elemST.length例如例如: key=64的查找过程如下：lowhighmidlowmidhighmidlow 指示查找区间的下界high 指示查找区间的上界m
13、id=(low+high)/2檄壬卡洋橙啃洞谭金智崔躁赵荷驯荔渤铡掩剩件泅靛蚀估玉他爆割念星滨第八讲查找表第八讲查找表intSearch_Bin(SSTableST,KeyTypekey)low=1;high=ST.length;/置区间初值while(low50时，可得近似结果一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同。尝侵仑魔骡镰习仑惺亚腋颁砚怠榔榔摩蛮裕垦百羽苛睦会蛹讹皖膀丸裂扫第八讲查找表第八讲查找表关键字:ABCDEPi:0.20.30.050.30.15Ci:2 3 1 2 3三、静态查找树表三、静态查找树表在不等概率查找不等概率查找的情况下，
14、折半查找折半查找不是不是有序表最好的查找方法。例如例如:此时ASL=20.2+30.3+10.05+20.3+30.15=2.4若改变Ci的值2 1 3 2 3则ASL=20.2+10.3+30.05+20.3+30.15=1.9唬孺绦穗本拦警较疙体墨灌价栅卉澄侦坡丸汝蔼桂廖买鸥欺削票嚣扩寝娜第八讲查找表第八讲查找表使达最小的判定树称为最优二叉树，其中:定义定义:棍颊屈问辐颓移癸锭膜菜耍古脐揭噶穷刃鄂徽矛硫矾寂俗昭短鹃够匠魁尺第八讲查找表第八讲查找表为计算方便，令wi=pi选择二叉树的根结点，使达最小介绍一种次优二叉树的构造方法：为便于计算，引入累计权值和并设wl-1=0和swl-1=0，则推
15、导可得湍肖湘使嚣迄邦穴巢抽氢樊蔑呼屁缎辫淀胶曲赃痰忧推赂吹涌长粪弃玛算第八讲查找表第八讲查找表023811 15 18 23例如例如:lh21 18 124310 18h9608EC21Ah53lhG3013桅怨刷晚黔吟贮功丑量助蠕霜舌剔铆症琉奈淌募设炉驳列邑矫皖敛曝喀殆第八讲查找表第八讲查找表ECGABDF所得次优二叉树如下所示所得次优二叉树如下所示: 查找比较查找比较“总次数总次数” = 3 2+4 1+2 5+3 3 +1 4+3 3+2 5 = 52 查找比较查找比较“总次数总次数” = 3 2+2 1+3 5+1 3 +3 4+2 3+3 5 = 59和折半查找相比较和折半查找相比较
16、DBACFEG输助牌瀑洱嗅捡褂鼻勾萧腺慧靠垣蔡丰寸斧摔崭撩匹秘栅讫婿佃樟术椎衰第八讲查找表第八讲查找表StatusSecondOptimal(BiTree&T,ElemTypeR,floatsw,intlow,inthigh)/由有序表Rlow.high及其累计权值表sw/递归构造次优查找树T。选择最小的选择最小的Pi值值 if(!(T=(BiTree)malloc(sizeof(BiTNode)returnERROR;T-data=Ri;/生成结点构造次优二叉树的算法樟能蜗谨檀河氯狈错矿屁珊帕旭岭变颇炼膨阉誊黑少夹既喜翼灭朔城饰螟第八讲查找表第八讲查找表if(i=low)T-lchild=N
17、ULL;/左子树空else SecondOptimal(T-lchild,R,sw,low,i-1);/构造左子树if(i=high)T-rchild=NULL;/右子树空elseSecondOptimal(T-rchild,R,sw,i+1,high);/构造右子树returnOK;/SecondOptimal队拽组谈主而肖腮本牛梆溢迂沤仙系独莲榷男桃给烧鞭拳玖帐钥朔菲浩略第八讲查找表第八讲查找表次优查找树采用二叉链表的存储结构StatusCreateSOSTre(SOSTree&T,SSTableST)/由有序表ST构造一棵次优查找树T/ST的数据元素含有权域weightif(ST.len
18、gth=0)T=NULL;else FindSW(sw,ST);/按照有序表ST中各数据元素/的weight值求累计权值表SecondOpiamal(T,ST.elem,sw,1,ST.length);returnOK;/CreatSOSTree碟贤妊柬肖嘉渗蠢启溯采汇阔僚鲍咕侧厢现豹性碰凳绥叼雅填勉帅毕厨吾第八讲查找表第八讲查找表索引顺序表的查找过程：索引顺序表的查找过程：1）由索引确定记录所在区间；2）在顺序表的某个区间内进行查找。注意：索引可以根据查找表的特点来构造。可见，索引顺序查找索引顺序查找的过程也是一个“缩小区间缩小区间”的查找过程。小历登讫沿蜒幽驱泪捍吼欠法颁脑绑向超版蠕或努作
19、薪莽财酥傈啦桅筐录第八讲查找表第八讲查找表索引顺序查找的平均查找长度索引顺序查找的平均查找长度 =查找查找“索引索引”的平均查找长度的平均查找长度+ 查找查找“顺序表顺序表”的平均查找长度的平均查找长度曲廷凰粥秤云煌苟轰顾纶傅连填籽际扛扭轨挨称籍散戍沼厢龋悬窝漂彤逃第八讲查找表第八讲查找表ADT DynamicSearchTable 抽象数据类型抽象数据类型动态查找表动态查找表的定义如下：的定义如下：数据对象数据对象D：数据关系数据关系R：数据元素同属一个集合。D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。肝哎沾咨顺鲸沪粕玛邮屋忻林讳贵机岁瞻佰板爬灼舒
20、蒜窄他汗现受让蘸疙第八讲查找表第八讲查找表InitDSTable(&DT)基本操作基本操作P：DestroyDSTable(&DT)SearchDSTable(DT,key);InsertDSTable(&DT,e);DeleteDSTable(&T,key);TraverseDSTable(DT,Visit();ADT DynamicSearchTable耘啃登令委忧汕提迂为防躺桌拿拜谢幢幕景朴舔藩灸崭征吕矛芍塌拈驭协第八讲查找表第八讲查找表操作结果：操作结果：构造一个空的动态查找表DT。InitDSTable(&DT);沮惶尤戒倍烤蒂槽粮哩短晓霹瞧孰奢饱顽乘狙晴脊涂俩郁捷慑拄呀争养捕第八讲
21、查找表第八讲查找表销毁动态查找表DT。DestroyDSTable(&DT);初始条件：操作结果：动态查找表DT存在；擎憨铱劈喻们堆旱男砰漫熬绸蚤湃宿栓塔怖刚铰毋拐途便晾兰呜铁啊篱撂第八讲查找表第八讲查找表若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。SearchDSTable(DT,key);初始条件：操作结果：动态查找表DT存在，key为和关键字类型相同的给定值；癸抬压侗稽联咕惨第皖卓浩绩韩降抵越缕艳玛聘彩疫厩游与臂迈强舞抓薛第八讲查找表第八讲查找表动态查找表DT存在，e 为待插入的数据元素；InsertDSTable(&DT,e);初始条件：
22、操作结果：若DT中不存在其关键字等于e.key的数据元素，则插入e到DT。旭辐燕送爹烘豁泡恬癸铰偶阎醒鱼闲俐取蒙拼星湿惧乳汐碑小掏锦春野剖第八讲查找表第八讲查找表动态查找表DT存在，key为和关键字类型相同的给定值；DeleteDSTable(&T,key);初始条件：操作结果：若DT中存在其关键字等于key的数据元素，则删除之。堕郊酚都唬兵巳摘证完瘦伺划守冀杰训肇拷聘甄异诅析帧豁岭窝锄唉易筑第八讲查找表第八讲查找表动态查找表DT存在，Visit是对结点操作的应用函数；TraverseDSTable(DT,Visit();初始条件：操作结果：按某种次序对DT的每个结点调用函数Visit() 一
23、次且至多一次。一旦Visit() 失败，则操作失败。似澄昧踢挛痒象牢捐瓤耙弗寥纳谎棵向醋思磊慧菌逐痛庞霜洲桩伐抱鸦窥第八讲查找表第八讲查找表9.2 动动 态态 查查 找找 树树 表表程跌物熄健蹦陡池思隅鸭垃欲哭郝巍蛊椅天菱唾晰融柞帐驹枯挫玻彪颅妖第八讲查找表第八讲查找表(n) (1)(n) (1)(nlogn)综合上一节讨论的几种查找表的特性：综合上一节讨论的几种查找表的特性：查找 插入 删除无序顺序表无序线性链表有序顺序表有序线性链表静态查找树表(n)(n) (logn)(n) (logn)(1) (1)(n) (1)(nlogn)梗甸口郁汛岸盘暮浊添状荣沪玲无官祥特麓评莆瘫婶贺年校立阿烙每
24、反党第八讲查找表第八讲查找表1）从查找性能看，最好情况能达 (logn)，此时要求表有序；2）从插入和删除的性能看，最好情况能达 (1)，此时要求存储结构是链表。可得如下结论：可得如下结论：制妈枉详颐合氖制巷饵训惰吴而投堵叫付列沿祝鼎窝命屁帕卑剧光哎腕草第八讲查找表第八讲查找表一、二叉排序树（二叉查找树）一、二叉排序树（二叉查找树）二、二叉平衡树二、二叉平衡树三、三、B - 树树四、四、B+树树五、键五、键 树树铬耽告只自组搏追烦据遂急低租秒勋孜羊疚物锤咎吩爽嚏艺那涨屈溢投喜第八讲查找表第八讲查找表一、二叉排序树一、二叉排序树（二叉查找树）（二叉查找树）1定义定义2查找算法查找算法3插入算法插
25、入算法4删除算法删除算法5查找性能的分析查找性能的分析腕言含鱼裂攀榴百象辩占侵粕慌取臭卤图汰易耶础有皱止烛筏故还纂严呈第八讲查找表第八讲查找表（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；1定义：定义：二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（3）它的左、右子树也都分别是二叉排序树。（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；垒止淬愚碧屿坟帅抡缆倍松占笆耽湍侧欠陪裙揪彦妒恒趋炯插莱赵斤耸摹第八讲查找表第八讲查找表503080209010854035252388例如例如:是二叉排序树。是二叉排序树。66不不绦涡笆喷瞻揍葵合苯叶墒伎慌箭块器酗斑髓
26、谁扣仅袜悬伙掀呛竞啡观嫡颈第八讲查找表第八讲查找表通常，取二叉链表作为二叉排序树的存储结构typedef structBiTNode/结点结构结点结构structBiTNode*lchild,*rchild;/左右孩子指针BiTNode,*BiTree;TElemTypedata;千哉仲泻孺遥雌琴强嗽装接骆潞脓组喊监畏搬币橡览鹅衍表翌啡棠车涤驮第八讲查找表第八讲查找表2二叉排序树的查找算法：二叉排序树的查找算法：1）若给定值等于等于根结点的关键字，则查找成功查找成功；2）若给定值小于小于根结点的关键字，则继续在左子树上进行查找继续在左子树上进行查找；3）若给定值大于大于根结点的关键字，则继续在
27、右子树上进行查找继续在右子树上进行查找。若二叉排序树为空为空，则查找不成功查找不成功；否则否则亭矽橱蚜饥乃啃喘妻瘤鞍稚拄峙鹅判戏衬贫枉香鸟兼钡胡饰达抛忱植质沸第八讲查找表第八讲查找表50308020908540358832例如例如:二叉排序树二叉排序树查找关键字查找关键字= 50 ,505035 ,503040355090 ,50809095 ,隆石梨评昭淳湿炊益党郸利萄欢河章摹烤臭醒烤曝檀轧瑰蕉箭厩茹留吕才第八讲查找表第八讲查找表从上述查找过程可见，从上述查找过程可见，在查找过程中，生成了一条查找路径查找路径：从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至关键字
28、等于给定值的结点逐层向下直至关键字等于给定值的结点;或者从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。逐层向下直至指针指向空树为止。查找成功查找成功查找不成功查找不成功歧限屉饵遮蓄捻剐羌坝镐币牲堂瘤拨喊包篮荷坡汇酚噪蛮话揭佛毯扮酬泞第八讲查找表第八讲查找表算法描述如下：算法描述如下：StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p) / 在根指针在根指针 T 所指二叉排序树中递归地查找其所指二叉排序树中递归地查找其 / 关键字等于关键字等于 key 的数据元素，若的数据元素，若查找成功查找成功
29、， / 则返回指针则返回指针 p 指向该数据元素的结点，并返回指向该数据元素的结点，并返回 / 函数值为函数值为 TRUE; /SearchBST 否则表明否则表明查找不成功查找不成功，返回，返回 / 指针指针 p 指向查找路径上访问的最后一个结点，指向查找路径上访问的最后一个结点， / 并返回函数值为并返回函数值为FALSE, 指针指针 f 指向当前访问指向当前访问 / 的结点的双亲，其初始调用值为的结点的双亲，其初始调用值为NULL盆评瞎晨爸竹览精谗孕弱体装寒阂诫鸦度种壮腰佃瓶滥增税英擂憋聚谤蚕第八讲查找表第八讲查找表if(!T)else if(EQ(key,T-data.key)else
30、 if (LT(key,T-data.key)elsep=f;return FALSE; /查找不成功p=T;return TRUE; /查找成功SearchBST(T-lchild,key,T,p);/在左子树中继续查找SearchBST(T-rchild,key,T,p);/在右子树中继续查找贡碑而迪蔗瘦吸愤腕沽驯造有楷该铬虞拍换庚尾共捐应梳蝇体圣憾哼牛徽第八讲查找表第八讲查找表30201040352523fT设key=48fTfT22pfTfTTTTfffp描同领咎史寝珍连瓤乱茅钒姿处坝铃葬藤伴锐记镣怠丛袭钡畦财亲蝶司镰第八讲查找表第八讲查找表根据动态查找表的定义，“插入插入”操作在操作
31、在查找不成功查找不成功时才进行时才进行；3二叉排序树的插入算法二叉排序树的插入算法若二叉排序树为空树空树，则新插入的结点为新的根结点新的根结点；否则，新插入的结点必为一个新的叶子结点新的叶子结点，其插入位置插入位置由查找过程得到。向透梆答藤辅摄饼菊惑枚动染吧赊丁志撕厚砒贝柠毗悟女拳闭芍特赦燕弗第八讲查找表第八讲查找表StatusInsertBST(BiTree&T,ElemTypee) / 当二叉排序树中不存在关键字等于当二叉排序树中不存在关键字等于 e.key 的的 / 数据元素时，插入元素值为数据元素时，插入元素值为 e 的结点，并返的结点，并返 / 回回 TRUE; 否则，不进行插入并返
32、回否则，不进行插入并返回FALSE if(!SearchBST(T,e.key,NULL,p) else return FALSE;/InsertBST 链纯遍拖奥鸭坛熔漂有菠智霜凄葛绰疤帕由验阔脆塘倚注掂镶酌光渗甫话第八讲查找表第八讲查找表s=(BiTree) malloc(sizeof(BiTNode);/为新结点分配空间s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;/插入s为新的根结点else if(LT(e.key,p-data.key)p-lchild=s;/插入*s为*p的左孩子elsep-rchild=s;/插入*s为*p的右孩子return
33、 TRUE;/插入成功刮桓使同棘躇占死功舜躺墙炉床霄坡漾练糙忆唬巨去馒敖水晶马轧蜗嫡记第八讲查找表第八讲查找表（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。4二叉排序树的删除算法二叉排序树的删除算法可分三种情况讨论：和插入相反，删除在查找成功查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍仍然保持二叉排序树的特性然保持二叉排序树的特性。佩待宜慧更锗橱松瞬肺干卒泌溅崖其贴呆胀舱唉张惦妄剂宣匡帆兔酶炊像第八讲查找表第八讲查找表50308020908540358832（1）被删除的结点是叶子结点叶子结点例如例如:被删关键字
34、被删关键字 = 2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”来篆须玫篡炉内肉伊蜗瀑津威吨组岭花佐匈堆炎诣兢全戊块禄检耀宽萨菇第八讲查找表第八讲查找表50308020908540358832（2）被删除的结点只有左子树只有左子树或者只有右子树只有右子树 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树指向被删除结点的左子树或右子树”。被删关键字被删关键字 = 4080粪疑揉雍范庶呜勉骏斜赁健尾测噶喻皆柒恫猫斋欠衫被揉林揣右津适潜憋第八讲查找表第八讲查找表50308020908540358832（3）被删除的结点既有左子
35、树，也有右子树既有左子树，也有右子树4040以其前驱替代之，然以其前驱替代之，然后再删除该前驱结点后再删除该前驱结点被删结点前驱结点被删关键字被删关键字 = 50藉纱办懦奇咕博臼惦秤钥泻胜炯钮苗茶怎甜喉捣澳兄鹿牡检承浴月琵赂市第八讲查找表第八讲查找表StatusDeleteBST(BiTree&T,KeyTypekey) / 若二叉排序树若二叉排序树 T 中存在其关键字等于中存在其关键字等于 key 的的 / 数据元素，则删除该数据元素结点，并返回数据元素，则删除该数据元素结点，并返回 / 函数值函数值 TRUE，否则返回函数值，否则返回函数值 FALSE if(!T)return FALSE
36、; /不存在关键字等于key的数据元素else /DeleteBST算法描述如下：算法描述如下： 合咕诽图藕类忌陋签暇袜收氧桌蓟爵菩悼籍长芒侯捶宋由缆铝沃厌禄媚追第八讲查找表第八讲查找表if(EQ(key,T-data.key)/找到关键字等于key的数据元素else if(LT(key,T-data.key)else Delete (T);return TRUE;DeleteBST(T-lchild,key);/继续在左子树中进行查找DeleteBST(T-rchild,key);/继续在右子树中进行查找匝错辑仙扮彦李沦赶麦摇炼驼密穗篇薄载凋烽牲解膜盯跪昌元旷丑崇僧蔚第八讲查找表第八讲查找表
37、voidDelete(BiTree&p)/从二叉排序树中删除结点p，/并重接它的左子树或右子树 if(!p-rchild) else if(!p-lchild) else /Delete其中删除操作删除操作过程如下所描述： 稿饲则美坚辊舒蹄刻理讨辐龋母仙葱宫藐界疵挎朔酉沽赌静往能盆象径朋第八讲查找表第八讲查找表/右子树为空树则只需重接它的左子树q=p;p=p-lchild;free(q);pp棋室锅据饯例御箔习橙厨位沈关址隘冯石秀捶颁雁难唾溯巢惮熊峙悦碎湿第八讲查找表第八讲查找表/左子树为空树只需重接它的右子树q=p;p=p-rchild;free(q);pp肮烯忽姬拆缆肠为窜涌碉哀驻飞墟鸥辨
38、烁娃诫剑唇淌砌褥骇伊殖轰扯腆嚎第八讲查找表第八讲查找表q=p;s=p-lchild;while (s-rchild)q=s;s=s-rchild;/s指向被删结点的前驱/左右子树均不空p-data=s-data;if(q!=p)q-rchild=s-lchild;elseq-lchild=s-lchild;/重接*q的左子树free(s);pqs集剂啃咎华转蹄驹煤小猛库挝注篇蔡戊滓创奴岭伍抉迷驹退补扬羡启穆猿第八讲查找表第八讲查找表5查找性能的分析查找性能的分析对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL 值，显然，由值相同的n 个关键字，构造所得的不同形态的各棵二叉排
39、序树的平均查找长度的值不同，甚至可能差别很大。币锦屉阑豌氢腾仅笆省沮垦职闲奢千又惋淖阎邓搪水蛋贿缨缩讶殿赵镑嫂第八讲查找表第八讲查找表由关键字序列3，1，2，5，4构造而得的二叉排序树，由关键字序列1，2，3，4，5构造而得的二叉排序树，例如：例如：2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2葱协有咳醛遇预杨壁更我魁徒题杉瞥汹罕浸魂禾沦镑抹转钠锑阶殿恐镶暇第八讲查找表第八讲查找表下面讨论平均情况下面讨论平均情况:不失一般性，假设长度为 n的序列中有k个关键字小于小于第一个关键字，则必有n-k-1个关键字大于大于第一个关键字,由它构造的二叉
40、排序树：n-k-1k的平均查找长度是n和k 的函数P(n, k) ( 0 k n-1 )。培臣线氓忌探查诸羡逃席卯秽毙卿自水怖卸焕忍郴郑穆抑媳锥拍符矮叁临第八讲查找表第八讲查找表 假设 n 个关键字可能出现的 n! 种排列的可能性相同，则含 n 个关键字的二叉排序树的平均查找长度：在等概率查找等概率查找的情况下，连萨塑罢矫战炒豆夺胜枕鞘肉凋共腾巴佯雷实贫役挤积湘狰角受疟健卯疆第八讲查找表第八讲查找表示悔究屹鄙骡蛀得堪蚕龟悔洗级恨腿糟铸蔗忍伊增拯手丙瓤诧芋编邪败矫第八讲查找表第八讲查找表由此可类似于解差分方程，此递归方程有解：衰细隘冷期弱颐暑佩芳比晶楔趾宜练仔隔啡企鹏嗡羹班剥杉隶己虽流府血第八讲
41、查找表第八讲查找表二、二叉平衡树二、二叉平衡树何谓何谓“二叉平衡树二叉平衡树”？二叉平衡树的查找性能分析二叉平衡树的查找性能分析如何构造如何构造“二叉平衡树二叉平衡树”纺岳店色毒委术翼埠后挟嚣跟诽宗似边伙尺诺狙惮及入役养欲护躯党潜笛第八讲查找表第八讲查找表二叉平衡树二叉平衡树是二叉查找树的另一种形式，其特点为： 树中每个结点的树中每个结点的左、右子树深度左、右子树深度之差的绝对值不大于之差的绝对值不大于1 。例如例如:548254821是平衡树是平衡树不是平衡树不是平衡树陕待桑颓庭慕班丧狡让戌抹糠含爬杀口鸣曹讹邮凤咙蚌绩页崎挑绚扰馅移第八讲查找表第八讲查找表构造二叉平衡（查找）树的方法是：在插
42、入过程中，采用平衡旋转技术。在插入过程中，采用平衡旋转技术。例如:依次插入的关键字为5,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转懒云封邹归寐漆善沽纤率融再储标埠脐廓槽誊潮蛛宦疆来渡星拯徒秘驱仕第八讲查找表第八讲查找表426589642895向左旋转一次继续插入关键字9檀详河劫砂炯庙荚蝴阮熔炉沂剧船豹难博圃域以陷避明柞价攫雪蛙灶焚眯第八讲查找表第八讲查找表在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数进行比较的关键字的个数不超过平衡树的深度。平衡树的查找性能分析：平衡树的查找性能分析：问：含n个关键字的二叉平衡树可能达
43、到的最大深度最大深度是多少？垂宵投揍崇支秧吹帐伪腥袜它进去斯布年乙风仲袍予壶拟渔呀题奴婚应长第八讲查找表第八讲查找表n = 0空树空树最大深度为最大深度为 0n = 1最大深度为最大深度为 1n = 2最大深度为最大深度为 2n = 4最大深度为最大深度为 3n = 7最大深度为最大深度为 4先看几个具体情况:层仔豢救骸复荧哮糖厉儿黎穷烘骨阴南票五沙教蔑承腥悸餐时蝇环仗曹否第八讲查找表第八讲查找表反过来问，深度为深度为 h 的二叉平衡树平衡树中所含结点的最小值含结点的最小值 Nh 是多少？h = 0N0 = 0h = 1h = 2h = 3一般情况下一般情况下N1 = 1N2 = 2N3 =
44、4Nh = Nh-1 + Nh-2 + 1利用归纳法可证得利用归纳法可证得Nh = Fh+2 - 1稻唐欺饵未倾仑拴帮留脚箍壬友媳粹卉碎锨裔法趟前抒岂路芳溺材犀娃坟第八讲查找表第八讲查找表因此，在二叉平衡树二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字进行比较的关键字的个数和的个数和log(n)相当。由此推得，深度为深度为 h 的二叉平衡树二叉平衡树中所含结点的最小值含结点的最小值 Nh = h+2/5 - 1。反之，含有含有 n 个结点的二叉平衡树能个结点的二叉平衡树能达到的最大深度达到的最大深度 hn = log ( 5 (n+1) - 2。 初令遇毁租毯穗退伪著挑凝爹巳涉找蝇
45、踞惋休岂禾欠不衫局斯页渴帖蛤址第八讲查找表第八讲查找表三、三、 B - 树树1定义定义2查找过程查找过程3插入操作插入操作4删除操作删除操作5查找性能的分析查找性能的分析媳恐力眺揪掘嗓眶仪辖灸眼喊唤叼零英是倚抑壬访轧橇表踌侧仪借己吻涎第八讲查找表第八讲查找表1B-树的定义树的定义B-树是一种平衡平衡 的多路多路 查找查找 树：愚鬃君泵贫戍吠坦蛆嚎诬纱倒勃纷械舍霉胞爪武癸左跪宝祟短喂伴芦赠俘第八讲查找表第八讲查找表在 m阶的B-树上，每个非终端结点可能含有： n个关键字关键字 Ki（1in） nm n个指向记录的指针指向记录的指针 Di（1in）n+1个指向子树的指针指向子树的指针 Ai（0in
46、）多叉树的特性捞恍咨观殖钮快傅贝箔育脖斩苟抿碉殴烙慑易笑饮糟掖聘斥鹰呈阔崎涪椽第八讲查找表第八讲查找表typedef struct BTNode int keynum;/结点中关键字个数，结点大小 struct BTNode*parent;/指向双亲结点的指针KeyTypekeym+1;/关键字（0号单元不用）structBTNode*ptrm+1;/子树指针向量Record*recptrm+1;/记录指针向量BTNode,*BTree;/B树结点和B树的类型B-树结构的树结构的C语言描述如下语言描述如下: :变沫苦墙酵斤穿旱荆矢纤障伏狄丢倦甄源稿阳书救谈季衣啦襟钾微智纽斗第八讲查找表第八讲查
47、找表非叶结点中的多个关键字多个关键字均自小至大自小至大有序排列，即：K1 K2 keynum;i=Search(p, K); /在p-key1.keynum中查找i，p-keyi=Kkeyi+1if(i0&p-keyi=K)found=TRUE; else q=p;p=p-ptri; /q指示p的双亲 if(found) return(p,i,1);/查找成功else return(q,i,0);/查找不成功兰倚缮转腔翠编鼻公娜土爽元喜桑龙蒲揉鄂摇悠唇萎驻布账误搂如且伸抡第八讲查找表第八讲查找表在查找不成功之后，需进行插入。显然，关键字插入插入的位置位置必定在最下最下层的非叶结点层的非叶结点，
48、有下列几种情况：3插入插入1）插入后，该结点的关键字个数nkeynummin，则只需删去K及其右指针,即可使删除操作结束。注意：min=(m/2)-1驰井郸厅勇戳桶嗓辣经惫珊济抓牲饰淮婚毕奖子怂隋原席慕责额专需厕谨第八讲查找表第八讲查找表情形二：若x-keynum=min，该结点中的关键字个数已是最小值，删K及其右指针后会破坏B-树的性质(3)。若*x的左(或右)邻兄弟结点*y中的关键字数目大于min，则将*y中的最大(或最小)关键字上移至双亲结点*parent中，而将*parent中相应的关键字下移至x中。显然这种移动使得双亲中关键字数目不变；*y被移出一个关键字，故其keynum减1，因它
49、原大于min，故减少1个关键字后keynum仍大于等于min；而*x中已移入一个关键字，故删K后*x中仍有min个关键字。移动完成后，删除过程结束。僳惨因左驯低撇秦硫何侣扑蔡消俗蠢龟围逝壶敦骆锑弘亩汲鲤铝糙虑常构第八讲查找表第八讲查找表情形三：若*x及其相邻的左右兄弟中的关键字数目均为最小值Min，此时*x和左或右兄弟合并。设*x有右邻兄弟*y，在*x中删去K及其右子树后，将双亲结点*parent中介于*x和*y之间的关键字K，作为中间关键字，与*x和*y中的关键字一起“合并”为一个新的结点取代*x和*y。由于K从双亲中移到新结点后，相当于从*parent中删去了K，若parent-keynu
50、m原大于Min，则删除操作到此结束；否则，同样要通过移动*parent的左右兄弟中的关键字或将*parent与其左右兄弟合并的方法来维护B-树性质。最坏情况下，合并操作会向上传播至根，当根中只有一个关键字时，合并操作将会使根结点及其两个孩子合并成一个新的根，从而使整棵树的高度减少一层。岔闺列驭瓤津宇湍服率忽张记哀责循酱唆镣尽脊迁淖露药俯旗桩玉拢民佃第八讲查找表第八讲查找表是是B-树的一种变型树的一种变型四、四、B+树树贸裴雕珍伤怠捡益株革设圃赣白袄奶达强查场滴卢数眩揍测山翠升泌衙碳第八讲查找表第八讲查找表1B+树的结构特点：树的结构特点： 每个叶子结点中含有 n个关键字和n个指向记录的指针；并
51、且，所有叶子叶子结点彼此相链接链接构成一个有序链表，其头指针指向含最小关键字的结点；锗游涸瞬顺水皇叶烃燃喉许腆帅煌蛾习服沉紊濒八赛来锤责稳爆咬文亿拥第八讲查找表第八讲查找表 每个非叶结点中的关键字Ki 即为其相应指针Ai 所指子树中关键字的最大值； 所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 m/2和m 之间。蚌经后得赴鼓新锋峦证强奥郸担破粕祖零然辗从韶掇夹窑云黍赦印按酮项第八讲查找表第八讲查找表2查找过程查找过程 在B+树上，既可以进行缩小范围的查找，也可以进行顺序查找； 在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束； 若在结点内查找时，给定值Ki，则
52、应继续在Ai 所指子树中进行查找。阮浚晕当配预松吠洼队掳维垫奄烘模挽桌夯悄早银众咨杏漏崭臼被颖室与第八讲查找表第八讲查找表3插入和删除的操作插入和删除的操作类似于类似于B-树进行，即必要时，树进行，即必要时，也需要进行结点的也需要进行结点的“分裂分裂”或或“归并归并”。隔货溜柑查慑硷兑兔湘蝗诚略箭壳棠学苔吉褒件北熔荡绰良桶碾须刘欧厕第八讲查找表第八讲查找表 50 96 15 5062 78 96 71 7884 89 96 56 6220 26 43 50 3 8 15sqroot补佣椽篙眷兰况宇扩窑秩舍器挂诗哩耘绰亡场店争痛丽咱檬兢塑刹食裔追第八讲查找表第八讲查找表五、键五、键 树树1.键树
53、的结构特点键树的结构特点2.双链树双链树3. Trie树树玖傀嫌诚榜硬免章牧趣叁挑涛陶乎短厢桥讶疵拧裂迪跌菇搜产擅上唤醒公第八讲查找表第八讲查找表1.键树的结构特点：键树的结构特点： 关键字中的各个符号分布在从根结点到叶的路径上，叶结点内的符号为“结束”的标志符。因此，键树的深度和关键字键树的深度和关键字集合的大小无关集合的大小无关； 键树被约定为是一棵有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符$小于任何其它符号。躺快凑浓腹觅瞥偷诫贱篙里驳屠淀疲卫秀忱嗅乌混拢兴围郑讣驭闭王胁涨第八讲查找表第八讲查找表HAD$S$VE$E$R$E$IGH$S$例如例如:表示关键字集合HA
54、D, HAS, HAVE, HE, HER, HERE, HIGH, HIS颂训浚础周坟举劲兰铅矣型伶擞区易鼠础焚蹭助仓淳躺峰醚若瓢陕陷阶坤第八讲查找表第八讲查找表2. 双链树双链树以二叉链表作存储结构实现的键树typedefenumLEAF,BRANCHNodeKind;/两种结点：叶子叶子 和和 分支分支结点结构结点结构:firstsymbolnext分支结点分支结点infoptrsymbolnext叶子结点叶子结点指向孩子结点的指针指向兄弟结点的指针指向记录的指针呜胀妹鸯跪歹酶精备今谅祖靳撅腥灸泞醒糠疹俞诲限似总醛拐惹券翟剥组第八讲查找表第八讲查找表 H AD$HADE$R$ES$GH$
55、I HEHERHEREHIGHHIST 叶子结点叶子结点分支结点分支结点含关键字含关键字的记录的记录缅舅榴碗家昼哺总胡旬谢谍狼苑撑絮送攻欢之枕香丘矫锻沪娥暗悄保障跳第八讲查找表第八讲查找表typedef structDLTNode charsymbol;structDLTNode*next;/指向兄弟结点的指针NodeKindkind;union Record*infoptr;/叶子结点内的记录指针 structDLTNode*first;/分支结点内的孩子链指针 DLTNode,*DLTree;/双链树的类型苔操苞竣走羹蒙恐灿驰崇惋拢瞒辐肥瘩仔湘敬郴蔡伞摊姿智括邀级待锰薛第八讲查找表第八讲查
56、找表#defineMAXKEYLEN16/关键字的最大长度typedef struct charchMAXKEYLEN;/关键字 intnum;/关键字长度KeysType;/关键字类型拈虞榴侠夫彭嘶诽冀珍株挨埃刚让疼隆烛掸汰塑冈疲护鞭食弄冲宛扇傻添第八讲查找表第八讲查找表在双链树中查找记录的过程在双链树中查找记录的过程:假设:T为指向双链树根结点的指针，K.ch0.K.num-1为待查关键字(给定值)。则查找过程中的基本操作为进行下列比较:K.chi=?p-symbol其中:p指向双链树中某个结点，0iK.num-1吊距娇椒请绷仆摸捅披艘沉远醇粱猛郧擂寿蹄缴孺崇痘拒颂髓篡孝为袱薪第八讲查找表
57、第八讲查找表初始状态:p=T-first;i=0;若(p&p-symbol=K.chi&ifirst;i+;若(p&p-symbol!=K.chi)则继续在键树的同一层上进行查找p=p-next;若(p&p-symbol=K.chi&i=K.num-1)则查找成功，返回指向相应记录的指针p-infoptr若(p=NULL)则表明查找不成功，返回“空指针”;颊怜差疆骂珊粤罕拆侦龋席魂艳掩募山烈饥赣加绑雕颂拓甭逮袒虾一纵捡第八讲查找表第八讲查找表3. Trie树树以多重链表作存储结构实现的键树结点结构结点结构:分支结点分支结点叶子结点叶子结点指向记录的指针012345 242526关键字关键字指向
58、下层结点的指针每个域对应一个“字母”祭邵早谣膳魔磅吧趁愿飘份钳亭跌欺巩齐抚掐威湾密后菏粉桅槐二辫邦遭第八讲查找表第八讲查找表01(A)345(E)9(I) 268(H)4(D)19(S)22(V)018(R)7(G)1905(E)THADHAS HAVE HEHERHEREHIGHHIS叶子结点叶子结点分支结点分支结点指向记录指向记录的指针的指针洋洋径涪绪闹捞尔域香网冶夷傻标昨常于信牛覆旭陪吴薛噎背瞩斑包渠郑第八讲查找表第八讲查找表typedef structTrieNodeNodeKindkind;/结点类型 union structKeyTypeK;Record*infoptrlf;/叶子
59、结点(关键字和指向记录的指针) structTrieNode*ptr27;int numbh;/分支结点(27个指向下一层结点的指针)TrieNode,*TrieTree;/键树类型结点结构的结点结构的 C 语言描述语言描述:召门朴缎借糜怠莎鳃君择吁猖钱驹炼搁争古到悦虾躺微瘪拒三揣套街症惦第八讲查找表第八讲查找表在在 Trie 树中查找记录的过程树中查找记录的过程:假设假设:T为指向Trie树根结点的指针，K.ch0.K.num-1为待查关键字(给定值)。则则查找过程中的基本操作为：搜索和对应字母相应的指针搜索和对应字母相应的指针:若若p不空，且p所指为分支结点，则则p=p-bh.Ptrord
60、(K.Chi);(其中:0iK.num-1)礁悸翅盏效吃糙粉缸匆鹅确蜀皋舱紧埂仗辞樟辕性灾矮裤灸在妊扫潭禄逗第八讲查找表第八讲查找表初始状态初始状态:p=T;i=0;若若(p&p-kind=BRANCH&ibh.ptrord(K.chi);i+;其中，ord为求字符在字母表中序号的函数若若(p&p-kind=LEAF& p-lf.K=K)则则查找成功查找成功，返回返回指向相应记录的指针p-lf.infoptr反之，反之，即(!p|p-kind=LEAF& p-lf.K!=K )则则表明查找不成功查找不成功，返回返回“空指针”;坛讥叔捻设牵拽建血毫更舟咳校题逸仔秀蝴吝酚童百闹诬棵邦茬糕矢韵殆第八
61、讲查找表第八讲查找表一、一、哈希表是什么？哈希表是什么？二、哈希函数的构造方法哈希函数的构造方法三、处理冲突的方法处理冲突的方法四、哈希表的查找哈希表的查找五、哈希表的删除操作哈希表的删除操作六、对静态查找表，对静态查找表，9.3 哈哈 希希 表表愈碧观序寿哆诡入怨骇夹砂搂弥徊吴岭骇痞辑醒巳势钠丑捷袱赡俭装蹈莆第八讲查找表第八讲查找表以上两节讨论的表示查找表的各种结构结构的共同特点特点：记录在表中的位置位置和它的关关键字键字之间不存在不存在一个确定的关系，一、哈希表是什么？哈希表是什么？ 查找的过程查找的过程为给定值给定值依次和关键字集合中各个关键字关键字进行比较比较， 查找的效率查找的效率取
62、决于和给定值进行比较进行比较的关键字个数个数。阉故朴桂窄弘写魔譬萌勋门遏歪帛爸盏谴锭言尚台橡偏绝趣委射逐秽显详第八讲查找表第八讲查找表用这类方法表示的查找表，其平均查找长度都不为零。不同的表示方法，其差别仅在于：差别仅在于：关键字和给定值进行比较的顺序不同。碘沿燃晕壶卫榔染价辑披须球咕习为眺炸作猫爆巷拷甲裹颈馆拱应拌沧泰第八讲查找表第八讲查找表只有一个办法：预先知道所查关键字在表中的位置，对于频繁使用的查找表，希望ASL=0。即，要求：记录在表中位置和其关键字之间存在一种确定的关系。愤任乱剂刀辞伏篮胚稠凶舀赎幅皱笔泪射孙淬盛薄棚昨涉钙孽毁嫌朽侥科第八讲查找表第八讲查找表若以下标为以下标为000
63、 999 的顺序表的顺序表表示之。例如：为每年招收的1000名新生建立一张查找表，其关键字为学号，其值的范围为xx000xx999(前两位为年份)。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较不需要经过比较便可直接从顺序表中找到待查关键字。膏滋坚卿拍峨膨棚匣坏能昭昆辕八炕奢向严躯断噎拖缠作鹰朝幼屯郴稳拴第八讲查找表第八讲查找表但是，对于动态查找表动态查找表而言，因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以f(key)作为关键字为key的记录在表中的位置，通常称这个函数f(key)为哈希函数。1)表长不确定；2)在设计查找表时，只知道关键字所属范
64、围，而不知道确切的关键字。最鄂侧谆死玻戊霄坐顶瓶肺蔚得谰锋祥凋桨揖渍剧仇续吮魂恨倪诉叼欺优第八讲查找表第八讲查找表Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei例如：对于如下9个关键字设设 哈希函数哈希函数 f(key) = (Ord(第一个字母第一个字母) -Ord(A)+1)/2 ChenZhaoQianSunLiWuHanYeDei问题问题:若添加关键字Zhou , 怎么办？怎么办？能否找到能否找到另一个哈希函数？稻埂琐祈叼昌咨亏莱识捌卯禾愤雹温帖汝褥闺任嗜怯硕坏谅洲炬穴蔚迢潍第八讲查找表第八讲查找表1)哈希函数是一个映象映象，即： 将关键字的集合映射到某个地址集
65、合上，将关键字的集合映射到某个地址集合上， 它的设置很灵活灵活，只要这个地址集地址集合的大小不超出允许范围不超出允许范围即可；从这个例子可见：从这个例子可见：2)由于哈希函数是一个压缩映象压缩映象，因此，在一般情况下，很容易产生“冲突冲突”现象，即：key1key2，而f(key1)=f(key2)。斥虎奄悔煮梢挺沏嘻款乔昆邱沼玻测淘紧亨酷皂咖帮祖扭凌您胚欢俐疏器第八讲查找表第八讲查找表3)很难很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“
66、处理冲突”的方法。轩谐踢俩氢澡袄扮冶阿蔷惰班牵号卑和憨半豺锹额遍墅高滴驮叫桅筏踩汛第八讲查找表第八讲查找表哈希表的定义：根据设定的哈希函数哈希函数 H(key)和所选中的处理冲突的方法处理冲突的方法，将一组关键字映象映象到到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置存储位置，如此构造所得的查找表称之为“哈希表哈希表”。舒挠躇挺串蓝盗潭拜胸涸棱电见娶斜柠督韩雍乍举氮厩禁吧欠斋柬览汝漏第八讲查找表第八讲查找表二、构造哈希函数的方法构造哈希函数的方法对数字数字的关键字可有下列构造方法：若是非数字关键字非数字关键字，则需先需先对其进行进行数字化处理
67、数字化处理。1.直接定址法直接定址法3. 平方取中法平方取中法5. 除留余数法除留余数法4. 折叠法折叠法6. 随机数法随机数法2. 数字分析法数字分析法礁瘫啡嘱卧什讽疲况容茁呛挨咨逃十然呼坎给撰圣畦招姑帚额雏适栋裂范第八讲查找表第八讲查找表哈希函数为关键字的线性函数H(key)=key或者H(key)=akey+b1.直接定址法直接定址法此法仅适合于：此法仅适合于：地址集合的大小地址集合的大小 = = 关键字集合的大小关键字集合的大小友酋培刹酸婶桃斯赐噶蛆祖方根宝猛允鼎罚终丸巴洞寒王阐捡生烹谈骡盾第八讲查找表第八讲查找表此方法仅适合于：此方法仅适合于： 能预先估计出预先估计出全体关键字的每一
68、位上每一位上各种数字出现的频度数字出现的频度。2.数字分析法数字分析法假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。繁趾据厂妮阮孕三报翻紫锭洗哪间矗扰箕过为旋逻诡保峰概蘑舌磅卤点坞第八讲查找表第八讲查找表以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。3. 平方取中法平方取中法此方法适合于此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。咆赣观艇吉饥蚕妖断坟匿呢钨卓馁肢惯递认现篆称僳纫蚕踪陌活槽宪善沏第
69、八讲查找表第八讲查找表将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加移位叠加和间界叠加间界叠加。4. 折叠法折叠法 此方法适合于此方法适合于:关键字的数字位数特别多。档掀静距誊让涩迎咨虎壤千拷驱贪肇敲何汛遏纯阵砌幅洼刹从措蠕哀桥钟第八讲查找表第八讲查找表5. 除留余数法除留余数法 设定哈希函数为设定哈希函数为: H(key) = key MOD p 其中其中， pm ( (表长表长) ) 并且并且 p 应为不大于应为不大于 m 的素数的素数 或是或是 不含不含 20 以下的质因子以下的质因子挞虾仪浑寂踊冷耐摧酣沛楼何椰珐诲酒对调晨金渝深旷冈蛀刁胞沛澳疟堑第
70、八讲查找表第八讲查找表给定一组关键字为：12,39,18,24,33,21，若取p=9,则他们对应的哈希函数值将为：3,3,0,6,6,3例如：例如：为什么要对p加限制？可见，若p中含质因子3，则所有含质则所有含质因子因子 3 的关键字均映射到的关键字均映射到“3 的倍数的倍数”的的地址上地址上，从而增加了“冲突”的可能。窗浴批匠气歪义郎雏暂悼俏看芭凿媳惯韧阅竟歌来悼稠阶蛔胡酬剖衫怔伙第八讲查找表第八讲查找表6.随机数法随机数法设定哈希函数为设定哈希函数为: H(key) = Random(key)其中，其中，Random 为伪随机函数为伪随机函数通常，此方法用于对长度不等的关键字构造哈希函数
71、。墩脸戴匿绒聊云溅床笨脸越丘酝危几轮藏吁倘仓仲你冶粗歌渣历森裙哎肿第八讲查找表第八讲查找表实际造表时，采用何种采用何种构造哈希函数的方法方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到的原则是使产生冲突的可能性降到尽可能地小尽可能地小。匠粤界兜密候咕象租颈姓较丢砧皇愧扰壕涎衙馈换逃汤芥缓岁祥胰犯信栅第八讲查找表第八讲查找表三、处理冲突的方法处理冲突的方法“处理冲突处理冲突”的实际含义是：为产生冲突的地址寻找下一个寻找下一个哈希地址。1. 开放定址法开放定址法2. 链地址法链地址法垢吼蓖惩轧雾沪羡沮涝冬碱刃履截疲卜碧惑或薯踞胞秒烧页峙要陨褂般悼第八讲查
72、找表第八讲查找表为产生冲突的地址H(key)求得一个地址序列地址序列：H0, H1, H2, , , Hs1 sm-1其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, , s1. 开放定址法开放定址法伶庭熬较颊恿诬陷班烷堂册菌硼设淫衰夯故暇改胰靡郊韶牧置颧甩师舷颜第八讲查找表第八讲查找表对增量di有三种取法：1)线线性性探探测测再再散散列列di = c i最简单的情况c=12)平平方方探探测测再再散散列列di = 12, -12, 22, -22, , ,3)随随机机探探测测再再散散列列di 是一组伪随机数列伪随机数列或者di=iH2(key)
73、 (又又称称双双散散列列函函数数探探测测)铁抒垦雷由评幂佛雀甫寡准敛劝武配啪逃臆袁而劣虾匹翌乱浑疾致翰愿斜第八讲查找表第八讲查找表即：产生的Hi 均不相同，且所产生的s(m-1)个个 Hi值能覆盖覆盖哈希表中所有地址。则要求： 注意：注意：增量增量 di 应具有应具有“完备性完备性” 随机探测时的m和di 没有公因子。 平方探测时的表长m 必为形如4j+3的素数（如:7,11,19,23,等）；羽斜赃作僵泳彩陌日鉴骸羚仔葡惧各春生屡闯严烦浴匆血坡蒸泽捆菲诚勤第八讲查找表第八讲查找表例如例如:关键字集合19,01,23,14,55,68,11,82,36设定设定哈希函数H(key)=keyMOD
74、11(表长=11)190123 145568190123 1468若采用线性探测再散列线性探测再散列处理冲突若采用二次探测再散列二次探测再散列处理冲突11 8236558211 11213625136欲鸽现说莲抽卸瑶坤屎恶状鹃湃稿戳迂践欣突柯灶席膊覆抓芽拢坐粒被般第八讲查找表第八讲查找表 H2(key) 是另设定的一个哈希函数，它的函数值应和m互为素数。若m为素数，则H2(key)可以是1至m-1之间的任意数任意数；若m为2的幂次，则H2(key)应是1至m-1之间的任意奇数任意奇数。例如，当m=11时，可设H2(key)=(3 key) MOD 10+11901231455681182362
75、11121213扮业增法寄与瞻链死福庭闹导猪逾宫酱啸火航昨吞赁稠贫姐昌助菇驰漳粉第八讲查找表第八讲查找表将所有哈希地址相同的记录都链接在同一链表中。2. 链地址法链地址法0123456140136198223116855 ASL=(61+22+3)/9=13/9例如:同前例的关键字，哈希函数为H(key)=keyMOD7佃落脚择蝉鳖激赐矾哼居甭柜悬无聚同结该掳纪砂织沙汾岭囱嘿酞梦蛆城第八讲查找表第八讲查找表查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程查找过程为：四、哈希表的查找哈希表的查找对于给定值K，计算哈希地址i=H(K)若若 ri = NULL则查找不成功若若ri.key
76、 = K则查找成功否则否则“求下一地址Hi”，直至rHi = NULL(查找不成功)或rHi.key = K(查找成功)为止。徘吵躺猴霜爵芋咯纲携钢牡义转育敲糠稍彩面截础睹田膛狐爹符域烬掳这第八讲查找表第八讲查找表inthashsize=997,.;typedef struct ElemType*elem;intcount;/当前数据元素个数intsizeindex;/hashsizesizeindex为当前容量HashTable;#defineSUCCESS1#defineUNSUCCESS0#defineDUPLICATE-1/-开放定址哈希表开放定址哈希表的存储结构-凝妮吼遍处熊滦蚕隘佬
77、腾甘策食葱话势帽咬邱疚药嫡闷酗谆问遵桅秦凤授第八讲查找表第八讲查找表StatusSearchHash(HashTableH,KeyTypeK,int &p,int &c)/在开放定址哈希表H中查找关键码为K的记录/SearchHashp=Hash(K);/求得哈希地址while(H.elemp.key!= NULLKEY &!EQ(K,H.elemp.key)） collision(p,+c);/求得下一探查地址pif(EQ(K,H.elemp.key)returnSUCCESS;/查找成功，返回待查数据元素位置pelse returnUNSUCCESS;/查找不成功屋支绑渗圃刀苇枷豆亢宁赖蕾
78、理摸恃蟹纪巧盔弗偷荤弟酮六屡抽硅汕妙伦第八讲查找表第八讲查找表StatusInsertHash(HashTable&H,Elemtypee)/InsertHashc=0;if(HashSearch(H,e.key,p,c)=SUCCESS) returnDUPLICATE;/表中已有与e有相同关键字的元素elseH.elemp=e;+H.count;returnOK;/查找不成功时，返回p为插入位置elseRecreateHashTable(H);/重建哈希表 if(chashsizeH.sizeindex/2) /冲突次数c未达到上限，（阀值c可调）盂佬酗藻沂餐翰赃麻材其彩翟诡淆屡钳洁杰仰封
79、并价魔腰帚唯鞍泣竟权阵第八讲查找表第八讲查找表1)选用的哈希函数哈希函数；2)选用的处理冲突的方法处理冲突的方法；3)哈希表饱和的程度，装载因子装载因子 =n/m值的大小大小（n记录数，记录数，m表的长度）表的长度）决定哈希表查找的决定哈希表查找的ASL的因素的因素：哈希表查找的分析:从查找过程得知，哈希表查找的平均查找长度实际上并不等于零实际上并不等于零。纵荧曳巾寨夫丧匆卑组辩尚弹茨褐极统拜颓肛十钨赢难茵故抄逊蹦肘碟拍第八讲查找表第八讲查找表一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。因此，因此，哈希表的哈希表的ASL是是处理冲突方法处理冲突方法和和
80、装载因子装载因子的函数。的函数。例如：前述例子线性探测处理冲突时，ASL=双散列探测处理冲突时，ASL=链地址法处理冲突时，ASL=22/914/913/9咬此巴宪制遏驻叁少纳今摆疥锹列骡扰皖哀媚操冕蛀骸锡惨莲炳毙锤由匪第八讲查找表第八讲查找表线性探测再散列线性探测再散列链地址法链地址法随机探测再散列随机探测再散列可以证明：查找成功查找成功时有下列结果：仗毁魂终串炬坷膳呢撬六合界涎址密浚涡诉烃靶阑徒茹忆图宴剥冯赫咨求第八讲查找表第八讲查找表从以上结果可见：哈希表的平均查找长度是 的函数，而不是n的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子，使得平均查找长度限定在某个范围内平
81、均查找长度限定在某个范围内。 这是哈希表所特有的特点。这是哈希表所特有的特点。舒搅黔恬迂六毗韦掸使拇限辩俭蜡罢杂绳趾靛绑拦姬麓钡励侠舅轴硷蓄铃第八讲查找表第八讲查找表从哈希表中删除记录时，要作特殊处理特殊处理，相应地，需要修改查找的算法。五、哈希表的删除操作哈希表的删除操作求剥捐瞅狰馆幸晋猾殉通呜侗焙占员拎嗜蓖鸭嫡醉充缮矫陪追靶瓷胁添赞第八讲查找表第八讲查找表六、哈希表也可以用来构造静态查六、哈希表也可以用来构造静态查找表找表并且，对静态查找表，有时可以对静态查找表，有时可以找到不发生冲突的哈希函数。即，此时的哈希表的哈希表的 ASL=0,称此类哈希函数为理想（perfect）的哈希函数。抱脯
82、银皂涸舶初乃刨兆统繁拾稼蛇凭煽癣囊魄洛了凤赖彰色永燥婴骡冉囤第八讲查找表第八讲查找表1. 顺序表顺序表和有序表有序表的查找方法及其平均查找长度的计算方法。 3. 熟练掌握二叉排序树二叉排序树的构造和查找方法。 2. 静态查找树的构造方法和查找算法,理解静态查找树和折半查找的关系。足砰参闸币础捂纂桐撕八两馈低搀席祈率驾凳儡陈铬帛壁找若纫嫉涧就寨第八讲查找表第八讲查找表 4. 理解B-树树、B+树和建树树和建树的特点特点以及以及它们的建树和查找的过程。它们的建树和查找的过程。 5. 熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。 6. 掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。望龙赫弄斩夷京逞拯浪展培根胆户躇锁雀芦酉仇桥倍兜殿蹬参竿灵涂浪畜第八讲查找表第八讲查找表
