查找的概念没什么好说的,但值得提的是查找分为内外查找。
查找分为三大类:线性表查找,树形查找,散列查找(又叫哈希表)
线性表查找
线性表查找主要有顺序查找,时间复杂度为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树太麻烦,以后学了再在这做笔记