软件技术基础新课件(查找与排序)分析.ppt

例 设有一组关键字序列为(48，24，53，20，35，90)，构造二叉排序树。 此二叉树的中序遍历是？ 二叉排序树的查找分析 二叉排序树的平均查找长度取决于二叉排序树的深度。 这与折半查找类似（取决于其判定树）。 然而，折半查找长度为n的表的判定树是惟一的，而含有n个结点的二叉排序树却不惟一。 所以，二叉排序树查找成功的平均查找长度取决于二叉排序树的形状，而二叉排序树的形状既与结点数目有关，更取决于建立二叉排序树时结点的插入顺序。 例 已知长度为6的线性表是(45，24，53，13，30，85)，若按表中元素的顺序依次插入，得到二叉排序树如图 (a)所示；若依次序13,?24,?30,?45，53，85插入，得到二叉排序树为图 (b)所示 二叉排序树查找的平均比较次数取决于二叉树的深度。 最好情况是：所生成的二叉排序树中，任一结点的左、右子树的深度相差都不超过1，即二叉排序树是一棵平衡二叉树。 最坏情况是：所生成的二叉排序树蜕化为单支树时，其平均比较次数就和顺序查找相同了。 4、 散列（ 哈 希 查 找） 无论是顺序查找、折半查找、分块查找，还是二叉排序树查找，都需进行一系列和关键字的比较才能确定被查元素在查找表中的位置，查找的效率依赖于查找过程中所进行的比较次数。 而哈希查找的思想与前面四种方法完全不同，哈希查找方法是利用关键字进行某种运算后直接确定元素的存储位置，所以哈希查找方法是用关键字进行计算元素存储位置的查找方法。 非常适用于数据元素长度不等情况，如文件系统 在讨论哈希查找之前，先讨论适用于哈希查找的查找表的组织方式——哈希表。 4.3.1 哈希表的建立 哈希表的建立：以线性表中的每个元素的关键字K为自变量，通过一种函数H(K)计算出函数值，然后将该元素存入与该函数值相应的存储单元中。 查找时，只要根据要查找的关键字用同样的函数计算出地址H(K)，然后直接到相应的单元中去取所要找的元素。 通过函数H(K)计算的函数值建立起来的符号（地址）表就称为哈希表。 问题：对同一个哈希函数H(K)和两个关键字K1和K2，如果K1≠K2，而H(K1)=H(K2)，这种现象称为冲突。 在构造哈希函数时应避免冲突。但没有冲突的函数是很不好找的，因为通常哈希函数是一个压缩映象，即关键字集合大，地址集合小。一般只能尽可能地避免冲突的发生。 例如，一个符号表其标识符至多由5个英文字母组成，则不同的标识符可能有 265+264+263+262+26=12 356 630 (个)。 如果一个标识符对应一个存储地址，就不会发生冲突了，但这是不可能也没有必要的。因为存储空间难以满足，而且任何一个源程序也不会有这么多的标识符。 由于哈希法用哈希函数转换记录关键字得到存储地址，把各记录散列到相应的存储单元里去，所以也称之为散列地址法或关键字转换法。 对于哈希法，主要考虑两个问题： (1) 构造一个合适的哈希函数。分析数据元素的关键字集合之特点，找出适当的函数H(K)，使计算出的存储地址尽可能均匀地分布在哈希表中；同时也希望函数H(K)尽量简单，便于快速计算；哈希函数H(K)一般应是一个压缩映象函数，它应具有较大的压缩性，以节省存储空间。 常用的构造哈希函数的方法有： ①??? 数字分析法； ②??? 平方取中法； ③??? 折叠法； ④??? 除留余数法； ⑤??? 直接定址法； ⑥??? 随机数法。 (2) 如何解决冲突。哈希函数应具有较好的散列性，冲突是不可避免的，但应尽量减少。若已知哈希函数及冲突处理方法，哈希表的建立步骤如下： Step1：取出一个数据元素的关键字Key，计算其在哈希表中的存储地址D=H(Key)。若存储地址为D的存储空间还没有被占用，则将该数据元素存入；否则发生冲突，执行Step2。 Step2：根据规定的冲突处理方法，计算关键字为Key的数据元素的下一个存储地址。若该存储地址的存储空间没有被占用，则存入；否则继续执行Step2，直到找出一个存储空间没有被占用的存储地址为止。 Step3：重复Step1和Step2，直到所有的数据元素都被存储为止。 4.3.2 处理冲突的方法 哈希法中不可避免地会出现冲突现象，所以关键的问题是如何解决冲突。处理冲突的方法多种多样，常用的方法有：开放定址法、链地址法、再哈希法和公共溢出区法。