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