查找的概念

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

对查找表经常进行的操作：

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

查找表可以分为两类：

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

查找算法的评价指标：
关键字的平均比较次数，也称平均查找长度ASL(Average Search Length)

$$ASL=\sum _{i=1}^n{p}_i{c}_i(关键字比较次数的期望值)$$
$n$：记录的个数；
$p_i$：查找第i个记录的概率（通常认为$p_i$ = $1/n$）；
$c_i$：找到第i个记录所需的比较次数；

  查找的方法取决于查找表的结构，即表中数据元素是依何种关系组织在一起的；
  因为“查询”或“检索”在计算机应用系统中使用频度都很高，因此需要设法提高查找表的查找效率；
  为提高查找效率，一个办法就是在构造查找表时，在集合中的数据元素之间认为地加上某种确定的约束关系；
 
 

线性表的查找

顺序查找（线性查找）

顺序查找的特点：
优点：算法简单，逻辑次序无要求，且不同存储结构均适用；
缺点：ASL太长，时间效率低；

应用范围：

• 顺序或线性链表表示的静态查找表
• 表内元素之间无序

顺序表的表示：

//数据元素类型定义
typedef struct{
	KeyType key;	//关键字域
	......			//其他域
}ElemType;

//顺序表结构定义类型
typedef struct{
	ElemType *R;	//表基址
	int length;		//表长
}SStable;			//Sequential Search Table
SStable ST;			//定义顺序表ST

算法：

int Search_Seq(SSTable ST, KeyType key){
	//若成功返回其位置信息，否则返回0
	for(i = ST.length; i >= 1; --i){
		if(ST.R[i].key == key)	return i;
		else return 0;
	}
}

其他形式：

int Search_Seq(SSTable ST, KeyType key){
	for(i = ST.length; i >= 1;ST.R[i].key != key; --i)
		if(i <= 0) break;
	if(i > 0) return i;
	else return 0;
}

改进：把待查关键字key存入表头（“哨兵”、“监视哨”），从后往前逐个比较，可免去查找过程中每一个都要检测是否完毕，加快速度

//设置监视哨的顺序查找
int Search_Seq(SSTable ST, KeyType key){
	ST.R.key = key;
	for(i = ST.length; ST.R[i].key != key; --i);
	return i;
}

时间复杂度：$O(n)$
$AS{L}_s(n)=(1+2+...+n)/n=(n+1)/2$

1、记录的查找概率不相等时如何提高查找效率

查找表存储记录原则——按查找概率高低存储：
1）查找概率越高，比较次数越少；
2）查找概率越低，比较次数越多；
 
 
2、记录的查找概率无法测定时如何提高查找效率

方法——按查找概率动态调整记录顺序
1）在每个记录中设一个访问频度域；
2）始终保持记录按非递增有序的次序排列；
3）每次查找后均将刚查到的记录直接移至表头；
 
 

折半查找（二分或对分查找）

 
折半查找：每次将待查记录所在区间缩小一半
 
折半查找的特点：
优点：效率比顺序查找高；
缺点：只适用于有序表，且限于顺序存储结构（对线性链表无效）；
 

 

算法：

int Search_Binary(SSTable St, KeyType key){
	low = 1;
	high = ST.length;					//置区间初值
	while(low <= high){
		mid = (low + high)/2;
		if(ST.R[mid].key == key)
			return mid;					//找到待查元素
		else if(key < ST.R[mid].key)	//缩小查找区间
			high = mid - 1;				//继续在前半区间进行查找
		else low = mid +1;				//继续在后半区间进行查找
	}
	return 0;		//顺序表中不存在待查元素
}//Search_Binary

递归算法：

int Search_Binary(SStable ST, keyType key, int low, int high){
	if(low > high) return 0;			//查找不到时返回0
	mid = (low + high)/2;
	if(key == ST.elem[mid].key)
		return mid;
	else if(key < ST.elem[mid].key)
	......	//递归，在前半区间进行查找
		else......	//递归，在后半区间进行查找
}

 


如果为顺序查找，则$ASL=(11+1)/2=6$

平均查找长度ASL（成功时）：
设表长$n=2^h-1$， 则 $h=lo{g}_2(n+1)$（此时，判定树为深度 = h的满二叉树），且表中每个记录的查找概率相等：$P_i=1/n$，则：
$$ASL=\sum _{i=1}^n{p}_i{c}_i=\frac{1}{n}\sum _{i=1}^n{c}_i=n\sum _{j=1}^{h}j\cdot 2^{j-1}$$
$$=\frac{n+1}{n}lo{g}_2(n+1)-1$$
$$\approx lo{g}_2(n+1)-1（n>50）$$
$j$ 为第 $j$ 层的每个结点要比较的次数；$2^{j-1}$ 为第 $j$ 层结点数
 
 

分块查找

 


优点：插入和删除比较容易，无需进行大量移动；
缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算；
适用情况：如果线性表既要快速查找又经常动态变化，则可采用分块查找；
 
查找方法的比较：

最后

以上就是繁荣电源为你收集整理的数据结构——线性表的查找查找的概念线性表的查找的全部内容，希望文章能够帮你解决数据结构——线性表的查找查找的概念线性表的查找所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。