查找的概念没什么好说的，但值得提的是查找分为内外查找。 查找分为三大类：线性表查找，树形查找，散列查找（又叫哈希表）
线性表查找
线性表查找主要有顺序查找，时间复杂度为o（n2），主要掌握折半查找（又叫二分），时间复杂度为nlog（n），因为之前学过二分查找，在算法思想，分而治之思想中，正好学到了，这里不重复学习，最后有索引结构的分块查找，下面贴出代码。
代码语言：javascript复制//分块查找算法
#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]=%dn",j,k);
else
printf("未找到%dn",k);
return 1;
}树形结构查找
树形结构查找主要是分为内查找和外查找，内查找为二叉排序树（又叫搜索二叉树），同时也是动态查找（指在查找时，除了找到指定数，还能够对指定数进行删除等操作）但由于如果随机删除多次，会导致二叉排序树歪向一边，此时查找效率下降，于是有了平衡二叉树（又叫AVL树）。此外，外查找有b 和b-树。关于学习，因为之前学的树中学到了二叉搜索树和平衡二叉树，不重复学习；b树太麻烦，以后学了再在这做笔记
散列查找
废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接：查找
