数据结构与算法设计PPT (28).pdf

第7章 查找7.1 查找问题定义查找问题查找表-待查找的对象集合，提供查找操作 类型-静态查找表（static search table）：结合内元素不会变动-动态查找表（dynamic search table）可以对查找表的元素进行增加、删除属性-key（关键字）：一组唯一标识一个对象的一个或多个属性。查找问题定义 设k1，k2，kn是互不相同的关键字值，集合T(即查找表)中有n个记录，形为(k1,I1),(k2,I2),(kn,In)，其中Ij是与关键字kj相关的信息，1=j=n。给定一个特定的关键字值K，检索问题即在T中确定记录(kj,Ij)，使kj=K 给定键值K和查找表A，返回K在A中的位置或不存在的标识，如果K出现多次，则返回任何出现的一个位置查找算法的效率度量 查找算法的算法效率用比较次数衡量-查找失败情况下的比较次数-查找成功的最坏情况下的比较次数-平均查找长度（AVL-平均比较次数）对于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL=!#$pi ci，其中pi为查找第i个元素的概率，且!#$pi=1。一般情形下认为查找每个元素的概率相等，ci为查找第i个元素所用到的比较次数。静态查找表分成以下几类-顺序查找(Sequential search),-折半查找（Binary search）-块查找（Block search）动态查找表类别划分 二叉搜索树（Binary Search Tree）AVL 树（AVL Tree）B-树（B-Tree）