|
本章简介 由于查找运算的使用频率很高几乎在任何一个计算机系统软件和应用软件中都会涉及到所以当问题所涉及的数据量相当大时 查找方法的效率就显得格外重要在一些实时查询系统中尤其如此因此本章将系统地讨论各种查找方法并通过对它们的效率 分析来比较各种查找方法的优劣 查找的基本概念 查找表和查找 一般假定被查找的对象是由一组结点组成的表(Table)或文件而每个结点则由若干个数据项组成并假设每个结点都有一个 能惟一标识该结点的关键字 查找(Searching)的定义是给定一个值K在含有n个结点的表中找出关键字等于给定值K的结点若找到则查找成功返回该 结点的信息或该结点在表中的位置;否则查找失败返回相关的指示信息 查找表的数据结构表示 ()动态查找表和静态查找表 若在查找的同时对表做修改操作(如插入和删除)则相应的表称之为动态查找表否则称之为静态查找表 ()内查找和外查找 和排序类似查找也有内查找和外查找之分若整个查找过程都在内存进行则称之为内查找;反之若查找过程中需要访问外 存则称之为外查找 平均查找长度ASL 查找运算的主要操作是关键字的比较所以通常把查找过程中对关键字需要执行的 平均比较次数(也称为平均查找长度)作为衡量 一个查找算法效率优劣的标准 平均查找长度 ASL(Average Search Length)定义为 其中 ①n是结点的个数; ②P i 是查找第i个结点的概率若不特别声明认为每个结点的查找概率相等即 p l =p …=p n =/n ③c i 是找到第i个结点所需进行的比较次数 注意 为了简单起见假定表中关键字的类型为整数 typedef int KeyType; //KeyType应由用户定义 |
