查找的概念没什么好说的，但值得提的是查找分为内外查找。
查找分为三大类：线性表查找，树形查找，散列查找（又叫哈希表）
线性表查找
线性表查找主要有顺序查找，时间复杂度为o（n2），主要掌握折半查找（又叫二分），时间复杂度为nlog（n），因为之前学过二分查找，在算法思想，分而治之思想中，正好学到了，这里不重复学习，最后有索引结构的分块查找，下面贴出代码。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
//分块查找算法 #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树太麻烦，以后学了再在这做笔记
