文章目录

一、查找的基本概念

二、 两种查找表

三、顺序表查找

四、有序表查找

五、分块查找

六、B（B-tree）树

七、B+树：

一、 查找的基本概念

  • 查找表：由同一类型的数据元素构成的集合。
  • 关键字：数据元素中某个数据项的值。
  • 查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。
  • 平均查找长度：

二、两种查找表

静态查找表：只作查找操作的查找表

  • 1、查找某个特定的数据元素是否在查找表中
  • 2、检索某个特定数据元素和各种属性。

动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。

  • 1、查找时插入数据元素
  • 2、查找时删除数据元素

三、顺序表查找


int Sequential_Search(int *a,int n,int key)
{
   
	int i;
	for(i=1;i<=n;i++)
	{
   
		if(a[i]==key)
		return i;
	}
	return 0;
}

int Sequential_Search2(int *a,int n,int key)
{
   
	int i;
	a[0]=key;/*设置哨兵*/
	i=n;
	while(a[i]!=key)
	{
   
		i--;
	}
	return i;/*返回0则说明查找失败*/
}

四、有序表查找

折半查找

  • 又称为二分查找，前提是线性表中的记录必须有序，线性表必须采用顺序存储
int Binary_Search(int *a,int n,int key)
{
   
	int low,high,mid;
	low=1;
	high=n;
	while(low<=high)
	{
   
		mid=(low+high)/2;/*折半*/
		if(key<a[mid])	//查找值比中间值小 
			high=mid-1;	//最高下标调整到中位下标小一位 
		else if (key>a[mid])//若查找值比中指大 
			low=mid+1;		//最小下标调整到中位下标大一位 
		else
			return mid;//相等则说明mid即为查找到的位置 
	}
	return 0;
}


五、分块查找

  • 把数据集分成了若干块，并且这些需要满足两个条件：


六、B（B-tree）树

一种平衡的多路查找树




B树的查找：

B树的插入：




B树的删除：





七、B+树：