第七章 查找

 

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

掌握散列技术,包括散列函数、散列表、散列冲突的发生及其解决方法、以及负载因子;

理解不同查找技术的优缺点。

上一篇:来一波CSS兼容问题小总结吧


下一篇:平衡二叉树ASL