数据结构：查找

查找

查找：在数据集合中寻找满足某种条件的数据对象。

查找表：是由同一类型的数据元素(或记录)组成的数据集合。

关键字：数据元素中的某个数据项的值，用以表示该数据元素。

主关键字：可唯一识别一个数据元素。

衡量标准：查找过程中对关键字的平均比较次数——平均查找长度ASL。设查找到第i个元素的概率为p，比较次数为c，则查找成功的ASL_{succ}=\sum^n_{i=1}p_ic_i

一、顺序查找

从表中最后一元素开始，顺序用关键字与给定的x比较，直至找到相等的元素。

1、算法实现

int Seq_Search(SSTable ST , KeyType key){ 
    int p ; 
    ST. elem[0].key=key ; /* 设置监视哨兵,失败返回0 */
    for (p=ST.length; !EQ(ST. elem[p].key, key); p--)
    return(p) ; 
} 

2、算法分析

等概率情况下，p_i=\frac{1}{n},c_i=n-i+1 ASL_{succ}=\sum^n_{i=1}\frac{1}{n}(n-i+1)=\frac{n+1}{2}=O(n) ASL_{fail}=n+1=O(n)

二、折半查找

条件：查找表中的数据元素按照关键字有序排序。

1、算法实现

分别用Low、High、Mid表示待查找区间的下界、上界与中间查找位置。 初始化Low=0，High=n-1，接下来开始查找：

1. 取Mid=(Low+High)/2
2. 比较Mid与所找x值，若Mid<x，则High=Mid-1；若Mid>x，则Low=Mid+1；并重新计算Mid值。
3. 若Mid==x，成功查找；若Low>High，查找失败。

2、代码实现

int Bin_Search(SSTable ST , KeyType key){ 
    int Low=1,High=ST.length, Mid ;
    while (Low<High){ 
        Mid=(Low+High)/2 ;
        if (EQ(ST. elem[Mid].key, key)) 
        return(Mid) ; 
        else if (LT(ST. elem[Mid].key, key)) 
        Low=Mid+1 ;
        else High=Mid-1 ;
    }
    return(0) ; /* 查找失败 */ 
}

3、算法分析

查找时可以看作通过二叉判定树查找，由满二叉树性质知，第i 层上的结点数为2^{i-1}\ (i≤h)，设表中每个记录的查找概率相等，即P_i=1/n，查找成 功时的平均查找长度ASL： ASL=\sum^n_{i=1}\frac{1}{n}i\times 2^{i-1}=\frac{n+1}{n}\log{n+1}-1=O(\log{n})

三、分块查找（索引查找）

1、算法思路

索引表组织：

将查找表分成几块。块与块之间有序，即第i+1块的所有关键字均大于(或小于)第i块关键字；块内无序。 在查找表的基础上附加一个索引表，每一块以其最大值作为索引表的一个元素。

查找：

1. 查找索引表，确定x所存在的块号（折半查找）。
2. 到块中进行查找（顺序查找）。

2、代码实现

class Index{ 
    keyType maxkey ; /* 块中最大的关键字 */
    int startpos ; /* 块的起始位置指针 */
};

int Block_search(
RecType ST[ ] , 
Index ind[ ] , 
KeyType key , 
int n , 
int b
){ 
/* 在分块索引表中查找关键字为key的记录 */ 
 /*表长为n ，块数为b */
    int i=0 , j , k ;
    while ((i<b)&&LT(ind[i].maxkey, key) ) 
        i++ ;
    if (i>b) { 
        printf(“Not found”); 
        return(0); 
    }
    j=ind[i].startpos ;
    while ((j<n)&&LQ(ST[j].key, ind[i].maxkey) ){ 
        if ( EQ(ST[j].key, key) ) break ;
        j++ ;
    } /* 在块内查找 */
    if (j>n||!EQ(ST[j].key, key) ){ 
        j=0; 
        printf(“\nNot found”); 
    }
    return(j); 
}

3、算法分析

设表长为n个记录，均分为b块，每块记录数为s，则b=⌈n/s⌉。

设记录的查找概率相等，每块的查找概率为1/b，块中记录的查找概率为1/s，则平均查找长度：

ASL=L_b+L_w=\sum^b_{j=1}j+\frac{1}{s}\sum^s_{i=1}i=\frac{b+1}{2}+\frac{s+1}{2}

4、方法比较

四、优先队列（堆）

给定n个元素的序列，如果对其中i=1～\frac{n}{2}个元素，满足k_i\le k_{2i}且k_i\le k_{2i+1}，该序列称为优先队列/堆。

大顶堆（堆顶是堆里最大的元素），小顶堆（堆顶是堆里最小的元素）

1、优先队列调整

构建优先队列本质上是构建一棵二叉树，父结点的值一定比子女结点小（小顶堆）。

给定一个序列，从i=\frac{n}{2}开始操作，直至i=1（从子树开始操作）：

1. 若k_i\le k_{2i}且k_i\le k_{2i+1}，则不做操作。
2. 若k_i\le k_{2i}且k_i\gt k_{2i+1}，则取不满足的那一对(k_{2i+1})进行交换。
3. 若k_i\gt k_{2i}且k_i\gt k_{2i+1}，则与较小的那一个进行交换；若k_{2i}==k_{2i+1}，直接交换k_i与k_{2i}。

小顶堆建立：

代码实现：

void HeapAdjust(HeapType &H,int s,int m){ 
    ElemType rc=H.r[s];
    for (int j=2*s;j<=m;j*=2){ //从当前结点开始，依次操作子结点
        if ((j<m) && (H.r[j].key<H.r[j+1].key))
            ++j;
        if (rc.key > H.r[j].key) break;//满足大顶堆
        H.r[s].key=H.r[j].key; 
        s=j;
    }
    H.r[s]=rc;
}

/*
主函数
*/
for (int i=H.length/2; i>0; --i)//从n/2开始操作
    HeapAdjust(H,i,H.length);

2、插入

往堆里插入元素就是在已经调整好的最大堆/最小堆的叶结点中插入元素，但插入之后可能会破坏堆的结构，因此需要将堆重新调整，使其满足最大堆/最小堆。

3、删除

堆的删除就是从堆中删除堆顶元素。删除堆顶元素之后，用堆的最后一个叶结点去填补刚被删除的堆顶元素，并将堆的实际元素-1。（就是将数组的最后一个元素填补第一个元素）但用最后一个元素取代堆顶的元素之后可能会破坏堆的平衡，因此需要将堆重新调整，使其满足最大堆/最小堆。

4、堆查找

常用于查找top K（查找n个数据中最大/最小的K个元素），如果查找最大的K个数，使用小顶堆。

top K的求解过程是：扫描原数组，用数组的前K个元素建立一个堆。以查找最小的K个数为例，对于K之后的元素，如果比堆顶元素小，那么替换堆顶元素并调整堆，直至扫描完成所有的n个数据。

5、性能分析

insert：O(\log{n})

delete：O(\log{n})

serach：O(1)

数组方式存储。

五、树型查找

二叉查找树、B树

insert：O(\log{n})

delete：O(\log{n})

serach：O(\log{n})

链表方式存储，实现参照树结构。

六、散列（哈希表）

1、算法思路

在关键字与存储方式之间建立一个映射关系。无需比较就可以查找到待查关键字。

数组F：散列表

F中每个单元：桶bucket（一个桶可以对应多个元素，如下列散列冲突）

关键字集U：k\in U，函数h(k)为k的散列地址/散列值。

散列冲突：多个关键字对应同一个存储地址。

2、哈希函数构造

散列函数的定义域必须包括需要存储的全部关键字，如果列表允许有m个地址时,其值域必须在 0 到 m-1 之间。

定义域：U包括所有关键字K

值域：H=h(k)需要在散列表内

a、直接定址法：

利用线性函数：Hash(k)=a*k+b

一对一映射，不产生冲突；但散列地址空间大小与关键字集合大小相同。

适用情况：事先知道关键字的值，关键字取值集合不是很大且连续性较好

b、数字分析法：

利用数字在某些位分布不均，选取其中若干位作为哈希地址。

仅适用于事先明确知道表中所有关键字每一位数值的分布情况，它完全依赖于关键字集合。

c、平方取中法：

将关键字平方后取中间几位作为哈希地址。

这种方法适于事先不知道关键字的分布情况且关键字的位数不是很大。

d、折叠法：

法把关键字自左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。 把这些部分的数据叠加起来，就可以得到具有该关键字的记录的散列地址。

叠加可以使用移位、分界（沿各部分的分界来回折叠）两种形式：

适用情况：关键码位数很多，事先不知道关键码的分布。

e、除留余数法：

Hash(k)=k\%p，设散列表中允许的地址数为m，取一个不大于m，但最接近于或 等于m的质数p。

计算简单，且不需事先知道关键字分布，是最常用的。

f、随机数法：

Hash(k)=random(k)

当散列表中关键字长度不等时，该方法比较合适。

3、解决散列冲突

a、开放定址法

当冲突发生时，形成某个探测序列；按此序列逐个探测散列表中的其他地址，直到找到给定的关键字或一个空地址为止，将发生冲突的记录放到该地址中。

d_i：第i次探测时的增量序列

m：散列表长

H_i(k)=(H(k)+d_i)\%m

探测终止条件：

• 探测到的地址为空：插入——写入该地址；查找——查找失败。
• 探测到的地址有给定关键字：插入——失败；查找——成功。

d_i=1,2,3,4……

易产生冲突聚集。

d_i=1^2,-1^2,2^2,-2^2……

不易产生聚集，但不能保证探测到所有地址。

d_i=random

利用伪随机数。

b、再哈希

构造若干个哈希函数，当发生冲突时，利用不同的哈希函数再计算下一个新哈希地址，直到不发生冲突为止。即：H_i=RH_i(key), i=1, 2, …, k

RH_i ：一组不同的哈希函数。第一次发生冲突时，用RH_1计算，第二次发生冲突时，用RH_2计算…依此类推知道得到某个RH_i不再冲突为止。

• 优点：不易产生冲突的“聚集”现象；
• 缺点：计算时间增加。

c、链地址

产生冲突时继续保存在该地址下，直接构造链表存储。

不易产生冲突的“聚集”；删除记录也很简单，但查找时要遍历链表。

例如，已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表长度为13，哈希函数为：H（key）= key % 13，则用链地址法处理冲突：

d、公共溢出区

另外建立一个溢出表，保存冲突的所有元素记录。发生冲突的元素存入溢出表中。

例： 已知一组关键字(15, 4, 18, 7, 37, 47) ，散列表长度为7 ，哈希函数为：H(key)=key MOD 7，用建立公共溢出区法处理冲突。得到的基本表和溢出表如下：

4、哈希查找

针对关键字x，根据哈希函数得到给定存储地址，比较所储存的关键字k；若存在不同于x的k，根据解决冲突的方式继续查找，直至找到对应关键字或者地址为空。

#define NULLKEY -1 
/* 根据关键字类型定义空标识 */
typedef struct
{ KeyType key ; /* 关键字域 */
otherType otherinfo ; /* 记录的其它域 */
}RecType ;

int Hash_search(RecType HT[], KeyType k, int m)
/* 查找散列表HT中的关键字K,用开放定址法解决冲突 */
{ int h, j ;
h=h(k) ;
while (j<m && !EQ(HT[h].key, NULLKEY) )
{ if (EQ(HT[h].key, k) ) return(h) ;
else h=R(k, ++j) ; 
}
return(-1) ;
}

#define M 15
typedef struct node
{ KeyType key;
struct node *link;
}HNode;

5、算法分析

ASL取决于：

• 哈希函数
• 处理冲突方式
• 填满因子：a=已填入关键字/哈希表长度

ASL分为成功/失败进行计算。

查找小结