7.1 查找的基本概念

查找：在数据集合中寻找满足某种条件的数据元素的过程

查找表：用于查找的顺序集合 查找表不是一个新的数据结构

关键字：数据元素中唯一标识该元素的某个数据项的值 唯一、不重复

平均查找长度(ASL)：所有查找过程中进行关键字的比较次数的平均值

7.2 顺序查找和折半查找

7.2.1 顺序查找

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;
}

若表是有序表

7.2.2 折半查找

折半查找又称二分查找，仅适用于有序的顺序表

int Binary_Search(SSTable 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;
}

7.2.3 分块查找

特点：块内无序，块间有序

将长度为n的查找表平均分为b块，每块有s个元素，则

当时最小，若对索引表采用折半查找，则

7.3 B树和B+树

7.3.1 B树及其基本操作

B树又称多路平衡查找树，其特性如下

• 树中每个结点至多有m颗子树，即至多含有m-1个关键字
• 若根结点不是终端结点，则至少有两颗子树
• 除根结点外所有非叶子结点至少有颗子树，即至少含有个关键字

对一颗含有n个关键字的m阶B树

• 最小高度
• 最大高度
• n个关键字的B树必有n+1个叶子结点

B树.png

插入：

• 需要关键字个数
• 新元素一定是插入到终端结点，插入依据查找
• 若超过上限，则从中间位置分为两部分，当前结点放入父结点中

删除：

• 对终端结点删除，关键字未达下限则直接删除
• 对根结点删除，用直接前驱/直接后继代替
• 删除终端结点后小于下限，若右结点有多余，则从当前结点后继和后继的后继或者是前驱和前驱的前驱借用
• 若左右结点都无多余，则将关键字删除后与左兄弟或右兄弟结点中关键字合并

7.3.2 B+树的基本概念

• 每个分支结点最多有m棵子树（孩子结点)。
• 非叶根结点至少有两棵子树，其他每个分支结点至少有棵子树。
• 结点的子树个数与关键字个数相等。
• 所有叶结点包含全部关键字及指向相应记录的指针.
• 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。

B+树.png

7.4 散列表

7.4.1 散列表的基本概念

散列表又称哈希表，是一种数据结构，特点是数据元素的关键字与其存储地址直接相关

散列函数：一个把查找表中的关键字映射成该关键字对应地址的函数

7.4.2 处理冲突的办法

7.4.2.1 拉链法

把所有的同义词存储在同一个链表中

查找：

• Addr=Hash(key)
• 查找Addr上是否有记录

装填因子定义为一个表的装满长度

7.4.2.2 开放定址法

可存放新表项的空闲地址即可向同义词表项开放，又向非同义词开放

求d_i的方法：

• 线性探测法：发生冲突时，看下一个单元是否为空
• 平方探测法：只有表长=4j+3才能探测到所有位置
• 伪随机序列法

7.4.3 散列函数的构造方法

• 直接定址法 H(key)=a*key+b
• 除留余数法 H(key)=key%p，取一个不大于m但最接近m的质数p
• 数字分析法
• 平方取中法