7-查找

7-查找

1.概念

查找表:查找数据的集合，由同一类型的数据元素(或记录)
关键字:数据元素中唯一表示元素的某个数据项的值，使用基于关键字的查找，查找结果应该唯一
查找长度:在查找运算中需要对比关键字的次数
平均查找长度(ASL)：所有查找过程中进行关键字的比较次数的平均值

2查找

2.1.顺序查找

线性查找，通常用于线性表，时间复杂度O(n).

typedef struct{
    ElemType *elem;
    int TableLen;
}SSTable;
int Search_Seq(SSTable ST,ElemType key){
    int i;
    for (i=0;i<ST.TableLen && ST.elem[i]!=key;i++);
    return i=ST.TableLen ? -1:i;
}

优化:
1.若表中元素有序：若当前关键字大于目标关键字时，查找失败；优点:查找失败时ASL更少
2.查找判定树:成功结点的关键字对比次数=结点所在层数；失败结点关键字对比次数=其父节点所在层数
3.若被查概率不同:按照被查概率降序;优点:查找成功时ASL更少

2.2.折半查找(二分查找法)

仅适用于有序的顺序表，时间复杂度O(log2n)

//升序时排列
int Binary_Search(SSLTable L,ElemType key){
    int low=0,high=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;
}

折半查找判定树的构造

若low和high有奇数个元素，则mid分割后，左右元素个数相等；
若low和high有偶数个元素，则mid分割后，左元素个数比右元素个数少一个(mid向下取整)；

特性：
只有最下面的一层是不满的；
若查找有n个关键字，失败结点有n+1个；

2.3.分块查找(索引顺序查找)

先折半查找块集，折半查找要最终停在low>high，要在low所指块中查找

typedef struct {
    ElemType maxValue;
    int low,high;
}Index;//索引表
ElemType List[100];//顺序表实际存储元素

2.3.1顺序查找

长度为n的查找表被均匀分为b块，每块s个元素，则

$7-查找 - 图1$

当s=n^(1/2)时 ASL最小=n ^(1/2)+1

2.3.2折半查找

$7-查找 - 图2$ %7D%5Crceil%2B%5Cfrac%7Bs%2B1%7D2%0A#card=math&code=ASL%3D%5Clceil%7Blog_2%28b%2B1%29%7D%5Crceil%2B%5Cfrac%7Bs%2B1%7D2%0A)

3.B树

又称多路平衡查找树，所有结点的孩子的个数的最大值称为B树的阶,通常用m表示
结点关键字个数

$7-查找 - 图3$

//5叉排序树
typedef struct Node{
    ElemType keys[4];
    struct Node *child[5];
    int num;
};

性质:
1)树中每个结点至多有m棵子树，即至多含有m-1个结点；
2)若根结点不是终端结点，则至少有2棵子树；
3)在m叉查找树中，规定除根结点外，任何结点至少有m/2向上取整个分叉，即至少有m/2(向上取整)-1个关键字；
4)所有叶结点(失败结点)都出现在同一层次上，并且不带信息；
Q:含有n个关键字的m阶B树，最小高度，最大高度是多少？
n个关键字的B树必有n+1个结点

$7-查找 - 图4$ %5C%5C%0A%E6%9C%80%E5%A4%A7%E9%AB%98%E5%BA%A6%3A%0Ah%5Cleq%20%5Clog%7B%5Clceil%7Bm%2F2%7D%5Crceil%7D%7B%5Cfrac%7Bn%2B1%7D2%2B1%7D%0A#card=math&code=%20%7B%E6%9C%80%E5%B0%8F%E9%AB%98%E5%BA%A6%7D%0A%E6%9C%80%E5%B0%8F%E9%AB%98%E5%BA%A6%3A%0Ah%5Cleq%20%5Clog_m%28n%2B1%29%5C%5C%0A%E6%9C%80%E5%A4%A7%E9%AB%98%E5%BA%A6%3A%0Ah%5Cleq%20%5Clog%7B%5Clceil%7Bm%2F2%7D%5Crceil%7D%7B%5Cfrac%7Bn%2B1%7D2%2B1%7D%0A)

3.1B树的插入

新元素一定是插入到最底层的终端结点中，用“查找”来确定插入位置

3.2B树的删除

若被删除关键字在终端节点，则直接删除该关键字(注意关键字个数是否低于下限[m/2]-1)
若被删除关键字在非终端节点，则用直接前驱或直接后继来代替被删除的关键字；
直接前驱:当前关键字左侧指针所指子树的最右下的元素；直接后继:当前关键字右侧指针所指子树的最左下的元素
若被删除关键字在终端节点，则直接删除该关键字，但低于下限时

右兄弟够借，找当前结点的后继和后继的后继，并且还需调整其双亲结点；
右兄弟不够借，找左兄弟借；
左右兄弟都不够借，则左(或右)兄弟结点及双亲结点中的关键字进行合并，若双亲结点也不够，重复上述步骤；

4.B+树

一棵m阶的B+树需满足以下条件:

每个分支结点最多有m棵子树;
非叶根结点至少有两棵子树，其他每个分支结点至少有[(m/2)向上取整];
结点的子树个数与关键字个数相等;
所有叶节点包含全部关键字及指向相应记录的指针，叶节点中将关键字按大小顺序排列，并且相邻结点按大小顺序相互链接起来，支持顺序查找；
所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针;

5.散列查找

基于散列表(又称哈希表)。数据元素的关键字与其存储地址直接相关。通过散列函数(哈希函数)Add=H(key)

若不同的关键字通过散列函数映射到同一个值，则称它们为”同义词”
通过散列函数确定的位置以及存放了其他的元素，则称这种情况为”冲突”

理想情况下:时间复杂度O(1)
装填因子=表中记录数/散列表长度。因子越大，装的越满

5.1常见的散列函数

5.1.1除留取余法

H(key)=key%p
散列表长度m，取一个不大于m但最接近或等于m的质数p

5.1.2直接定址法

H(key)=key或H(key)=a*key+b 适合关键字的分布基本连续的情况

5.1.3数字分析法

r个数码在各位上的出现频率不同

5.1.4平方取中法

取关键字的平方值的中间几位最为散列地址

5.2处理冲突的方法(3种)

5.2.1拉链法

拉链法(链接法、链地址法)把所有同义词存储在一个链表中

5.2.2开放定址法

删除元素时不能简单删除，应该用标记删除的方法，在删除的位置上用Bool(或其他类型)标记被删除的位置，便于后续的查找
H(key)=(H(key)+d)%m;m表示散列表表长，d为增量序列

5.2.2.1线性探测法

即发生冲突时，每次往后探测相邻的下一单元是否为空；

5.2.2.2平方探测法

散列表长度m必须可以表示成4j+3的素数，才能探测所有位置
当d=0,1^2 -1^2 2^2 -2^2……故，又称二次探测法

5.2.2.3伪随机序列法

定义一个伪随机序列，例d=0,5,24,11,23

数据结构与算法

7-查找

7-查找

1.概念

2查找

2.1.顺序查找

2.2.折半查找(二分查找法)

2.3.分块查找(索引顺序查找)

2.3.1顺序查找

2.3.2折半查找

3.B树

3.1B树的插入

3.2B树的删除

4.B+树

5.散列查找

5.1常见的散列函数

5.1.1除留取余法

5.1.2直接定址法

5.1.3数字分析法

5.1.4平方取中法

5.2处理冲突的方法(3种)

5.2.1拉链法

5.2.2开放定址法

5.2.2.1线性探测法

5.2.2.2平方探测法

5.2.2.3伪随机序列法

5.2.3再散列法