使用C语言实现查找

目录

1.查找

2.顺序查找

（1）平均查找长度

 3.有序表的查找

（1）算法思想

（2）代码实现

（3）查找成功和查找失败（查找效率）

（4）查找判定树的构造

4.分块查找

（1）索引表

---

1.查找

（1）查找：在数据集合中寻找满足某种条件的数据元素的过程；

（2）查找表（查找结构）：用于查找的数据集合，由同一类型的数据元素组成；

（3）关键字：数据元素唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果是唯一的。

（4）查找长度：查找运算中，需要对比关键字的次数称为查找长度；

（5）平均查找长度（查找成功和查找失败）：所有查找过程中进行关键字的比较次数的平均值。

2.顺序查找

如果以顺序表或者线性表表示静态查找表，则可以用顺序查找实现。

顺序查找的过程：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，如果某个记录的关键字和给定值比较相等，则查找成功，直到当查找完所有的记录的关键字，还未查找到相应的值，则查找失败。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
#define maxn 10
 
typedef int ElemType;
 
typedef struct SSTable{
	ElemType*data;
	int Tablelen;
}SSTable;
 
void InitSSTable(SSTable&ST){
	ST.data=(ElemType*)malloc(maxn*sizeof(ElemType));
	ST.Tablelen=0;
}
 
void InsertSSTable(SSTable&ST,ElemType e){
	if(ST.Tablelen>=maxn-1){
		printf("表已满!\n");
		return;
	}
	ST.data[ST.Tablelen]=e;
	ST.Tablelen++;
}
 
bool findElem(SSTable ST,ElemType key,int&index){
	for(int i=0;i<ST.Tablelen;i++){
		if(ST.data[i]==key){
			index=i;
			return true;
		}
	}
	return false;
}
 
int main(){
	SSTable ST;
	InitSSTable(ST);
	ElemType e;
	printf("请输入元素(end_-1): ");
	scanf("%d",&e);
	while(e!=-1){
		InsertSSTable(ST,e);
		printf("请输入元素(end_-1): ");
		scanf("%d",&e);
	}
	printf("请输入查找的元素: ");
	ElemType key;
	int index=-1;
	scanf("%d",&key);
	if(findElem(ST,key,index)){
		printf("查找成功位置 = %d\n",index+1);
	}else{
		printf("查找失败!\n");
	}
	return 0;
} 

（1）平均查找长度

 3.有序表的查找

（1）算法思想

折半查找（Binary Search）的查找过程：首先确定待查找记录所在的范围，然后逐步的缩小范围直到找到或者找不到待查找的记录。

（2）代码实现

 

#include<stdio.h>
#include<stdlib.h>
 
#define maxn 10
 
typedef int ElemType;
 
int List[maxn];
 
int Binary_Search(int List[],ElemType key,int n,int low,int high){
	while(low<high){
		int mid=(low+high)/2;
		if(List[mid]>key){
			low=mid+1;
		}else if(List[mid]<key){
			high=mid-1;
		}else if(List[mid]==key){
			return mid;
		}
	}
	return -1;
}
 
int main(){
	ElemType e;
	int i=0;
	int low=0;
	int high=0;
	printf("请输入元素(end_-1): ");
	scanf("%d",&e);
	while(e!=-1){
		List[i]=e;
		printf("请输入元素(end_-1): ");
		scanf("%d",&e);
		i++;
	} 
	high=i-1;
	printf("请输入待查找的记录: ");
	ElemType key;
	scanf("%d",&key);
	int index=Binary_Search(List,key,i,low,high);
	if(index!=-1){
		printf("查找成功 = %d\n",index+1);
	}else{
		printf("查找失败!\n");
	}
	return 0;
}

（3）查找成功和查找失败（查找效率）

 

查找成功时的平均查找长度：ASL（succ）=（1*1+2*2+3*4+4*1）/8= 2.75

 

查找失败时的平均查找长度：ASL(unsucc)=（3*7+2*4）/9=3.22（失败节点的个数为n+1）.

（4）查找判定树的构造

 如果当前low和high之间有奇数个元素时，则mid分隔之后，左右两边元素个数相等；

如果当前low和high之间有偶数个元素时，则mid分隔之后，左边元素个数少一个；

若mid=[(low+high)/2]（向下取整）,则对于任何一个节点，必有：

右子树节点数-左子树节点数=0或者1.

因此判定树一定是平衡二叉树，且树高=log2(n+1)（向上取整）或者log2(n)+1（向下取整）。

4.分块查找

分块查找也称为索引顺序查找。这是顺序表的一种改进，需要建立一张“索引表”。

索引表按关键字有序，则表或者有序或者分块有序。“分块有序”：是第二个子表中所有记录的关键字均大于第一个子表中的最大关键字，第三个子表中的所有关键字均大于第二个子表中的最大关键字，依次下去……。

（1）索引表

 注：若索引表中不包含目标关键字，则折半查找索引表最终导致low>high，但是要在low所在的快进行分块的查找。

数据结构定义：

#include
#include
 
#define maxn 45
 
typedef int ElemType;
 
typedef struct Index {
	ElemType maxValue;
	int low,high;
}Index;
 
ElemType List[maxn];

参考书籍《数据结构》清华大学。