数据结构复习资料 第九章 查找.doc

第九章 查找第九章 查 找重 点：正确理解衡量一个查找算法优劣的主要标准，即平均查找长度；掌握各种查找算法及它的适应范围。掌握各种查找算法性能的分析。难 点：折半查找，二叉排序树的构造及其查找算法，哈希查找及相应的查找算法。学习提要：1. 练掌握顺序表和有序表的查找方法。2. 熟练掌握二叉排序树的构造和查找方法。3 .掌握二叉平衡树的维护平衡方法。4. 熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。5. 掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。1.基本概念查找表（Search Table）静态查找表动态查找表查找(Search) 查找的结果通常有两种可能：查找成功查找不成功关键字（key）主关键字（Primary key）说明：今后所讨论的是基于主关键码字的查找。平均查找长度（ASLAverage Search Length）衡量查找算法的标准：（1）平均查找长度；（2）算法所需要的存储量和算法的复杂性等。这里只考虑基于关键码（主关键码）的查找。对不同的存储结构，其查找的方法也不同。9.1 静态查找表一顺序查找（可以用顺序表或线性链表表示静态查找表）1顺序查找是线性表的最简单的查找方法。方法优点缺点2查找算法见书。注意：“监视哨”技术的引入，这是程序设计技巧上的改进。3查找长度的分析二. 二分法查找（折半查找）是一种效率较高的线性表的查找方法，但对查找表有2点要求：（1）线性表中结点必须是按关键码字排好序的；（2）线性表必须顺序存储。1二分法查找的方法：优点缺点2算法 三索引顺序表的查找（分块查找）详见，图9.6。分块查找又称索引顺序查找，这是顺序查找的一种改进方法。方法由于索引项组成的索引表按关键字有序，则确定块的查找可以用顺序查找，亦可用折半查找，而块中记录是任意排列的，则在块中只能是顺序查找。查找分两步完成：（1）首先找到所在块（用顺序或折半查找法均可）（2）在块中的查找（只能用顺序查找方法）分块查找的平均查找长度其中，为查找索引表确定所在块的平均查找长度；为在块中查找元素的平均查找长度。例 对一表长的查找表，若利用索引查找时，平均应分成几块？其平均查找长度最小为多少？解：， 因此，应均匀分成14块，其。若用折半查找确定所在块，则分块查找的平均查找长度为* *分块查找介于顺序查找（效率最低但限制最少）和二分法查找（效率最高但限制最强）之间。9.2 动态查找法如何克服二分法查找的插入，删除不方便的缺点，而又能保持其快速检索的优点呢？采用二叉排序树组织查找表中的记录便可达到目的。一二叉排序树1定义(递归定义) 例 * 中序遍历二叉排序树上的结点可得到一个从小到大排好序的序列。2二叉排序树的查找方法3查找算法* 二叉排序树的平均检索长度与二分法检索相同量级为。二在二叉排序树上插入、删除结点1在二叉排序树上插入结点例：将以下结点依次插入一棵初始为空的二叉排序树中：* 中序遍历此二叉排序树可得一有序序列（从小到大）所以，将关键码组织成一棵二叉排序树的过程实际上起了对此集合中的关键码进行排序的作用。2在二叉排序树上删除结点不同于插入结点，删除结点可以删除而二叉排序树上的任何结点，但不能将以该结点上为根的子树都删除，只能删除掉这一结点，并且还要保持二叉树原来的性质（任是一棵二叉排序树）删除根结点例四平衡二叉树（AVL树）1定义（递归定义）2平衡因子例* 平衡二叉树上所有结点的平衡因子只可能是-1、0和1。* 满二叉树一定是完全二叉树，完全二叉树一定是平衡二叉树，但反之则不然。9.3 哈希表（Hash Table）一什么是哈希表其基本思想散列表用散列法存储的线性表叫散列表。1散列法存储的具体过程2碰撞（冲突）同义词如何解决碰撞？（即用什么方法存储同义词）一个好的散列函数通常只有减少碰撞发生的次数，无法保证绝对不产生碰撞。发生碰撞，找另一个函数再映象到新的集合，可解决碰撞，但处理效率低。基本区域发生碰撞时： 同义词可存放在基本区域内还没被占用的单元里。 可放到基本区域以外另开辟的区域（称溢出区）中负载因子（散列法的一个重要参数）： 负载因子的大小，对于碰撞的发生频率影响很大。（散列表装得越满，则再要装入新结点时碰上已有结点的可能性越大）时碰撞是不可避免的，一般取，但太小，浪费空间。一般要取得适当，既不过多地增加碰撞，有较快的检索速度，又不浪费空间。3检索（查找）* 哈希存储是一种希望在检索时不需进行关键码比较的存储方式（但由于有冲突存在，在实际检索时仍需进行比较）* 散列法的一个重要特征是平均检索长度不直接依赖于表里结点个数。散列法的平均检索长度不随表里结点数目的增加而增加，而随负载因子的增加而增加，如果安排得好，平均检索长度可以小于1.5。因此，散列法成为一种很受欢迎的组织线性表的方法。进行散列存储时需要考虑的2个重要问题是： 如何构造（选择）“均匀的”散列函数? 用什么方法解决冲突?二如何构造哈希函数构造哈希函数有若干方法，详见。仅要求学生掌握有哪些构造哈希函数的方法。三处理冲突的方法哈希函数当冲突发生时，有四种处理冲突的方法，但只要求学生掌握两种。1开放定址法，其中：哈希函数；哈希表表长； 为增量序列，有三种取法例：构造哈希表表长，关键字分别为，试比较三种不同的处理冲突的方法（取伪随机数序列为9），其中：哈希函数 mod 11。二次聚集2再哈希法，3链地址法将互为同义词的所有关键字的记录存储在同一线性链表中。例：。已知一组关键字（19，14，23，01，68，20，84，27，55，11，10，79），则按哈希函数 mod 13和链地址法处理冲突构造所得的哈希表()。例：已知