查找

1.基本概念

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

查找表（查找结构）：用于查找的数据集合合称为查找表，它是由同一类型的数据元素（或记录）组成

关键字：数据元素汇总唯一识别该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的

查找长度：在查找运算中，需要对比关键字的次数称为查找长度

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

2.顺序查找

算法思想

顺序查找有称为“线性查找”，通常用于线性表中，算法的中心思想就是从到到位挨个进行查找

实现代码

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);
    //查找成功，则返回元素下标，查找失败则返回-1
    return i==ST.TableLen?-1:i;
        
}

//方法二：从后往前
int Search_Seq(SSTable ST,ElemType key)
{
    ST.elem[0]=key;
    int i;
    for(i=0ST.TableLen;ST.elem[i]！=key; --i);
    //查找成功，则返回元素下标，查找失败则返回-1
    return i;
        
}

查找效率

有序的排列有利于提高查找的效率

3.折半查找

实现思想

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

实现代码

typedef struct   //查找表的数据结构
{
    ElemType *elem;    //动态数组基址
    int TableLen;     //表的长度
}SSTable;


int Binary_Search(SSTable ST,ElemType key)
{
    int low=1,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 分隔后，左半部分⽐右半部分少⼀个元素，并且折半查找的判定树一定是平衡二叉树，只有最下面一层是不满的

4.分块查找

实现思想

分块查找有称索引顺序查找，实现通过索引表中确定待查记录所属的分块（可顺序、可折半），然后在快内顺序查找

“索引表”中保存每个分块的最⼤关键字和分块的存储区间

实现代码

//索引表
typedef struct
{
    ElemType maxValue;
    int low,high;
}Index;

//顺序表存储实际元素
ElemType List[100];

查找效率

注：常考的效率为顺序查找索引表

5.B树

一般来说比较注重的是B树的性质、插入、删除、查找等相关内容

举例——五叉排序树

struct Node   
{
    ElwmType key[4];       //最多四个关键字
   struct Node *child[5];   //最多五个孩子
    int num;    // 结点中有几个关键字
}

B树的定义

B树，⼜称多路平衡查找树，B树中所有结点的孩⼦个数的最⼤值称为B树的阶，通常⽤m表示。⼀棵m阶B树或为空树，或为满⾜如下特性的m叉树：

1）树中每个结点⾄多有m棵⼦树，即⾄多含有m-1个关键字

2）若根结点不是终端结点，则⾄少有两棵⼦树

3）除根结点外的所有⾮叶结点⾄少有⌈m/2⌉棵⼦树，即⾄少含有 ⌈m/2⌉-1个关键字

4）所有的叶结点都出现在同⼀层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）

5)所有⾮叶结点的结构如下：

n	p 0	k1	p1	k2	p2	…	kn	pn

其中，Ki（i = 1, 2,…, n）为结点的关键字，且满⾜K1 < K2 <…< Kn；Pi（i = 0, 1,…, n）为指向⼦树根结点的指针，且指针Pi-1所指⼦树中所有结点的关键字均⼩于Ki，Pi所指⼦树中所有结点的关键字均⼤于Ki，n（⌈m/2⌉- 1≤n≤m - 1）为结点中关键字的个数。