作者：whisper

链接：http://proprogrammar.com:443/article/136

声明：请尊重原作者的劳动，如需转载请注明出处

---

    说明：本章主要讲了静态查找表（顺序查找法，分块查找法，折半查找法），动态查找树表（二叉排序树，平衡二叉树，B 树，B+树），散列表，字符串模式匹配

    查找表可分为两类:

    静态查找表：仅作查询和检索操作的查找表。
    动态查找表：有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。

    如何进行查找？

    查找的方法取决于查找表的结构。
    由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。
    为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找表。

    静态查找表

    假设静态查找表的顺序存储结构为

typedef struct {
    ElemType *elem; // 数据元素存储空间基址，建表时，按实际长度分配，0 号单元留空
    int length; // 表的长度
} SSTable;

    数据元素类型的定义为:

typedef struct {
    keyType key; // 关键字域
    … … // 其它属性域
} ElemType , TElemType ;

    顺序查找表——顺序查找法

    以顺序表或线性链表表示静态查找表

    回顾顺序表的查找过程：

    假设给定值e = 64,要求ST.elem[i] = e, 问: i = ?

int location( SqList L, ElemType& e, Status (*compare)(ElemType, ElemType)) {
    i = 1;
    p = L.elem;
    while ( i<=L.length &&!(*compare)(*p++,e))) i++;

    if ( i<= L.length) return i;
    else return 0;
} //location

Search_Seq(SSTable ST, KeyType kval) {
    // 在顺序表ST 中顺序查找其关键字等于
    // key 的数据元素。若找到，则函数值为
    // 该元素在表中的位置，否则为0。
    ST.elem[0].key = kval; // 设置“哨兵”

    for (i=ST.length-1; ST.elem[i].key != kval; --i);
    // 从后往前找
    return i; // 找不到时，i 为0
} // Search_Seq

    分析顺序查找的时间性能

    定义： 查找算法的平均查找长度(Average Search Length) 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值.

                                                                                

    其中: n 为表长，Pi 为查找表中第i 个记录的概率,且Σ(n,i=1) Pi = 1 ，Ci 为找到该记录时，曾和给定值比较过的关键字的个数.

    对顺序表而言，Cᵢ = n-i+1

    ASL = nP₁ +(n-1)P₂ + +2Pₙ₋₁ +Pₙ

    在等概率查找的情况下，Pi = 1/n

    ASLₛₛ = (1/n)Σ(n,i=1)(n − i +1) = (n+1)/2

    在不等概率查找的情况下，ASLₛₛ 在Pₙ≥Pₙ₋₁≥···≥P₂≥P₁ 时取极小值。

    若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。

    有序查找表——折半查找法

    上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。

    若以有序表表示静态查找表，则查找过程可以基于“折半”进行。

int Search_Bin ( SSTable ST, KeyType kval ) {
    low = 1; high = ST.length - 1; // 置区间初值
    while (low <= high) {
        mid = (low + high) / 2;
        if （kval == ST.elem[mid].key )
            return mid; // 找到待查元素
        else if ( kval < ST.elem[mid].key) )
            high = mid - 1; // 继续在前半区间进行查找
        else low = mid + 1; // 继续在后半区间进行查找
    }

    return 0; // 顺序表中不存在待查元素
} // Search_Bin

    一般情况下，表长为n 的折半查找的判定树的深度和含有n 个结点的完全二叉树的深度相同。

    假设n=2ʰ-1 并且查找概率相等则:

    在n>50 时，可得近似结果:

    索引顺序表——分块查找法

    在建立顺序表的同时，建立一个索引。

    例如：

    索引顺序表的查找过程：
    1）由索引确定记录所在区间；
    2）在顺序表的某个区间内进行查找。

    可见，索引顺序查找的过程也是一个“缩小区间”的查找过程。

    注意：索引可以根据查找表的特点来构造。

    索引顺序查找的平均查找长度=查找“索引”的平均查找长度+查找“顺序表”的平均查找长度

    动态查找树表

    综合上一节讨论的几种查找表的特性：

    可得如下结论：

    1）从查找性能看，最好情况能达O(logn)，此时要求表有序；

    2）从插入和删除的性能看，最好情况能达O(1)，此时要求存储结构是链表。

    注：找出既有序又是链表的结构，即树表

    二叉排序树（二叉查找树）

    定义

    二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：

    （1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；
    （2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；
    （3）它的左、右子树也都分别是二叉排序树。

    例如下图不是二叉排序树：

    通常，取二叉链表作为二叉排序树的存储结构。

typedef struct BiTNode { // 结点结构
    TElemType data; 
    struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;

    二叉排序树的查找算法

    若二叉排序树为空，则查找不成功；否则：

    (1)若给定值等于根结点的关键字，则查找成功；
    (2)若给定值小于根结点的关键字，则继续在左子树上进行查找；
    (3)若给定值大于根结点的关键字，则继续在右子树上进行查找。

    例如：二叉排序树如图所示：

    查找关键字=50,35,90,95

    从上述查找过程可见，在查找过程中，生成了一条查找路径:

    从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点; ——查找成功
    从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。——查找不成功

    算法描述如下：

Status SearchBST (BiTree T, KeyType kval, BiTree f, BiTree &p ) {
    // 在根指针T 所指二叉排序树中递归地查找其
    // 关键字等于kval 的数据元素，若查找成功，
    // 则返回指针p 指向该数据元素的结点，并返回
    // 函数值为TRUE; 否则表明查找不成功，返回
    // 指针p 指向查找路径上访问的最后一个结点，
    // 并返回函数值为FALSE, 指针f 指向当前访问
    // 的结点的双亲，其初始调用值为NULL
    if (!T)
    { 
        p = f; 
        return FALSE; 
    } // 查找不成功
    else if ( EQ(kval, T->data.key) )
    { 
        p = T; 
        return TRUE; 
    } // 查找成功
    else if ( LT(kval, T->data.key) )
        return SearchBST (T->lchild, kval, T, p );
    // 在左子树中继续查找
    else
        return SearchBST (T->rchild, kval, T, p );
    // 在右子树中继续查找
} // SearchBST

    设key = 48、22 

    二叉排序树的插入算法

    根据动态查找表的定义，“插入”操作在查找不成功时才进行;

    若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。

Status Insert BST(BiTree &T, ElemType e ) {
    // 当二叉排序树中不存在关键字等于e.key 的
    // 数据元素时，插入元素值为e 的结点，并返
    // 回TRUE; 否则，不进行插入并返回FALSE
    if (!SearchBST ( T, e.key, NULL, p ))
    { 
        s = new BiTNode;
        // 为新结点分配空间
        s->data = e;
        s->lchild = s->rchild = NULL;

        if ( !p ) T = s; // 插入s 为新的根结点
        else if ( LT(e.key, p->data.key) )
            p->lchild = s; // 插入*s 为*p 的左孩子
        else p->rchild = s; // 插入*s 为*p 的右孩子

        return TRUE; // 插入成功
    }
    else return FALSE;
} // Insert BST

    二叉排序树的删除算法

    和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。可分三种情况讨论：

    （1）被删除的结点是叶子；
    （2）被删除的结点只有左子树或者只有右子树；
    （3）被删除的结点既有左子树，也有右子树。

    （1）被删除的结点是叶子结点

    被删关键字= 20、88。其双亲结点中相应指针域的值改为“空”

    （2）被删除的结点只有左子树或者只有右子树

    被删关键字= 40、80。其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。

    （3）被删除的结点既有左子树，也有右子树

    被删关键字= 50。以其前驱替代之，然后再删除该前驱结点

    注：其前驱一定没有右孩子，即最多只有左孩子，其左孩子以第二种情况处理

    算法描述如下：

Status DeleteBST (BiTree &T, KeyType kval ) {
    // 若二叉排序树T 中存在其关键字等于kval 的
    // 数据元素，则删除该数据元素结点，并返回
    // 函数值TRUE，否则返回函数值FALSE
    if (!T) return FALSE;
    // 不存在关键字等于kval 的数据元素
    else 
    { 
        if ( EQ (kval, T->data.key) )
        { 
            Delete (T); 
            return TRUE; 
        }
        // 找到关键字等于key 的数据元素
        else if ( LT (kval, T->data.key) )
             return DeleteBST ( T->lchild, kval );
        // 继续在左子树中进行查找
        else
            return DeleteBST ( T->rchild, kval );
        // 继续在右子树中进行查找
    }
} // DeleteBST



其中删除操作过程如下所描述：
void Delete ( BiTree &p ){
// 从二叉排序树中删除结点p，
// 并重接它的左子树或右子树
if (!p->rchild) { }
else if (!p->lchild) { }
else { }
} // Delete

    注：删除并没有实现

    查找性能的分析

    对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL 值，显然，由值相同的n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。

    例如：

    由关键字序列1，2，3，4，5 构造而得的二叉排序树，ASL =（1+2+3+4+5）/ 5= 3

    由关键字序列3，1，2，5，4 构造而得的二叉排序树ASL =（1+2+3+2+3）/ 5 = 2.2

    平衡二叉树

    平衡二叉树是二叉查找树的另一种形式，其特点为：树中每个结点的左、右子树深度之差的绝对值不大于1 。

    例如:

       

                             是平衡树                                                              不是平衡树

    构造平衡二叉（查找）树的方法是：在插入过程中，采用平衡旋转技术(LL、RR、LR、RL)。

    例如:依次插入的关键字为5, 4, 2, 8, 6, 9

    平衡树的查找性能分析：

    在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。
    因此，在平衡二叉树上进行查找时，查找过程中和给定值进行比较的关键字的个数和log(n) 相当。

    B - 树

    B-树的定义

    B-树是一种平衡的多路查找树：

    多叉树的特性：

    查找树的特性：

    注：非叶节点关键字比前一个子树大，比后一个子树小

    平衡树的特性：

    查找过程：

    从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找两个过程交叉进行。
    若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；
    若查找不成功，则返回插入位置。

    查找性能的分析

    在B-树中进行查找时，其查找时间主要花费在搜索结点（访问外存）上，即主要取决于B-树的深度。

    结论：

    在含N 个关键字的B-树上进行一次查找，需访问的结点个数不超过

    B+树（是B-树的一种变型）

    B+树的结构特点：

    每个叶子结点中含有n 个关键字和n 个指向记录的指针；
    并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点；
    每个非叶结点中的关键字Ki 即为其相应指针Ai 所指子树中关键字的最大值；
    所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于Γm/2┐ 和m 之间。

    注：非叶结点关键字等于对应子树中关键字最大值

    查找过程

    ※在B+ 树上，既可以进行缩小范围的查找，也可以进行顺序查找；
    ※ 在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束；
    ※若在结点内查找时，给定值≤Ki，则应继续在Ai 所指子树中进行查找；

    散列表

    散列表是什么？

    以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。

    用这类方法表示的查找表，其平均查找长度都不为零。不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。

    对于频繁使用的查找表，希望ASL = 0。只有一个办法：预先知道所查关键字在表中的位置，即，要求：记录在表中位置和其关键字之间存在一种确定的关系。

    例如：为每年招收的1000 名新生建立一张查找表，其关键字为学号，其值的范围为xx000 ~ xx999 (前两位为年份)
    若以下标为000 ~ 999 的顺序表表示之。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。
    但是，对于动态查找表而言，1) 表长不确定；2) 在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。
    因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以f(key) 作为关键字为key 的记录在表中的位置，通常称这个函数f(key) 为散列函数。

    例如：对于如下9 个关键字{Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei} 设散列函数f(key) = └ (Ord(第一个字母) -Ord('A')+1)/2 ┘ 问题: 若添加关键字Zhou , 怎么办？

    从这个例子可见:
    1)散列(Hash)函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可;
    2)由于散列函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：key1≠ key2，而f(key1) = f(key2)。
    3) 很难找到一个不产生冲突的散列函数。一般情况下，只能选择恰当的散列函数，使冲突尽可能少地产生。
    因此，在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的散列函数之外;还需要找到一种“处理冲突” 的方法。

    散列表的定义:

    根据设定的散列函数H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“散列表”。

    构造散列函数的方法

    对数字的关键字可有下列构造方法:

    若是非数字关键字，则需先对其进行数字化处理。

    1. 直接定址法

    散列函数为关键字的线性函数H(key) = key 或者H(key) = a×key + b
    此法仅适合于：地址集合的大小=关键字集合的大小

    2. 数字分析法

    假设关键字集合中的每个关键字都是由s 位数字组成(u1, u2, …, us)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为地址。
    此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。

    3. 平方取中法

    以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。
    此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。

    4. 折叠法

    将关键字分割成若干部分，然后取它们的叠加和为散列地址。有两种叠加处理的方法：移位叠加和间界叠加.
    此方法适合于: 关键字的数字位数特别多。

    5. 除留余数法

    设定散列函数为:H(key) = key MOD p 其中，p≤m (表长)并且p 应为不大于m 的最大素数.
    为什么要对p 加限制？
    例如：给定一组关键字为: 12, 39, 18, 24, 33, 21，若取p=9, 则他们对应的散列函数值将为: 3, 3, 0, 6, 6, 3 可见，若p 中含质因子3, 则所有含质因子3 的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。

    6.随机数法

    设定散列函数为: H(key) = Random(key)其中，Random 为伪随机函数。通常，此方法用于对长度不等的关键字构造散列函数。

    实际造表时，采用何种构造散列函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。

    处理冲突的方法

    “处理冲突” 的实际含义是：为产生冲突的地址寻找下一个散列地址。

    1. 开放定址法

    为产生冲突的地址H(key) 求得一个地址序列：H₀, H₁, H₂, …, Hₛ ，1≤ s≤m-1 其中：H₀ = H(key)、Hᵢ = ( H(key) + dᵢ ) MOD m ，i=1, 2, …, s

    对增量dᵢ 有三种取法：

    1) 线性探测再散列

    dᵢ = c× i 最简单的情况c=1

    2) 平方探测再散列
    dᵢ = 1², -1², 2², -2², …,

    3) 随机探测再散列
    dᵢ 是一组伪随机数列或者dᵢ=i×H₂(key) (又称双散列函数探测)

    例如: 关键字集合{ 19, 01, 23, 14, 55, 68, 11, 82, 36 }设定散列函数H(key) = key MOD11 ( 表长=11 ) ，若采用线性探测再散列处理冲突

    线性探测处理冲突时， ASL =22/9

    若采用二次探测再散列处理冲突

    2. 链地址法

    将所有散列地址相同的记录都链接在同一链表中。

    例如:同前例的关键字，散列函数为H(key)=key MOD 7

    散列表的查找

    查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为:

    对于给定值K, 计算散列地址i = H(K)
    若r[i] = NULL 则查找不成功
    若r[i].key = K 则查找成功
    否则“求下一地址Hi” ，直至r[Hi] = NULL (查找不成功)或r[Hi].key = K (查找成功) 为止。

    散列表查找的分析: 从查找过程得知，散列表查找的平均查找长度实际上并不等于零。

    决定散列表查找的ASL 的因素：

    1) 选用的散列函数;
    2) 选用的处理冲突的方法;
    3) 散列表饱和的程度，装载因子α=n/m 值的大小（n—记录数，m—表的长度）

    一般情况下，可以认为选用的散列函数是“均匀”的，则在讨论ASL 时，可以不考虑它的因素。因此，散列表的ASL 是处理冲突方法和装载因子的函数。

    可以证明：查找成功时有下列结果：

    线性探测再散列

                                   

    随机探测再散列

                                   

    链地址法

                                   

    从以上结果可见，散列表的平均查找长度是α 的函数，而不是n 的函数。这说明，用散列表构造查找表时，可以选择一个适当的装填因子α，使得平均查找长度限定在某个范围内。这是散列表所特有的特点。

    散列表的删除操作

    从散列表中删除记录时，要作特殊处理，相应地，需要修改查找的算法。

    散列表也可用来构造静态查找表

    并且，对静态查找表，有时可以找到不发生冲突的散列函数。即，此时的散列表的ASL=0, 称此类散列函数为理想（perfect）的散列函数。

    串的模式匹配算法

    串的一种重要操作，很多软件中若有“编辑”菜单项的话，则其中必有“查找”子菜单项。

    串的模式匹配即子串定位。

    首先，回忆一下串匹配(查找)的定义:
    INDEX (S, T, pos)
    初始条件：串S 和T 存在，T 是非空串，1≤pos≤StrLength(S)。
    操作结果：若主串S 中存在和串T 值相同的子串返回它在主串S 中第pos 个字符之后第一次出现的位置; 否则函数值为0。
    设s 和t 是给定的两个串，在主串s 中找到等于子串t 的过程称为模式匹配。如果在s 中找到等于t 的子串，则称匹配成功，函数返回t 在s 中的首次出现的存储位置(或序号)，否则匹配失败，返回-1。
    t 也称为模式。为了运算方便，设字符串的长度存放在0 号单元，串值从1 号单元存放，这样字符序号与存储位置一致。

    简单算法（BF 算法）

    算法思想：首先将s1 与t1 进行比较，若不同，就将s2 与t1 进行比较，...，直到s的某一个字符si 和t1 相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s 的某一个字符si 与t 的字符tj 不同时，则s 返回到本趟开始字符的下一个字符，即si-j+2，t 返回到t1，继续开始下一趟的比较，重复上述过程。若t 中的字符全部比完，则说明本趟匹配成功，本趟的起始位置是i-j+1 或i-t[0]，否则，匹配失败。设主串s=＂ababcabcacbab＂，模式t=＂abcac＂

int StrIndex_BF (char *s,char *t)
    /*从串s 的第一个字符开始找首次与串t 相等的子串*/
{ 
    int i=1,j=1;
    while (i<=s[0] && j<=t[0] ) /*都没遇到结束符*/
        if (s[i]==t[j]) 
        { 
            i++;
            j++; 
        } /*继续*/
        else 
        {
            i=i-j+2; 
            j=1; 
        } /*回溯*/

    if (j>t[0]) 
        return (i-t[0]); /*匹配成功，返回存储位置*/
    else return –1;
}

    最好情况下的时间复杂度是O(n+m)。
    最坏情况下的时间复杂度是O(n*m)。

    首尾匹配算法

    先比较模式串的第1 个字符，再比较模式串的第n 个字符，最后比较模式串中从第2 个到第n-1 个字符。

    注：首尾匹配算法可以避免最坏情况

    KMP(D.E.Knuth,V.R.Pratt, J.H.Morris) 算法

    KMP 算法的时间复杂度可以达到O(m+n)

    希望某趟在sᵢ 和tⱼ 匹配失败后，指针i 不回溯，模式t 向右“滑动”至某个位置上，使得tₖ 对准sᵢ继续向右进行。显然，现在问题的关键是串t“滑动”到哪个位置上？不妨设位置为k。

    结论：模式中的前k-1 个字符与模式中tⱼ字符前面的k-1 个字符相等时，模式t 就可以向右“滑动”至使tₖ 和sᵢ 对准，继续向右进行比较即可。

    模式中的每一个tⱼ都对应一个k 值，这个k 值仅依赖与模式t 本身字符序列的构成，而与主串s 无关。用next[j]表示tⱼ 对应的k 值。

    模式串的next 函数：

    KMP 算法

    在求得模式的next 函数之后，匹配可如下进行：假设以指针i 和j 分别指示主串和模式中的比较字符，令i 的初值为pos，j 的初值为1。若在匹配过程中si=tj，则i 和j 分别增１，若si≠tj 匹配失败后，则i 不变，j 退到next[j]位置再比较，若相等，则指针各自增１，否则j 再退到下一个next 值的位置，依此类推。
    直至下列两种情况：一种是j 退到某个next 值时字符比较相等，则i 和j 分别增１继续进行匹配; 另一种是j 退到值为零（即模式的第一个字符失配），则此时i 和j 也要分别增１，表明从主串的下一个字符起和模式重新开始匹配。

int StrIndex_KMP(char *s,char *t,int pos)/*从串s 的第pos 个字符开始找首次与串t 相等的子串*/
{ 
    int i=pos,j=1,slen,tlen;
    while (i<=s[0] && j<=t[0] ) /*都没遇到结束符*/
        if (j==0||s[i]==t[j]) 
        { 
            i++; 
            j++; 
        }
        else j=next[j]; /*回溯*/

    if (j>t[0]) return i-t[0]; /*匹配成功，返回存储位置*/
    else return –1;
}

    本章学习重点

    1. 顺序表、有序表、索引顺序表的查找方法及其平均查找长度的计算方法。
    2. 动态查找树的构造方法和查找方法及其和有序表的差别。
    3. 熟练掌握二叉排序树、平衡二叉树的构造和查找方法。
    4. 理解B-、B+树的特点。
    5. 熟练掌握散列表的构造方法，深刻理解散列表与其它结构的表的实质性的差别。
    6. 掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
    7.掌握串的模式算法。

---

亲爱的读者：有时间可以点赞评论一下