第七章 查找_有序表的顺序查找不成功asl-程序员宅基地

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。

　　(3)处理冲突的方法

　　　　①开放定址法:可存放新表项的空闲地址既向他的同义词开放，也向它的非同义词开放。

　　　　　　Hi = (H(key) + di)%m      di:增量   m：表长

　　　　　　❶.线性探测法：di = 0,1,2,3,4,.....m-1。 容易造成相邻的散列地址上“聚集堆积”起来，降低效率。

　　　　　　❷平方探测法：di = 02,12,-12,22，-22.....k2,-K2.   K<=m/2，m必须是一个可以表示成4k+3的素数

　　　　　　　　特点：可以避免堆积的问题，缺点是不能探测到散列表的所有单元，但至少能探测到一半的单元。

　　　　　　❸再散列法：

　　　　　　　　Hi = ( H ( key ) + i * Hash2(key)) % m

　　　　②拉链法：把所有的同义词存储在一个线性表中，操作时在后面进行插入和删除结点。

　　　　　　　　适用于经常插入和删除的情况。

　　(4)散列查找的性能分析

　　　　ASL成功  =  (每个元素查找成功的长度和)/元素个数

　　　　散列表的查找效率取决于三个因素：散列函数、处理冲突的方法、装填因子。

　　　　装填因子α = (表中元素的个数)/(散列表的长度m)