• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

查找

算法笔记 站点默认 2周前 (12-02) 15次浏览 已收录 0个评论

查找的概念没什么好说的,但值得提的是查找分为内外查找。
查找分为三大类:线性表查找,树形查找,散列查找(又叫哈希表)

线性表查找

线性表查找主要有顺序查找,时间复杂度为o(n2),主要掌握折半查找(又叫二分),时间复杂度为nlog(n),因为之前学过二分查找,在算法思想,分而治之思想中,正好学到了,这里不重复学习,最后有索引结构的分块查找,下面贴出代码。

//分块查找算法
#include <stdio.h>
#define MAXI 20			//索引表的最大长度
#define MAXL 100		//最大长度
typedef int KeyType;	//定义关键字类型为int
typedef char InfoType;

typedef struct
{	KeyType key;		//关键字项
	InfoType data;		//其他数据项,类型为InfoType
} RecType;				//查找元素的类型

typedef struct 
{
	KeyType key;	//KeyType为关键字的类型
	int link;		//指向对应块的起始下标
} IdxType;			//索引表元素类型
//顺序表算法 
void CreateList(RecType R[],KeyType keys[],int n)	//创建顺序表
{
	for (int i=0;i<n;i++)
		R[i].key=keys[i];
}
void DispList(RecType R[],int n)	//输出顺序表
{
	for (int i=0;i<n;i++)
		printf("%d ",R[i].key);
	printf("\n");
}
int IdxSearch(IdxType I[],int b,RecType R[],int n,KeyType k) //分块查找
{	
	int s=(n+b-1)/b;			//s为每块的元素个数,应为n/b的向上取整
	int low=0,high=b-1,mid,i;
	while (low<=high)			//在索引表中进行折半查找,找到的位置为high+1
	{	mid=(low+high)/2;
		if (I[mid].key>=k)
			high=mid-1;
		else 
			low=mid+1;
	}
	//应在索引表的high+1块中,再在主数据表中进行顺序查找
	i=I[high+1].link;
	while (i<=I[high+1].link+s-1 && R[i].key!=k)
		i++;
	if (i<=I[high+1].link+s-1)
		return i+1;			//查找成功,返回该元素的逻辑序号
	else
		return 0;			//查找失败,返回0
}


int main()
{
	int n=25,b=5,j;
	RecType R[MAXL];
	IdxType I[MAXI]={{14,0},{34,5},{66,10},{85,15},{100,20}};
	KeyType a[]={8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87};
	KeyType k=85;
	CreateList(R,a,n);
	printf("查找表:"); DispList(R,n);
	j=IdxSearch(I,b,R,n,k);
	if (j!=-1)
		printf("R[%d]=%d\n",j,k);
	else
		printf("未找到%d\n",k);
	return 1;
}

树形结构查找

树形结构查找主要是分为内查找和外查找,内查找为二叉排序树(又叫搜索二叉树),同时也是动态查找(指在查找时,除了找到指定数,还能够对指定数进行删除等操作)但由于如果随机删除多次,会导致二叉排序树歪向一边,此时查找效率下降,于是有了平衡二叉树(又叫AVL树)。此外,外查找有b+和b-树。关于学习,因为之前学的树中学到了二叉搜索树和平衡二叉树,不重复学习;b树太麻烦,以后学了再在这做笔记

散列查找


个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:查找
喜欢 (0)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到