1.查找的定义
在数据集合中查找满足某种条件的数据元素的过程称为查找。查找的结果有查找成功和查找失败。
2.顺序查找法
(1)一般线性表的顺序查找
算法如下:
1 typedef struct{ 2 ElemType *elem; 3 int TableLen; 4 }SSTable; 5 int Search_Seq(SSTable ST, ElemType key){ 6 ST.elem[0] = key; 7 for(i=ST.TableLen; ST.elem[i]!=key; i--); 8 return i; 9 }
性能分析:
(1)ASL成功= (n+1)/2 ASL不成功= n+1
(2)优点:对数据存储没有要求,可以顺序存储,也可以链式存储。
(3)缺点:当n较大时,平均查找长度长,效率低。
(2)有序表的顺序查找
ASL成功 = (n+1)/2 ASL不成功 = n/2 + n/(n+1)
3.折半查找法
仅适用于有序的顺序表
1 int Binary_Search(SeqList L, ElemType key){ 2 int low=0, high=L.TableLen-1, mid; 3 while(low<=high){ 4 mid = (low+high)/2; 5 if(L.elem[mid]==key){ 6 return mid; 7 }else if(L.elem[mid]>key){ 8 high = mid-1; 9 }else{ 10 low = mid+1; 11 } 12 } 13 return -1; 14 }
性能分析:
ASL成功 =log2(n+1)-1
时间复杂度:O(log2n)
4.分块查找
块内无序,但是块间有序。
步骤:第一步在索引表中确定待查记录所在的块,可以顺序存储也可以链式存储。第二步是在块内顺序查找。
5.散列(Hash)技术。
(1)基本概念
①散列函数:一个把查找表中的关键字映射成该关键字对应的地址的函数,记为Hash(key) = Addr.
②冲突:散列函数可能会把两个或两个以上的不同关键字映射到同一地址,称这种情况为冲突,这些发生碰撞的关键词称为同义词。
③散列表:根据关键字而直接进行访问的数据结构。也就是说,散列表建立了关键字和存储地址之间的一种直接映射关系。
理想情况下,对散列表进行查找的时间复杂度是O(1)
(2)散列函数的构造方法
①直接定址法
H(key) = key 或 H(key) = a * key + b
这种方法计算简单,不会发生冲突。它适合关键字的分布基本连续的情况,若关键字分布不连续,空位较多,则会造成存储空间的浪费。
②除留余数法
假定散列表表长为m,取一个不大于m但最接近m的最大的质数p,则利用公式:H(key) = key%p
掌握散列技术,包括散列函数、散列表、散列冲突的发生及其解决方法、以及负载因子;
理解不同查找技术的优缺点。