10_查找算法

数据结构和算法

10.1 静态查找和动态查找

• 静态查找
  
  • 数据集合稳定，不需要添加、删除元素的查找操作。
• 动态查找
  
  • 数据集合在查找的过程中需要同时添加或删除元素的查找操作。

10.2 查找结构

• 对于静态查找来说，我们不妨可以用线性表结构组织数据，这样可以使用顺序查找算法，如果我们再对关键字进行排序，则可以使用折半查找算法或斐波那契查找算法来提高查找的效率。
• 对于动态查找来说，我们则可以考虑使用二叉排序树的查找技术，另外我们还可以使用散列表结构来解决一些查找问题。

10.3 顺序查找

• 顺序查找由叫线性查找，是最基本的查找技术，它的查找过程是：从第一个（或者最后一个）记录开始，逐个进行记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功。如果查找了所有记录仍然找不到与给定值相等的关键字，则查找不成功。

// 顺序查找。a为要查找的数组，n为要查找的数组的长度，key为要查找的关键字
int Sq_Search(int *a, int n, int key)
{
    int i;
    for( i=1; i <= n; i++ )
    {
        if( a[i] == key )
        {
            return i;
        }
    }
    return 0;
}
// 顺序查找优化方案，a为要查找的数组，n为要查找的数组的长度，key为要查找的关键字
int Sq_Search(int *a, int n, int key)
{
    int i = n;
    a[0] = key;
    while( a[i] != key )
    {
        i--;
    }
    return i;
}

10.4 插值查找

// 插值查找
#include <stdio.h>
int bin_search(int str[], int n, int key)
{
    int low, high, mid;
    low = 0;
    high = n-1;
    while( low <= high )
    {
        mid = low + (key - a[low]/a[high] - a[low]) * (high-low);  // 插值查找的唯一不同点
        if( str[mid] == key )
        {
            return mid;
        }
        if( str[mid] < key )
        {
            low = mid + 1;
        }
        if( str[mid] > key )
        {
            high = mid -1;
        }
    }
    return -1;
}
int main()
{
}

• 时间复杂度：O(log2n)

10.5 斐波那契（黄金比例）查找

10.6 线性索引查找

10.6.1 稠密索引

10.6.2 分块索引

10.6.3 倒排索引

10.7 二叉排序树

• 二叉排序树（Binary Sort Tree）
  
  • 又称为二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树：
    
    • 若它的左子树不为空，则左子树上所有结点的值均小于它的根结构的值；
    • 若它的右子树不为空，则右子树上所有结点的值均大于它的根结构的值；
    • 它的左、右子树也分别为二叉排序树（递归）。

10.7.1 二叉排序树的查找操作

// 二叉树的二叉链表结点结构定义
typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 递归查找二叉排序树 T 中是否存在 key
// 指针 f 指向 T 的双亲，其初始值调用值为 NULL
// 若查找成功，则指针 p 指向该数据元素结点，并返回 TRUE
// 否则指针 p 指向查找路径上访问的最后一个结点，并返回FALSE
Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
    if( !T )  // 查找不成功
    {
        *p = f;
        return FALSE;
    }
    else if( key == T->data )  // 查找成功
    {
        *p = T;
        return TRUE;
    }
    else if( key < T->data )
    {
        return SearchBST( T->lchild, key, T, p );   // 在左子树继续查找
    }
    else
    {
        return SearchBST( T->rchild, key, T, p );   // 在右子树继续查找
    }
}

10.7.1 二叉排序树的插入操作

// 当二叉排序树 T 中不存在关键字等于 key 的数据元素时，
// 插入 key 并返回 TRUE, 否则返回 FALSE
Status InsertBST(BiTree *T, int key)
{
    BiTree p, s;
    if( !SearchBST(*T, key, NULL, &p) )
    {
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = key;
        s->lchild = s->rchild = NULL;
        if( !p )
        {
            *T = s;   // 插入 s 为新的根结点
        }   
        else if( key < p->data )
        {
            p->lchild = s;   // 插入 s 为左孩子
        }
        else
        {
            p->rchild = s;   // 插入 s 为右孩子
        }         
        return TRUE;                                                                                                                                                                                                                                                                                   
    }
    else
    {
        return FALSE;   // 树中已有关键字相同的结点，不再插入
    }
}

10.7.3 二叉排序树的删除操作

Status DeleteBST(BiTree *T, int key)
{
    if( !*T )
    {
        return FALSE;    // 该元素为空，非空为真，找不到这个元素
    }
    else
    {
        if( key == (*T)->data )
        {
            return Delete(T);
        }
        else if( key < (*T)->data )
        {
            return DeleteBST( &(*T)->lchild, key );
        }
        else 
        {
            return DeleteBST( &(*T)->rchild, key );
        }
    }
}
Status Delete(BiTree *p)
{
    BiTree q, s;
    if( (*p)->rchild == NULL )
    {
        q = *p;
        *p = (*p)->lchild;
        free(q);
    }
    else if( (*p)->lchild == NULL )
    {
        q = *p;
        *p = (*p)->rchild;
        free(q);
    }
    else
    {
        q = *p;
        s = (*p)->lchild;
        while( s->rchild )
        {
            q = s;
            s = s->rchild;
        }
        (*p)->data = s->data;
        if( q != *p )   // q 没有右子树
        {
            q->rchild = s->lchild;
        }
        else
        {
            q->lchild = s->lchild;
        }
        free(s);
    }
    return TRUE;
}

10.8 平衡二叉排序树

• 我们将二叉树上的结点上的左子树的深度的值减去右子树的深度的值称为平衡银子BF（Balance Factor)，平衡二叉排序树就是一棵树上所有结点的平衡因子的绝对值小于等于1的树。
  
  • 要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
  • 左子树和右子树的深度之差称为平衡因子。

10.8.1 平衡二叉排序树的实现原理

#define LH 1
#define EH 0
#define RH -1
typedef struct BiTNode 
{
    int data;
    int bf;   // balance factor
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void R_Rotate(BiTree *p)
{
    BiTree L;
    L = (*p)->lchild;
    (*p)->lchild = L->rchild;
    L->rchild = (*p);
    *p = L;
}
void LeftBalance(BiTree *T)
{
    BiTree L, Lr;
    L = (*T)->lchild;
    switch( L->bf )
    {
        case LH:
            (*T)->bf = L->bf = EH;
            R_Rotate(T);
            break;
        case RH:
            Lr = L->rchild;
            switch( Lr->bf )
            {
                case LH:
                    (*T)->bf = RH;
                    L->bf = EH;
                    break;
                case EH:
                    (*T)->bf = L->bf = EH;
                    break;
                case RH:
                    (*T)->bf = EH;
                    L->bf = LH;
                    break;
            }
            Lr->bf = EH;
            L_Rotate( &(*T)->lchild );
            R_Rotate(T);
    }
}
int InsertAVL(BiTree *T, int e, int *taller)
{
    if( !*T )
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = e;
        (*T)->lchild = (*T)->rchild = NULL;
        (*T)->bf = EH;
        *taller = TRUE;
    }
    else
    {
        if( e == (*T)->data )
        {
            *taller = FALSE;
            return FALSE;
        }
        if( e < (*T)->data )
        {
            if( !InsertAVL(&(*T)->lchild, e, taller) )
            {
                return FALSE;
            }
            if( *taller )
            {
                switch( (*T)->bf )
                {
                    case LH:
                        LeftBalance(T);
                        *taller = FALSE;
                        break;
                    case EH:
                        (*T)->bf = LH;
                        *taller = TRUE;
                        break;
                    case RH:
                        (*T)->bf = EH;
                        *taller = FALSE;
                        break;
                }
            }
        }
        else
        {
            if( !InsertAVL(&(*T)->rchild, e, taller) )
            {
                return FALSE;
            }
            if( *taller )
            {
                switch( (*T)->bf )
                {
                    case LH:
                        (*T)->bf = EH;
                        *taller = FALSE;
                        break;
                    case EH:
                        (*T)->bf = RH;
                        *taller = TRUE;
                        break;
                    case RH:
                        RightBalance(T);
                        *taller = FALSE;
                        break;
                }               
            }
        }
    }
}

10.9 多路查找树（Multi-way search tree)

10.9.1 2-3树定义

• 多路查找树中的每一个结点都具有两个孩子或者三个孩子，我们称之为2-3树。
• 一个结点拥有两个孩子和一个元素我们称之为2结点，它跟二叉排序树类似，左子树包含的元素小于结点的元素，右子树包含的元素大于结点的元素。不过与二叉排序树不同的是，这个2结点要么没有孩子，要有就应该有两个孩子，不能只有一个孩子。
• 2-3树所有叶子都在同一层次。

10.9.2 2-3树的插入原理

10.9.3 2-3树的删除原理

10.9.4 2-3-4树

10.9.5 B树

• B树是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例。
• 我们把结点最大的孩子树数目称为B树的阶（order），因此，2-3树是3阶B树，2-3-4树是4阶B树。
• 一个m阶的B树具有如下属性：
  
  • 如果根结点不是叶结点，则其至少有两棵子树
  • 每一个非根的分支结点都有k-1个元素（关键字）和k个孩子，其中k满足：[m/2] <= k <= m
  • 所有叶子结点都位于同一层次
  • 每一个分支结点包含下列信息数据：
    
    • n, A0, K1, A1, K2, A2, K3, A3......
    • 其中k为关键字，且Ki < ki+1
    • Ai为指向子树根结点的指针

10.10 散列表（哈希表）查找

• 我们要在a[]中查找key关键字的记录：

  • 顺序表查找：挨个查找
  • 有序表查找：二分法查找
  • 散列表查找：？

• 散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使得每个关键字 key 对应一个存储位置 f(key)。

• 我们把这种对应关系 f 称为散列函数，又称为哈希(hash)函数。采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash Table)。

10.10.1 散列表的查找步骤

• 当存储记录时，通过散列函数计算出记录的散列地址
• 当查找记录时，我们通过同样的是散列函数计算记录的散列地址，并按此散列地址访问该记录。
• 我们可以取关键字的某个线性函数值为散列地址，即：f(key) = a * key + b

10.11 散列函数的构造方法

10.11.1 数字分析法

• 数字分析法通常适合处理关键字位数比较大的情况，例如我们现在要存储某家公司员工登记表，如果用手机号作为关键字，那么我们发现抽取后四位数字作为散列地址是不错的选择。

10.11.2 平方取中法

• 平方取中法是将关键字平方之后取中间若干位数字作为散列地址。
• eg: 1234^2 = 15|227|56

10.11.3 折叠法

• 折叠法是将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，并按散列表表长取后几位作为散列地址。

10.11.4 除留余数法

• 此方法为最常用的构造散列函数方法，计算公式为：
• f(key) = key mod p(p<=m)
• 事实上，这个方法不仅可以对关键字直接取模，也可通过折叠，平方取中后再取模。
• 例如下表，我们对有12个记录的关键字构造散列表时，就可以用 f(key) = key mod 12 的方法。

10.11.5 随机数法

• 选择一个随机数，取关键字的随机函数值为它的散列地址。
• 即: f(key) = random(key)。
• 这里的random是随机函数，当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

10.11.6 视不同的情况采用不同的散列函数

• 现实中，我们应该视不同的情况采用不同的散列函数
• 参考方向：
  
  • 计算散列地址所需的时间
  • 关键字的长度
  • 散列表的大小
  • 关键字的分布情况
  • 记录查找的频率

10.12 处理散列冲突的方法

10.12.1 开放定址法

• 所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大， 空的散列地址总能找到，并将记录存入。
• 它的公式是：fi(key) = (f(key)+di) MOD m (di=1,2,...,m-1)
• 例：假设关键字集合为{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}，使用除留余数法（m=12)求散列表。

• 可以修改 di 的取值方式，例如使用平方运算来尽量解决堆积问题：
• fi(key) = (f(key)+di0 MOD m(di=1^2,-1^2,2^2,-2^2,...,q^,-q^2,q<=m/2)
• 还有一种方法是，在冲突时，对于位移量 di 采用随机函数计算得到，我们称之为随机探测法：
• fi(key) = (f(key)+di) MOD m (di 是由一个随机函数获得的数列）

10.12.2 再散列函数法

• fi(key) = RHi(key)(i=1,2,3,...,k)

10.12.3 链地址法

10.12.4 公共溢出区法

10.13 散列表查找的代码实现

#define HASHSIZE 12
#define NULLKEY -32768
typedef struct 
{
    int *elem;  // 数据元素的基址，动态分配数组
    int count;  // 当前数据元素的个数
} HashTable;
void InitHashTable(HashTable *H)
{
    H->count = HASHSIZE;
    H->elem = (int *)malloc(HASHSIZE * sizeof(int));
    if( !H->elem )
    {
        return -1;
    }
    for( i=0; i < HASHSIZE; i++ )
    {
        H->elem[i] = NULLKEY;
    }
    return 0;
}
// 使用除留余数法
int Hash(int key)
{
    return key % HASHSIZE;
}
// 插入关键字到散列表
void InsertHash(HashTable *H, int key)
{
    int addr;
    addr = Hash(key);
    while( H->elem[addr] != NULLKEY )  //如果不为空，则冲突出现
    {
        addr = (addr + 1) % HASHSIZE;
    }
    H->elem[addr] = key;
}
// 散列表查找关键字
int SearchHash(HashTable H, int key, int *addr)
{
    *addr = Hash(key);
    while( H.elem[*addr] != key )
    {
        *addr = (*addr + 1) % HASHSIZE;
        if( H.elem[*addr] == NULLKEY || *addr == Hash(key) )
        {
            return -1;
        }
    }
    return 0;
}