数据结构课件第九章

查找和排序是数据处理系统中最重要的两个操作；其次是插入、删除操作；讨论查找、排序，不可避免要涉及文件、记录、关键字等概念。文件——查找表，是由同一类型的数据元素(记录)构成的集合记录——构成文件的数据元素，是文件中可存取的数据的基本单位字段——数据项，数据的最小单位关键字——某个可以用来标识记录的数据项主关键字——某个可以用来唯一标识记录的数据项次关键字——可以用来识别若干记录的数据项第九章查找数据结构课件第九章共43页，您现在浏览的是第1页!D01曲守宁数据库004S01王永燕数据结构003L01潘玉奇程序设计002S01严蔚敏数据结构001………………………课程号课程名教师课程类别课程安排表文件记录数据项主关键字次关键字数据结构课件第九章共43页，您现在浏览的是第2页!对文件经常进行的操作有:1)查询某个“特定”的数据元素是否存在4)对数据元素进行排序2)插入某个数据元素3)删除某个数据元素查找算法排序算法不管何种操作，都遵循一个重要的性质:都是对主关键字操作数据结构课件第九章共43页，您现在浏览的是第3页!9.1静态查找9.1.1顺序查找从表最后一个记录开始，逐个向前进行记录关键字和给定值的比较，相等，查找成功；不等，比较下一个记录；思想:直至个记录，若均不等，则查找不成功。数据结构课件第九章共43页，您现在浏览的是第4页!9.1.2有序表的查找表中数据元素按照主关键字顺序排列。折半查找斐波那契查找插值查找5，13，19，21，37，56，64，75，80，88，92数据结构课件第九章共43页，您现在浏览的是第5页!9.2动态查找表静态查找只是对表中元素进行检索，返回成功或不成功；动态查找不但对表中元素进行检索，还可以通过检索过程来实现表的更新；检索到，则返回成功；检索不到，则将新元素插入到表中适当位置。数据结构课件第九章共43页，您现在浏览的是第6页!查询操作:

13

8523

1837如何查找元素5?555查找成功！数据结构课件第九章共43页，您现在浏览的是第7页!同一序列，不同二叉排序树的查找性能差别很大。例，{45,24,53,12,37,93}452453123793122437455393O(n)O(log

n+1)数据结构课件第九章共43页，您现在浏览的是第8页!例,ABCDABCDEFGABCDEFABCDFGE数据结构课件第九章共43页，您现在浏览的是第9页!如何在二叉排序树的构造过程中实现平衡化从而得到平衡二叉树？例，序列{1324379053}13024-1037-2-10左旋，以失去平衡结点的儿子结点为基准。37241300090-10-1053-20-210先右旋，以失去平衡结点的儿子结点为基准。再左旋，以失去平衡结点的儿子结点为基准。53905390370-1000平衡！数据结构课件第九章共43页，您现在浏览的是第10页!LL型:新结点加入到左子树的左子树中。11021调整规则:右旋，以失去平衡的结点的儿子结点为基准，整棵子树向右下方旋转。ABBLBRARBABRARBL00数据结构课件第九章共43页，您现在浏览的是第11页!LR型:新结点加入到左子树的右子树中。1调整规则:ABBLARCCLCR先左旋，以失去平衡的结点的儿子结点为基准，构造成LL型。后右旋。1002-11数据结构课件第九章共43页，您现在浏览的是第12页!例，设关键字为年龄字段，H(key)=key年龄学号姓名01020356100........................12356100192021192021......张三王五李据结构课件第九章共43页，您现在浏览的是第13页!(2)数字分析法对关键字进行按“位”分析，取重复度小的若干位组合成哈希地址。例，多条记录，关键字为8位十进制数，要求取两位作为哈希地址。813465377137224781387422823013678142281781338967取4、5、6、7位中的任意两位即可。数据结构课件第九章共43页，您现在浏览的是第14页!(4)折叠法将关键字从低到高分割成位数相同的几部分，然后取各部分的叠加和(舍去进位)作为哈希函数。例，图书编号0–442–20586–404422058645864422004+)10088最终取四位0088作为哈希地址。数据结构课件第九章共43页，您现在浏览的是第15页!(6)随机数法取关键字的随机函数值作为哈希地址。H(key)=random(key)总结:灵活运用协同工作数据结构课件第九章共43页，您现在浏览的是第16页!例，除留余数法中关键字28356377105p=21哈希地址7140140解决方法:因地制宜提高素质数据结构课件第九章共43页，您现在浏览的是第17页!(1)开放定址法H(key)=(key)modm在keymodm的基础上，若发现冲突，则使用增量di进行新的探测，直至无冲突出现为止。H(key)哈希函数m哈希表长di增量序列关键如何设计di线性探测法二次探测法随机探测法H(key)=(key+di

)modm数据结构课件第九章共43页，您现在浏览的是第18页!(2)再哈希法定义双重哈希函数。H(key)R

(key)若H(key)出现冲突，则再使用R

(key)求取哈希地址。数据结构课件第九章共43页，您现在浏览的是第19页!二分查找法要求查找表中各元素的键值必须是()排列。

A．递增或递减B．递增C．递减D．无序数据结构课件第九章共43页，您现在浏览的是第20页!从一棵二叉排序树中查找一个元素时，其平均时间复杂度为()。A．O(1)B．O(n)C．O(1og2n)D．O(n2)

数据结构课件第九章共43页，您现在浏览的是第21页!从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为__________和__________。向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的__________子树上。数据结构课件第九章共43页，您现在浏览的是第22页!数据结构课件第九章共43页，您现在浏览的是第23页!12...n-2n-1nTomAnnieJohnRoseJack查找John比较2次查找Jack比较n-1次若查找不存在比较n次数据结构课件第九章共43页，您现在浏览的是第24页!折半查找5，13，19，21，37，56，64，75，80，88，92lowhighmid=(low+high)/2查找211234567891011midmid=6high=mid–1=5highmid=3midlow

=mid+1=4lowmid=4mid找到查找85lowhighmid=6midlow

=mid+1=7lowmid=9midlow

=mid+1=10lowmid=10midhigh=mid–1=9highhigh<low查找不成功数据结构课件第九章共43页，您现在浏览的是第25页!9.2.1二叉排序树(二叉分类树)二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：

(1)左子树上所有结点的值均小于等于它的根结点的值；

(2)右子树上所有结点的值均大于它的根结点的值；

(3)根结点的左、右子树也分别为二叉排序树。

13

8523

1837数据结构课件第九章共43页，您现在浏览的是第26页!

13

8523

1837如何查找元素9?99

9查询+插入操作:查找不成功，执行插入。数据结构课件第九章共43页，您现在浏览的是第27页!为了实现二叉排序树的平均查找长度和log

n等数量级，需要对二叉排序树进行“平衡化”处理，即构造平衡二叉树。9.2.2平衡二叉树——AVL树Adelson—Velskii—Landis平衡二叉树或者是一棵空树，或者是具有下列性质的二叉树:其左子树和右子树的深度之差的绝对值不超过1；其左子树和右子树都是平衡二叉树；平衡二叉树首先是一棵二叉排序树；数据结构课件第九章共43页，您现在浏览的是第28页!结点的平衡因子:该结点的左子树的深度减去右子树的深度。由于平衡二叉树要求左右子树深度之差的绝对值不大于1，故结点的平衡因子只可能为-1、0、1。4524531293例，0100-1可以证明平衡二叉树的深度与logn同数量级。数据结构课件第九章共43页，您现在浏览的是第29页!平衡二叉树调整规则:RR型:新结点加入到右子树的右子树中。1调整规则:左旋，以失去平衡的结点的儿子结点为基准，整棵子树向左下方旋转。ABBLBRAL-10-2-1BAALBLBR00数据结构课件第九章共43页，您现在浏览的是第30页!RL型:新结点加入到右子树的左子树中。1调整规则:ABBRALCCLCR-100-211先右旋，以失去平衡的结点的儿子结点为基准，构造成RR型。后左旋。ACCLALBCRBR-2-1-1CBCLALACRBR0-10数据结构课件第九章共43页，您现在浏览的是第31页!9.3哈希表前面介绍的内容中，记录在文件中的存储地址是随机的三李四王五192120200305200301200302李四王五张三212019查找某一条记录需要进行一系列的“比较”。查找的效率依赖于比较的次数。能否在记录的关键字和存储地址之间构造这样一种关系f，使得关键字和存储地址一一对应？此对应关系f称为哈希函数。学号姓名年龄010203数据结构课件第九章共43页，您现在浏览的是第32页!1.哈希函数的构造方法(1)直接定址法取关键字或关键字的某个线性函数值为哈希地址。H(key)=key(i)或H

(

key)=akey+b.(ii)(i)例，以年龄作为关键字(ii)例，统计解放后出生人口，以出生年份作为关键字地址出生年份011949021950231971481996..................H(key)=key–1949+1数据结构课件第九章共43页，您现在浏览的是第33页!(3)平方取中法取关键字平方后的中间几位作为哈希函数。实验证明:一个数字的平方值的中间部分通常对各位数字都比较敏感。200524200502012005022005032005X402098745764020105200400144120025X20048422002501024320025209820101441取4位48420243数据结构课件第九章共43页，您现在浏览的是第34页!(5)除留余数法H(key)=keymod

p例，关键字28336882107p=21哈希地址7125192数据结构课件第九章共43页，您现在浏览的是第35页!2.哈希冲突对于不同的关键字可能得到同一哈希地址，即key1≠key2，而f(key1)＝f(key2)，这种现象称为哈希冲突。造成原因:A.主观设计不当例，数字分析法中813465377137224781387422823013678142281781338967冲突！数据结构课件第九章共43页，您现在浏览的是第36页!B.客观存在如何设计都不可能完全避免冲突的出现？哈希地址是有限的，而记录是无限的。解决方法:(1)开放定址法(2)再哈希法(3)链地址法(4)建立一个公共溢出区数据结构课件第九章共43页，您现在浏览的是第37页!线性探测法di=1,2,3,…,m-1随机探测法di=

随机数二次探测法di=12,-12,22,-22,32,…,+k2-例，关键字为(17,60,29,38)，哈希表长11，H(ke