数据结构复习资料
查找有内查找和外查找之分。若整个查找过程全部 在内存进行，则称这样的查找为内查找；反之，若在查 找过程中还需要访问外存，则称之为外查找。我们仅介 绍内查找。 要衡量一种查找算法的优劣，主要是看要找的值与关 键字的比较次数，但我们将找到给定值与关键字的比较 次数的平均值来作为衡量一个查找算法好坏的标准，对 于一个含有n个元素的表，查找成功时的平均查找长度可 表示为ASL= ∑ pi ci ,其中Pi为查找第i个元素的概率， i =1 且 ∑ pi =1。一般情形下我们认为查找每个元素的概率相i =1 nn
等，Ci为查找第i个元素所用到的比较次数。