查找（数据结构）

今天数据结构复习到查找部分，正好将这一部分初步整理出来，以便之后学习的时候参考复习。

基本概念

查找：在数据集合中寻找满足某种条件的数据元素的过程。
查找结果：
查找成功
查找失败
查找表：用于查找数据集合。
查找表的操作：
1.查找是否存在某个特定元素（静态）
2.检索满足条件的某个特定元素的属性（静态）
3.在查找表中删除一个数据元素（动态）
4.在查找表中插入一个数据元素（动态）
动态：二叉排序树的查找；散列查找；
静态：顺序查找；折半查找；散列查找；
关键字：数据元素中唯一标识该元素的某个数据项的值。
平均查找长度：是衡量查找算法效率的最主要指标。

1.顺序查找（线性查找）

1）一般线性表的顺序查找（无序）

算法：

// 顺序查找
typedef struct{                      //查找表的顺序结构
    ElemType *elem;                  //元素储存空间地址，建表时按实际长度分配，0号单元留空（哨兵）
    int TableLen;                    //表的长度
}SSTable;
int Search_seq(SSTable ST,ElemType key){
    //在顺序表ST中顺序查找关键字为key的元素，若找到则返回元素在表中的位置
    ST.elem[0] = key;                //"哨兵"
    for(i=ST.TableLen;ST.elem[i]!=key;i--)  ;   //从后往前找
    return i;                        //若表中不存在关键字为key的元素，将查找到i为0时退出for循环
}

缺点：当n较大的时，平均查找长度较大，效率低；
优点：对数据元素的存储没有要求，顺序存储或链式存储皆可；对表中记录的有序性也没有要求，无论记录是否按照关键码有序均可应用。
平均查找长度：(n+1)/2

注意：对线性的链表只能进行顺序查找。

2）有序表的顺序查找

查找失败可以不再找到表的另一端，能降低顺序查找失败的平均查找长度。
查找平均长度：
成功：(n+1)/2
失败：n/2+n/(n+1)

2.折半查找（二分查找）

算法：

//二分查找
int Binary_Search(SeqList L,ElemType key){
    //在有序表L中查找关键字为key的元素，若存在则返回其位置，不存在则返回-1
    int low = 0,hight = L.TableLen-1,mid;
    while(low<=high){
        mid = (low + high)/2;        //取中间位置
        if(L.elem[mid] == key)
            return mid;              //查找成功则返回所在位置
        else if(L.elem[mid]>key)
            high = mid - 1;          //从前半部分继续查找
        else
            low = mid + 1;           //从后半部分继续查找
    }
    return -1;
}

判定树（计算成功和不成功的平查找长度）

3.分块查找（索引顺序查找）

块内的元素可以无序，但块之间是有序的。
步骤：
1.在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表
2.在块内顺序查找

散列表

散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr。（的地址可以是数组下标、索引、或内存地址等）
冲突：散列函数可能会把两个以上的不同关键字映射到同一地址
同义词：发生冲突的不同关键字
散列表：是根据关键字而直接进行访问的数据结构
对散列表进行查找的时间复杂度为O(1)

散列函数的构造方法

注意:
1.散列函数的定义域必须包含全部需要储存的关键字，而值域的范围则依赖于散列函数表的大小或地址范围
2.散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间，从而减少冲突的发生
3.散列函数应尽量简单，能够在较短的时间内就计算出任一关键字对应的散列地址
4.实际的选择中，采用何种构造散列函数的方法取决于关键字集合的情况，但是目标是为了使产生的冲突的可能性尽量的降低

（1）直接定址法

直接取关键字的某个函数值为散列地址，散列函数为：H(key)=a×key+b。这种方法计算简单，并且不会产生冲突。
它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，将造成储存空间的浪费。

（2）除留余数法

这是一种最简单、最常用的方法，假定散列表表长为m，出下一个不大于m但最接近或等于m的质数p，利用H(key)=key%p的公式把关键字转换成散列地址。
该方法关键的是选好p，使得每一个关键字通过函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性。

（3）数字分析法

设关键字是r进制数（如十进制），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几处数码经常出现，则应选数码分布较为均匀的若干位作为散列地址。
这种方法适合于已知的关键字集合，如果更换了关键字，就需要重新构造新的散列函数。

（4）平方取中法

顾名思义，取关键字的平方值的中间几位作为散列地址。具体多少位要看实际情况而定。这种方法取到的散列地址和关键字的每一位都有关系，使得散列地址分布布较均匀。
适用于关键字的每一位取值都不够均匀或均小于散列地址所需的函数。

####（5）折叠法

将关键字分割成位数相同的及部分（最后一部分的位数可以短一些），然后取这几部分的折叠和作为散列地址。
关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到散列地址。

####（6）随机数法

选择一随机函数，取关键字的随机值作为散列地址。
通常用于关键字长度不同的场合。

处理冲突的方法

任何设计出来的散列函数都不可能绝对地避免冲突，为此，必须考虑在发生冲突时应该如何进行处理，即为产生冲突的关键字寻找下一个“空”的Hash地址。

（1）开放定址法

可存放新表项的空闲地址既向它的同义词表现开放，又向它的非同义词表项开放。

A.线性探测法

冲突发生时，顺序表查看表中下一个单元（当探测到表尾m-1时，下一个探测地址是表首地址0），直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。
缺点：可能时第i个散列地址的同义词存入第i+1个散列地址，这样本应存入第i+1个散列地址的元素就争夺第i+2个散列地址的元素的地址……，从而在成大量元素的响铃的散列地址上“聚集”（或堆积）起来，大大降低了查找效率。

B.平方探测法（二次探测法）

这是一种较好的处理冲突的方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少探测到一半的单元。

C.再散列法（双散列法）

需要两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时，则利用第二个散列函数Hash2(key)=>[H=(H(key)+i*Hash2(key))%m]计算该关键字的地址增量。

D.伪随机序列法

利用伪随机数序列

（2）拉链法

为了避免非同义词发生冲突，可以把所有的同义词储存在一个线性链表中，这个线性链表由其散列地址唯一标识。
适用于经常进行插入和删除的情况。

散列的查找和性能分析

查找与构造方式基本一致。
散列表的查找效率取决于三个因素：散列函数、处理冲突的方式和填装因子。
填装因子：α=表中记录数n/散列表长度m