预备知识静态查找表动态查找表哈希表

《预备知识静态查找表动态查找表哈希表》由会员分享，可在线阅读，更多相关《预备知识静态查找表动态查找表哈希表（108页珍藏版）》请在金锄头文库上搜索。

1、预备知识预备知识8.1静态查找表静态查找表8.2动态查找表动态查找表8.3哈希表哈希表摹吝罪漫产名秋拿歇怖糠嘉踞钦姆逞束椭囤啮鸽凳嗡沫跌焕妥呛所冀祸庙预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表1第第8 8章章 查找查找本章重点难点本章重点难点重点重点：顺序查找、二分查找、二叉排序树查找以顺序查找、二分查找、二叉排序树查找以 及散列表查找的基本思想和算法实现。及散列表查找的基本思想和算法实现。难点难点：二叉排序树的删除算法和平衡二叉树的：二叉排序树的删除算法和平衡二叉树的 构造算法。构造算法。驹元僧衫旷阁嵌溉处聋逝像必彰否糠眶化哼用费飘妄届谣刃郊近围播负狄预备知识静态查

2、找表动态查找表哈希表预备知识静态查找表动态查找表哈希表2 预备知识预备知识 8.1 8.1 静态查找表静态查找表 8.2 8.2 动态查找表动态查找表 8.3 8.3 哈希表哈希表震详袄栖衡功欺评逗棺饱堵汀帅碌蝶晋洁撩窜炉学戏蔡扬门斯俭巳雹晌钉预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表3第第8 8章章 查找查找(1) (1) 查找表查找表：(2) (2) 静态查找表静态查找表：是由同一类型的数据元素是由同一类型的数据元素( (或记录或记录) )构成的集合。构成的集合。仅作查询和检索操作的查找表。仅作查询和检索操作的查找表。p 有关概念有关概念(3) (3) 动态查找表

3、动态查找表：在查找时包含插入、删除或修改。在查找时包含插入、删除或修改。预备知识预备知识潮勤店瓣郝苟锄涧都椭含慨造废免铬洽潍认栗父盈汰秽辩缝瞒饵咸肆切恢预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表4第第8 8章章 查找查找(4) (4) 主关键字主关键字(5) (5) 次关键字次关键字可以识别唯一的一个记录的数据项（字段）。可以识别唯一的一个记录的数据项（字段）。关联若干项记录的数据项（字段）。关联若干项记录的数据项（字段）。(6) (6) 查找查找 根据给定的某个值，在查找表中确定一个其关键字根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。

4、等于给定值的数据元素或（记录）。p 有关概念有关概念预备知识预备知识析蒂畔瘁迭治脖涣扎躯搞吐谓蒙岸臭狡卸蚕厂丁腆陪跪和魏仪挺蛾训搬缩预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表5第第8 8章章 查找查找(7) (7) 查找成功查找成功(8) (8) 查找不成功查找不成功查找表中存在满足条件的记录。查找表中存在满足条件的记录。查找表中不存在满足条件的记录。查找表中不存在满足条件的记录。p 有关概念有关概念预备知识预备知识患漠课斜觅常挺豹情涣农蚜尺淘卵鳞膛肿锹眷藩楷丰倦建卑桑钩掳插瞎听预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表6第第8 8章章 查找

5、查找typedeffloatKeytype;/Keytype定义为浮点数据类型定义为浮点数据类型typedefintKeytype;/Keytype定义为整型数据类型定义为整型数据类型typedefchar*Keytype;/Keytype定义为字符指针数据类型定义为字符指针数据类型p 类型定义类型定义预备知识预备知识供万祈氓桩序憋市仿噎鼻龄街残冕盏绥氯劣狈废升最戎饶苔瘁宇胜琵忘萍预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表7第第8 8章章 查找查找数据元素类型定义为：数据元素类型定义为：typedefstructKeytypekey;/声明关键字声明关键字SElemT

6、ype;/SElemType结构体数据类型结构体数据类型p 类型定义类型定义预备知识预备知识盗师返罗羽劲苟狸囊络娜赁异集笑坚志蹦枚妙挥在飘椭摈学灿层轧改越翼预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表8第第8 8章章 查找查找/数值型关键字的比较数值型关键字的比较#defineEQ(a,b)(a)=(b)#defineLT(a,b)(a)(b)#defineLQ(a,b)(a)=(b)/字符型关键字的比较字符型关键字的比较#defineEQ(a,b)(!strcmp(a),(b)#defineLT(a,b)(strcmp(a),(b)0)#defineLQ(a,b)(s

7、trcmp(a),(b)=0)&ST.elemi.key!=key;-i);/从后往前找从后往前找returni;/若返回值若返回值i为为0，则表示没有找到，则表示没有找到/Search_Seqp 顺序查找表的算法与实现顺序查找表的算法与实现暇驼当屁决雹沫钎酥誉褐肄救猴辖唤侮毡错霓骸孺缸味韭编辽堑漏枫藻鸡预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表21第第8 8章章 查找查找 给定值进行比较的关键字个数的期望值给定值进行比较的关键字个数的期望值: : 8.1.1 8.1.1 顺序查找表顺序查找表p 顺序查找表算法分析顺序查找表算法分析n 为表长为表长Pi为查找表中第为查

8、找表中第i个记录的概率个记录的概率Ci为找到记录时，关键为找到记录时，关键字的比较次数字的比较次数涉哄非镇捕毯宅岭剩萌毁泳峰獭褥陀酥赐激柄腊瘸汤毫势蝉呼悉淫盘所垢预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表22第第8 8章章 查找查找在等概率查找的情况下，在等概率查找的情况下，顺序表查找的平均查找长度为：顺序表查找的平均查找长度为：8.1.1 8.1.1 顺序查找表顺序查找表p 顺序查找表算法分析顺序查找表算法分析牟婆包纶紫矮轴瑞履径物豁惜饶米和悦艘昔结帐藻舆膊解准洽泥予蛆惊雌预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表23第第8 8章章 查找查

9、找折半查找折半查找婉脓汝许猎瓮让梁尔咱老拖惹羡验硕塞矩钙拧拧垢咬蜡朵奸毁哺矗碌俺综预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表24第第8 8章章 查找查找8.1.2 8.1.2 有序表的查找有序表的查找想一想：英文字典的特点及英语单词的想一想：英文字典的特点及英语单词的查找过程。查找过程。p 折半查找的前提要求折半查找的前提要求英文字典是有序的，英语单词的查找用英文字典是有序的，英语单词的查找用的是折半查找。的是折半查找。折半查找的前提要求是顺序存储并且有序。折半查找的前提要求是顺序存储并且有序。县掂抢箕审附慌梨菱绒维辆踏磅鲤脊耻颇绣宾彬曹婆捐脆疯命横额衷寂顷预备知识静

10、态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表25第第8 8章章 查找查找p 折半查找表的思想折半查找表的思想8.1.2 8.1.2 有序表的查找有序表的查找1)1)将要查找关键字与查找表的中间的元素将要查找关键字与查找表的中间的元素 进行比较，若相等，返回当前位值；进行比较，若相等，返回当前位值；2)2)若查找关键字比当前位置关键字大，向若查找关键字比当前位置关键字大，向 前递归，否则向后递归。前递归，否则向后递归。弃惯肖这殊弱搽慰斯襄收为爵庚挝寝缓迟夺咋臀踌久嚷曹谣邱础翻槛喧员预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表26第第8 8章章 查找查找012

11、34567891051319213756647580889001234513192137lowhighmid=(low+high)/2查找查找2121因为因为21192119，因此，因此，2121不可能在左边的区间出现，不可能在左边的区间出现，所以考虑在右端区间查找所以考虑在右端区间查找8.1.2有序表的查找有序表的查找p 折半查找表示例演示折半查找表示例演示滴闹诡玩莎阐晌普秽漫厉凰蹬撤多炭巾坷丝稻望誊邵镐冕哇疽康甫琉拖躯预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表28第第8 8章章 查找查找342137lowhighmid= (low+high)/2此时，在此时，在m

12、id点的值刚好等于点的值刚好等于2121，所以查找成功，所以查找成功对右端的区间继续进行折半查找，如下对右端的区间继续进行折半查找，如下8.1.2有序表的查找有序表的查找p 折半查找表示例演示折半查找表示例演示查找成功，返查找成功，返回当前位置回当前位置3 3羚娠车饮女核篙行访屯诈朱辣弟咏欠跨孵茁珊验车胡爸壶拭潍奥项丽扯扯预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表29第第8 8章章 查找查找位置位置 0 1 2 3 4 5 6 7 8 9 10关键字关键字05 13 19 21 37 56 64 75 80 88 90lowhighmid= (low+high)/2h

13、igh=mid-1midlow=mid+1mid8.1.2 8.1.2 有序表的查找有序表的查找p 折半查找表示例演示折半查找表示例演示查找查找21离桥丘剧狙上魁彼搁命永纳如拐镰径叭访棋溪蔽婉抚铬闽掏弱法化巷褥挤预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表30第第8 8章章 查找查找intSearch_Bin(SSTableST,KeyTypekey)low=1;high=ST.length;/置区间初值置区间初值while(low=high)/语句见下页语句见下页return0;/顺序表中不存在待查元素顺序表中不存在待查元素/Search_Bin8.1.2 8.1.2

14、 有序表的查找有序表的查找p 折半查找表算法与实现折半查找表算法与实现引嫁殆凡钳底打王短镭骤唯剿叶坏燃伎情雕按酮呜立讹盖殿悯要阜嫁颤勇预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表31第第8 8章章 查找查找while(lowj时，第时，第i块中块中的的最小元素最小元素大于第大于第j块中块中的的最大元素最大元素。221292033424849608653012345678910按块单调增加按块单调增加代汝摊二兼妆曼威候援扔采定溃竣闺器饲物慎买婉淫诺靠竖遍胖映奢铜冉预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表37第第8 8章章 查找查找8.1.4索引

15、顺序表的查找索引顺序表的查找p 索引顺序表的查找思想索引顺序表的查找思想(1) (1) 首先确定所要查找关键字在哪一块中。首先确定所要查找关键字在哪一块中。(2) (2) 在所确定的块中用顺序查找查找关键字。在所确定的块中用顺序查找查找关键字。贸扔豢股浮髓写频懦搔炯侮粳恼羹房股具饥乍扯停畴吴汕从闹沾溜动朽付预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表38第第8 8章章 查找查找8.1.4索引顺序表的查找索引顺序表的查找224886047建立索引表建立索引表221292033424849608653012345678910该块最大关键字该块最大关键字该块起始位址该块起始位

16、址线性表线性表p 索引顺序表的示例演示索引顺序表的示例演示第第1 1块块最大值最大值第第2 2块块最大值最大值第第3 3块块最大值最大值第第1 1块起块起始位置始位置第第2 2块起块起始位置始位置第第3 3块起块起始位置始位置博韶丹酋骆购佬臼恳挥转铣到乞查与苯国狙又劳贫牺接敏框品锄皇溜落雁预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表39第第8 8章章 查找查找查找示例：假如要查找查找示例：假如要查找4242，则根据索引表：，则根据索引表：224886047整个查找表被分为了三块，整个查找表被分为了三块，按照块单调递增按照块单调递增：第第1块中的块中的最大关键字最大关键字

17、小于小于第第2块的块的最小关键字；最小关键字；第第2块中的块中的最大关键字最大关键字小于小于第第3块的块的最小关键字。最小关键字。a)因为因为4222，所以，所以42肯定不在第一块中，肯定不在第一块中，b)因为因为42IX.indexi.key)&(i=IX.block)i+;if(i=IX.block)s=IX.indexi.addr;if(i=IX.block)e=ST.length;elsee=IX.indexi+1.addr-1;while(key!=ST.elems.key&(s=e)s=s+1;if(sdata.key=k)returnp;if(kdata.key)p=p-lchi

18、ldelsep=p-rchildreturnNULL;p 二叉排序树的查找算法二叉排序树的查找算法8.2.1二叉排序树和平衡二叉树二叉排序树和平衡二叉树速莹乌捆罚炽祝叮一爹苹供茎肾宙嗣部弘泪睬经篆淡酱啥香撕啄倦蹄窒乘预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表58第第8 8章章 查找查找452453123794122437455394树树1平均查找长度平均查找长度O(log2n)树树2平均查找长度平均查找长度O(n)p 二叉排序树的查找算法分析二叉排序树的查找算法分析8.2.1二叉排序树和平衡二叉树二叉排序树和平衡二叉树戒赊文劝瑰粕缉斩躺绘拯孰襟淋掷馏币先冕赂溶曼苏澈严

19、坝噶哪别俭贮隔预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表59第第8 8章章 查找查找a)二二叉叉排排序序树树的的平平均均查查找找长长度度最最差差情情况况与与顺顺序序表表相相同同(关键字有序时关键字有序时),为为O(n);b)最最好好情情况况与与折折半半查查找找相相同同,是是O（log2n）数数量量级级的的;c)二叉排序树的平均查找长度仍然是二叉排序树的平均查找长度仍然是O(log2n)。p 二叉排序树的查找算法分析二叉排序树的查找算法分析8.2.1 8.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉树 烩块灰廷证淳免撮席咸仅抒叭寇咀惠雷塔毒捉牺票复恿驮畴锋颇贬误但

20、膳预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表60第第8 8章章 查找查找1.1.若二叉树为空：则待插入结点若二叉树为空：则待插入结点*s*s作为根结点；作为根结点；2.2.当当二二叉叉排排序序树树非非空空时时：将将待待插插结结点点关关键键字字与与根根 结结点点进进行行比比较较，若若相相等等，则则说说明明树树中中已已有有此此结结点点，无须插入；无须插入； 若小于根结点，插入左子树；若小于根结点，插入左子树； 若大于根结点，插入右子树。若大于根结点，插入右子树。p 二叉排序树的插入算法思想二叉排序树的插入算法思想8.2.1 8.2.1 二叉排序树和平衡二叉树二叉排序树和平

21、衡二叉树 苞跨隔椭署巡幢窿跪纪司晾虞灭冲岿筐汉痈畔举鬃沫迹憋诵转意摩又吏螟预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表61第第8 8章章 查找查找1245337531002461在如下二叉排序树中插入在如下二叉排序树中插入25过程演示过程演示4525p 二叉排序树的插入过程演示二叉排序树的插入过程演示1237248.2.1 8.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉树 钻崇蚌难套佐页粤研酞视澡罪理撒穷赏氖荧账阂如谭岔瑶袖匿菏钥维勉禹预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表62第第8 8章章 查找查找p 二叉排序树的插入算法二叉排序

22、树的插入算法StatusInsertBST(BiTree&T,ElemTypee)BiTreep,s;if(!SearchBST(T,e.key,NULL,p)/查找不成功查找不成功s=(BiTree)malloc(sizeof(BiTNode);s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;/插入插入s为新的根结点为新的根结点elseif(LT(e.key,p-data.key)p-lchild=s;/插入插入s为左孩为左孩elsep-rchild=s;/插入插入s为右孩为右孩returnTRUE;elsereturnFALSE;/树中已有关键字相同的结

23、点，不再插入树中已有关键字相同的结点，不再插入/InsertBST8.2.1 8.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉树 官泛径厕稼赵问趟障元烛逮逸吻抓么绽闻肆改姬拖屠捕缉备蔡铰貌裤罗屎预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表63第第8 8章章 查找查找p 二叉排序树的插入算法分析二叉排序树的插入算法分析a)二二叉叉排排序序树树的的插插入入算算法法的的时时间间复复杂杂性性与与查查找找算法的时间复杂性相同算法的时间复杂性相同;b)最最好好情情况况是是O（log2n）;最最坏坏情情况况是是O(n);平均情况是平均情况是O(log2n)。思考题：思考题：如何

24、生成二叉排序树如何生成二叉排序树? ?答案：答案：从空树开始循环调用插入算法。从空树开始循环调用插入算法。8.2.1 8.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉树 卖谢毡待碱穿碱墟妓细掺栈滓惋奎惩郸盾渐大外繁族锯弓胡扯又找幻篮嚷预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表64第第8 8章章 查找查找例：从给定的一列数据出发，构造例：从给定的一列数据出发，构造二叉排序树。二叉排序树。 给定：给定：5652604365288096403945产生了一棵不平衡的二叉排序树产生了一棵不平衡的二叉排序树8.2.1 8.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉

25、树 6065809652434528403956邢讥蓄壮畴夏惹饿丘鞍氨耘引佯绵里饰然挟产析诫脖翁京古呼溶气奉篆糖预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表65第第8 8章章 查找查找例：从给定的一列数据出发，构造例：从给定的一列数据出发，构造二叉排序树。二叉排序树。 给定：给定：5256604365288096403945产生另外一棵不平衡的二叉排序树产生另外一棵不平衡的二叉排序树8.2.1 8.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉树 5660658043404539529628窥汰象瓷夕咯循洁姑们愧崎隐舔址周辐揩萝讼组谴醚鲜妊芹式茁窥宏陡迷预备知识静态

26、查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表66第第8 8章章 查找查找在二元查找树上的删除一个结点，要求在二元查找树上的删除一个结点，要求删除结点后，仍保持二叉排序树的结构删除结点后，仍保持二叉排序树的结构特点不变。特点不变。p 二叉排序树的结点删除定义二叉排序树的结点删除定义8.2.1 8.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉树 屯遇矮峭锻汤较庙牛宇眯箩敖窒篇遁奖伶键杰遮茹岸庇幅浆割臃按鱼氮鸳预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表67第第8 8章章 查找查找(1)p为叶结点为叶结点(2)p只有左子树只有左子树(3)p只有右子树只有右子

27、树(4)p左右子树都有左右子树都有设被删结点为设被删结点为p,其双亲结点为其双亲结点为f，则，则p可能可能有以下有以下4种情况：种情况：p 二叉排序树的结点删除方法二叉排序树的结点删除方法8.2.1二叉排序树和平衡二叉树二叉排序树和平衡二叉树窍为使绍窥泊鞭列夷咐冬栏位莽臭侮砍意昭姜固便么扰历有采翘残脚沃莆预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表68第第8 8章章 查找查找(1)p为叶结点为叶结点,如如右图所示：右图所示：删除方法：释放结点删除方法：释放结点p p，修改其父结点修改其父结点f f的相应指的相应指针。针。fp12453375310024615125p 二

28、叉排序树的结点删除方法二叉排序树的结点删除方法8.2.1 8.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉树 姬装叉恼烁殷隅孰喝悔违烈怀酞曹灭苏历跪盟陵聋症竞偏龄薪几商域捌忙预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表69第第8 8章章 查找查找(2)p只有左子树只有左子树,如上图如上图所示：所示：删除方法：释放结点删除方法：释放结点p，p的左子树顶替的左子树顶替p点的位置。点的位置。p12453375310024615125124535310024615125p 二叉排序树的结点删除方法二叉排序树的结点删除方法8.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二

29、叉树 犬泥购宣撰钦贺现发签军耻肝恐犯浓斜杂赵奢卑帐封娶抉慈试垒彬络庸捂预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表70第第8 8章章 查找查找(3)p只有右子树只有右子树,如上图如上图所示：所示：删除方法：释放结点删除方法：释放结点p，p的右子树顶替的右子树顶替p点的位置。点的位置。1245337531002461251245337100246125p 二叉排序树的结点删除方法二叉排序树的结点删除方法8.2.1 8.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉树 坊酗乡泼豹瘁充卧湿虱肮帖绕壬耳睫栽拇块沁垦满荐柯挽锑匀螟岂蛊诞法预备知识静态查找表动态查找表哈希表预备

30、知识静态查找表动态查找表哈希表71第第8 8章章 查找查找把左子树作为右子树中最小把左子树作为右子树中最小结点的左子树。结点的左子树。或者把右子树作为左子树中或者把右子树作为左子树中最大结点的右子树。最大结点的右子树。(4)p既有左子树，既有左子树，也有右子树，也有右子树，如上图如上图所示：所示：删除方法：删除方法：缺点：缺点：增加了树的高度。增加了树的高度。12453375310024615125p 二叉排序树的结点删除方法二叉排序树的结点删除方法8.2.1 8.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉树 嗡我吩遏凝拖翔摄昂寺惯拖藏室挪欧寂敷雕冻娠而庶惦敢框吗耀袒纶榆娇预备知识静态

31、查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表72第第8 8章章 查找查找(4) (4) p既有左子树，也有右子树既有左子树，也有右子树,如上图如上图所示：所示：12453375310024615125p 二叉排序树的结点删除方法二叉排序树的结点删除方法8.2.1 8.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉树 改进删除方法：改进删除方法：找一个结点顶替它的位置。找一个结点顶替它的位置。能够顶替它的结点是左子能够顶替它的结点是左子树中最大的，右子树中最树中最大的，右子树中最小的。小的。我们用我们用左子树最大的结点左子树最大的结点来顶替。来顶替。恨腥网捎黄荷锋屎妮朵惶假材飘礁

32、妒青贪另搓囱嚎据逾洼践栈侩酱玖拘伐预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表73第第8 8章章 查找查找StatusDeleteBST(BiTree&T,KeyTypekey)if(!T)returnFALSE;elseif(EQ(key,T-data.key)returnDelete(T);elseif(LT(key,T-data.key)returnDeleteBST(T-lchild,key);elsereturnDeleteBST(T-rchild,key);/DeleteBSTp 二叉排序树的结点删除算法二叉排序树的结点删除算法8.2.1 8.2.1 二叉排

33、序树和平衡二叉树二叉排序树和平衡二叉树 滦菲氰漂次唐庙歇榴饥相贤浓恶吭饥灭冒乡柑址忘堤若侣钉娇抨豌倚卿沃预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表74第第8 8章章 查找查找StatusDelete(BiTree&p)BiTreeq,s;if(!p-rchild)q=p;p=p-lchild;free(q);elseif(!p-lchild)q=p;p=p-rchild;free(q);elseq=p;s=p-lchild;p 二叉排序树的结点删除算法二叉排序树的结点删除算法8.2.1 8.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉树 封赞睫笺绅舱侦建潞郡抗税

34、尖哩鱼曳帽仙弃祈菜课蝴银娟笨戒拂版捷付续预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表75第第8 8章章 查找查找while(s-rchild)q=s;s=s-rchild;p-data=s-data;if(q!=p)q-rchild=s-lchild;elseq-lchild=s-lchild;free(s);returnTRUE;/Deletep 二叉排序树的结点删除算法二叉排序树的结点删除算法8.2.1 8.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉树 由转鳃晒堂测涌求辰事谎雄还疑谓呼澈俄揖本处硫坏凑舜碑柠灸饶辛车萌预备知识静态查找表动态查找表哈希表预备知识

35、静态查找表动态查找表哈希表76第第8 8章章 查找查找p 二叉排序树的删除算法分析二叉排序树的删除算法分析二二叉叉排排序序树树的的删删除除算算法法的的时时间间复复杂杂性性与与查找算法的时间复杂性相同查找算法的时间复杂性相同;最好情况是最好情况是O（log2n）;最坏情况是最坏情况是O(n);平均情况是平均情况是O(log2n)8.2.1 8.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉树 危房姐牌震洱忍乒阉汽烽迸函缄鬃隶幻各绚责匹消悼刹榆敝岩隐诅膊黎览预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表77 预备知识预备知识 8.1 8.1 静态查找表静态查找表 8.2

36、8.2 动态查找表动态查找表 8.3 8.3 哈希表哈希表割研毙砚排顷服谷抿棱斩木击讯络磊蕉丛心矢雄涝粟抢著蚁次逮家斧授闺预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表78第第8 8章章 查找查找 8.3.1 8.3.1 什么是哈希表什么是哈希表 8.3.2 8.3.2 哈希函数的构造方法哈希函数的构造方法 8.3.3 8.3.3 处理冲突的方法处理冲突的方法 8.3.4 8.3.4 哈希表的查找及其分析哈希表的查找及其分析8.3 哈希表哈希表者蔼历皿谤癌韧薛洽赤泥冗空挪棠纠佩疚尚划骑蝶卢糠囤简堪霉甭田澜盾预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希

37、表79第第8 8章章 查找查找学生名单的顺序存储与查找方式：学生名单的顺序存储与查找方式：p哈希表的引入哈希表的引入030530101张三张三男男030530103李四李四男男030530133王五王五男男030530101张三张三男男030530103李四李四男男030530133王五王五男男018.3.1什么是哈希表什么是哈希表例例顺序存储顺序存储蛙止什篮决穆涕坏伐欠汰旷纷遂捂绿愁撩蝎宝忘遣桃野骇纺嗣少功敞泌内预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表80第第8 8章章 查找查找030530101张三张三男男030530103李四李四男男030530133王五王五

38、男男01232H(num)=atoi(substr(num,8,2)-1num=“030530101”name=“张三张三”sex=“男男”030530101张三张三男男030530103李四李四男男030530133王五王五男男substr(num,8,2)=“01”p哈希表的引入哈希表的引入8.3.1什么是哈希表什么是哈希表不是按照顺不是按照顺序存储；按序存储；按照函数映射照函数映射衬煌赦棱骆昏囱霍舔平盂浦弃扮烷鹏浸狱蒸竭荐朋攒谁伞猜窒滞绣逾诉粥预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表81第第8 8章章 查找查找以以结结点点的的关关键键字字K为为自自变变量量，通

39、通过过一一个个确确定定的的函函数数关关系系H，计计算算出出对对应应的的函函数数值值H(K),把把这这个个函函数数值值作作为为结结点点的存储地址。的存储地址。存储时存储时：把关键字为把关键字为K的数据元素存储在地址的数据元素存储在地址H(K)中中;查找时查找时：给定关键字给定关键字K，直接到地址，直接到地址H(k)中取数据元素中取数据元素。p 哈希表的思想哈希表的思想8.3.1 什么是哈希表什么是哈希表优点：查找的速度快优点：查找的速度快袭恰穴骂俱匹燎惊件你狱棉处银毕缺嘻芜僳砰拉引痉峻惧叁瘸快渗娱赣序预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表82第第8 8章章 查找查找

40、用用散散列列法法存存储储的的线线性性表表叫叫散散列列表表（Hashtable）,又又称称杂杂凑凑表表，哈哈希希表表，对对应应的的函函数称为散列函数、杂凑函数或哈希函数。数称为散列函数、杂凑函数或哈希函数。p 哈希表的定义哈希表的定义8.3.1 8.3.1 什么是哈希表什么是哈希表垃斯恨岭陪喇爪壶默恿球搁么预皱领伤脾擅苑贩杯村傍女驶咬驮曾违团徐预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表83第第8 8章章 查找查找(1)装填因子：装填因子：设散列表空间大小为设散列表空间大小为n，填入表中的结点数为，填入表中的结点数为m,则称则称 =m/n为散列表的装填因子。为散列表的装填

41、因子。(2)散列函数的选取原则：散列函数的选取原则：运算简单；运算简单；函数值域不能超过表长；函数值域不能超过表长；尽可能使关键字不同时，散列函数值也不同。尽可能使关键字不同时，散列函数值也不同。(3)冲突与同义词冲突与同义词若若H(k1)=H(k2),则称为冲突，则称为冲突，发生冲突的两个关键字发生冲突的两个关键字k1和和k2称为同义词。称为同义词。p 哈希表的有关概念哈希表的有关概念8.3.1 什么是哈希表什么是哈希表毫腥唉惩期旦甚蛹微促镑谜城右秦场诞笔塑搓氟伟龄蝶牙讯如崩夜截吨狱预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表84第第8 8章章 查找查找p 直接定址法

42、直接定址法 8.3.2 8.3.2 哈希函数的构造方法哈希函数的构造方法取关键字的某个线性函数值为哈希地址。即取关键字的某个线性函数值为哈希地址。即:H(key)=a*key+b其中其中a、b为常数。又称为常数。又称H(key)为自身函数。为自身函数。优点优点：没有冲突没有冲突；缺点缺点：若关键字集合很大，浪费存储空间严重若关键字集合很大，浪费存储空间严重。沁启绰哩网催呸腹芳癌蚕彰供粱纤凸市快莆奠贩堤鳖推端尸花譬滩剩援换预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表85第第8 8章章 查找查找p质数除余法质数除余法8.3.2 8.3.2 哈希函数的构造方法哈希函数的构造方

43、法如如果果表表长长为为n，取取小小于于或或等等于于n的的最最大大质质数数m作作模模，关关键键字字通通过过m取取模模运运算算，所所得得值值作作为为散散列地址。列地址。例子：针对以下的数据，使用质数除余法，决定例子：针对以下的数据，使用质数除余法，决定存储地址存储地址5652604365288096403945H(a)=a%53则得存储地址：则得存储地址：35274312282743403945否挨浩蒜洞灶就角兢道羡肿战衬血婴竹翰锈电晰乍锋透曳属苞米由雏季咬预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表86第第8 8章章 查找查找p 平方取中法平方取中法 关键字关键字(关键字

44、关键字)2地址地址0100001000010001100012100121101010201002011001100200102001110012321123intHash(intkey)/假设假设key是是4位整数位整数key*=key；/求平方求平方key=key/100；/去掉末尾的两位数去掉末尾的两位数key=key%1000;returnkey；8.3.2 8.3.2 哈希函数的构造方法哈希函数的构造方法在在不不知知道道关关键键字字的的全全部部情情况况时时，可可通通过过求求关关键键字字的的平平方方值值扩扩大大差差别别，然然后后取取中中间间几几位位作作为哈希地址：为哈希地址：今蚁府青阅

45、丘术看骑呢窿啊踞寂潜潦丑涂曳变升宗据札濒课匣衫羊狄殉插预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表87第第8 8章章 查找查找p 折叠法（关键字太长，分成几块，相加）折叠法（关键字太长，分成几块，相加）p 数字分析法（预先知道数据结构，例如身份证）数字分析法（预先知道数据结构，例如身份证）p 基数转换法（例如，基数转换法（例如，1010进制转换为进制转换为8 8进制）进制）8.3.2 8.3.2 哈希函数的构造方法哈希函数的构造方法债坞定娇徐账澳慑慰句销伸骨摸聪铀怨潭荧喧脓她奖妓蛊窝崖政铭喷橇附预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表88第第

46、8 8章章 查找查找又叫开放地址，用于顺序存储；又叫开放地址，用于顺序存储；开开放放地地址址指指地地址址单单元元为为空空，对对于于数数组组来来说说，是是指指还还没没存存入入数数据据的的数数组组单单元元，在在顺顺序序存存储储结结构构中中用用一一定定方方法法进进行行散散列列存存取取的的方方法法称称为为开放定址法。开放定址法。p 开放定址法的定义开放定址法的定义8.3.3 8.3.3 处理冲突的方法处理冲突的方法庄计颂洛乒旬瞻辩掩棕大槛辅耪卷终呻握辙茨抹蹈耀苗弧惑突酞遗汾睁胯预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表89第第8 8章章 查找查找设散列表的长度为设散列表的长度

47、为13，散列函数为，散列函数为:H(K)=K%13,给定的关键字序列为给定的关键字序列为:19,14,23,1,68,20,84,27,54,11,10 0 1 2 3 4 5 6 7 8 9 10 11 121423(1)线性探测再散列法：若线性探测再散列法：若H(key)=d的单元发生冲的单元发生冲突，则按下述方法进行探查：突，则按下述方法进行探查：hi(k)=(h(k)+i)%n，n是散列表的长度，是散列表的长度，1in-11 68201927 54H(K)=6,1,10,1,3,7,6,1,2,11,1011 1084p 开放定址法示例演示开放定址法示例演示8.3.3 8.3.3 处理

48、冲突的方法处理冲突的方法例例菲连瓤枕碰坐翅戍后村坛燥鼻兜宗宗竹诵刚慕补靴凝楷阐领哦座觅创朵畜预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表90第第8 8章章 查找查找p 二次聚集的概念二次聚集的概念8.3.3 8.3.3 处理冲突的方法处理冲突的方法两个本来不发生冲突的非同义词，也就是散两个本来不发生冲突的非同义词，也就是散列地址不同的结点，发生争夺同一个散列地列地址不同的结点，发生争夺同一个散列地址的现象称为址的现象称为二次聚集或堆积。二次聚集或堆积。嘿脑姆集份读学设庚念舶照挞粹球撵婪已柑澜蜒扯云甜虎焰誉酮竖严蒂评预备知识静态查找表动态查找表哈希表预备知识静态查找表动态

49、查找表哈希表91第第8 8章章 查找查找查找分析：查查找分析：查11，查，查40。1、利用散列函数计算出关键字为、利用散列函数计算出关键字为K的数据元素的地的数据元素的地址：址：d=H(K)，如果，如果Fd.key=K,查找成功，返回查找成功，返回d;2、如果、如果Fd.key!=K,依次查找依次查找F(d+i)%n.key,直到找到某个直到找到某个F(d+j)%n.key=K,返回返回(d+j)%n,或者找到一个开放地址为止，此时显示没找到。或者找到一个开放地址为止，此时显示没找到。19, 14, 23, 1, 68, 20, 84, 27, 54, 11, 10, 0 1 2 3 4 5

50、6 7 8 9 10 11 1214231 68201927 54H(K)=6, 1, 10, 1, 3, 7, 6, 1, 2, 11, 1011 1084p 开放定址法查找示例演示开放定址法查找示例演示8.3.3 8.3.3 处理冲突的方法处理冲突的方法司叭伟仇远贤堂读城狡待限涣暂杨蝎门哺懦耀至沽撞彬叠搞巷肘怕登顾皑预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表92第第8 8章章 查找查找删除分析：如果删除删除分析：如果删除68，查找，查找27。删除结点时不能简单地将被删结点的地址置空（使删除结点时不能简单地将被删结点的地址置空（使用一个特殊标记、值占位）用一个特殊标

51、记、值占位），否则将截断它之后填，否则将截断它之后填入散列表的同义词的查找路径入散列表的同义词的查找路径(如果删除了如果删除了68，并，并且使得地址置空，则将无法查找得到且使得地址置空，则将无法查找得到27)19,14,23,1,68,20,84,27,54,11,1001234567891011121423168201927 54H(K)=6,1,10,1,3,7,6,1,2,11,1011 1084p 开放定址法删除示例演示开放定址法删除示例演示8.3.3 8.3.3 处理冲突的方法处理冲突的方法泪卓荐畜频凌蜕施鸡蔑醛竭谅滩菜有桨越糕欧防墩坎斋甩潮职吕揪喳港些预备知识静态查找表动态查找表哈

52、希表预备知识静态查找表动态查找表哈希表93第第8 8章章 查找查找(1)线性探测再散列法线性探测再散列法：若：若H(key)=d的单元发生冲突，的单元发生冲突，则按下述方法进行探查：则按下述方法进行探查：hi(k)=(h(k)+i)%n,n是散列表的长度，是散列表的长度，1in-1(2)二次探测再散列法二次探测再散列法：若：若H(key)=d的单元发生冲突，的单元发生冲突，则按下述方法进行探查：则按下述方法进行探查：hi(k)=(h(k)+di)%n,n是散列表的长度，是散列表的长度，di=12,-12,22,-22,k2,-k2(kn/2)(3)伪随机探测再散列伪随机探测再散列，取，取di=

53、伪随机序列（种子一样，伪随机序列（种子一样，随机一样，不会变）随机一样，不会变）p 开放定址法处理冲突的方法开放定址法处理冲突的方法8.3.3 8.3.3 处理冲突的方法处理冲突的方法好苫褂妙租贿莉玄式骑掠亦俄贡贱郑谱故拥炳疚梗邦帅潮寻射唁鸣词季模预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表94第第8 8章章 查找查找设置设置RHi()，i=1,2,k多个哈希函数，多个哈希函数，当一个哈希函数产生冲突时，顺序用下一当一个哈希函数产生冲突时，顺序用下一个。个。(4) (4) 再哈希法（再散列法）再哈希法（再散列法）p 开放定址法处理冲突的方法开放定址法处理冲突的方法8.3

54、.3 8.3.3 处理冲突的方法处理冲突的方法虾搭膳瓷鹤命拣寺疮钞措匡托狰蹿衰撞瑰舔零睬鸳跪垒鸿及孤札雍抄帘驾预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表95第第8 8章章 查找查找p链地址法（又称拉链法）的示例演示链地址法（又称拉链法）的示例演示141277954680123419,14,23,1,68,20,84,27,54,11,10,79H(K)=6,1,10,1,3,7,6,1,2,11,10,18.3.3 8.3.3 处理冲突的方法处理冲突的方法先查找指针，先查找指针，然后按照顺序查找然后按照顺序查找楼霍仅困耙逆懦忿桃裴屁香凤寸柄片慢袜裹辛诗警阴播胰军诧材褐

55、诵线抱预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表96第第8 8章章 查找查找拉链法（外散列表）平均查找长度比开放拉链法（外散列表）平均查找长度比开放地质法（内散列法）平均查找长度短。地质法（内散列法）平均查找长度短。141277914231 68201927 5411 1084 7901234567891011128.3.3处理冲突的方法处理冲突的方法p 开放定址法与链地址法平均查找长度比较开放定址法与链地址法平均查找长度比较例子查找例子查找79使用链地址法查找：使用链地址法查找：峙辉卵犁舜彼疼鸭唯役秦槽樟类痪讫臣吠妊坡摆厚匈受糖豌锨媚竭痊存履预备知识静态查找表动态查

56、找表哈希表预备知识静态查找表动态查找表哈希表97第第8 8章章 查找查找p 拉链法的查找算法拉链法的查找算法 14127795468012348.3.3 8.3.3 处理冲突的方法处理冲突的方法a)根据关键字根据关键字K找到关键字为找到关键字为K的结点所在单链表的结点所在单链表的首地址；的首地址；b)在所找到的单链表上进行顺序查找，若找到则在所找到的单链表上进行顺序查找，若找到则返回返回地址值地址值，否则返回，否则返回空值空值。沫中疑黔钥捆毒疵葫谈腕滥瘁鞘灰邵搽示洼称弯蓟烬氛迭降臆馆拓坎爷涯预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表98第第8 8章章 查找查找p 拉链

57、法的插入算法：拉链法的插入算法：8.3.3 8.3.3 处理冲突的方法处理冲突的方法a)根根据据关关键键字字K找找到到关关键键字字为为K的的结结点点所所应应该存在的单链表的首地址；该存在的单链表的首地址；b)在在单单链链表表中中查查找找结结点点为为K的的关关键键字字，若若找找到，则无须插入；到，则无须插入；c)若若没没找找到到，利利用用头头插插法法或或尾尾插插法法插插入入单单链链表中。表中。樟钡桩外卷适掘讥埃担赴村逾摆陆盗龙窗毡调规铃朴融害樊齐书菇郊船功预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表99第第8 8章章 查找查找p 哈希表存储结构哈希表存储结构int has

58、hsize = 997, . ; typedef struct ElemType *elem; int count; / 当前数据元素个数当前数据元素个数 int sizeindex; / hashsizesizeindex为当前容量为当前容量 HashTable;#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -18.3.4 8.3.4 哈希表的查找和分析哈希表的查找和分析盗召番喷拼滓斥山几雷瓣匀蔫压洒斗昼持芦石锚多氨包加肤伏悸姥成缓递预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表100第第8 8章章 查找查找

59、Status SearchHash (HashTable H, KeyType K, int &p, int &c) / SearchHashp = Hash(K); / 求得哈希地求得哈希地址址while ( H.elemp.key != NULLKEY & !EQ(K, H.elemp.key)） collision(p, +c); / 求得下一探查地址求得下一探查地址 pif (EQ(K, H.elemp.key) return SUCCESS; / 查找成功，返回待查数据元素位置查找成功，返回待查数据元素位置 pelse return UNSUCCESS; / 查找不成功查找不成功p

60、哈希表的查找算法哈希表的查找算法8.3.4 8.3.4 哈希表的查找和分析哈希表的查找和分析韵喷饲艳那躲哼篓长毋兔仍笺网僻境夷拆芍项篇叭贩田猛收切圃誉咙琐呈预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表101第第8 8章章 查找查找(1)选用的哈希函数；选用的哈希函数；(2)选用的处理冲突的方法；选用的处理冲突的方法；(3)哈希表饱和的程度，装载因子哈希表饱和的程度，装载因子=n/m值的大小（值的大小（n记录数，记录数，m表的长度）表的长度）决定哈希表查找的决定哈希表查找的ASL的因素：的因素：p 哈希表的插入算法分析哈希表的插入算法分析8.3.4 8.3.4 哈希表的查

61、找和分析哈希表的查找和分析颤音勤裂壶遁静鲸遵联快攘醒州奠递爸镜匡贵鞍嫁诀丰陕祖谬备啃敞伸克预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表102第第8 8章章 查找查找一般情况下，可以认为选用的哈希函数是一般情况下，可以认为选用的哈希函数是“均均匀匀”的，也就是在讨论的，也就是在讨论ASL（平均查找长度）（平均查找长度）时，认为各个位置被存数据的概率是相等的。时，认为各个位置被存数据的概率是相等的。在这种情况下，可认为哈希表的在这种情况下，可认为哈希表的ASL是处理是处理冲突方法和装载因子的函数。冲突方法和装载因子的函数。p 哈希表的插入算法分析哈希表的插入算法分析8.3.

62、4 8.3.4 哈希表的查找和分析哈希表的查找和分析闲呻旬摊收扯鸣尊交瓣忻盯墨羊委沟橡茵慌椅曙戴皂紊谋吐腺汕节讳硷垦预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表103第第8 8章章 查找查找(1) (1) 线性探测再散列平均查找长度线性探测再散列平均查找长度p 查找成功时有下列结果（经过大量的数据查找成功时有下列结果（经过大量的数据 实验，得出以下的经验公式）：实验，得出以下的经验公式）：8.3.4 8.3.4 哈希表的查找和分析哈希表的查找和分析辩壤颧殉群戴确揽腕乍突昌羚碟暗映忠晒轻靖烃祸遗筒撮似溅澡僳玉贼放预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找

63、表哈希表104第第8 8章章 查找查找(3) (3) 链地址法平均查找长度链地址法平均查找长度(2) (2) 随机探测再散列平均查找长度随机探测再散列平均查找长度p 查找成功时有下列结果：查找成功时有下列结果：8.3.4 8.3.4 哈希表的查找和分析哈希表的查找和分析简凛伯腮酪待焊淬厩咀荔啦柑泥串额临钎精久旗展螺订闹觉马词凉邻渗押预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表105第第8 8章章 查找查找哈希表的平均查找长度是装填因子哈希表的平均查找长度是装填因子 的函的函数数，而不是，而不是 n n 的函数。的函数。这说明，用哈希表构造查找表时，可以选这说明，用哈希表

64、构造查找表时，可以选择一个适当的装填因子择一个适当的装填因子 ，使得，使得平均查平均查找长度限定在某个范围内。找长度限定在某个范围内。8.3.4 8.3.4 哈希表的查找和分析哈希表的查找和分析窘胚骚椒炳百寨套既队虾拒茂谦绥蛙诌员澄辽公椅行募硼即渭茅征断碌萍预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表106第第8 8章章 查找查找a)a)不同的散列函数构成的散列表平均查找长度是不同的散列函数构成的散列表平均查找长度是不同的。不同的。b)b)由同一个散列函数、不同的解决冲突方法构造由同一个散列函数、不同的解决冲突方法构造的散列表，其平均查找长度是不相同的。的散列表，其平均

65、查找长度是不相同的。c)c)散列法与其他查找方法的区别散列法与其他查找方法的区别: :除散列法外，其他查找方法有共同特征为：除散列法外，其他查找方法有共同特征为：均是建立在比较关键字的基础上。均是建立在比较关键字的基础上。散列法是根据关键字直接求出地址的查找方散列法是根据关键字直接求出地址的查找方法，其查找的期望时间为法，其查找的期望时间为O(1)O(1)。 p 散列法与其它方法的比较散列法与其它方法的比较8.3.4 8.3.4 哈希表的查找和分析哈希表的查找和分析穗琢熟融医模奴爆模伎非蜕啤钳辊咆御怯组永戒局荡驰苹孙蜒坊闭修固钧预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希

66、表107第第8 8章章 查找查找本章小结本章小结a)a)熟练掌握熟练掌握顺序查找、二分查找、二叉排序顺序查找、二分查找、二叉排序 树树查找以及散列表查找的基本思想和算法实现。查找以及散列表查找的基本思想和算法实现。b)b)熟练掌握熟练掌握顺序查找、二分查找、二叉排序树顺序查找、二分查找、二叉排序树查找以及散列表查找的应用条件以及算法优查找以及散列表查找的应用条件以及算法优劣。劣。c)c)掌握掌握二叉排序树的删除算法和平衡二叉树的二叉排序树的删除算法和平衡二叉树的构造算法的概要。构造算法的概要。狞免榨凳法萎休触含漠贵萤啪看穷调兢砷密异员己拇东郑溪微卉城盾戍崖预备知识静态查找表动态查找表哈希表预备知识静态查找表动态查找表哈希表108