线性表的查找

查找运算是非常常见的,面对一些数据量很大的实时系统,如订票系统、互联网上的信息检索系统等,查找效率非常重要。接下来我将针对查找运算,讨论何时采用何种数据结构,使用什么样的方法,并通过对它们的效率进行分析来比较各种算法在不同条件下的优劣。

查找的基本概念

  • 查找表:由同一类型的数据元素(或记录)构成的集合
  • 静态查找表:对查找表没有修改操作
  • 动态查找表:对查找表具有修改操作
  • 关键字:记录中某个数据项的值,可用来识别一个记录
  • 主关键字:唯一标识数据元素
  • 次关键字:可以标识若干个数据元素
  • 查找算法的评价指标:
    关键字的平均比较次数,也称平均搜索长度ASL(Average Search Length)
    $$ASL=\sum_{i=1}^{n}p_ic_i$$
    n:记录的个数
    $p_i$:查找第i个记录的概率(通常认为pi=1/n)
    $c_i$:找到第i个记录所需的比较次数

线性表的查找

顺序查找(线性查找)

应用范围:顺序表或线性链表表示的静态查找表,表内元素之间无序

数据元素类型定义:

1
2
3
4
typedef struct	{
Keytype key; //关键字域
InfoType otherinfo; //其他域
}ElemType;

顺序表定义:

1
2
3
4
typedef struct	{
ElemType *R; //存储空间基地址
int length; //当前长度
}SSTable;

顺序查找算法:

1
2
3
4
5
6
int Search_Seq(SSTable ST,KeyType key)	{
for (i=ST.length;i>=1;--i)
if (ST.R[i].key==key)
return i;
return 0;
}

该算法在查找过程中每步都要检测整个表是否查找完毕(即是否i>=1),可以对其稍加改进,把待查关键字key存入表头(哨兵),从后向前逐个比较。

顺序查找算法(改进):

1
2
3
4
5
int Search_Seq(SSTable ST,KeyType key)	{
ST.R[0].key=key; //哨兵
for (i=ST.length;ST.R[i].key!=key;--i); //空循环,直至找到关键字退出循环
return i; //返回找到的关键字i
}

性能分析:

  • 空间复杂度:一个辅助空间
  • 时间复杂度:设表中各记录查找概率相等,
    a:查找成功时的平均查找长度
    $$ASL=\sum_{i=1}^{n}p_ic_i=(1+2+…+n)/n=(n+1)/2$$
    b:查找不成功时的平均查找长度为n+1

算法特点:

  • 算法简单,对表结构无任何要求(顺序和链式),但是n很大时查找效率较低,不宜使用此类算法。
  • 改进措施:非等概率查找时,可按照查找概率进行排序

折半查找(二分查找)

应用范围:要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

折半查找算法(非递归):

1
2
3
4
5
6
7
8
9
10
11
12
13
int Search_Bin(SSTable ST,KeyType key)	{
int low=1,high=ST.length; //置查找区间初值
while (low<=high) {
mid=(low+high)/2; //确定区间中值
if (key==ST.R[mid].key)
return mid; //找到待查元素
else if (key<ST.R[mid].key)
high=mid-1; //缩小范围,继续在前一子表进行查找
else
low=mid+1; //缩小范围,继续在后一子表进行查找
}
return 0; //表中不存在待查元素
}

折半查找算法(递归):

1
2
3
4
5
6
7
8
9
10
11
12
int Search_Bin(SSTable ST,KeyType key,int low,int high)	{
// int low=1,high=ST.length; //外部主函数中定义
if (low>high)
return 0; //递归结束条件
mid=(low+high)/2; //确定区间中值
if (key==ST.R[mid].key)
return mid; //找到待查元素
else if (key<ST.R[mid].key)
return Search_Bin(ST,key,low,mid-1); //缩小范围,继续在前一子表进行查找
else
return Search_Bin(ST,key,mid+1,high); //缩小范围,继续在后一子表进行查找
}

实例:已知如下11个数据元素的有序表(关键字即为数据元素的值)(5,13,19,21,37,56,64,75,80,88,92),请给出查找关键字21和70的数据元素的查找过程。

性能分析:

折半查找可以用二叉树来描述,把当前查找区间的中间位置作为根,左子表和右子表分别作为根的左子树和右子树,由此得到的二叉树称为折半查找的判定树

  • 若所有结点的空指针域设置为一个指向一个方形结点的指针,称方形结点为判定树的外部结点,圆形结点为内部结点
  • 假定每个元素的查找概率相等,由判定树可知,对该有序表进行折半查找的平均查找长度为
    $$ASL=\frac{1}{11}(11+22+43+4*4)=3$$

  • 从判定树上可见,成功的折半查找恰好是走了一条从判定树的根到被查结点的路径,经历比较的关键字个数恰为该结点在树中的层次,最多不超过数的深度$log_2n+1$;查找不成功的过程就是走了一条从根结点到外部结点的路径d或d-1。

  • 时间复杂度为$O(log_2n)$

算法特点:

  • 比较次数少,查找效率高
  • 对表结构要求高,只能用于顺序存储的有序表,查找前需要先排序。
  • 不适用于数据元素经常变动的线性表。

分块查找(索引顺序查找)

  • 性能介于顺序查找折半查找之间。
  • 需要为每个子表建立一个索引项,包括关键字项(其值为该字表内的最大关键字)和指针项(指示该字表的第一个记录在表中的位置)。
  • 索引项组成的索引表按关键字有序,则确定块的查找可以用顺序查找,也可以用折半查找;而块中记录是任意排列的,只能用顺序查找。
  • 如果线性表既要快速查找又经常动态变化,则可以采用分块查找。
-------------The End-------------