数据结构之静态查找表——顺序查找、折半查找与分块查找

前言

在非数值运算问题中，数据存储量一般很大，为了能在大量信息中找到某些值，就需要用到查找技术。而为了提高查找效率，就需要对一些数据进行排序。查找和排序是两大重要技术，其数据处理量几乎占到数据总处理量的80%以上，所以查找与排序的有效性直接就影响到基本算法的有效性。本篇文章主要来讨论查找技术中的静态查找，主要包括顺序查找法、折半查找法以及分块查找法。

关于查找

查找表：是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系，没有严格的前驱和后继的关系，因此查找表是一种应用灵活的结构。

关键字：用来标识一个数据元素(或记录)的某个数据项的值。

主关键字：可唯一地标识一个记录的关键字
次关键字：用以识别若干记录的关键字

查找成功与否

若查找表中存在这样一条记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置。
否则称“查找不成功”。查找结果给出“空记录”或“空指针”

查找目的

查询某个“特定的”数据元素是否在查找表中；
检索某个“特定的”数据元素的各种属性；
在查找表中插入一个数据元素；
删除查找表中的某个数据元素。

查找的分类

静态查找表：仅作“查询”(检索)操作的查找表，即查找前后，表没有变化。
动态查找表：作“插入”和“删除”操作的查找表。有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素，此类表为动态查找表。

查找算法的评估方法

关键字的平均比较次数——平均查找长度(ASL,Average Search Length)

n: 表示记录的总个数

Pi:表示查找第i个元素的概率，一般认为是等概率事件，即：Pi=n/1

Ci:表示找到第i个记录所需要的比较次数

一、顺序查找法

1.特点：用所给出的关键字与线性表中的各个元素进行比较，直到成功或者失败。其存储结构一般为顺序存储结构，也可以是链式存储结构。

2.代码：

//顺序查找法
#include<stdio.h>
#define LAST_SIZE 20
typedef struct{
	int r[LAST_SIZE];//r[0]为工作单元， 作为"监视哨"的存储位置 
	int length;
}RecordList;
//使用"监视哨"法进行顺序查找 
int search1(RecordList h, int k){
	int i;
	h.r[0]=k;//将关键字赋给r[0]作为"监视哨"
	i=h.length;
	//i从表尾位置开始向前移动逐个比较，当全部比较完后还没有找到关键字
	//则会移动到第0个位置，即"监视哨"位置，而结束循环返回0 
	while(h.r[i]!=k) i--;
	return (i); 
}
//测试 
int main(){
	RecordList h;
	int i,key,j;
	printf("请输入表的长度：");
	scanf("%d",&h.length);
	printf("请输入%d个值将顺序表初始化：\n",h.length);
	for(i=1;i<=h.length;i++){
		scanf("%d",&h.r[i]);
	}
	printf("请输入你要查找的值：");
	scanf("%d",&key);
	j=search1(h,key);
	if(j!=0)
	  printf("查找成功！\n该元素的位置为：%d\n",j);
	else
	  printf("查找失败！\n");
	return 0;
}

3.运行结果：

4.不用监视哨法函数代码

//不使用"监视哨"法进行顺序查找
int search2(RecordList h,int k){
	int i=h.length;
	while(i>=1&&h.r[i]!=k) i--;
	if(i>=1)
	  return (i);
	else
	  return 0;
}

5.小结

在数组r的第0个位置作为“监视哨”存放待查找值，当从后往前至第1个位置还没找到待查找的元素，则将遇到监视哨而终止循环，即查询失败！监视哨的主要作用是防止越界。

而不用监视哨法中多了一条循环条件判断语句：i>=1,也是用来检查是否越界的。利用监视哨可以省去这一语句，从而提高查找的效率，这就是使用监视哨法的好处。

二、折半查找法

折半查找法在我之前写过的一个博客中

传送门：数据结构之折半查找法——C语言实现

三、分块查找法

1.算法思想

首先将列表分成若干个子块（子表）。一般情况下，块的长度均匀，最后一块可以不满。每一个块中元素可以任意排列，即块内无序，块间有序。

然后构造一个索引表，其中每个索引项对应一个块，并记录每块的起始位置，以及块中的最大元素，即最大关键字，按最大关键字将块与块排序，达到块间有序。

图解：

从上图中可以看出，索引表将主表分为4块，每块包含5个元素。

要想查找主表中的某个元素，需要分为两步查找：第1步需要确定要查找元素所在的块，第2步在该单元查找指定的元素。例如，要查找元素31，首先需要将31与索引表中的元素进行比较，因为26<31<46，所以需要在第2个块中查找，该快的起始下标是5，因此从主表中的下标为5的位置开始查找31，直到找到该元素为止。如果在该块中没有找到31，则说明主表中不存在该元素，则查找失败。